AoC Day 18: Settlers of The North Pole

twitter logo github logo ・1 min read

Part of "Advent of Code" series

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 Jan 3

Conversation with an Author - Ali Spittel

Malik and Dan sit down to talk shop with Ali Spittel

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

Customize DEV by logging in

  • Follow users
  • Follow tags
  • Dark mode
  • Font style (like sans serif)
  • Notifications
Get Started