AoC Day 18: Settlers of The North Pole

twitter logo github logo ・1 min read

Advent of Code (26 Part Series)

1) AoC Day 1: Chronal Calibration 2) AoC Day 2: Inventory Management System 3 ... 24 3) AoC Day 3: No Matter How You Slice It 4) AoC Day 4: Repose Record 5) AoC Day 5: Alchemical Reduction 6) AoC Day 6: Chronal Coordinates 7) AoC Day 7: The Sum of Its Parts 8) AoC Day 8: Memory Maneuver (Placeholder) 9) AoC Day 9: Marble Mania 10) AoC Day 10: The Stars Align 11) AoC Day 11: Chronal Charge 12) AoC Day 12: Subterranean Sustainability 13) AoC Day 13: Mine Cart Madness 14) AoC Day 14: Chocolate Charts 15) AoC Day 15: Beverage Bandits 16) AoC Day 16: Chronal Classification 17) AoC Day 17: Reservoir Research 18) AoC Day 18: Settlers of The North Pole 19) AoC Day 19: Go With the Flow 20) AoC Day 20: A Regular Map 21) AoC Day 21: Chronal Conversion 22) AoC Day 22: Mode Maze 23) AoC Day 23: Experimental Emergency Teleportation 24) AoC Day 24: Immune System Simulator 20XX 25) AoC Day 25: Four-Dimensional Adventure 26) Advent of Code Wrap-Up

That darn Conway is persistent, isn't he?! That's right, Day 18 is looking like the return of Conway, but in 2 dimensions, and with 3 possible states (Open Ground, Wooded Acre, and Lumberyard) as opposed to the less complicated Alive or Dead we saw a few days ago.

It'll be interesting to see if the repeating semi-stable shapes that we see in a normal 2D Conway's Game of Life are present here or how having 3 possible states affects them.

Good luck! I wood love to see your solutions! 🎄

twitter logo DISCUSS (6)
markdown guide
 

JavaScript solution

I'm gonna omit reader.js which is the same as the other solutions and jump to the point:

18-common.js

const MAP = {
    OPEN_GROUND: '.',
    TREES: '|',
    LUMBERYARD: '#'
};

const tick = originalMap => {
    const n = originalMap.length;
    const nextMap = Array.from({length: n}, row => Array.from({length: n}));

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const originalAcre = originalMap[i][j];
            const adjacents = getAdjacents(originalMap, i, j, n);

            // For an open ground acre
            if (originalAcre === MAP.OPEN_GROUND) {
                const adjacentTrees = adjacents.filter(acre => acre === MAP.TREES).length;
                nextMap[i][j] = adjacentTrees >= 3 ? MAP.TREES : MAP.OPEN_GROUND;
            }
            // For a trees acre
            else if (originalAcre === MAP.TREES) {
                const adjacentLumberyards = adjacents.filter(acre => acre === MAP.LUMBERYARD).length;
                nextMap[i][j] = adjacentLumberyards >= 3 ? MAP.LUMBERYARD : MAP.TREES;
            }
            // For a lumberyard acre
            else if (originalAcre === MAP.LUMBERYARD) {
                const adjacentLumberyards = adjacents.filter(acre => acre === MAP.LUMBERYARD).length;
                const adjacentTrees = adjacents.filter(acre => acre === MAP.TREES).length;
                nextMap[i][j] = adjacentLumberyards >= 1 && adjacentTrees >= 1 ? MAP.LUMBERYARD : MAP.OPEN_GROUND;
            }
        }
    }

    return nextMap;
};

const getAdjacents = (originalMap, i, j, n) => {
    const positions = [[i-1, j-1], [i-1, j], [i-1, j+1], [i, j-1], [i, j+1], [i+1, j-1], [i+1, j], [i+1, j+1]];

    return positions
        .filter(([i, j]) => i >= 0 && j >= 0 && i < n && j < n)
        .map(([i, j]) => originalMap[i][j])
        .filter(acre => acre !== undefined);
};

const serialize = map => map.map(row => row.join('')).join('');

const printSolution = solution => {
    const serializedMap = (Array.isArray(solution) ? serialize(solution) : solution).split('');
    const trees = count(serializedMap, MAP.TREES);
    const lumberyards = count(serializedMap, MAP.LUMBERYARD);
    console.log(`The total resource value of the lumber collection area is ${trees * lumberyards}`);
};

const count = (map, type) => {
    return map.reduce((total, acre) => total + (acre === type ? 1 : 0), 0);
};

module.exports = {
    MAP,
    tick,
    serialize,
    printSolution
};

18a.js

const { readFile } = require('./reader');

const {
    tick,
    printSolution
} = require('./18-common');

(async () => {
    let outskirts = (await readFile('18-input.txt')).map(row => row.split(''));

    for (let i = 0; i < 10; i++) {
        outskirts = tick(outskirts);
    }

    console.log(outskirts.map(row => row.join('')).join('\n'));

    printSolution(outskirts);
})();

18b.js

const { readFile } = require('./reader');

const {
    MAP,
    tick,
    serialize,
    printSolution
} = require('./18-common');

(async () => {
    let outskirts = (await readFile('18-input.txt')).map(row => row.split(''));

    const previousStates = new Map();
    let elapsedMinutes = 0;
    let serialized;
    let hasDetectedLoop = false;
    do {
        elapsedMinutes++;
        outskirts = tick(outskirts);

        serialized = serialize(outskirts);
        if (previousStates.has(serialized)) {
            hasDetectedLoop = true;
        }
        else {
            previousStates.set(serialized, elapsedMinutes);
        }
    } while (!hasDetectedLoop);

    console.log(`Loop detected at minute ${elapsedMinutes}!`);

    const firstRepetitionMinutes = previousStates.get(serialized);
    const loopDurationMinutes = elapsedMinutes - firstRepetitionMinutes;
    const equivalentMinute = ((1000000000 - firstRepetitionMinutes) % loopDurationMinutes) + firstRepetitionMinutes;

    console.log(`The minute 1000000000 is equivalent to the minute ${equivalentMinute}`);

    const solution = [...previousStates.entries()].find(([state, minute]) => minute === equivalentMinute)[0];

    printSolution(solution);
})();
 

For Part 2 I logged out the results and manually counted period length that I used to calculate my solution. I guess I could calculate the period programmatically, but I'm just too lazy :)

<?php
$input = require_once 'readFile.php';

function calcNext($area) {
  $next = [];
  for ($y=0; $y < count($area); $y++) {
    for ($x=0; $x < count($area[0]); $x++) {
      $adjacent = [];
      $tl = $tm = $tr = $cl = $cr = $bl = $bc = $br = false;
      $curr = $area[$y][$x];

      !empty($area[$y-1][$x-1]) && $adjacent[] = $area[$y-1][$x-1];
      !empty($area[$y-1][$x]) && $adjacent[] = $area[$y-1][$x];
      !empty($area[$y-1][$x+1]) && $adjacent[] = $area[$y-1][$x+1];
      !empty($area[$y][$x-1]) && $adjacent[] = $area[$y][$x-1];
      !empty($area[$y][$x+1]) && $adjacent[] = $area[$y][$x+1];
      !empty($area[$y+1][$x-1]) && $adjacent[] = $area[$y+1][$x-1];
      !empty($area[$y+1][$x]) && $adjacent[] = $area[$y+1][$x];
      !empty($area[$y+1][$x+1]) && $adjacent[] = $area[$y+1][$x+1];

      $count = array_reduce($adjacent, function($acc, $var) {
        $acc[$var]++;
        return $acc;
      }, ['.' => 0, '|' => 0, '#' => 0]);

      if ($curr == '.') {
        $next[$y][$x] = $count['|'] >= 3 ? '|' : '.';
      } else if ($curr == '|') {
        $next[$y][$x] = $count['#'] >= 3 ? '#' : '|';
      } else if ($curr == '#') {
        $next[$y][$x] = $count['#'] >= 1 && $count['|'] >= 1 ? '#' : '.';
      }
    }
  }
  return $next;
}

function countWood($area) {
  $wood = $lumber = 0;
  for ($y=0; $y < count($area); $y++) {
    for ($x=0; $x < count($area[0]); $x++) {
      $area[$y][$x] == '|' && $wood++;
      $area[$y][$x] == '#' && $lumber++;
    }
  }
  return $wood * $lumber;
}

function generateTen($area, $time = 10) {
  $next = $area;
  for ($i=0; $i < $time; $i++) {
    $next = calcNext($next);
  }
  return countWood($next);
}

function generateMany($input) {
  $next = $input;
  $count = $countRep = $repeats = 0;

  for ($i=0; ; $i++) {
    $next = calcNext($next);
    $count = countWood($next);
    if ((1000000000 - 1 - $i) % 28 == 0 && $count) {
      $countRep == $count && $repeats++;
      $countRep = $count;
      if ($repeats > 1) {
        return $countRep;
      }
    }
  }
}

echo "Part 1: " . generateTen($input) . "\n";
echo "Part 2: " . generateMany($input) . "\n";
?>

readFile.php

<?php
$file = fopen("input.txt", "r") or exit("Unable to open file");

while(!feof($file)) {
  $array[] = fgets($file);
}

fclose($file);

return array_map(function($str) {
  $str = preg_replace("/\r|\n/", "", $str);
  return str_split($str);
}, array_filter($array));
?>
 

Very similar to Conway's Life, but the result is kind of more life-like.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my @grid;
while (<>) {
    chomp;
    push @grid, [ split // ];
}

for (1.. 10) {
    my @next;
    for my $y (0 .. $#grid) {
        for my $x (0 .. $#{ $grid[$y] }) {
            my %adjacent;
            my @coords = grep   $_->[0] >= 0 && $_->[0] <= $#{ $grid[$y] }
                             && $_->[1] >= 0 && $_->[1] <= $#grid,
                         [$x - 1, $y - 1], [$x, $y - 1], [$x + 1, $y - 1],
                         [$x - 1, $y    ],               [$x + 1, $y    ],
                         [$x - 1, $y + 1], [$x, $y + 1], [$x + 1, $y + 1];
            ++$adjacent{ $grid[ $_->[0] ][ $_->[1] ] } for @coords;
            $next[$x][$y] = {
                '.' => sub { ($adjacent{'|'} // 0) >= 3 ? '|' : '.' },
                '|' => sub { ($adjacent{'#'} // 0) >= 3 ? '#' : '|' },
                '#' => sub { ($adjacent{'#'} && $adjacent{'|'}) ? '#' : '.' },
            }->{ $grid[$x][$y] }->();
        }
    }
    @grid = @next;
}

my %count;
++$count{$_} for map @$_, @grid;
say +($count{'|'} // 0) * ($count{'#'} // 0);

Animation

 

A python solution very similar to that of day 12.

import functools


class Simulation:

    def __init__(self, fname):
        self.map = load_initial(fname)
        self.height = len(self.map)
        self.width = len(self.map[0]) if self.height > 0 else 0
        self.old_map = [[0 for _ in range(self.width)] for _ in range(self.height)]

    def step(self):
        self.old_map, self.map = self.map, self.old_map  # double buffering
        for y, row in enumerate(self.old_map):
            for x, current in enumerate(row):
                neighborhood = self.neighborhood(x, y)
                trees = sum(1 for (xx, yy) in neighborhood if self.old_map[yy][xx] == '|')
                lumberyard = sum(1 for (xx, yy) in neighborhood if self.old_map[yy][xx] == '#')
                self.map[y][x] = current
                if current == '.' and trees >= 3:
                    self.map[y][x] = '|'
                elif current == '|' and lumberyard >= 3:
                    self.map[y][x] = '#'
                elif current == '#' and (lumberyard == 0 or trees == 0):
                    self.map[y][x] = '.'

    def run(self, steps=1):
        last_seen = {}
        step = 0
        while step < steps:
            hashable = self.show()
            if hashable in last_seen:
                remaining = (steps - step) % (step - last_seen[hashable])
                step = steps - remaining
                last_seen = {}
            else:
                last_seen[hashable] = step
            self.step()
            step += 1

    @functools.lru_cache(maxsize=None)
    def neighborhood(self, x, y):
        neighbors = []
        for dx in [-1, 0, +1]:
            xx = x + dx
            if 0 > xx or xx >= self.width:
                continue
            for dy in [-1, 0, +1]:
                yy = y + dy
                if 0 > yy or yy >= self.height or (xx == x and yy == y):
                    continue
                neighbors.append((xx, yy))
        return neighbors

    def show(self):
        return '\n'.join(''.join(c for c in row) for row in self.map)


def load_initial(fname):
    with open(fname, 'r') as file:
        return [[c for c in row.strip()] for row in file]


def part(fname, steps):
    simulation = Simulation(fname)
    simulation.run(steps)
    trees = sum(1 for row in simulation.map for c in row if c == '|')
    lumber = sum(1 for row in simulation.map for c in row if c == '#')
    return trees * lumber


def test_load_initial():
    expected = list(map(list, ['.#.#...|#.',
                               '.....#|##|',
                               '.|..|...#.',
                               '..|#.....#',
                               '#.#|||#|#|',
                               '...#.||...',
                               '.|....|...',
                               '||...#|.#|',
                               '|.||||..|.',
                               '...#.|..|.']))

    assert expected == load_initial('test_input.txt')


def test_one_step():
    expected = """\
.......##.
......|###
.|..|...#.
..|#||...#
..##||.|#|
...#||||..
||...|||..
|||||.||.|
||||||||||
....||..|."""

    simulation = Simulation('test_input.txt')
    simulation.step()
    assert expected == simulation.show()


def test_ten_steps():
    expected = """\
.||##.....
||###.....
||##......
|##.....##
|##.....##
|##....##|
||##.####|
||#####|||
||||#|||||
||||||||||"""

    simulation = Simulation('test_input.txt')
    simulation.run(10)
    assert expected == simulation.show()


def test_part1():
    assert 1147 == part('test_input.txt', 10)


if __name__ == '__main__':
    print('Part1', part('input.txt', 10))
    print('Part2', part('input.txt', 1000000000))
 

Yawn. It was a relief to get something solvable after the problems from Saturday and Monday which were incredibly hard, but another Conway's Game of Life, with another huge iteration count? Just cranking the handle here, nothing new to solve.

I modelled it with a 2D array. Getting more familiar with Kotlin arrays and sequences now.

enum class Acre(val symbol: Char) {
    OPEN('.'),
    TREES('|'),
    LUMBERYARD('#')
}

data class Pos(val x: Int, val y: Int)

val Pos.neighbours: Sequence<Pos> get() = sequence {
    (-1..1).flatMap { dy ->
        (-1..1).map { dx -> 
            if (dy != 0 || dx != 0) yield(Pos(x+dx,y+dy))
        }
    }
}

class Landscape(val width: Int, val height: Int) {
    val acres: Array<Array<Acre>> = Array<Array<Acre>>(height) { Array<Acre>(width) { Acre.OPEN }}

    val positions: Sequence<Pos> get() = sequence {
        (0..height-1).flatMap { y -> (0..width-1).map { x -> yield(Pos(x, y)) }}
    }

    fun validPos(p: Pos): Boolean = 0 <= p.y && p.y < height && 0 <= p.x && p.x < width

    fun neighbourCount(p: Pos, a: Acre): Int =
        p.neighbours.count { n -> this[n] == a }

    fun totalCount(a: Acre): Int = positions.count { pos -> this[pos] == a }

    fun resourceValue(): Int = totalCount(Acre.TREES) * totalCount(Acre.LUMBERYARD)
}

operator fun Landscape.get(p: Pos): Acre = if (validPos(p)) acres[p.y][p.x] else Acre.OPEN
operator fun Landscape.set(p: Pos, a: Acre) { if (validPos(p)) acres[p.y][p.x] = a }

I made an infinite sequence of states again:

fun Landscape.tick(): Landscape {
    val next = Landscape(width, height)
    positions.forEach { pos ->
        val neighbours = pos.neighbours.map(this::get).toList()
        next[pos] = when (this[pos]) {
            Acre.OPEN -> 
                if (neighbourCount(pos, Acre.TREES) >= 3) 
                    Acre.TREES
                else
                    Acre.OPEN

            Acre.TREES ->
                if (neighbourCount(pos, Acre.LUMBERYARD) >= 3)
                    Acre.LUMBERYARD
                else
                    Acre.TREES

            Acre.LUMBERYARD ->
                if (neighbourCount(pos, Acre.LUMBERYARD) >= 1 && neighbourCount(pos, Acre.TREES) >= 1)
                    Acre.LUMBERYARD
                else
                    Acre.OPEN
        }
    }
    return next
}

fun Landscape.timeline(): Sequence<Landscape> = sequence {
    var next = this@timeline
    while (true) {
        yield(next)
        next = next.tick()
    }
}

So part 1 was trivial:

fun part1(input: Landscape): Int =
    input.timeline().drop(10).first().resourceValue()

For part 2 I made a generic loop finder:

inline fun <reified T> findLoop(ts: Sequence<T>): Pair<Int, Int> {
    val seen = mutableMapOf<T, Int>()
    val firstRepeat = ts.zip(indices).dropWhile { (t, i) -> 
        if (seen.containsKey(t))
            false
        else {
            seen[t] = i
            true
        }
    }.first()

    return Pair(seen[firstRepeat.first]!!, firstRepeat.second)
}

Then used this to do the old find-loop-run-last-few-iterations dance:

fun part2(input: Landscape): Int {
    val (loopStart, loopEnd) = findLoop(input.timeline())
    val iterations = 1000000000
    val loops = (iterations - loopStart) / (loopEnd - loopStart)
    val lastLoop = (iterations - loopStart) % loops
    val lastLoopTimeline = input.timeline().drop(loopStart)
    val lastIteration = lastLoopTimeline.drop(lastLoop).first()
    return lastIteration.resourceValue()
}
 

Also, Conway’s Game of Life? More like Conway’s Game of Logs! 😬

Classic DEV Post from Jul 10

How is your portfolio built?

Ryan Palo profile image
Ryan is a mechanical engineer in the East SF Bay Area with a focus on dynamic languages like Ruby & Python. Goal: learn a ton and become a physics, math, and programming teacher. Message me on DEV.TO