# AoC Day 20: A Regular Map

### Ryan Palo Dec 20 '18 γ»1 min read

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!

Classic DEV Post from Nov 14 '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

## 20a.js

## 20b.js

Oh no, I've spent 19 days

avoidingregular 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:

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.

## 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.

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:

## 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:

For part 2, I had to slightly modify the

`walk`

subroutine:I've been killed by day 20 :-)

One day after but now it works !!