A Maze of Twisty Little Cubicles

#adventofcode #algorithms #computerscience #javascript

Advent of Code 2016 Day 13

Part 1

Yeesh! Shortest path again?
Feels like Day 24, but with a much smaller area
A reminder before rendering the area
Rendering the area
Finding the shortest path

Yeesh! Shortest path again?!

Day 24, which I couldn't find manually or algorithmically
Day 22, which I solved manually after getting a big hint from reddit
Day 17, which I solved and built a simulator for
Day 11, which I attempted ahead of today - first, actually - since it was referenced by later Days
And now Day 13

I'm 2/4. I'd love to be 3/5!

Feels like Day 24, but with a much smaller area

Good news is there are no checkpoints
Better news is I'm confident I can at least render the area, so that I can attempt to traverse it visually
Bad news is I feel confident there will be several paths to the destination coordinate, and I'll likely need to identify them all manually
Worse news is I'm almost certain I won't be writing a programmatic algorithm for this puzzle

A reminder before rendering the area

The example is surprisingly not deceitful:

  0123456789
0 .#.####.##
1 .O#..#...#
2 #OOO.##...
3 ###O#.###.
4 .##OO#OO#.
5 ..##OOO.#.
6 #...##.###

It renders slightly more area than is needed
Because the shortest path from (1,1) to (7,4) visits coordinates below 4
In fact, I may need to render much more of the area beyond my destination coordinate in order to traverse the shortest path

Rendering the area

For destination (x,y)

Create an array y * 2 in length (to be safe)
  Each element is an array x * 2 in length (to be safe)
    Each value is either an open space or a wall depending on the results of evaluating the formula outlined in the instructions

This is my concise, eloquent JavaScript algorithm:

// using destination [x,y]
let office = new Array(y * 2)
  .fill(null)
  .map(
    (el, y) => new Array(x * 2)
      .fill(null)
      .map(
        (el, x) => [
          ...((x*x + 3*x + 2*x*y + y + y*y) + input)
            .toString(2)
            .matchAll(/1/g)
        ].length % 2 == 0 ? '.' : '#'
      )
  )
office[y][x] = "X"
console.log(office.map(row => row.join('')).join('\n'))

This was my first use of matchAll() and a regular expression to generate a count of a particular character in a string
I can't believe I never thought to do this
I usually split the string into an array, filter that array to one including only instances of the target character, then getting the length of that filtered array
Wow, seems so much more complicated than this new method!

With the destination marked as an X in the middle, I rendered this area: