AoC Day 22: Mode Maze

Day 22, can you believe it? Only 3 more days until Christmas! But first, we have to find the friend of someone who may or may not be Santa inside a deep, rocky, narrow, and wet cave system. But do we charge in there blindly and without a plan? No! We are programmers! We need to do some analysis first to evaluate the risk of the area.

This weekend is the last chance to make up some ground against this relentless onslaught of code challenges! Or, depending on your priorities, this weekend might be a perfect chance to get caught up on eating tons of cookies and drinking eggnog. Or both! 😀

Good luck with this one! Let's see how you do.

Comments

[Neil Gall]

Ah, a proper coding puzzle again after the last couple of days of drudge-work.

Firstly a data model.

data class Pos(val x: Int, val y: Int) {
    val up: Pos get() = Pos(x, y-1)
    val down: Pos get() = Pos(x, y+1)
    val left: Pos get() = Pos(x-1, y)
    val right: Pos get() = Pos(x+1, y)
    fun neighbours(): Set<Pos> = setOf(up, down, left, right)
}
data class Model(val depth: Int, val target: Pos)

Some might suggest the input data format is so simple you can just use string splits and regular expressions. But if I want to make one point in this Advent Of Code it's that parser combinators always result in simpler, better code.

fun parse(input: String): Model {
    val integer = INTEGER.map(String::toInt)
    val depth = string("depth: ").next(integer)
    val coord = sequence(integer, string(",").next(integer), ::Pos)
    val target = string("target: ").next(coord)
    val model = sequence(depth, WHITESPACES.next(target), ::Model)
    return model.parse(input.trim())
}

Previous solutions with 2D arrays have resulted in slightly messy code. Let's factor out the 2D array stuff.

typealias Grid<T> = Array<Array<T>>

inline fun <reified T> makeGrid(width: Int, height: Int, empty: T) =
    Array<Array<T>>(height) { Array<T>(width) { empty } }

operator fun <T> Grid<T>.get(p: Pos): T = this[p.y][p.x]
operator fun <T> Grid<T>.set(p: Pos, t: T) { this[p.y][p.x] = t }

fun <T> Grid<T>.positions(): Sequence<Pos> =
    indices.asSequence().flatMap { y ->
        this[y].indices.asSequence().map { x -> Pos(x, y) }
    }

There's one simple insight to part 1, which is that the calculated value for each position depends on the positions above and to the left. So the whole grid can be calculated in a right-then-down or down-then-right order. Let's do the whole thing in an object initialiser:

data class Cave(val model: Model, val limit: Pos = model.target) {
    val grid = makeGrid(limit.x+1, limit.y+1, Square(0, 0))

    init {
        (0..limit.y).forEach { y ->
            (0..limit.x).forEach { x ->
                val p = Pos(x, y)
                val geologicIndex = when {
                    p == model.target -> 0
                    y == 0 -> x * 16807L
                    x == 0 -> y * 48271L
                    else -> grid[p.left].erosionLevel * grid[p.up].erosionLevel
                }
                val erosionLevel = (geologicIndex + model.depth) % 20183L
                grid[p] = Square(geologicIndex, erosionLevel)
            }
        }
    }
}

The descriptions of erosion level, region type and risk level could all be collapsed since there is a 1:1 relationship. But in my experience of building software, if the customer felt the need to describe these things separately, then model them independently. It's lower cost to have each representation in the code and live with the simple mappings than have to mentally remember the equivalences. And it pays off immensely when the requirements change subtly in the future.

enum class Type(val risk: Int, val symbol: Char) {
    ROCKY(0, '.'),
    WET(1, '='),
    NARROW(2, '|')
}

data class Square(val geologicIndex: Long, val erosionLevel: Long) {
    val type: Type = when(erosionLevel % 3) {
        0L -> Type.ROCKY
        1L -> Type.WET
        2L -> Type.NARROW
    }
}

Part 1

Part 1 is answered simply by computing the sum risk level for the entire cave.

fun part1(input: Model): Int = Cave(input).riskLevel()

Part 2

A meaty part 2 today, which introduces a whole new algorithmic requirement. We have to find the shortest path from the start to the trapped friend. Like Day 15 this can be solved with an application of Dijkstra's algorithm. The difference here is that the cost of moving from region to region varies depending on the equipped tool, and indeed in some cases transitions are not possible due to incompatible tools.

First we'll model the tools, the mappings to region types:

enum class Tool(val symbol: Char) { 
    NEITHER('N'),
    TORCH('T'),
    CLIMBING_GEAR('C')
}

fun Square.availableTools(): Set<Tool> = when(type) {
    Type.ROCKY  -> setOf(Tool.CLIMBING_GEAR, Tool.TORCH)
    Type.WET    -> setOf(Tool.CLIMBING_GEAR, Tool.NEITHER)
    Type.NARROW -> setOf(Tool.TORCH, Tool.NEITHER)
}

Dijkstra's algorithm needs a "current best" value for each position in the graph. This is a product of time and equipped tool. We'll also make some helpers for deriving new states:

data class State(val time: Int, val tool: Tool)

fun State.move(p: Pos) = State(time + 1, tool)
fun State.changeTool(t: Tool) = State(time + 7, t)

The Dijkstra algorithm follows the same basic structure as before:

1. Start with all positions unvisited and the current position at the start
2. While we haven't visited the end position:
   • Calculate the cost of moving to all the neighbours of the current position
   • If this is less than the current cost for that neighbour, update it
   • Move to the unvisited position with the current least cost
3. The minimum cost is left in the end position

fun Cave.dijkstra(start: Pos, end: Pos): State {
    val unvisited = grid.positions().toMutableSet()

    val noPath = State(Int.MAX_VALUE, Tool.NEITHER)
    val states = makeGrid(limit.x+1, limit.y+1, noPath)

    fun valid(p: Pos) = 
        unvisited.contains(p) && 0 <= p.x && p.x <= limit.x && 0 <= p.y && p.y <= limit.y

    states[start] = State(0, Tool.TORCH)

    while (unvisited.contains(end)) {

        val minTime = unvisited.map { p -> states[p].time }.min()
        unvisited.filter { p -> states[p].time == minTime }.forEach { current ->
            val availableTools = grid[current].availableTools()
            val state = states[current]

            current.neighbours().filter(::valid).forEach { neighbour ->
                // we'll come to updating neighbours in a bit
            }

            unvisited.remove(current)
        }
    }

    return states[end]
}

The difference today is that the cost of moving to a neighbour position is considerably more complex and must take the transition of tools into account. Firstly, we must match the tools available at the current position with the tools available at the neighbour position. Then:

1. If we can move to the neighbour without changing tool the cost is 1 minute.
2. Or if we can move to the neighbour after changing tool the cost is 7 minutes to change tool then 1 minute to move.
3. Or if no tool change is possible to reach the neighbour, the move is impossible.

val neighbourTools = if (neighbour == end) setOf(Tool.TORCH) else grid[neighbour].availableTools()

val neighbourState =
    if (neighbourTools.contains(state.tool))
        state.move(neighbour)
    else {
        val commonTools = neighbourTools.intersect(availableTools)
        if (commonTools.isEmpty())
            noPath
        else 
            state.changeTool(commonTools.first()).move(neighbour)
    }

if (neighbourState.time < states[neighbour].time) {
    states[neighbour] = neighbourState
}   

The final aspect of part 2 is that the optimal route may extend beyond the target position. We have no idea how far, but changing tools takes eight times longer than just moving, so the furthest beyond the direct route to the target we might go without changing tools is approximately eight times more. Fudging it a bit and waiting a good old time for the answer:

fun part2(input: Model): Int? =
    (1..8).map { scale ->   
        val cave = Cave(input, Pos(input.target.x*scale, input.target.y*scale))
        val state = cave.dijkstra(Pos(0, 0), input.target)
        state.time
    }.min()
}

Sadly this doesn't get me an answer that Advent of Code is happy with. I am seeing a longer path for scale=4 than scale=3, which is strange, and points to the path being dependent on the order that the positions are visited rather than the intrinsic properties of the positions. I'll keep working on this one.

[Juan Manuel Gimeno]

Part1 was easy: translate the definitions into python code and let the memoization decoration do catching for efficiency.

Part2 is an application of the A* algorithm, which I ended consulting in Wikipedia because my recall was wrong and, although I solved the given example, I fail at the problem.

import collections
import functools

ROCKY, WET, NARROW = range(3)


@functools.lru_cache(maxsize=None)
def geologic_index(region, depth, target):
    x, y = region
    if region == (0, 0) or region == target:
        return 0
    elif y == 0:
        return x * 16807
    elif x == 0:
        return y * 48271
    else:
        return erosion_level((x - 1, y), depth, target) * erosion_level((x, y - 1), depth, target)


@functools.lru_cache(maxsize=None)
def erosion_level(region, depth, target):
    return (geologic_index(region, depth, target) + depth) % 20183


def type_(region, depth, target):
    return erosion_level(region, depth, target) % 3


def risk_level(depth, target):
    width, height = target
    return sum(type_((x, y), depth, target) for x in range(width + 1) for y in range(height + 1))


def test_geologic_index():
    assert geologic_index((0, 0), 510, (10, 10)) == 0
    assert geologic_index((1, 0), 510, (10, 10)) == 16807
    assert geologic_index((0, 1), 510, (10, 10)) == 48271
    assert geologic_index((1, 1), 510, (10, 10)) == 145722555
    assert geologic_index((10, 10), 510, (10, 10)) == 0


def test_erosion_level():
    assert erosion_level((0, 0), 510, (10, 10)) == 510
    assert erosion_level((1, 0), 510, (10, 10)) == 17317
    assert erosion_level((0, 1), 510, (10, 10)) == 8415
    assert erosion_level((1, 1), 510, (10, 10)) == 1805
    assert erosion_level((10, 10), 510, (10, 10)) == 510


def test_type():
    assert type_((0, 0), 510, (10, 10)) == ROCKY
    assert type_((1, 0), 510, (10, 10)) == WET
    assert type_((0, 1), 510, (10, 10)) == ROCKY
    assert type_((1, 1), 510, (10, 10)) == NARROW
    assert type_((10, 10), 510, (10, 10)) == ROCKY


def test_risk_level():
    assert risk_level(510, (10, 10)) == 114


# Part 2

CLIMBING_GEAR, TORCH, NEITHER = range(3)
COMPATIBILITY = {ROCKY: {CLIMBING_GEAR, TORCH},
                 WET: {CLIMBING_GEAR, NEITHER},
                 NARROW: {TORCH, NEITHER}}

State = collections.namedtuple('State', 'region equipment')


class Cave:
    def __init__(self, depth, target):
        self.depth = depth
        self.target = target

    def type_(self, region):
        return type_(region, self.depth, self.target)

    def explore(self):
        fscore = collections.defaultdict(lambda: float('inf'))
        gscore = {}
        start = State(region=(0, 0), equipment=TORCH)

        gscore[start] = 0
        fscore[start] = self.heuristic(start)

        open_states = {start}
        closed_states = set()

        while True:
            current_state = min(open_states, key=lambda s: fscore[s])
            open_states.remove(current_state)

            if current_state.region == self.target and current_state.equipment == TORCH:
                return gscore[current_state]

            closed_states.add(current_state)

            for next_state, distance in self.neighborhood(current_state):

                if next_state in closed_states:
                    continue

                tentative_gscore = gscore[current_state] + distance

                if next_state not in open_states:
                    open_states.add(next_state)
                elif tentative_gscore > gscore[next_state]:
                    continue

                gscore[next_state] = tentative_gscore
                fscore[next_state] = tentative_gscore + self.heuristic(next_state)

    def heuristic(self, state):
        return abs(self.target[0] - state.region[0]) \
               + abs(self.target[1] - state.region[1])

    def neighborhood(self, current):
        next_states_and_distances = []
        for next_region in adjacent(current.region):
            if current.equipment in COMPATIBILITY[self.type_(next_region)]:
                next_states_and_distances.append((State(region=next_region, equipment=current.equipment), 1))
        for equipment in [CLIMBING_GEAR, TORCH, NEITHER]:
            if equipment != current.equipment and equipment in COMPATIBILITY[self.type_(current.region)]:
                next_states_and_distances.append((State(region=current.region, equipment=equipment), 7))
        return next_states_and_distances


def adjacent(region):
    x, y = region
    moves = []
    if x > 0:
        moves.append((x - 1, y))
    if y > 0:
        moves.append((x, y - 1))
    return moves + [(x + 1, y), (x, y + 1)]


def explore(depth, target):
    return Cave(depth, target).explore()


def test_cave():
    cave = Cave(510, (10, 10))
    assert cave.type_((0, 0)) == ROCKY
    assert cave.type_((1, 0)) == WET
    assert cave.type_((0, 1)) == ROCKY
    assert cave.type_((1, 1)) == NARROW
    assert cave.type_((10, 10)) == ROCKY


def test_explore():
    cave = Cave(510, (10, 10))
    assert cave.explore() == 45


def _test_part2():
    cave = Cave(8112, (13, 743))
    assert cave.explore() == 1010


if __name__ == '__main__':
    print("Part1: ", risk_level(8112, (13, 743)))
    print("Part2: ", explore(8112, (13, 743)))

[E. Choroba]

Part 1 wasn't so hard, I basically just followed the description.

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

my ($depth)   = <> =~ /\d+/g;
my ($tx, $ty) = <> =~ /(\d+),(\d+)/;

my @cave;
sub level {
    my ($x, $y) = @_;
    ($cave[$x][$y] + $depth) % 20_183;
}

$cave[0][0] = 0;
$cave[$tx][$ty] = 0;

for my $x (0 .. $tx) {
    $cave[$x][0] //= $x * 16_807;
    for my $y (1 .. $ty) {
        $cave[$x][$y]
            //= $x == 0 ? $y * 48_271
                        : level($x - 1, $y) * level($x, $y - 1);
    }
}

my $s = 0;
for my $y (0 .. $ty) {
    for my $x (0 .. $tx) {
        my $l = level($x, $y) % 3;
        print +('.', '=', '|')[$l];
        $s += $l;
    }
    print "\n";
}

say $s;

Part 2, on the other hand, was quite a challenge. I implemented kind of a priority queue (not the real one, but I knew there wouldn't be almost any gaps between the priorities). I also memoized the geologic index and level functions to speed it up, but it still took a bit over 1 minute.

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

use enum qw( ROCKY WET NARROW );
use enum qw( GEAR TORCH NEITHER );

my ($depth)   = <> =~ /\d+/g;
my ($tx, $ty) = <> =~ /(\d+),(\d+)/;

my @cave;
my %level;
sub level {
    my ($x, $y) = @_;
    no warnings 'recursion';
    $level{$x}{$y} //= (cave($x, $y) + $depth) % 20_183;
}

$cave[0][0] = 0;
$cave[$tx][$ty] = 0;

sub cave {
    my ($x, $y) = @_;
    return $cave[$x][$y] if defined $cave[$x][$y];
    if ($x == 0) {
        $cave[$x][$y] = $y * 48_271;
    } elsif ($y == 0) {
        $cave[$x][$y] = $x * 16_807;
    } else {
        no warnings 'recursion';
        $cave[$x][$y] = level($x - 1, $y) * level($x, $y - 1);
    }
    $cave[$x][$y]
}

my %allowed = ((ROCKY)  => { (GEAR)  => undef, (TORCH)   => undef },
               (WET)    => { (GEAR)  => undef, (NEITHER) => undef },
               (NARROW) => { (TORCH) => undef, (NEITHER) => undef });

my @reach = ([{ (TORCH) => 0 }]);
$reach[0][0]{$_} = 7 for grep exists $allowed{ level(0, 0) % 3 }{$_},
                         GEAR, NEITHER;
my %queue = (0 => [[0, 0]]);
my $step = 0;
while (keys %queue) {
    my $current = delete $queue{$step};
    next unless $current;

    for my $coords (@$current) {
        my ($x, $y) = @$coords;
        for my $candidate ([$x + 1, $y], [$x - 1, $y],
                           [$x, $y - 1], [$x, $y + 1]
        ) {
            my ($i, $j) = @$candidate;
            next if $i < 0 || $j < 0;
            for my $tool_from (TORCH, GEAR, NEITHER) {
                next
                    unless exists $allowed{ level($x, $y) % 3 }{$tool_from}
                    && defined $reach[$x][$y]{$tool_from};

                for my $tool_to (TORCH, GEAR, NEITHER) {
                    next unless exists
                            $allowed{ level($x, $y) % 3 }{$tool_to}
                        && exists $allowed{ level($i, $j) % 3 }{$tool_to};

                    my $new = $reach[$x][$y]{$tool_from} + 1
                            + 7 * ($tool_from != $tool_to);
                    if (! defined $reach[$i][$j]{$tool_to}
                        || $new < $reach[$i][$j]{$tool_to}
                    ) {
                        $reach[$i][$j]{$tool_to} = $new;
                        push @{ $queue{$new} }, [$i, $j];
                    }
                }
            }
        }
    }

    if (defined $reach[$tx][$ty] && exists $reach[$tx][$ty]{+TORCH}) {
        say $step, ' ', $reach[$tx][$ty]{+TORCH};
        my $best = $reach[$tx][$ty]{+TORCH};
        last if $best < $step;
    }
} continue {
    say ++$step;
}

say $reach[$tx][$ty]{+TORCH};