A Regular Map
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-06-11 01:28:31

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

## Task: Solve for X where...
### Part 1
```
X = the fewest doors you can pass through to reach the room for which the shortest path from your starting location to that room would require passing through the most doors
```

## Example input
```
^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$
```
It represents:
- Directions to every room in the facility, from a start `^` to a finish `$`
- `()` denote branches in the path
- `|` denote each option within a branch

## Part 1
1. All of the emotions for this puzzle
2. What data structure could I use?
3. Could I create it for the first three examples?
4. Stumped: How would I even use this data structure to generate all possible paths?

### All of the emotions for this puzzle
- `Map` in the title generates intimidation at the need for a `shortest path` algorithm
- `Regular` in the title generates excitement and intimidation at the need for a `regular expression`
- Seeing several examples and their answers makes me excited to write an algorithm that works for at least the examples
- Reading the instructions makes me confident that I understand how the puzzle works and what I could manually do to solve it
- Seeing my puzzle input makes me quiver in fear, presuming I will not likely solve this puzzle

### What data structure could I use?
Example input:
```
^ENWWW(NEEE|SSE(EE|N))$
```

Paths:
```
ENWWW NEEE
ENWWW SSE EE
ENWWW SSE N
```

Levels:
```
0: ENWWW
1: NEEE - from level-0 has-no-sub-level
   SSE - from level-0 has-sub-level
2: EE - from level-1 path-2
   N - from level-1 path-2
```

Data structure possibilities:
```
{ 
  '0': [ 'ENWWW' ], 
  '1': [ 'NEEE', 'SSE' ], 
  '2': [ 'EE', 'N' ] 
}
```
Won't work because it doesn't tell me that both level-2 strings link to the second level-1 string

```
{ 
  '0': [ 'ENWWW' ], 
  '1': [ ['NEEE', 0], ['SSE', 0] ], 
  '2': [ ['EE', 1], ['N', 1] ] 
}
```
Might work, since I'm capturing the location of the string in the parent-level from which the string in the sub-level extends

```
['ENWWW', 
 ['NEEE', 
  'SSE', 
  ['EE', 
   'N']
 ]
]
```
May work, but seems tedious to connect and have to check for an array data type and the preceding value.

Also, crafting this object from single characters and a level tracker seems impossible because of its increasingly nested structure.

```
{
  'path': 'ENWWW',
  'children': [
    {
      'path': 'NEEE'
    },
    {
      'path': 'SSE',
      'children': [
        {
          'path': 'EE'
        },
        {
          'path': 'N'
        }
      ]
    }
  ]
}
```
May work, but crafting this object seems impossible because I would have to re-trace each nested 'children' and 'path' for each character.

### Could I create it for the first three examples?
I wrote an algorithm that successfully generated this data structure for the puzzle's second example:
```
^ENWWW(NEEE|SSE(EE|N))$
{ 
  '0': [ 'ENWWW' ], 
  '1': [ ['NEEE', 0], ['SSE', 0] ], 
  '2': [ ['EE', 1], ['N', 1] ] 
}
```

The algorithm generated this data structure for the third example:
```
^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$
{
  '0': [ [ 'ENNWSWW' ], [ 'SSSEEN' ], [ 'EE' ], [ 'NNN' ] ],
  '1': [
    [ 'NEWS', 0 ],
    [ '', 0 ],
    [ 'WNSE', 1 ],
    [ '', 1 ],
    [ 'SWEN', 2 ],
    [ '', 2 ]
  ]
}
```

And this data structure for the fourth example:
```
^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$
{
  '0': [ [ 'ESSWWN' ] ],
  '1': [ [ 'E', 0 ], [ 'NNENN', 0 ] ],
  '2': [ [ 'EESS', 1 ], [ 'SSS' ], [ 'WWWSSSSE', 1 ] ],
  '3': [ [ 'WNSE', 0 ], [ '', 0 ], [ 'SW', 2 ], [ 'NNNE', 2 ] ]
}
```

I was excited, until I noticed something I had overlooked:
```
EESS(WNSE|)SSS
```
I was incorrectly missing instances where, inside a branch, the portions before and after a branch needed to be connected.

I added a flag for this, but don't think it would ultimately help me:
```
{
  '0': [ [ 'ESSWWN' ] ],
  '1': [ [ 'E', 0 ], [ 'NNENN', 0, true ] ],
  '2': [ [ 'EESS', 1 ], [ 'SSS', 1, false ], [ 'WWWSSSSE', 1, true ] ],
  '3': [ [ 'WNSE', 0 ], [ '', 0, true ], [ 'SW', 2 ], [ 'NNNE', 2, true ] ]
}
```

### Stumped: How would I even use this data structure to generate all possible paths?
- As the examples got more intricate, I got more confused
- And my puzzle input is massively complex, making me void of confidence and ideas toward solving

While I might be able to carefully walk through the puzzle input and craft the map...that would take days.

I hereby give up on this puzzle.

That's tough to accept, especially given how little progress I made in attempting it.

## Celebrating my accomplishments
- I feel like I fully understood what the puzzle's rules
- I feel like I fully understood how the solution for each example was derived
- I feel like I explored a few viable - albeit impractical - data structures for the paths

Bummers:
- I didn't solve any parts
- I didn't describe or animate any algorithms
- I didn't make a simulator that would generate a map

I sense that I'll gain the fewest number of stars in 2018 as compared to 2019-2021, possibly of all the years.

These puzzles are just plain tough for me: highlighting each gap in my untrained skillset of computer science.

The good news: since I'm working backwards, I will likely finish the year with a few 2-gold-star achievements!

On to the next day!