Robert Mion

Posted on

# A Regular Map

## 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!