Advent of Code 2022 Day 16
Part 1
- Aiming for several small wins
- Using
regex
to parse the valve attributes - Building the valve attribute data structure
- Trying my luck at building a search algorithm
- 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
I need these parts:
AA
0
DD
II
BB
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
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
I'd like something similar to this:
{
'AA': {
'open': false,
'rate': 0,
'valves': ['DD','II','BB']
}
}
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:
- The valve I'm at
- The amount of pressure released thus far from all open valves across all minutes passed
- The list of open valves
- 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:
AA
0
[]
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
That means:
- The max pressure it encountered was
1395
, short of the expected1651
- 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)