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%

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%

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

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!

Finding the shortest path

This part was fun!

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.