DEV Community

Cover image for Grid Computing
Robert Mion
Robert Mion

Posted on

Grid Computing

Advent of Code 2016 Day 22

Part 1

  1. Short instructions and no unit test? Uh-oh.
  2. Making sense of all this
  3. Checking reddit too soon

Short instructions and no unit test? Uh-oh.

  • I'm not feeling very confident about this puzzle
  • Time to read the instructions and analyze my puzzle input very closely

Making sense of all this

  • The grid refers to a rectangular area of nodes
  • For my puzzle input, the grid's area is 35x25
  • The location each node is in its name, specifically the substring xN-yN where N is a positive integer
  • For my puzzle input, those parts are x0-34-y0-24
  • Adjacent nodes consist only of horizontal and vertical, not diagonal
  • The ultimate task seems to be transferring data between nodes

For Part 1, the task is to identify each pair of nodes (A,B) - not necessarily directly adjacent to one another - that satisfy three criteria:

  • Node A is not empty (its Used is not zero)
  • Nodes A and B are not the same node
  • The data on node A (its Used) would fit on node B (its Avail)

Used and Avail?
The first few lines of my puzzle input are:

Filesystem              Size  Used  Avail  Use%
/dev/grid/node-x0-y0     94T   65T    29T   69%
/dev/grid/node-x0-y1     88T   69T    19T   78%
Enter fullscreen mode Exit fullscreen mode

If those nodes were A and B:

  • Node A is not empty: check
  • Nodes A and B are not the same node: check
  • The data on node A (its Used) would fit on node B (its Avail): fail

Scanning my list...

  • Every node's Used appears to be greater than 60
  • Every node's Avail appears to be less than 30

But, there can't be 0 pair, right?

Starting at x21:

  • Each y11 has a Used greater than 400 and an Avail less than 20

Am I missing something, or are there no viable pair?

I search my puzzle input for a 0T as a wild guess.

One match:

                              Used  Avail
/dev/grid/node-x27-y14   90T    0T    90T    0%
Enter fullscreen mode Exit fullscreen mode

It can't be a coincidence that there's only one match.

I'm still confused as to whether:

  • I need to attempt to move data in Part 1
  • The single instance of a 0T Used and greater than 30 Avail means anything significant
  • I should proceed with writing any code, at least to extract each number related to each file

Checking reddit too soon

  • I wish I had let this challenge sink in a bit more before getting a hint from reddit
  • But, there's no going back now
  • Thankfully, there is going forward!

I confirmed that the single 0T node is extremely significant:

  • It's the only node that can move data!

Next, I hope to validate one solver's spoiler that:

  • Each viable pair will include that node

If that's the case, then the answer should be:

  Grid area: 25x35 = 
- 0T node: 1
- y11 nodes with huge Used values: 14
-----------
  860
Enter fullscreen mode Exit fullscreen mode

Awesome! That was the correct answer!

Part 2

  1. Hey, the example I was looking for!
  2. Rendering my puzzle input as a grid
  3. Finding the shortest path

Hey, the example I was looking for!

As happy as I am to see it, reddit spoiled the surprise:

  • It's a sliding tile puzzle!

I think I know enough about my puzzle input to just draw the grid.

Rendering my puzzle input as a grid

  • Based on the min-max numbers for each x,y coordinate in my node list, I know my grid is 35 tiles wide and 25 tiles tall
  • Based on the 14 nodes with Used amounts magnitudes larger than all others, I know where each wall is
  • And based on the 1 node with 0T Used, I know where the empty node is
  • The instructions specify the top-left and top-right corners as destination node and target node

With all that, I could render my grid!
Revealing the grid

Finding the shortest path

This part was fun!
Animating the journey to the destination

To my delight, that is the correct answer!

I did it (with help)!!

  • I solved both parts!
  • I cheated by reading some reddit comments, but that was to confirm an observation I had but didn't feel compelled to explore
  • I didn't actually write any algorithms!
  • I visually solved a shortest path puzzle!

The overly complicated language of the puzzle successfully hid the fact that it was - in essence - a sliding tiles puzzle.

I wish I could have seen that before resorting to reddit.

Regardless, once I had a direction, I felt confident in making an attempt - and eventually succeeding - at solving both parts!

The commenters referenced Day 15 as being a similarly-themed puzzle.

My noggin will be on high alert when that day comes.

Top comments (0)