DEV Community

Cover image for AoC Day 18: Settlers of The North Pole
Ryan Palo
Ryan Palo

Posted on

AoC Day 18: Settlers of The North Pole

#adventofcode #discuss

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! 🎄

Top comments (6)

Collapse
 
themindfuldev profile image
Tiago Romero •

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);
})();
Collapse
 
jenovs profile image
Viktors Jenovs •

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

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

Collapse
 
jmgimeno profile image
Juan Manuel Gimeno •

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

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

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

Read next

pidgey0403 profile image

Tips for working from the office?

Gabrielle Niamat -

ssukhpinder profile image

Top Prompts for Content Revision: Master SEO & Engaging Writing

Sukhpinder Singh -

leg_end profile image

Don't stop a process once started!

conjurer -

saamiabbaskhan profile image

Are We Sacrificing Readability for Conciseness in Modern Java?

Saami abbas Khan -