AoC Day 18: Settlers of The North Pole

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
};

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

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

<?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";
?>

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

#!/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);

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

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 }

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()
    }
}

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

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

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()
}