DEV Community

Robert Mion
Robert Mion

Posted on

Proboscidea Volcanium

Advent of Code 2022 Day 16

Part 1

  1. Aiming for several small wins
  2. Using regex to parse the valve attributes
  3. Building the valve attribute data structure
  4. Trying my luck at building a search algorithm
  5. Building an boring simulator

Aiming for several small wins

  • This is another optimal path search-themed puzzle
  • I'm not very good at solving these algorithmically
  • The ones I have solved, I did so using my design tool or by building and using a simulator
  • I hope to build a simulator for Part 1
  • I don't think I'll have enough luck or patience using it to find the correct answer
  • That's ok, though. I'm excited to see how far I get.

The small wins:

  • Use regex to extract the important bits from each line
  • Build a data structure that maps valves, flow rates and interconnected tunnels
  • Brainstorm a search algorithm that navigates the tunnels and turns on valves
  • Build a simulator that lets users navigate the tunnels and turn on valves via buttons across 30 turns

Using regex to parse the valve attributes

For a line like this:

Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Enter fullscreen mode Exit fullscreen mode

I need these parts:

AA
0
DD
II
BB
Enter fullscreen mode Exit fullscreen mode

Those happen to be one of the following:

  • Pairs of all capital letters
  • Digit(s)

Thus, my regular expression should match either two capital letters or one or more digits:

/[A-Z]{2}|\d+/g
Enter fullscreen mode Exit fullscreen mode

Small win: acquired!

Building the valve attribute data structure

For the first line, again:

Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Enter fullscreen mode Exit fullscreen mode

I'd like something similar to this:

{
  'AA': {
    'open': false,
    'rate': 0,
    'valves': ['DD','II','BB']
  }
}
Enter fullscreen mode Exit fullscreen mode

Should be easy enough to make that from my regex above.

Small win: acquired!

Trying my luck at building a search algorithm

  • I got ambitious
  • I figured I'd try to write a recursive function that enacted all valve pathways possible in 30 iterations

Here's how that went.

The function expects four parameters:

  1. The valve I'm at
  2. The amount of pressure released thus far from all open valves across all minutes passed
  3. The list of open valves
  4. The number of minutes that have passed

Each time the function is called:

  • If the number of minutes passed is 30 and pressure is greater than a globally-stored maximum value, update that valve with pressure and display it in the console

Otherwise, for each of the valves' connected to valve I'm at:

  • If the valve I'm at has a flow rate of 0: call the function to simulate a move to that valve, incrementing the minutes by 1
  • If the valve I'm at has a flow rate above 0 and is in the list of opened valves: call the function to simulate a move to that valve, incrementing the minutes by 1
  • If the valve I'm at has a flow rate above 0 and is not in the list of opened valves: call the function to simulate opening this valve, adding it to the list of open valves and incrementing the minutes by 1

I call the function with the four arguments set as:

  1. AA
  2. 0
  3. []
  4. 0

Then I let it run for...a while.

Eventually, I see this in my console:

EE 1395 [ 'DD', 'CC', 'BB', 'JJ', 'EE', 'HH' ] 30
Enter fullscreen mode Exit fullscreen mode

That means:

  • The max pressure it encountered was 1395, short of the expected 1651
  • It is still exploring nodes in the tree where the valves were opened in order DD -> CC -> BB; not the optimized order DD -> BB -> JJ
  • In summary, it is working...just not quite how I need it to

Good news:

  • Writing all of this out helped me identify a few gaps in my conditions

Fork in the road:

  • Do I continue troubleshooting my algorithm?
  • Or switch to building the hopefully more fun simulator?

Building an boring simulator

  • I wasn't planning for it to be boring

But, after:

  • Doing a bunch of direct DOM manipulation
  • Fixing silly mistakes in my code
  • Successfully re-creating the 30 minutes depicted in the example

I confirmed that my simulator works.

And is not fun to use.

Still...

Small win: acquired!

Moving on without earning any stars

  • I'm proud of my small wins
  • I'm proud that I attempted to write a recursive search algorithm
  • I'm proud that I built a working simulator

Even though I assumed I wouldn't identify the correct answer for Part 1, I'm still bummed that I didn't prove myself wrong.

Hopefully I'll feel more capable solving tomorrow's puzzle.

Top comments (0)