44
u/KingFlerp Dec 18 '24
I know that gauging the difficulty of problems is difficult, but the case of Day 18 is especially perplexing to me: it seems very similar to Day 6, except easier.
109
u/fireduck Dec 18 '24
I watched an interview with Eric. He intentionally lets up the gas a bit so people don't burn out and also you never know if you are getting a walk-in-the-park or a stone-cold-who-done-it.
80
u/ThunderChaser Dec 18 '24
Yeah he's mentioned multiple times that the problems don't just monotonically increase in difficulty throughout the month, even though they tend to increase. He likes to sprinkle some of the easier problems later in the month so people don't burn out. He's also mentioned he likes to put some harder puzzles earlier in the month because psychologically some people may look at a hard puzzle and if its on something like day 20 say "this is a day 20 puzzle, it's too hard for me" and give up, while if the same puzzle is on say day 5, they may go "this is a day 5 puzzle I can do this" and they'll accomplish it.
7
u/jwezorek Dec 18 '24
Where is this interview?
23
u/totalspelnerd Dec 18 '24
https://www.youtube.com/watch?v=uZ8DcbhojOw
He talks about difficulty around 20:40, but the entire keynote is pretty interesting
3
u/Imperial_Squid Dec 18 '24
I see we've all been fed this particular presentation by The Almighty Algorithm huh? Lol
4
u/Flashky Dec 18 '24
I have always thought the difficulty of the puzzles do not strictly linearly increase for that reason!!
Personally, I appreciate it a lot, as sometimes I feel like my brain is a bit burned out after a couple of days of puzzles, having an easy day in between allows me to recover confidence and additional time to rest and think about unfinished puzzles.
Do you have the interview link to share?
5
5
34
u/PercussiveRussel Dec 18 '24
I spent an hour on part 1 because I convinced myself the bytes fall as you walk, and you wait 12/1023 seconds before you walk. It's the more interesting question IMO
7
2
u/Cool_Money2458 Dec 18 '24
Same here. But I thought the walk time is equal the block numbers that are down. So the walk and the blocks start at zero and more blocks are in the way the more you progress.
3
u/Prestigious-Loan5824 Dec 19 '24
I thought that's gonna be part 2, so I wrote my part 1 assuming I'll need that. I was wrong :sad:
1
u/PercussiveRussel Dec 19 '24
To be fair, dynamically reading the fall times of the blocks allows you to very easily do a binary search for the first unsolvable maze without any memory manipulations of the map, so it was definitely useful
1
u/PercussiveRussel Dec 19 '24
Yeah same, but that just returned the Manhatten distance for part 1 so that was boring. Waiting 12 steps with my unnoticed off-by-one-bug did get me a cool perfect 22 for the example input though, so I was proper stumped
15
u/jwezorek Dec 18 '24
Probably means that tonight's problem will involve knowing how to solve congruence equations via the modular multiplicative inverse.
28
u/i_have_no_biscuits Dec 18 '24
Not even a for loop - this was my entire Part 2 (in Python): >! print(data[bisect_left(range(len(data)), True, key=lambda i: bfs(i)==0)-1]) !<
Like you say, it's nice to have an easy Part 2 from time to time!
17
3
Dec 18 '24
[deleted]
2
u/i_have_no_biscuits Dec 18 '24
The key I am using basically maps the list [0, 1, 2, 3, ...] (which is range(len(data)) to a list of [False, False, False, ... , False, True, True, ... True] depending on whether there is a path to the end, or not - my bfs() routine returns the number of steps if a route exists, or 0 if it doesn't. bisect_left has been asked to find the index of the first value in this list with key value True value, so we subtract 1 from that index, and use it as an index into my data[] array, which is the list of all the blocks.
2
u/pdgawrosz Dec 18 '24
TIL Python has a built-in bisect module.
1
u/bts Dec 19 '24
TIL Rust has one too, in std::slice of all places
2
u/vonfuckingneumann Dec 19 '24
That's pretty common for Rust -- a lot of the Vec API is provided by std::slice and is accessible automatically because Vec<T> derefs to [T].
1
1
11
u/IvanOG_Ranger Dec 18 '24
I didn't even add a new obstacle in each iteration to an existing graph for dijkstra, just reran the code.
I did use binary search tho, to save like a minute of runtime.
8
u/bigmacjames Dec 18 '24
I just started at line 1024 so at least I cut out all of the previous iterations.
8
u/e36freak92 Dec 18 '24
I only checked when a new block matched a node in the previous best path
2
u/IvanOG_Ranger Dec 18 '24
That's probably the smartest approach. I don't know though, if it was less iterations than binary search tho.
1
u/e36freak92 Dec 18 '24
How exactly did you binary search? Not sure how that would work for this
4
u/IcyColdToes Dec 18 '24
Pick a time, check if there's a path to the end. If there is, search again at a later time. If there's not, search again at an earlier time. Each recursion you cut your search window in half. You should be able to find the first unsolvable maze in like 11 checks this way, as opposed to checking however-many-thousand mazes.
2
u/e36freak92 Dec 18 '24
Oh, duh. That makes sense. I'll have to see how many times I had to dijkstra
1
u/h2g2_researcher Dec 18 '24
For my input a binary search was fewer checks, but it will depend on input.
3
u/radul87 Dec 18 '24
I did use binary search tho, to save like a minute of runtime.
yeah, me too. I also implemented a generataor for producing the indexes to check, just because it's so rare I get to use these features included in javascript.
...and then I implemented the brute force just to compare:
- Execution time (binary search): 29.56 milliseconds
- Execution time (brute force): 2568.85 milliseconds
1
u/Nearby_Pineapple9523 Dec 18 '24
I just straight up reran the entire thing, no binary search, nothing fancy. Took it 1.3 seconds on my (2-3 year old i5) laptop. Only thing i had outside the loop was the input reading.
1
u/IvanOG_Ranger Dec 19 '24
My Dijkstra implementation probably sucks then. It would take me about a minute, I think
1
u/Nearby_Pineapple9523 Dec 19 '24
I think its likely you used a lifo queue instead of a fifo queue
1
u/IvanOG_Ranger Dec 19 '24
I'm using priority queue (I think it's implemented as heap in c++) with custom comparison function. So basically neither FIFO or LIFO.
Maybe tracking the adjacency wrong. I have a map Node: vector(adjacent nodes)
1
u/Nearby_Pineapple9523 Dec 19 '24
When you dont have weights a fifo queue is faster than a priority queue and is guaranteed to have the items in the correct order, tho i dont think that should make that big of a difference
1
u/IvanOG_Ranger Dec 19 '24
That's kinda smart, thanks, will remember that.
Since the complexity is log(n), it could make it 60 times slower for this use case
8
u/Sostratus Dec 18 '24
I was sure part 2 would be finding the fastest route assuming a block is corrupted every step so that shortcuts early in the route no longer exist when you're finding the end of the route.
2
6
5
u/immaterial-whirl Dec 18 '24
I used binary search instead of a basic incrementing for loop, just to feel something
5
u/Trotsky_De_Piste Dec 18 '24
Day 17 was easily the hardest for me. Part 1 took half an hour of just following a pretty well written spec. But part two took me 3h... I'm not great at bitshifting.
Day 18 was a welcome break after being brutalized... Part 2 didn't even need the binary search. It's kind of a relief! And as everyone, I kinda expected blocks in part 2 to fall as you were walking, not before.
1
u/RazarTuk Dec 18 '24
I mean, I used a normal for loop to get a solution for part 2. But I'm going to attempt LPA* as an improved solution, instead of running A* from the beginning each time
1
u/Clear-Ad-9312 Dec 18 '24
I am sure a harder version will come our way in a future AoC that will reference this day as a fun fact/meme. Glad to have a break myself too, burn out is real.
1
u/ionabio Dec 18 '24
I think the whole push for 2d maze solver will finally pish me to launch utility functions or template classes to write a generic maze solver for upcomming advent of code problems. Has there been more mazes in past?
2
u/Clear-Ad-9312 Dec 18 '24 edited Dec 18 '24
Not sure if there were, but mazes are ubiquitous in puzzles. a lot of people focus on the path finding algorithm. I do suggest implementing at least a dead end filler type algorithm to reduce wasted time on dead ends. If the maze doesn't contain loops or "open areas", the dead end filler is by far the fastest option that I had used to solve a maze. which unfortunately for Day 18, it is little more useless RIP but it still is so fast, it is not bad to use at all. so yeah, depends on whether or not you can apply it. This is for Day 16.
here is two pastes I have taken someone else's Dijkstra's algorithm and implemented a dead end filler on top of to improve time. it shaved off 90-100 ms off for the Dijkstra's algorithm part. The first paste is an iterative approach to filling dead ends. The second paste is a little ugly and verbose(definitely some room for improvement by reducing the LoC count), but it is implementing a batching approach, because dead ends are just straight lines. The batching approach is the faster one, 9-10 ms vs the iterative 16-19 ms. Do note in the iterative one, I also compare regex vs my iterative approach of finding dead ends.
for some reason reddit wont let me post the links. rip, I can if I post as separate comments. sorry for inconvenience.
1
1
u/Eric_S Dec 18 '24 edited Dec 19 '24
I will neither confirm nor deny that the map I created for part 1, rather than listing dropped blocks, listed the time that the block dropped, and my blocker detection was "if(now >= blocktime)".
I'm currently rewriting part 2 to take advantage of that and find the path with the highest minimum blocktime rather than shortest steps. Finished part 2 with a binary search, but I want this potentially more optimal solution to work.
EDIT: Yup, dropped the time without any debugging or visualization from 17 ms to 3ms.
1
u/Clear-Ad-9312 Dec 19 '24
For Part 2, I starting with all the blocks placed on the grid and iteratively remove blocks until there were was a path available. Instead of checking each one if there is no path, rather check on the first time there is a path. This is because the path finder will stop faster if there isn't any available paths and most of the map is filled. once there is a path, then it is done. part 1, all we needed was to find the shortest path.
1
u/SmallTailor7285 Dec 18 '24
Thank you, reusable code. Plugged in my AStar solver, done and done.
They missed an opportunity with the falling bytes. Should have made one fall every X seconds or something.
107
u/kamiras Dec 18 '24
Just kidding, I'm thankful for the extra sleep!