Discussion on: AoC Day 12: Subterranean Sustainability

View post

Here is currently my Python code for today. Took me some time because I did not understand that we had to sum the indeces of the pots(!).

For part 2 I am looking for loops in the evolution, so that if we reach a plant state (regardless of the indeces) that we have reached before, we loop over those same circular steps without recalculation until reaching to the end.

I could clean up a little, especially the code that cleans up the borders. Maybe if I find time I will do it, but I first hope to later make a Golang solution based on my Python code.

import re

with open('input') as f:
    data = f.readlines()

# Read plants and add padding of statically empty pots left and right
# Since the rules only take two pots to left and right into account,
# we are guaranteed that adding four pots left and right is sufficient.
plants_initial = "...." + data[0][15:-1] + "...."

# Read and save rules
rules = {}
for i in range(2, len(data)):
    rule_match = re.match(r'([#|\.]+) => ([#|\.])', data[i])
    rule, res = rule_match.group(1), rule_match.group(2)
    rules[rule] = res


# Evolve generations
def evolve(generations):
    plants = list(plants_initial)  # Clean start with initial plants
    seen = {}   # Keep track of loops when evolving
    shift = -4  # Added padding must be accounted for by shifting
    e = 0       # Initial evolve step
    while e < generations:
        e += 1  # Evolve step
        plants_copy = plants.copy()
        for idx, plant in enumerate(plants):
            # Ignore outer borders which extend infinitely with empty pots (".")
            if idx < 2 or idx > len(plants) - 3:
                continue
            # For real inputs all rules are defined. But for example we would
            # have to use (".") if rule was not defined for this pot.
            plants_copy[idx] = rules.get(''.join(plants[idx-2:idx+3]), ".")
        if plants_copy[3] == '#':
            # If we planted close to the left border, we must extend it:
            plants_copy.insert(0, '.')
            shift -= 1  # Adjusts the pot index shifting
        elif plants_copy[:5] == ['.'] * 5:
            # If we have deserted the whole left border, we can remove one pot:
            plants_copy.remove('.')
            shift += 1  # Adjusts the pot index shifting
        if plants_copy[-3] == '#':
            # If we planted close to the right border, we must extend it:
            plants_copy.append('.')
        elif plants_copy[-4:] == ['.'] * 5:
            # If we have deserted the whole right border, we can remove one pot:
            plants_copy = plants_copy[:-1]
        plants = plants_copy
        if seen.get(''.join(plants), False):
            # We have made a full circle! No need to recalculate next steps.
            # We can just warp into the future...
            circle_length = e - seen[''.join(plants)][0]  # The steps of this circle
            circles = (generations - e) // circle_length  # The circles to make
            e += circles * circle_length                  # Warping into future...
            shift_length = shift - seen[''.join(plants)][1]  # The shifts this circle performs
            shift += circles * shift_length                  # Adjusting shifts
        seen[''.join(plants)] = (e, shift)  # Add unseen pattern to dictionary
    return plants, shift


# Part 1:
plants, shift = evolve(generations=20)
print('Part 1:')
print(sum(i + shift for i, p in enumerate(plants) if p == '#'))

# Part 2:
plants, shift = evolve(generations=50000000000)
print('Part 2:')
print(sum(i + shift for i, p in enumerate(plants) if p == '#'))

Bjarne Magnussen • Dec 13 '18

Here is the Golang code. I don't think this is the best way of doing it in Golang, but it does the job!

package main

import (
    "bufio"
    "fmt"
    "os"
    "reflect"
    "regexp"
)

type entry struct {
    e     int
    shift int
}

// readLines reads a whole file into memory
// and returns a slice of its lines.
func readLines(path string) ([]string, error) {
    file, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer file.Close()

    var lines []string
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        lines = append(lines, scanner.Text())
    }
    return lines, scanner.Err()
}

// function to evolve generations.
func evolve(generations int) ([]rune, int) {
    seen := make(map[string]entry)
    shift := -4
    plantsCopy := make([]rune, len(plants))
    plantsOld := make([]rune, len(plants))
    copy(plantsOld, plants)
    for e := 1; e <= generations; e++ {
        plantsCopy = make([]rune, len(plantsOld))
        copy(plantsCopy, plantsOld)
        for idx := range plantsOld {
            if idx < 2 || idx > len(plantsOld)-3 {
                continue
            }
            plantsCopy[idx] = rules[string(plantsOld[idx-2:idx+3])]
        }
        if plantsCopy[3] == '#' {
            plantsCopy = append(plantsCopy, 0)
            copy(plantsCopy[1:], plantsCopy[0:])
            plantsCopy[0] = '.'
            shift--
        } else if reflect.DeepEqual(plantsCopy[:5], []rune{'.', '.', '.', '.', '.'}) {
            plantsCopy = plantsCopy[1:]
            shift++
        }
        if plantsCopy[len(plantsCopy)-3] == '#' {
            plantsCopy = append(plantsCopy, '.')
        } else if reflect.DeepEqual(plantsCopy[len(plantsCopy)-5:], []rune{'.', '.', '.', '.', '.'}) {
            plantsCopy = plantsCopy[:len(plantsCopy)-1]
        }
        if val, ok := seen[string(plantsCopy)]; ok {
            circleLength := e - val.e
            circles := (generations - e) / circleLength
            e = e + circles*circleLength
            shiftLength := shift - val.shift
            shift = shift + circles*shiftLength
        }
        seen[string(plantsCopy)] = entry{e: e, shift: shift}
        plantsOld = make([]rune, len(plantsCopy))
        copy(plantsOld, plantsCopy)
    }
    return plantsCopy, shift
}

var plants []rune
var rules map[string]rune

func main() {
    data, err := readLines("input")
    if err != nil {
        panic(err)
    }
    plantsInitial := "...." + data[0][15:] + "...."
    plants = []rune(plantsInitial)

    rules = make(map[string]rune)
    r, _ := regexp.Compile("([#|\\.]+) => ([#|\\.])")
    for _, d := range data[2:] {
        rule := r.FindStringSubmatch(d)[1]
        res := r.FindStringSubmatch(d)[2]
        rules[rule] = []rune(res)[0]
    }

    // Part 1:
    plants, shift := evolve(20)
    fmt.Println("Part 1:")
    var sum int
    sum = 0
    for i, p := range plants {
        if p == '#' {
            sum += i + shift
        }
    }
    fmt.Println(sum)

    // Part 2:
    plants, shift = evolve(50000000000)
    fmt.Println("Part 2:")
    sum = 0
    for i, p := range plants {
        if p == '#' {
            sum += i + shift
        }
    }
    fmt.Println(sum)
}