AoC Day 20: A Regular Map Ryan Palo twitter logo github logo Dec 20 '18・1 min read

Advent of Code (26 Part Series)

Day 20! Only 5 more days after this one! At this point, I've fallen severely behind, but I haven't given up yet. I'm determined to finish by Christmas.

In this challenge, we are enumerating the possible directions we could take while exploring the North Pole, as laid out by a Regular Expression. And this is only the first part! Once we finally have our map built, we have to find the very furthest room from us in the facility.

Hopefully, after completing this challenge, your expression will be one of Christmas joy!

DISCUSS (5) JavaScript solution

This was a very fun one, and I spent half of the time on the pen & paper figuring out how this tree would work.

As usual, I'm gonna omit reader.js which is the same as the other solutions and jump to the point:

20-common.js

class Term {
constructor() {
this.path = [];
}

this.path.push(char);
}

this.path.push(branch);
}
}

class Branch {

constructor(parentBranch) {
this.terms = [];
this.parentBranch = parentBranch;
}

this.currentTerm = new Term();
this.terms.push(this.currentTerm);
}

}

branch.currentTerm = null;
}
}

const getTerms = (input) => {
const chars = input.substring(1, input.length-1);

let currentBranch = new Branch();
for (const char of chars) {
if (char === '(') {
currentBranch = new Branch(currentBranch);
}
else if (char === '|') {
}
else if (char === ')') {
currentBranch = currentBranch.parentBranch;
}
else {
}
}
currentBranch.currentTerm = null;
return currentBranch;
};

const getKey = ({i,j}) => `\${i},\${j}`;

const getAdjacent = (currentPath, i, j) => {
if (currentPath === 'N') return { i: i-1, j };
if (currentPath === 'W') return { i, j: j-1 };
if (currentPath === 'E') return { i, j: j+1 };
if (currentPath === 'S') return { i: i+1, j };
}

// DFS sorta-Dijkstra algorithm
const calculateDistances = (distances, branch, distance = 0, i = 0, j = 0) => {
let termIndex = 0;
while (termIndex < branch.terms.length) {
const term = branch.terms[termIndex];
let pathIndex = 0;

let currentDistance = distance;
let currentI = i;
let currentJ = j;
while (pathIndex < term.path.length) {
const path = term.path[pathIndex];
if (path instanceof Branch) {
calculateDistances(distances, path, currentDistance, currentI, currentJ);
}
else {

const key = getKey(adjacent);
const adjacentDistance = distances.get(key);
currentDistance++;
if (adjacentDistance === undefined || currentDistance < adjacentDistance) {
distances.set(key, currentDistance);
}
}
pathIndex++;
}
termIndex++;
}
}

module.exports = {
getTerms,
calculateDistances
};

20a.js

const {
getTerms,
calculateDistances
} = require('./20-common');

const findMaxDistance = distances => {
return [...distances.values()].reduce((max, distance) => Math.max(max, distance), 0);
}

(async () => {
const input = (await readFile('20-input.txt'));
const root = getTerms(input);
const distances = new Map();
calculateDistances(distances, root);
const maxDistance = findMaxDistance(distances);

console.log(`The largest number of doors you would be required to pass through to reach a room is \${maxDistance}`);
})();

20b.js

const {
getTerms,
calculateDistances
} = require('./20-common');

const getRoomsWithMinDistance = (distances, minDistance) => {
return [...distances.values()].filter(distance => distance >= minDistance).length;
};

(async () => {
const input = (await readFile('20-input.txt'));
const root = getTerms(input);
const distances = new Map();
calculateDistances(distances, root);
const roomsWithMinDistance = getRoomsWithMinDistance(distances, 1000);

console.log(`The number of rooms which have a shortest path from your current location that pass through at least 1000 doors is \${roomsWithMinDistance}`);
})();

Oh no, I've spent 19 days avoiding regular expressions!

This isn't what it seems though. A regex is a tree, and the answer (to part 1 at least) can be found by a tree traversal. So we'll do just that by parsing the regex into a tree and running the appropriate traversal.

There are three things that can exist in the tree:

1. A single move (the direction doesn't matter)
2. A sequence of trees
3. A choice of trees
sealed class Tree {
object Move: Tree()
data class Seq(val steps: List<Tree>): Tree()
data class Opt(val choices: List<Tree>): Tree()
}

To parse the regex we just walk over the characters building a sub-tree each time we hit a parenthesis. Within a sub-tree a vertical bar starts a new sequence and appends it to the set of optionals.

fun parseTree(regex: String): Tree {
val chars = regex.toCharArray()

fun parseNode(start: Int): Pair<Int, Tree> {
var opts = mutableListOf<Tree>()
var seq = mutableListOf<Tree>()
var p = start
while (p < chars.size) {
when (chars[p]) {
'N', 'S', 'E', 'W' -> seq.add(Tree.Move)
'(' -> {
val (p_, t) = parseNode(p+1)
p = p_
}
'|' -> {
seq = mutableListOf<Tree>()
}
')', '\$' -> {
val t = if (opts.isEmpty()) Tree.Seq(seq) else Tree.Opt(opts + Tree.Seq(seq))
return Pair(p, t)
}
else -> throw IllegalStateException("unexpected char '\${chars[p]}'")
}
p += 1
}
throw IllegalStateException("EOF")
}

if (chars != '^') throw IllegalArgumentException("Missing ^")
return parseNode(1).second
}

Part 1

The traversal we want to do is to find the longest path through the tree, avoiding loops. This can be broken down to a longest path calculation for each of the three cases. Recursive data structures are best served by recursive algorithms.

1. For a single move, the length of the longest path is 1
2. For a choice of trees, the length of the longest path is the length of the longest choice
3. For a sequence of trees, the length is the sum of the lengths of the parts

Loops are a special case. When a tree has a loop leading it back to the start, we avoid the loop and the longest path we'd take is 0. This all translates into surprisingly simple code:

fun Tree.hasLoop(): Boolean = when(this) {
is Tree.Move -> false
is Tree.Seq -> steps.isEmpty()
is Tree.Opt -> choices.any(Tree::hasLoop)
}

fun Tree.longestPath(): Int = if (hasLoop()) 0 else when(this) {
is Tree.Move -> 1
is Tree.Seq -> steps.map(Tree::longestPath).sum()
is Tree.Opt -> choices.map(Tree::longestPath).max()!!
}

Part 2

The wording of the question has me stumped. "How many rooms can be reached" sounds like how many steps along any path are at least 1000 doors away, but I can't find an answer for that which satisfies the puzzle. I've also tried how many terminal rooms (i.e. at the end of any whole path) are at least 1000 doors away but no luck. The lack of examples doesn't help. Customers and their fuzzy requirements!

I'm one day behind :-( I hope I can still catch up.

Perl solution:

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

use List::Util qw{ min max };

chomp( my \$regex = <> );

my (\$x, \$y) = (0, 0);
my %grid = (\$x => { \$y => 'X' });

sub show {
my \$min_x = min(keys %grid);
my \$max_x = max(keys %grid);
my \$min_y = min(map keys %\$_, values %grid);
my \$max_y = max(map keys %\$_, values %grid);
for my \$y (\$min_y .. \$max_y) {
for my \$x (\$min_x .. \$max_x) {
print \$grid{\$x}{\$y} //= "#";
}
print "\n";
}
}

sub draw {
my (\$pos, \$stack) = @_;
my \$current = substr \$regex, \$pos, 1;
my \$done;
{'^' => sub { die if \$pos },
E   => sub {
\$grid{\$x + 1}{\$y} = '|'; \$grid{\$x + 2}{\$y} = '.';
\$_ = '#' for \$grid{\$x + 1}{\$y - 1}, \$grid{\$x + 1}{\$y + 1};
\$x += 2;
},
W   => sub {
\$grid{\$x - 1}{\$y} = '|'; \$grid{\$x - 2}{\$y} = '.';
\$_ = '#' for \$grid{\$x - 1}{\$y - 1}, \$grid{\$x - 1}{\$y + 1};
\$x -= 2;
},
N   => sub {
\$grid{\$x}{\$y - 1} = '-'; \$grid{\$x}{\$y - 2} = '.';
\$_ = '#' for \$grid{\$x + 1}{\$y - 1}, \$grid{\$x - 1}{\$y - 1};
\$y -= 2;
},
S   => sub {
\$grid{\$x}{\$y + 1} = '-'; \$grid{\$x}{\$y + 2} = '.';
\$_ = '#' for \$grid{\$x + 1}{\$y + 1}, \$grid{\$x - 1}{\$y + 1};
\$y += 2;
},
'(' => sub { push @\$stack, [\$x, \$y] },
'|' => sub { (\$x, \$y) = @{ \$stack->[-1] } },
')' => sub { pop @\$stack },
'\$' => sub { show(); \$done = 1 },
}->{\$current}->();
no warnings 'recursion';
draw(\$pos + 1, \$stack) unless \$done;
}

sub walk {
my @process = [0, 0];
my \$distance = 0;
while (@process) {
my @next;
while (my \$coords = shift @process) {
my (\$x, \$y) = @\$coords;
\$grid{\$x}{\$y} = 'x';
for ([0, 1], [1, 0], [-1, 0], [0, -1]) {
if (\$grid{ \$x + \$_-> }{ \$y + \$_-> } =~ /[-|]/
&& \$grid{ \$x + 2 * \$_-> }{ \$y + 2 * \$_-> } ne 'x'
) {
push @next, [ \$x + 2 * \$_->, \$y + 2 * \$_-> ];
}
}
}
@process = @next;
++\$distance;
}
say \$distance - 1;
}

draw(0, []);
walk();

For part 2, I had to slightly modify the walk subroutine:

sub walk {
my \$count = 0;
my @process = [0, 0];
my \$distance = 0;
while (@process) {
my @next;
while (my \$coords = shift @process) {
++\$count if \$distance >= 1000;
my (\$x, \$y) = @\$coords;
\$grid{\$x}{\$y} = 'x';
for ([0, 1], [1, 0], [-1, 0], [0, -1]) {
if (\$grid{ \$x + \$_-> }{ \$y + \$_-> } =~ /[-|]/
&& \$grid{ \$x + 2 * \$_-> }{ \$y + 2 * \$_-> } ne 'x'
) {
push @next, [ \$x + 2 * \$_->, \$y + 2 * \$_-> ];
}
}
}
@process = @next;
++\$distance;
}
say \$count;
}

I've been killed by day 20 :-)

One day after but now it works !!

from collections import defaultdict, namedtuple

Leg = namedtuple('Leg', 'start begin end cont_start cont_end')

def mkleg(start, begin, end, cont_start=None, cont_end=None):
return Leg(start, begin, end, cont_start, cont_end)

class Expedition:

def __init__(self, regexp):
self.regexp = regexp
self.distances = defaultdict(lambda: float('inf'))
self.doors = set()
self.legs = {mkleg((1, 1), 0, len(self.regexp))}

def explore(self):
assert self.regexp == '^' and self.regexp[-1] == '\$'
counter = 0
while len(self.legs) > 0:
next_leg = self.legs.pop()
self.explore_leg(next_leg)
counter += 1

def explore_leg(self, current_leg):
(x, y) = current_leg.start
idx = current_leg.begin
finish = False
while idx < current_leg.end and not finish:
old_pos = (x, y)
current = self.regexp[idx]
if current == '^':
self.distances[(x, y)] = 0
elif current == 'N':
y -= 2
elif current == 'E':
x += 2
elif current == 'S':
y += 2
elif current == 'W':
x -= 2
elif current == '\$':
pass
elif current == '(':
matching = self.find_matching(idx)
options = self.find_options(idx, matching)
for (option_begin, option_end) in options:
assert option_begin <= option_end
if option_begin < option_end:
leg = mkleg((x, y), option_begin, option_end, matching, current_leg.end)
else:
leg = mkleg((x, y), matching, current_leg.end)
finish = True
elif current == ')':
pass
else:
raise Exception('unexpected character ', current)
self.distances[(x, y)] = min(1 + self.distances[old_pos], self.distances[(x, y)])
idx += 1
if current_leg.cont_start and current_leg.cont_start < current_leg.cont_end:
leg = mkleg((x, y), current_leg.cont_start, current_leg.cont_end)

def find_matching(self, idx):
assert self.regexp[idx] == '('
opened = 0
while True:
idx += 1
current = self.regexp[idx]
if current == '(':
opened += 1
elif current == ')' and opened == 0:
return idx + 1
elif current == ')':
opened -= 1
elif current == '^':
raise Exception("regexp should be well constructed")

def find_options(self, begin, end):
assert self.regexp[begin] == '(' and self.regexp[end - 1] == ')'
options = []
opened = 0
option_start = begin + 1
for idx in range(begin + 1, end):
current = self.regexp[idx]
if current == '(':
opened += 1
elif current == ')':
opened -= 1
elif current == '|' and opened == 0:
options.append((option_start, idx))
option_start = idx + 1
idx += 1
options.append((option_start, end))
return options

def part1(regexp):
expedition = Expedition(regexp)
expedition.explore()
return max(expedition.distances.values())

def part2(regexp):
expedition = Expedition(regexp)
expedition.explore()
return sum(1 for v in expedition.distances.values() if v >= 1000)

def test_part1():
assert part1('^WNE\$') == 3
assert part1('^ENWWW(NEEE|SSE(EE|N))\$') == 10
assert part1('^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN\$') == 18
assert part1('^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))\$') == 23
assert part1('^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))\$') == 31

if __name__ == '__main__':
with open('input.txt', 'r') as file:   