DEV Community

Cover image for AoC Day 12: Subterranean Sustainability

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...
Collapse
 
jbristow profile image
Jon Bristow • 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:

ttyrec gif single

Multi line:

ttyrec gif multi

Actual GIF output from AWT:

awt gif

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

Collapse
 
bjarnemagnussen profile image
Bjarne Magnussen • 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)

Collapse
 
rpalo profile image
Ryan Palo

GET. OUT. This is amazing. Thank you.

Collapse
 
rpalo profile image
Ryan Palo

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 :/

Collapse
 
r0f1 profile image
Florian Rohrer

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 == '#'))
Collapse
 
jenovs profile image
Viktors Jenovs

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);
?>
Collapse
 
choroba profile image
E. Choroba

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
Collapse
 
neilgall profile image
Neil Gall • 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:

  1. Pad the state with 'false' at the start and the end to aid region matches.
  2. Split the state into sets of five positions, called regions.
  3. Look up each region in the rules to get the value at that position for the next state
  4. Trim empty space off the ends and calculate the new origin
  5. 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.

Collapse
 
aspittel profile image
Ali Spittel

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))
Collapse
 
jmgimeno profile image
Juan Manuel Gimeno

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))
Collapse
 
bjarnemagnussen profile image
Bjarne Magnussen • 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 == '#'))
Collapse
 
bjarnemagnussen profile image
Bjarne Magnussen

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)
}
Collapse
 
themindfuldev profile image
Tiago Romero Garcia

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}`);
})();
Collapse
 
rpalo profile image
Ryan Palo

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)