DEV Community

Cover image for A Maze of Twisty Little Cubicles
Robert Mion
Robert Mion

Posted on

A Maze of Twisty Little Cubicles

Advent of Code 2016 Day 13

Part 1

  1. Yeesh! Shortest path again?
  2. Feels like Day 24, but with a much smaller area
  3. A reminder before rendering the area
  4. Rendering the area
  5. 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 #...##.###
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

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'))
Enter fullscreen mode Exit fullscreen mode
  • 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:
My puzzle area

Finding the shortest path

It is the only path, really:
Shortest path illustrated

Part 2

  1. This seems familiar...
  2. Presenting: another elaborate GIF

This seems familiar...

How many locations (distinct x,y coordinates, including your starting location) can you reach in at most 50 steps?

Where have I seen this before?

Oh, yeah!

2019 Day 15: Oxygen System - Part 2

The task there was phrased as:

How many minutes will it take to fill the area with oxygen?

I solved it by hand-animating this 300+ frame GIF:
Similar puzzle theme

Thankfully, I'll only have to make a 50-frame GIF this time.

I'll use the alphabet again to track each step.

To track 50 steps, I'll use A-Z (26), then A-X (24).

This should be fun...?

Presenting: another elaborate GIF

Animating 50 steps

Is it the correct answer?

  • Yes! Woohoo!

I did it!!

  • I solved both parts!
  • Using visual methods, instead of programmatic algorithms!
  • I made another elaborate GIF akin to the one I made in 2019!
  • I'm 3/5 on shortest path puzzles this year!

Top comments (0)