DEV Community

AoC Day 12: Subterranean Sustainability

Ryan Palo on December 12, 2018

Whoops! Looks like I may have spoken too soon yesterday when I mentioned Conway's Game of Life. On Day 12, we're actually implementing a variatio...

Read full post

Jon Bristow • Dec 12 '18 • Edited

Kotlin Solution

This one was similar to a previous year's problem, but it's thankfully in 2d.

Part 1

"Just" make a map of the rules, chunk the input into 5 char seedlings and map them to the rules.

Oh wait... it can grow left and right... better add some padding.

private fun answer1(initial: String, rules: Map<String, String>): Int { val final = step(0, 20, initial, rules) return calculatePlants(final) } private fun calculatePlants(final: String) = final.mapIndexed { a, b -> a to b } .filter { (a, b) -> b == '#' }.sumBy { (first) -> first + -3 } private tailrec fun step( n: Int, max: Int, current: String, rules: Map<String, String> ): String = if (n >= max) { current } else { step( n + 1, max, "..$current..." .windowed(5, 1) .joinToString("") { rules[it] ?: "." }, rules ) }

Part 2

This one seemed like it might be hard, but then I realized that part1 was fast enough that I could just do the first couple hundred and watch for loops.

I didn't get a loop, but I did see a consistency! I made a quick function to seek for that and voila! (That's French, for 'voila!')

private fun answer2(initial: String, rules: Map<String, String>) = generateSequence(0L) { it + 1 } .mapIndexed { i, it -> calculatePlants( step(0, it.toInt(), initial, rules) ).let { plants -> plants + (50000000000L - it) * 86 } } .windowed(2, 1) .dropWhile { it[0] != it[1] } .first() .first()

Bonus Content

Single line:

Multi line:

Actual GIF output from AWT:

EDIT: FORGOT PLANT PUNS:
Um... hopefully this one isn't leaving you out in the weeds?

Er... put the petal to the metal?

Uh... Orange you glad I didn't say banana? (Does fruit count?)

Bjarne Magnussen • Dec 12 '18 • Edited

Haha, love your visualisations! Always fascinating how such simple things can create such complexity.

(Slightly off-topic, but I once came across these "meta-pixel" in Conway's Game of Life which literally gave me goose bumps: youtube.com/watch?v=xP5-iIeKXE8)

Ryan Palo • Dec 15 '18

GET. OUT. This is amazing. Thank you.

Ryan Palo • Dec 15 '18

Full marks + animations + bonus plant puns! Checking for loops was a good idea. I didn't think of that until I cheated and looked at the discussion here :/

Florian Rohrer • Dec 12 '18

Python.

Part 1

from more_itertools import windowed from more_itertools import with_iter from itertools import takewhile initial = "##...#......##......#.####.##.#..#..####.#.######.##..#.####...##....#.#.####.####.#..#.######.##..." rules = dict(tuple(l.strip().split(" => ")) for l in with_iter(open("input.txt"))) def dot_count(s): return sum(1 for _ in takewhile(lambda c: c == '.', s)) current = "....." + initial + "....." first = -5 for i in range(20): new_pop = "".join(rules.get("".join(w), ".") for w in windowed(current, 5)) c = dot_count(new_pop) first = first + c - 3 current = "....." + new_pop.rstrip(".").lstrip(".") + "....." print(sum(i for c, i in zip(current, range(first, len(current)+first)) if c == '#'))

Part 2

encountered = dict() current = "....." + initial + "....." first = -5 for i in range(100): # cycle detected at i=97  new_pop = "".join(rules.get("".join(w), ".") for w in windowed(current, 5)) c = dot_count(new_pop) first = first + c - 3 current = "....." + new_pop.rstrip(".").lstrip(".") + "....." if current in encountered: continue else: encountered[current] = i first += (50000000000-100) * (c-3) print(sum(i for c, i in zip(current, range(first, len(current)+first)) if c == '#'))

Viktors Jenovs • Dec 12 '18

Part 1 would be easy for anyone who has ever coded Game of Life (I somehow managed to leave out last line on the input so I spent unreasonable amount of time debugging).

For part 2 after seeing that even 10k generations take a lot I started to look for a pattern and came up with a formula to calculate value for any generation bigger than ~160 (that's when it starts to loop).

<?php $input = require_once 'readFile.php'; [, $init] = explode(": ", $input[0]); $comb = []; for ($i=2; $i < count($input); $i++) { [$pat, $res] = explode(" => ", $input[$i]); $comb[$pat] = $res[0]; } $pots = str_split($init); array_pop($pots); $gen = 1; while($gen <= 20) { $temp = []; $minVal = min(array_values(array_keys($pots))); $maxVal = max(array_values(array_keys($pots))); if ($pots[$minVal] != '.' || $pots[$minVal + 1] != '.') { $pots[$minVal - 1] = '.'; $pots[$minVal - 2] = '.'; } if ($pots[$maxVal] != '.' || $pots[$maxVal - 1] != '.') { $pots[$maxVal + 1] = '.'; $pots[$maxVal + 2] = '.'; } foreach ($pots as $key => $c) { $l1 = empty($pots[$key - 1]) ? '.' : $pots[$key - 1]; $l2 = empty($pots[$key - 2]) ? '.' : $pots[$key - 2]; $r1 = empty($pots[$key + 1]) ? '.' : $pots[$key + 1]; $r2 = empty($pots[$key + 2]) ? '.' : $pots[$key + 2]; $searchKey = $l2 . $l1 . $c . $r1 . $r2; $next = empty($comb[$searchKey]) ? '.' : $comb[$searchKey]; $temp[$key] = $next; } $pots = $temp; $gen++; } $sum = 0; foreach ($pots as $key => $value) { if ($value == '#') { $sum += $key; } } $afterBillions = 23 * (50000000000 - 72) + 2014; echo "Part 1: " . $sum . "\n"; echo "Part 2: " . $afterBillions . "\n"; ?>

php
readFile.php

<?php $file = fopen("input.txt", "r") or exit("Unable to open file"); // $file = fopen("input_test.txt", "r") or exit("Unable to open file"); while(!feof($file)) { $array[] = fgets($file); } fclose($file); return array_filter($array); ?>

E. Choroba • Dec 12 '18

Part 1 was easy. I used regular expressions to match the rules against the pots, and I needed to keep a record at what position the current pattern starts.

#!/usr/bin/perl use warnings; use strict; use feature qw{ say }; my $state = <>; $state =~ s/[^#.]//g; <>; my %rule; while (<>) { chomp; my ($left, $right) = split /\s*=>\s*/; $rule{$left} = $right; } my $start_at = 0; for (1 .. 20) { substr $state, 0, 0, '...'; --$start_at; $state .= '...'; my $new; while ($state =~ /(?=(.....))/g) { my $before = $1; if (exists $rule{$before} && '#' eq $rule{$before}) { $new .= '#'; } else { $new .= '.'; } } $state = $new; $state =~ s/\.+$//; $state =~ s/^(\.*)//; $start_at += length $1; } my $count = 0; $count += $start_at - 1 + pos $state while $state =~ /#/g; say $count;

Running it for many more than 20 steps I discovered the pattern stays the same, only moving to the right. So I printed its value for two different numbers, the rest was just two equations:

20000a + b = 2041377 20002a + b = 2041581 b = 2041377 - 20000a 20002a + 2041377 - 20000a = 2041581 2a + 2041377 = 2041581 2a = 204 a = 102 b = 2041377 - 20000 * 102 b = 1377

Neil Gall • Dec 12 '18 • Edited

Ahhh, a one-dimensional Conway's Game of Life.

Part 1 is easy enough - the tricky part is that the space is unbounded. I modelled the row of plants as a boolean array where the first and last are always true (i.e. the left and rightmost plants) and the position of the leftmost plant is stored separately. Thus if the row grows to the right the array gets longer and the origin stays the same, and if it grows to the left the array also gets longer but the origin decreases.

data class State(val plants: BooleanArray, val origin: Long)

At first I translated the rules into a map of BooleanArray to Boolean but the lookups seemed to have trouble so I converted the five bits of a rule's left hand side to an integer and used that as the key:

data class Region(val value: Int) { constructor(states: List<Boolean>): this(states.fold(0) { v, b -> (v shl 1) or (if (b) 1 else 0) }) override fun toString(): String = listOf(16,8,4,2,1).map { b -> if (value and b != 0) '#' else '.'}.joinToString("") }

The use of && and || for logic and and and or for boolean operations in Kotlin seems the wrong way round. Yes you want to bring C / Java programmers with you when you introduce a new language, but in this case I'd have gone for Python's readability.

Parsing

Parsing the input data of course uses JParsec. It's just so much easier not to have to deal with questions like "did I find all the parts?" or "does the rule have exactly 5 positions on the left" etc. It either parses or it throws an error and tells you the line and column where the parsing failed.

fun parse(input: String): Game { val plant = or(isChar('.').retn(false), isChar('#').retn(true)) val initial = string("initial state: ") .next(plant.many()) .map { ps -> State(ps, 0) } val rule = sequence( plant.times(5).map(::Region), string(" => ").next(plant), { r, q -> r to q } ) val parser: Parser<Game> = sequence( initial.followedBy(WHITESPACES), rule.sepBy(WHITESPACES).map { rs -> rs.toMap() }, ::Game ) return parser.parse(input) }

Part 1

Running one generation of the game involves:

Pad the state with 'false' at the start and the end to aid region matches.
Split the state into sets of five positions, called regions.
Look up each region in the rules to get the value at that position for the next state
Trim empty space off the ends and calculate the new origin
Also, do all this in a Sequence so the memory footprint is sequential rather than all at once.

val buffer: BooleanArray = BooleanArray(4) { false } fun State.run(rules: Rules): State { val buffered: BooleanArray = buffer + plants + buffer val regions: Sequence<Region> = (0..(buffered.size-5)) .asSequence() .map { i -> Region(buffered.slice(i..i+4)) } val output = regions .map { r -> rules.getOrDefault(r, false) } .toList() .dropLastWhile { !it } val leadingEmpties = output.takeWhile { !it }.count() return State(output.dropWhile { !it }, origin - 2 + leadingEmpties) }

Part 1 is just doing that 20 times.

Part 2

At first you read part 2 and think "oh, just up the iteration count to 50 billion".

No.

The secret is that the rules inevitably lead to a repeating pattern. Work out where the loop is, work out how many loops occur in 50 billion iterations, then you only need to run the loop once. The tricky part in this puzzle is that the same pattern of plants may occur with a different origin. Conway's original Game of Life is famous for its walker structures that move across the 2D space, replicating themselves perfectly.

I built a map keyed by a string representation of the plant pattern. When the current state already exists in the map, we have detected a loop. The value stored in the map describes the start of the loop. Then it's just a matter of determining the number of loops, the length of the last incomplete loop (if present), assemble the state at the end of the final loop and finish the sequence. All while avoiding 50 billion opportunities for an off-by-one error.

val total: Long = 50_000_000_000 val loopStart = states[state.str]!! val loopSize = count - loopStart.index val loops = (total - loopStart.index) / loopSize val originInc = state.origin - loopStart.origin val lastLoopStartState = State(state.plants, loopStart.origin + loops * originInc) val lastState = if (loopSize == 1) lastLoopStartState else { val lastLoopLength = total % loopSize lastLoopStartState.run(lastLoopLength, game.rules) }

In my case the loop was only one iteration long, but I suspect that's not true for everyone. My lastState calculation's else branch is therefore never taken so I don't have full confidence that's the correct logic.

I should also point out I took eight attempts to submit the right answer, constantly tweaking my code before realising I was doing 5 billion iterations, not 50 billion. I should have used the underscore syntax for the big number earlier.

Tiago Romero • Dec 13 '18

JavaScript solution

I'm gonna omit reader.js which is the same as the other solutions, but you can find it at github.com/themindfuldev/advent-of...

12-common.js

const parseInput = lines => { const initialStateRegex = /^initial state: (?<initialState>.+)$/; const noteRegex = /^(?<pattern>.+) => (?<pot>.)$/; const { initialState } = lines[0].match(initialStateRegex).groups; const notes = new Map(); for (let note of lines.slice(2)) { const { pattern, pot } = note.match(noteRegex).groups; notes.set(pattern, pot); } return { initialState, notes }; }; const processGeneration = (state, notes) => { let { start, pots } = state; const n = pots.length; let next = ''; let prefixExtensions = 0; let suffixExtensions = 0; for (let i = 0; i < n - 2; i++) { const segment = pots.substring(i, i + 5); if (notes.has(segment)) { const pot = notes.get(segment); next += pot; if (pot === '#') { if (i < 2 && prefixExtensions === 0) { prefixExtensions += 2 - i; } if ((i > n - 6) && suffixExtensions === 0) { suffixExtensions += i - (n - 6); } } } else { next += '.'; } } const prefix = '.'.repeat(2 + prefixExtensions); const suffix = '.'.repeat(suffixExtensions); return { start: start - prefixExtensions, pots: prefix + next + suffix } }; const processGenerations = (initialState, notes, generations = 1, log = true) => { let state = { start: -4, pots: `....${initialState}....` }; if (log) { console.log(state.pots); } for (let i = 0; i < generations; i++) { state = processGeneration(state, notes); if (log) { console.log(state.pots); } } return state; } const sumPots = ({ start, pots }) => { const n = pots.length; return pots.split('').reduce((sum, pot, i) => sum + (pot === '#' ? i + start : 0), 0); }; module.exports = { parseInput, processGeneration, processGenerations, sumPots };

12a.js

const { readFile } = require('./reader'); const { parseInput, processGenerations, sumPots } = require('./12-common'); (async () => { const lines = await readFile('12-input.txt'); const { initialState, notes } = parseInput(lines); const lastGeneration = processGenerations(initialState, notes, 20, false); const potsSum = sumPots(lastGeneration); console.log(`The sum of the numbers of all pots is ${potsSum}`); })();

12b.js

const { readFile } = require('./reader'); const { parseInput, processGeneration, processGenerations, sumPots } = require('./12-common'); (async () => { const lines = await readFile('12-input.txt'); const { initialState, notes } = parseInput(lines); const initialBatch = processGenerations(initialState, notes, 160, false); const initialSum = sumPots(initialBatch); console.log(`The sum for the first 160 batch is ${initialSum}`); const diffBatch = processGeneration(initialBatch, notes); const diffSum = sumPots(diffBatch) - initialSum; console.log(`The sum for the just 1 generation is ${diffSum}`); const totalSum = initialSum + diffSum * (50000000000 - 160); console.log(`The total sum is ${totalSum}`); })();

Juan Manuel Gimeno • Dec 12 '18

A python solution.

from collections import namedtuple from itertools import takewhile State = namedtuple("State", ["first", "plants", "generation"]) def normalize(state): first_plant = 0 for c in state.plants: if c == "#": break first_plant += 1 last_plant = len(state.plants) for c in reversed(state.plants): if c == "#": break last_plant -= 1 plants = "..." + state.plants[first_plant:last_plant] + "..." first = state.first + first_plant - 3 return State(first, plants, state.generation) def test_normalize(): expected_state = State(-3, "...#...#....#.....#..#..#..#...", 0) state = State(0, "#...#....#.....#..#..#..#", 0) assert expected_state == normalize(state) def step(state, rules): next_plants = ".." for idx in range(len(state.plants) - 4): current = state.plants[idx:idx+5] next_plants += rules.get(current, ".") return normalize(State(state.first, next_plants, state.generation+1)) def test_step(): expected_state = State(-3, "...#...#....#.....#..#..#..#...", 1) with open("test_input.txt", "r") as file: initial_state, rules = process(file) actual_state = step(initial_state, rules) assert expected_state == actual_state def simulate(state, rules, num_generations): seen_states = { state.plants : (state, 0) } while state.generation < num_generations: new_state = step(state, rules) if new_state.plants in seen_states: period = new_state.generation - seen_states[state.plants].generation delta = new_state.first - seen_states[state.plants].first remaining = num_generations - new_state.generation repetitions = remaining // period state = State( new_state.first + delta * repetitions, new_state.plants, new_state.generation + repetitions * period) seen_states = {} else: state = seen_states[state.plants] = new_state return state def sum_plant_positions(state): result = 0 pos = state.first for plant in state.plants: if plant == "#": result += pos pos += 1 return result def process(file): line = file.readline() initial_state = normalize(State(0, line[len("initial state: "):].strip(), 0)) file.readline() rules = dict(parse_rule(line.strip()) for line in file) return initial_state, rules def parse_rule(line): return line[:5], line[-1:] def test_process(): expected_state = State(-3, "...#..#.#..##......###...###...", 0) expected_rules = { "...##" : "#", "..#.." : "#", ".#..." : "#", ".#.#." : "#", ".#.##" : "#", ".##.." : "#", ".####" : "#", "#.#.#" : "#", "#.###" : "#", "##.#." : "#", "##.##" : "#", "###.." : "#", "###.#" : "#", "####." : "#" } with open("test_input.txt", "r") as file: actual_state, actual_rules = process(file) assert expected_state == actual_state assert expected_rules == actual_rules def part1(fname, num_generations): with open(fname, "r") as file: initial_state, rules = process(file) end_state = simulate(initial_state, rules, num_generations) return sum_plant_positions(end_state) def test_part1(): assert 325 == part1("test_input.txt", 20) if __name__ == "__main__": print("Part1: ", part1("input.txt", 20)) print("Part2: ", part1("input.txt", 50000000000))

Bjarne Magnussen • Dec 12 '18 • Edited

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) }

Ali Spittel • Dec 13 '18

Part B, so sneaky! Part A is uncommented, Part B commented.

with open('sample-input.txt', 'r') as f: rules = {} for idx, line in enumerate(f): if idx == 0: state = line.strip() elif idx > 1: rule = line.strip().split(" => ") rules[rule[0]] = rule[1] def get_score(state, n_change): n_change *= -1 score = 0 for l in state: if l == "#": score += n_change n_change += 1 return score n_change = 0 for _ in range(20): #1000 for large input  n_change += 4 state = "...." + state + "...." new_state = "" for idx, val in enumerate(state): left_chunk = state[idx-2:idx] right_chunk = state[idx+1:idx+3] chunk = left_chunk + val + right_chunk if chunk in rules: new_state += rules[chunk] else: new_state += "." start = 0 while new_state[start] == ".": start += 1 n_change -= start end = len(new_state) - 1 while new_state[end] == ".": end -= 1 state = new_state[start:end+1] # uncomment for pt2 # score = get_score(state, n_change) # print(((50_000_000_000 - 1000) * 42) + score)  print(get_score(state, n_change))

Ryan Palo • Dec 15 '18

I got part 1 done, but couldn't figure out how I could possibly do that big of a number of generations. So, I peeked (a little) here and, without seeing anyone explicitly giving it away -- but reading enough of the responses to get ideas -- I figured out the trick.

"""Day 12: Subterranean Sustainability Conway's game of life with plants! See which plants will live or die each generation. """ from collections import deque from itertools import islice from typing import List, Dict class Plants(deque): """A row of plants centered around zero""" def __init__(self, *args): deque.__init__(self, *args) self.zero = 0 def score(self) -> int: """Sums up all the indices (including negative) that have a plant""" return sum(i - self.zero for i, pot in enumerate(self) if pot == '#') def __getitem__(self, key) -> islice: """Allows slicing a deque""" if isinstance(key, slice): return islice(self, key.start, key.stop, key.step) else: return deque.__getitem__(self, key) def copy(self): result = Plants(self) result.zero = self.zero return result def next_generation(plants: Plants, rules: Dict[str, str]) -> Plants: """Given a row of pots with/without plants and some rules, creates the next generation of plants. The only rules that could increase the length in either direction require 3 dots on the end to check, so this makes sure there are 3 dots on each end just in case. """ this_generation = plants.copy() if any(c == '#' for c in this_generation[:3]): this_generation.extendleft(['.']*3) this_generation.zero += 3 if any(c == '#' for c in this_generation[len(this_generation) - 3:]): this_generation.extend(['.']*3) next_generation = this_generation.copy() for i in range(2, len(this_generation) - 2): next_generation[i] = rules.get("".join(this_generation[i-2:i+3]), '.') return next_generation def parse_rules(text: str) -> Dict[str, str]: """Parses the conversion rules from a block of text""" rules = {} for line in text.splitlines(): pattern, _, output = line.partition(" => ") rules[pattern] = output return rules def age(plants: Plants, generations: int, rules: Dict[str, str]) -> Plants: """Ages a set of plants n generations""" for i in range(generations): plants = next_generation(plants, rules) return plants if __name__ == "__main__": with open("python/data/day12.txt", "r") as f: rules = parse_rules(f.read()) initial_plants = Plants( "##..#..##....#..#..#..##.#.###.######..#..###.#.#..##.###.#.##..###..#.#..#.##.##..###.#.#...#.##..") # Part 1  plants = age(initial_plants, 20, rules) print(plants.score()) # Part 2: Wherein it's #@%!# linear above about 300  plants = age(initial_plants, 300, rules) print(plants.score() + (50000000000 - 300)*86)