DEV Community

Cover image for A Regular Map
Robert Mion
Robert Mion

Posted on

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
Enter fullscreen mode Exit fullscreen mode

Example input

^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$
Enter fullscreen mode Exit fullscreen mode

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))$
Enter fullscreen mode Exit fullscreen mode

Paths:

ENWWW NEEE
ENWWW SSE EE
ENWWW SSE N
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Data structure possibilities:

{ 
  '0': [ 'ENWWW' ], 
  '1': [ 'NEEE', 'SSE' ], 
  '2': [ 'EE', 'N' ] 
}
Enter fullscreen mode Exit fullscreen mode

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] ] 
}
Enter fullscreen mode Exit fullscreen mode

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']
 ]
]
Enter fullscreen mode Exit fullscreen mode

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'
        }
      ]
    }
  ]
}
Enter fullscreen mode Exit fullscreen mode

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] ] 
}
Enter fullscreen mode Exit fullscreen mode

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 ]
  ]
}
Enter fullscreen mode Exit fullscreen mode

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 ] ]
}
Enter fullscreen mode Exit fullscreen mode

I was excited, until I noticed something I had overlooked:

EESS(WNSE|)SSS
Enter fullscreen mode Exit fullscreen mode

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 ] ]
}
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)