https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 16> :thread:
# advent-of-code
a
j
Oh man today I'm struggeling, my guess is for part1 some kind of dynamic programming should do the trick
d
Finally got part 1
I just used DFS with pruning
I pruned any path that had a move loop, and any path that couldn’t get a better score if it were able to open the remaining valves in most flow order on each subsequent turn
My code is super ugly
part 2 is… yikes
b
wow, all it took for me was filtering immediate move backwards. thanks for that hint!
s
I don’t understand if my algorithm is flawed or there’s just some coding error, but I keep getting a way lower value than in the example. On each recursive step, I try to find the maximum of the following: - if we stay in the current node for the rest of the iterations (
currentSum + totalOpened * stepsLeft
); - if we open the current valve and walk down the unvisited neighbors, reducing the step count by 2; - if we don’t open the current valve and go through unvisited neighbors, reducing the step count by 1.
n
I'm currently think along the following lines: 1. compute the flow of all valves open for 30 min as upper limit 2. model every valve as 2 nodes, one for open and one for closed 3. build a directed graph, never allowing to go from e.g DO to DC 4. the weight of each link is the sum of all valves for 1 min - the gain of opening (this part is still fuzzy) 5. use dijksta to find the shortest path Still not sure that leads anywhere, but everything else failed so far...
b
@Sergei Petunin you’ll have to go through the same node more than once
d
I have some bug in part 2, gonna stop soon
s
@babel indeed, I just realized that you could go to some distant part of the graph to open a valve with large flow and then return to open some lower-flow valves. But then you have to allow loops, you can't prune them.
a
yikes, this one was tough. I ended up finishing both parts in just under 3 hours. Stupid bug in part B took me ages to track down, plus time spent on optimisations... I still ended up running with 
Xmx
of 20GB and a hardcoded fudge to get B to complete 😅
k
I'm thinking of using Dijkstra, but starting from minimum pressure valves towards the beginning.
j
I solved part2 by brute force (using par1) ... it runs for 200s which is quite long, but not sure if I want to optimize it more since it yields the result 🤷‍♂️
t
Finally found my bug in part 2. I am using the a star algorithm (already in my repo 😄 ). But I could not determine why it failed. I had to visualize the graph in dot and trace the path it took to get to the bug: The pressure release right at the end was not in a star cost, but adjusted afterwards. It thus failed to open any valves right at the end 🙈. Part 2 runs in ~40-60s
s
I now try to filter out the looped paths by storing the additional 
Node.visitedNeighbors
set, but I still get 1649 instead of 1651 on the test data, and for the actual data it just never completes
d
i got it working on the test input but not the real input
j
@Sergei Petunin your algorithm looks to be on the right track but instead of tracking visited neighbors to filter out loops, consider making bigger steps and think whether you really need to try to move in every direction from a node or just towards some unopened valve.
s
Do you mean for the current node calculate shortest paths to all remaining unopened valves and only take the steps that lead along those paths?
j
or just jump straight there (you know the distance)
s
Okay, thanks, I'll try. But from the first glance, it seems that adding shortest path calculations on top of what's already there would only increase the running time...
d
argh that seems to be the key insight i didn’t have 5.5 hours ago
j
you trade "wave algorithm (truncated with max length)" (which is quadratic in node count) for having to explore all neighbors one by one (exponential)
d
compress the paths from weight 1 with no-valve nodes
to weight N with only valve nodes
i.e. for each valve node just precompute shortest path to each other valve node
p
Done with part 1 🙂 https://github.com/PaulWoitaschek/AdventOfCode/blob/main/src/main/kotlin/de/woitaschek/aoc/year2022/Day16.kt Runs in about 300ms. The core thing here was to compute the distances from points to points first and then only thinking in terms of: Where do I want to release steam next?
c
I am stumped on calculating the total pressure. Nothing one the sample provides the given answer. Am I being stupid? Adding pressure of open values together for the total period is more than the given answer.
p
@corneil Do you account the minute at which you opened it?
c
If you add all the values in the sample together it is more than 1651. The is pressure at the time added together.
p
Nope, it’s not. 20*3+33*4+54*8+76*4+79*3+81*6=1651
But in my first manual sum, I mistook 76 for 79 ^^
c
What a pain. I'm missing a key insight, because even with all the optim I can think of (memoization, graph reduction), Part 2 still takes a couple of minutes to finish.
j
I've used the same technique I described above and even with bruteforce my part2 finished in ca 200s (on old i5-750). Then I realized I was stupid and instead of calculating paths to remaining open valves every time I visited a node (using wave) I could do graph-reduction upfront (i.e. leave just valves and "AA" and turn it into oriented graph towards valves) which reduced the runtime to 26s. @Cognitive Gear if your solution really takes minutes to finish then perhaps you're not reducing the graph well.
s
I did part 1 by jumping through the simplified graph, and it's pretty quick, but now it looks like I can't easily use this solution for part 2 https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/year2022/Day16.kt
e
finally got a working solution in Haskell; now time to do it again in Kotlin…
j
@Sergei Petunin if it's really quick then of course you can
s
@Jan Durovec it's recursively jumping to the next closed valve, and the jump distance is different every time. Since we now have two pointers instead of one, and they have to jump different distances, it looks like I have to deoptimize and walk step-by-step instead of jumping
j
that's true but I used it in a way that I split responsibilities. I.e. I knew I'll be opening valves ABC and elephant valves DEF and then summed the pressures to close valves in a given set using part1 algo
so you can but maybe not the way you wanted 😉
s
But how do you split the valves, do you just generate all possible splits between you and the elephant?
j
yes.. how many valves do you have? I have 15 so it is "just" (2^14 - 1) possible combinations which is cca 16k. So if your part1 is really fast you should get a result reasonably soon (under half a minute?).
c
Any hints for part 1? I’ve got as far as having a Valve class and have pre-computed the shortest path to each other Valve so i’ve got a graph I can traverse. But in terms of the algorithm for what to do I’m drawing a bit of a blank.
j
@Charles Flynn if you simplified the graph and reduced it to just valves with pre-compted distances to each other, then a dumb backtrack (DFS) should be good enough
c
Searching for what though?
j
calculating max of released pressure by opening them in a specific order
c
So some sort of recursive DFS and just take the highest result I can get?
j
yes, that's the task. To figure our the max of what you can release
I.e. you start with 30 mins left and no released pressure. You can decide to go to some valve and open it (adding remaining minutes * flow to total released pressure) and then recursively try to find the max of where you can go from there with the time you have left.
c
Cheers. Think i’ve got a good idea of what I want to try 🙂
Time for some food and back to this in a bit 🙂
s
@Jan Durovec indeed, second part was just 1,5 minutes. Thanks for nudging me in the right direction!
r
👋 I am kinda stuck here (with my current approach, where i wast doing dfs in order of max flow rates), went through previous threads, and i am thinking get the shortest path from each node to other node using djk and then traverse using dfs in the order of max flow rate of valve, until all/maximium valves are opened in the time period of 30 mints.
s
Probably not in the order of max flow. Imagine you have a smaller flow valve on the path to the larger one, then it makes sense to grab the smaller one first and then go for the larger one.
r
Ahh yes, that makes sense. Thanks
I was confused after looking at the example, where it first visit the shortest but max value which is 
AA->DD(20)
, from DD, next shortest and max-value is 
BB (13)
- in this case, it goes via 
CC
but doesn't grab/opens 
CC
valve along the way.
e
https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day16.kt there we go. a bit of a mess - it's a bit too generic, in that it potentially handle up to 31 of elephants - but it works
could be better, could be worse
Copy code
Benchmark         Mode  Cnt    Score    Error  Units
Day16Bench.part1  avgt    5   13.433 ±  1.347  ms/op
Day16Bench.part2  avgt    5  379.480 ± 75.804  ms/op
p
Finally got part 2 right. It takes 8 seconds though. Has someone suggestions how to speed it up? https://github.com/PaulWoitaschek/AdventOfCode/blob/main/src/main/kotlin/de/woitaschek/aoc/year2022/Day16.kt
j
My solution for part2 tries to build all graphs that get build by partiting between you and elephant to open and use part1, does that work?
p
https://github.com/PaulWoitaschek/AdventOfCode/blob/e6c556fe2a36e42acdd5112e44b5cbddf432ff76/src/main/kotlin/de/woitaschek/aoc/year2022/Day16.kt#L29 This was the kind of long hanging optimization that took me down from from 14s to 8s. The main idea was that I can do an early exit if I assume that from now on I the optimal nodes are directly nearby. If the score for these nodes is lower than my current maximum, I can skip
j
Answer to myself yes, but it need a few seconds
p
If I go with a 
availableMinutes - minute-8
it passes the test and is down to 600 ms but I think it’s only right for my input ^^
e
my optimizations: • use Floyd-Warshall to precompute all the distances so we can jump directly between non-zero valves instead of stepping one by one ◦ I did this a bit overkill; I computed all distances even though we only need distances among origin and the valves. but it's not that significant relative to the rest of the search • use A* search with heuristic "total pressure relieved by end of time from this state" (this is allowed to underestimate, not overestimate… a bit reverse from the usual A*, but that's because we're searching for the max, not the min) • additional cut-off for "if we could magically open every valve (counting travel distance from current point, but not between them, to keep it cheap), and the total pressure relieved by the end of time cannot beat the best heuristic seen so far, don't bother continuing to search" (this is allowed to overestimate, but not underestimate) additionally for part 2: • model the current position as a "set" of room+age (it's more like a multiset since we start with 2x the same entry, but anyhow) ◦ e.g. [AA, AA]@t=0 → [??, DD]@t=2 → [JJ, ??]@t=3 is modeled as [AA-0, AA-0] → [AA-2, DD-0] → [JJ-0, DD-1] ◦ symmetric between human vs elephant; doesn't care what the intermediate steps are, can step in sync or out of sync so time progress is always forwards
j
My solution. For part1 I had a look at @Sergei Petunin algorithm https://github.com/bulldog98/advent-of-code-2022/blob/main/advent2022/src/main/kotlin/Day16.kt
d
It uses path compression. For part 2, I DFS the self moves first, with an option to go to the back to start and wait for the elephant, then DFS the elephant part, also with an option to go back to the start to wait. This uses the A* approach of applying a heuristic to bail early if it’s not possible to beat the max score if you opened all the remaining valves ordered by most flow in subsequent turns.
part 2 takes like 10 seconds or so
m
What a brilliant decoy - valves that cannot be opened. I ignored those and implemented Dijkstra for finding the quickest paths (distances) between the actual valves. Much faster and simpler. And I am caching the calculation for part 2.
r
My sum is not coming accurate , i think i messed up my logic some-where. My algo looks like this • Keep flow rate in increasing order -> 22, 21... • Move from "AA" to the flow rate valves in same order (22,21) (shortest distance) -> also close valves which are in the path. Change source "AA" to other source when one path is complete (like for 22) • Repeat until u time out I think i messed up somewhere.
d
I refactored my solver to be general for N agents
The are lots of subtle ways to have bugs in the algorithm
r
Yeah, my code is pretty ugly though, debugging is a mess as well!
j
@ritesh It's not garanteed that moving to the higest one first is a good idea. If you can in 1 move get to the second highest and in an additional 1 to the third highest, while getting to the highest takes 4 moves it's better to go with the second and third highest
sometimes it's even better to skip one, since in the next room the valve will be way better
r
Yeah, i realised it, after few failed attempts. I wasn't thinking straight. I will give it a try again, later today. Thanks @Jonathan Kolberg
j
I brute forced both parts, part 2 took like 90 minutes on all cores in m1 macbook pro
I figured this was stupid but refused to look at hints
I have to think about how A* is possible with this
Computing all possible splits between me and elephant and running part 1 on that would take about 1.5 hours as well if I calculate things right
This was by far the toughest for me, the amount of code was just bigger as well
n
My final solution was to compute the powerset of the set of valves with flow (15 for my input), and then find the max of the sum of solving for a set and it's inverse. Not the most efficient, but simple to code and understand. See https://github.com/nkiesel/AdventOfCode_2022/blob/main/src/test/kotlin/Day16.kt for details
that takes less than 1 minute on a fairly old laptop
m
Finally I have a bit of breathing space to tackle the puzzles I missed. I coded this one using a simple bruteforce style recursive function with memoised state stored in a HashMap keyed by a State data object. This works perfectly and reasonably quickly but predictably once there is an elephant in the room it blows out the memory with the puzzle input (test data is fine). So this morning I thought to myself, I don’t need to write a hashing function for the state, I can use the 
hashcode()
of the data object and simply store that instead of the state object and then I can make a mutable state object, only one, and just memoize by hashcode. Low hanging improvement which will prevent it allocating objects so much. However… If I simply keep everything as is and only replace the key in the HashMap with the hashcode of the State, it gets the wrong answer on the test input, The answer is bigger 🤯 Can anyone explain this to me?
r
Oh man, this is still in unsolved state for me. I am going to give to try again today - i realised today it's more like a Travelling SalesPerson Problem hitting all nodes leading to max pressure - some kind of DP with Dijsktra/BFS/DFS should do the trick i think.
e
maia, sounds like a hash collision
m
ok hmm I will need to rework it ...
thanks I'll do a bit of research. it's def safer to code up a way to represent the state uniquely then
r
Ahh.. this was tough one for me. Finally, done with part 1.
25 Views
Open in Slack
PreviousNext
Powered by