## DEV Community Ryan Palo

Posted on

# AoC Day 18: Settlers of The North Pole

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! 🎄 Tiago Romero Garcia

## 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];

// For an open ground acre
if (originalAcre === MAP.OPEN_GROUND) {
nextMap[i][j] = adjacentTrees >= 3 ? MAP.TREES : MAP.OPEN_GROUND;
}
// For a trees acre
else if (originalAcre === MAP.TREES) {
nextMap[i][j] = adjacentLumberyards >= 3 ? MAP.LUMBERYARD : MAP.TREES;
}
// For a lumberyard acre
else if (originalAcre === MAP.LUMBERYARD) {
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);

printSolution(solution);
})();
`````` 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

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

\$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); \$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";
?>
``````

``````<?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));
?>
`````` 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 @coords = grep   \$_-> >= 0 && \$_-> <= \$#{ \$grid[\$y] }
&& \$_-> >= 0 && \$_-> <= \$#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[ \$_-> ][ \$_-> ] } 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);
``````  A python solution very similar to that of day 12.

``````import functools

class Simulation:

def __init__(self, fname):
self.height = len(self.map)
self.width = len(self.map) 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)

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

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

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))
`````` 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()
}
`````` Ryan Palo

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

DEV Community

## The AI Brief

### AI generated git commit messages

Minimize the struggle of remembering what you just coded. AI-generated commits make it easier to manage projects and keep track of changes. The Nutlope/aicommits project demonstrates how AI can improve commit messages.

### I open sourced an AI that creates any UI in seconds

Make AI-generated user interfaces a breeze. This open-source project harnesses the power of generative AI technologies like chatGPT to create versatile, quick, and intuitive UI components.

### Use AI to commit like a PRO in 1 second

Upgrade your commit message game with AI. Boost your productivity by using ChatGPT to generate commit messages and avoid context switching. OpenCommit is an open-source library that helps you achieve this easily.

### Build your own ChatGPT starter kit

Train AI models on custom data for improved domain-specific knowledge. Combine the power of WebView technologies and this starter kit to train your ChatGPT model on specific websites, allowing for better-optimized outcomes.