Grid Computing
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-08-15 13:50:09

## [Advent of Code 2016 Day 22](https://adventofcode.com/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!
![Revealing the grid](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/el6y39jgt09qgmaa7ps9.gif)

### Finding the shortest path
This part was fun!
![Animating the journey to the destination](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ztshg74vl0k00a2v1o50.gif)

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.