https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 24> :thread:
# advent-of-code
a
s
Can we pass through a blizzard, e.g. if it faces us directly and we move towards each other? Logic says now, but we don't occupy the same space at any point, we just swap places, so according to the problem statement I'd suppose we can.
j
@Sergei Petunin I assumed I could and my solution was accepted
my thinking was: I'm just gonna try, and if I don't get the expected answer that's probably going to be the mistake.
j
@Sergei Petunin I also used the concept of "is a given position free at given time" completely ignoring the direction from which I'm coming
m
Can you wait, allowing a blizzard to move to your positon?
j
I think not. I.e. you should never be at the same position with the blizzard so if some is coming, you need to move.
v
Is there any chances that in part 2 quickest path to destination will not give the quickest path backward, or am I overthinking?
j
@Vlad Petrushkevich hint:
In the above example, the first trip to the goal takes 
18
minutes, the trip back to the start takes 
23
minutes, and the trip back to the goal again takes 
13
minutes
m
Thanks, that was the issue I was having… I was allowing wait moves that result in a blizzard coming over.
j
I did BFS on priority queue trimming paths when were on same position lcm(rows,cols) rounds ago, it worked, but took about 15 seconds, so obviously it’s not the best approach
also my lcm today 😆
Copy code
val lcm = with(rows.count() to cols.count()) {
        when (this) {
            (4 to 6) -> 12 // test input
            (25 to 120) -> 600 // real input
            else -> TODO(this.toString())
        }
    }
m
@Jakub Gwóźdź I did the same trimming, but without a priority queue, just plain BFS, and mine takes 2-3 seconds.
j
Oh, good to hear that, I'll test it later 🙂
j
I suspect the overhead for pruning/prioritizing is not worth it for this problem. The worst case is, that every position without a blizzard is being explored in the BFS step.
without pruning my code runs in ~300ms for part 2 on real input.
j
c
God bless A*
e
Just a regular BFS (or forward DP, whatever you name it) works really fast here.
b
does A* still work while allowing back tracking/visited?
c
you have to set the state space you're searching over to include whether or not you have snacks
j
somehow my bfs with priority (manhattan distance to goal) does the right thing for example but not for real input (to small). Also used the cycle trick with lcm (real implementation of inner height, width)
b
@Cognitive Gear technically even going one direction, the answer could have involved backtracking, right?
c
no because the storm state changes
b
the example shows backtracking, although its so early on I don’t think it needed to
e
There are at most 
O(n*m)
states at each time. So if you explore a states forward in time, it works in 
O(n*m*answer)
j
hm I did miss that we could wait too, but that gave a too high answer 😞
s
The second part was a breeze with a proper implementation of the first one 🙂 I spent a lot of time on two conceptual mistakes: 1) I memoized the whole blizzard state instead of just the 
step % lcm(width - 2, height - 2)
, and 2) used DFS instead of BFS.
j
with up-to-lcm states memoization (which could be improved, but who cares, it’s only done once), the part2 time is now around 0.5 seconds, which is good enough for today. advent-of-code-2022/Day24.kt at main · jakubgwozdz/advent-of-code-2022 (github.com)
e
65ms/180ms on my thinkpad, 35ms/96ms on my M1
A*, also I discovered that you don't actually need to build any sets of spaces or blizzards
c
I used both memoization and Math.floorMod and the later was slower 🤷
o
This one was nice again, not too easy, but also not too complicated! Merry X-mas!
k
@Jonathan Kolberg did you find the issue? (I guess I have same problem)
p
Another BFS puzzle solution. Fun, nonetheless. https://github.com/tke/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day24.kt I especially liked how my part2 ended up just being
Copy code
fun part2() = solve { entrance travelTo exit travelTo entrance travelTo exit }
I modelled the blizzards as 4 distinct 
BooleanArray
indexed by 
x, y, t
where 
t
determines a positive or negative offset in either 
x
or 
y
based on the direction of the blizzards.
j
@kqr nope could not find it, rewrote the code multiple times, ended up using a code from someone else, will look into it in a few days again
t
That was fun, despite having to risk my life to retrieve forgotten snacks. I used a breadth-first search and enjoyed the extra challenge that the ever-changing landscape presented. • Blog • Code
k
@Jonathan Kolberg my problem was that my priority queue take only manhattan distance into account without time elapsed
j
@kqr I switched away from a priority queue that also solved it.
p
Finally found some time to tackle this. My part 2 takes about 20 seconds. Has someone an idea how to speed this up? https://github.com/PaulWoitaschek/AdventOfCode/blob/main/src/main/kotlin/de/woitaschek/aoc/year2022/Day24.kt
j
@Paul Woitaschek I think you overcomplicated the Journey class, part2 in it’s worst case should be part1(start to end) + part1(end to start) + part1(start to end) with starting minute of each next trip equal to ending minute of previous trip. No need to keep search state between the trips, they are independent. Also if you were at some point 600 minutes earlier (lcm(width, height)), you can safely trim this branch of search.
p
But what of the description says that you don't need to go backwards as there might be a faster path if you did?
j
description says only
From the same initial conditions, how quickly can you make it from the start to the goal, then back to the start, then back to the goal?
o
How could there be a faster path to get to the destination if the one you found is guaranteed to be the fastest?!?
j
The third trip starts from different minute = different positions of the blizzards, if that's what you're asking
o
I am not asking, Jakub. 🤣 I am trying to tell Paul that there is no need to keep state just like you did.
Unfortunately it's impossible to answer to a post here....
r
As a blizzard reaches the wall of the valley, a new blizzard forms on the opposite side of the valley moving in the same direction.
What happens when a blizzard reaches the Start and End position.
Copy code
#^#####
#.....#
#.....#
#.....#
#.....#
#.....#
#####v#
p
I believe start/end are assumed walls for the sake of the blizzards
j
@ritesh I believe it never happens for the given inputs
p
beat me to it 🙂 It’s not something I’ve seen occur in the examples or inputs I’ve seen.
26 Views
Open in Slack
PreviousNext
Powered by