Ryan Palo

Posted on Dec 20, 2018

AoC Day 20: A Regular Map

#adventofcode #discuss

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!

Top comments (5)

Tiago Romero Garcia • Dec 26 '18

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 = [];
    }

    addChar(char) {
        this.path.push(char);
    }

    addBranch(branch) {
        this.path.push(branch);
    }
}

class Branch {

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

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

    addChar(char) {
        this.currentTerm.addChar(char);
    }

    addBranch(branch) {
        branch.currentTerm = null;
        this.currentTerm.addBranch(branch);
    }
}

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 === '|') {
            currentBranch.addTerm();
        }
        else if (char === ')') {
            currentBranch.parentBranch.addBranch(currentBranch);
            currentBranch = currentBranch.parentBranch;
        }
        else {
            currentBranch.addChar(char);
        }
    }
    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 adjacent = getAdjacent(path, currentI, currentJ);
                currentI = adjacent.i;
                currentJ = adjacent.j;

                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 { readFile } = require('./reader');

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'))[0];
    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 { readFile } = require('./reader');

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'))[0];
    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}`);
})();

Neil Gall • Dec 21 '18 • Edited

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:

A single move (the direction doesn't matter)
A sequence of trees
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)
                    seq.add(t)
                    p = p_
                }
                '|' -> {
                    opts.add(Tree.Seq(seq))
                    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[0] != '^') 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.

For a single move, the length of the longest path is 1
For a choice of trees, the length of the longest path is the length of the longest choice
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!

E. Choroba • Dec 21 '18

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 + $_->[0] }{ $y + $_->[1] } =~ /[-|]/
                    && $grid{ $x + 2 * $_->[0] }{ $y + 2 * $_->[1] } ne 'x'
                ) {
                    push @next, [ $x + 2 * $_->[0], $y + 2 * $_->[1] ];
                }
            }
        }
        @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 + $_->[0] }{ $y + $_->[1] } =~ /[-|]/
                    && $grid{ $x + 2 * $_->[0] }{ $y + 2 * $_->[1] } ne 'x'
                ) {
                    push @next, [ $x + 2 * $_->[0], $y + 2 * $_->[1] ];
                }
            }
        }
        @process = @next;
        ++$distance;
    }
    say $count;
}

Juan Manuel Gimeno • Dec 21 '18 • Edited

I've been killed by day 20 :-)

Juan Manuel Gimeno • Dec 21 '18

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[0] == '^' 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)
                    self.legs.add(leg)
                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)
            self.legs.add(leg)

    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:
        contents = file.read().strip()
        print("Part1: ", part1(contents))
        print("Part2: ", part2(contents))

DEV Community

AoC Day 20: A Regular Map

Top comments (5)

JavaScript solution

20-common.js

20a.js

20b.js

Part 1

Part 2

Read next

Embracing the Fun: Share Your Favorite Tech April Fools'!

Music Monday — What are you listening to? (Covers Edition)

What Junior Devs Get Wrong

Leetcode Solution: #206: Reverse Linked List 🐬