Electromagnetic Moat
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-07-16 10:12:05

## [Advent of Code 2017 Day 24](https://adventofcode.com/2017/day/24)

## Part 1
1. Recognizing the task
2. Understanding the language of the puzzle
3. Analyzing the example input
4. Imagining an algorithm based on the example breakdown
5. First attempt: flat-out failure
6. Second attempt: shocking success!

### Recognizing the task
Abstractly, the task is to:
> Build a bridge out of the magnetic components strewn about nearby

The initial task is to:
Solve for `X` such that `X = `...
> the strength of the strongest bridge I can make with the components I have available

### Understanding the language of the puzzle
- A bridge is formed using components
- Each component is comprised of two ports
- Each port is identified by the number of pins it uses
- Components can only connect thru identically-numbered port ends
- Components can connect to either end of the component...not just left-to-right or right-to-left ends as depicted in the input
- The higher the port number, the stronger the bridge
- The first component must feature one zero-pin port
- It doesn't matter how many pins are in the ending port

### Analyzing the example input
The example puzzle input:
```
0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10
```
- It is a list of components
- Each one designating the pins in each of its two ports
- There are only a few components that could act as the first one
- There is one component whose ports have the same number of pins

### Imagining an algorithm based on the example breakdown
The list of bridges is depicted as:
```
0/1
0/1--10/1
0/1--10/1--9/10
0/2
0/2--2/3
0/2--2/3--3/4
0/2--2/3--3/5
0/2--2/2
0/2--2/2--2/3
0/2--2/2--2/3--3/4
0/2--2/2--2/3--3/5
```
If manipulated, it would resemble a tree, with two root nodes:
```
0/1
  10/1
    9/10
0/2
  2/3
    3/4
    3/5
  2/2
    2/3
      3/4
      3/5
```

Interesting. How might I re-create this data structure?

Likely using:
- Recursion
- Ordered lists where each item is a unique two element list
- Maybe `flatMap()` to generate sub-lists and eventually combine them into a flattened array?

This animation illustrates one approach:
![My proposed algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5r9ru3lyudervo11hb0z.gif)

This task seems doable.

I need to carefully consider how my algorithm and initial data structure should work.

### First attempt: flat-out failure
I tried re-creating the first and second steps of the example input:
1. Find all zero-pin port-containing components
2. Find each next possible set of components

Step 1 was easy:
- Filter the list of components to only the ones including a 0

Step 2 tripped me up:
- My filter was only finding one of the two remaining two-pin port components

I had no idea what I was doing wrong.

Time to step away, think on things, and return later.

### Second attempt: shocking success!
- My original GIF implies that I need to ultimately compare and merge leaf-node arrays all the way back up the tree to the root nodes
- That seemed tricky...like it was going to require a lot of extra code and headache

While walking my dog, I had a realization:
- Once I get to a leaf node, I know I've found the last possible component for the current bridge
- As long as I've been accumulating all prior components up to that point, I can calculate the strength of that bridge in the base case of the leaf node
- If the strength is greater than the current value stored in strength (updated in one of the other many recursive calls), update strength to the new greatest value
- At the end, return the current value in strength, which should reflect the strongest bridge

My recursive algorithm works like this:
![Animation of my working algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oazp11kr89ajulouol2a.gif)

What I saw as my algorithm ran Part 1:
![My console output for Part 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ng18pbugkfbyudm848jc.png)

## Part 2
1. Recognizing the new task
2. Part 1, but with a more complex comparison

### Recognizing the new task
Solve for `X` such that `X = `...
> the strength of the longest bridge I can make with the components I have available

### Part 1, but with a more complex comparison
- In Part 1, I tracked and compared only a strength
- Now, I need to track and compare a length and a strength

```
If at a leaf node
  If the length of the accumulated bridge components is greater than the current winner
    Update the winner to reflect this bridge's length and strength
  Else, if the lengths of the current winner and this bridge are equal
    Update the winner to reflect the length and strength of the stronger bridge
```

What I saw as my algorithm ran Part 2:
![My console output for Part 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f9ztgvux3q7qaackp1uf.jpg)

## I did it!!
- I solved both parts!...
- ...of a recursive algorithm puzzle!
- I got two gold stars for the second time on a Day 24!
- I made two GIFs: one depicting my initial, naive algorithm, and another outlining my refined, working algorithm

Any time I solve both parts of a puzzle after Day 15 calls for celebration!