A Regular Map

Advent of Code 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!