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!

Sentry blog image

How to reduce TTFB

In the past few years in the web dev world, we’ve seen a significant push towards rendering our websites on the server. Doing so is better for SEO and performs better on low-powered devices, but one thing we had to sacrifice is TTFB.

In this article, we’ll see how we can identify what makes our TTFB high so we can fix it.

Read more

Top comments (0)

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay