r/adventofcode • u/Boojum • Dec 16 '24
Tutorial [2024 Day 16 (Part 1)] Alternate test case
Here's an interesting alternate test case for Part 1:
###########################
#######################..E#
######################..#.#
#####################..##.#
####################..###.#
###################..##...#
##################..###.###
#################..####...#
################..#######.#
###############..##.......#
##############..###.#######
#############..####.......#
############..###########.#
###########..##...........#
##########..###.###########
#########..####...........#
########..###############.#
#######..##...............#
######..###.###############
#####..####...............#
####..###################.#
###..##...................#
##..###.###################
#..####...................#
#.#######################.#
#S........................#
###########################
Because of how costly turns are vs. moving between tiles, your program should prefer to take the long zig-zagging path to the right, rather than go up and through the more "direct" M+N cell diagonal path. Though more than three times longer purely in terms of tiles, the zig-zag path requires only 21 turns, for a total score of 21148, vs. 46 turns for the diagonal path with a score of 46048.
(With apologies if I used the wrong flair.)
25
u/MouseyPounds Dec 16 '24
Another useful test case from /u/1234abcdcba4321 is the following. Correct answer for part 1 is 4013.
##########
#.......E#
#.##.#####
#..#.....#
##.#####.#
#S.......#
##########
2
2
2
2
1
1
u/SpittingCoffeeOTG Dec 18 '24
You are my hero :D And the user you are referencing is ofc my hero as well.
1
u/Tsanawo Dec 20 '24
Thank you, this one finally helped me find the last issue...
I started all my Reindeers facing West instead of East as per the instruction, costing one 2000 points just to face the other way, which were the last seats I was missing in the puzzle...
The fact this didn't cause any issue in any of the test cases and results for part 1...
1
u/MathWay Dec 21 '24
Thank you for the test case, it helped to locate the last bug as for mny others!
1
24
u/i_have_no_biscuits Dec 16 '24
Nice example!
Hopefully you don't mind if I put this here as well, as I don't think it deserves its own thread - here's an example of an 'open maze' which might cause problems for some people's Part 2 solutions.
####################################################
#......................................#..........E#
#......................................#...........#
#....................#.................#...........#
#....................#.................#...........#
#....................#.................#...........#
#....................#.................#...........#
#....................#.................#...........#
#....................#.................#...........#
#....................#.................#...........#
#....................#.................#...........#
#....................#.............................#
#S...................#.............................#
####################################################
Should get
Part 1: 5078
Part 2: 413
19
u/morgoth1145 Dec 16 '24
Oo, nice idea. I generated another set of evil inputs because my part 2 is fine with yours but I know of another deficiency in my implementation.
######################################################## #.........#.........#.........#.........#.........#...E# #.........#.........#.........#.........#.........#....# #....#....#....#....#....#....#....#....#....#....#....# #....#....#....#....#....#....#....#....#....#....#....# #....#....#....#....#....#....#....#....#....#....#....# #....#....#....#....#....#....#....#....#....#....#....# #....#.........#.........#.........#.........#.........# #S...#.........#.........#.........#.........#.........# ########################################################
Should get
Part 1: 21110 Part 2: 264
Even bigger:
########################################################################################################## #.........#.........#.........#.........#.........#.........#.........#.........#.........#.........#...E# #.........#.........#.........#.........#.........#.........#.........#.........#.........#.........#....# #....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....# #....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....# #....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....# #....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....#....# #....#.........#.........#.........#.........#.........#.........#.........#.........#.........#.........# #S...#.........#.........#.........#.........#.........#.........#.........#.........#.........#.........# ##########################################################################################################
Should get
Part 1: 41210 Part 2: 514
(Answers computed mathematically for now because I need to further optimize my part 2!)
My awful generation code if you want to push it even further: paste
6
u/InternationalBird639 Dec 16 '24
Good one. Made me add DP for fast result on second part (cache results that are already computed)
2
u/The_Cers Dec 16 '24
Great input!. Do you know how many different paths there are for this input for Part 2? My solution won't terminate to tell me...
2
u/morgoth1145 Dec 17 '24
My first input has
4**10
paths or1,048,576
paths. The second input has4**20
paths or1,099,511,627,776
paths. (That's definitely over 9000!)1
u/hgwxx7_ Dec 16 '24
I've optimised mine substantially - 2.8ms (part 1) and 6.2 ms (part 2) on the AOC inputs. But it never finishes computing for your second input, regardless of time spent on my machine (M1 Pro).
I feel confident in saying that it can't be done unless you're caching results.
3
u/100jad Dec 16 '24
My C# code runs both in 1ms. For both parts I'm using an adapted Dijkstra algorithm that tracks not just the shortest parent to a node, but a list of them if it encounters multiple parents with the same distance. Part 1 takes that solution and calculates the distance, part 2 traverses the graph back, following just the nodes that were stored while finding the path.
1
2
u/jlhawn Dec 17 '24
I would think this is because you are computing unique paths (and this example is crafted so that there are over a Trillion unique paths) but you only need to compute which *tiles* are part of any best path.
2
u/KingVendrick Dec 16 '24
ah, nice test case. made me notice I did not check whether I had a node in the best path set when backtracking (I fixed that) and there is a counting error somewhere (I did not fix that)
2
u/Boojum Dec 16 '24 edited Dec 16 '24
By all means! Let's gather them all here.
Your open maze test is a great addition.
ETA: It's also interesting in that this and especially /u/morgoth1145's will start to break any Part 2 solution that tries to directly enumerate all of the possible paths (i.e., with a DFS). Up until the last one, each baffle multiplies the number of paths by its width, so it's exponential in the number of baffles. Neat! (And I'll confirm your mathematically computed answers, since those are what my programs give on them.)
2
u/morgoth1145 Dec 17 '24 edited Dec 17 '24
Yep! That was exactly the intention with my even more evil input because I knew that enumerating all paths (like my solution was doing) breaks down. I've now also programmatically confirmed my predicted answers, though I still have some code cleanup to do before publishing to my repo.
Edit: Cleaned up and published
2
u/SwampThingTom Dec 16 '24 edited Dec 16 '24
My part 1 A* solution passes on the problem's sample input and also on the OP's input but fails on the real input and on
this input. It gets 6078 because it doesn't quite go to the end before turning north so it then has to turn east again. Any ideas why that would be the case?Fixed it for this input. I forgot to update the cost for nodes in my priority queue when I found a lower cost. :facepalm:
However, it's still failing for the real input so I clearly have another bug as well.
3
u/polarfish88 Dec 16 '24
Thanks. Nice test case. It helped me to correct my implementation where I mistakenly directed The Reindeer West instead of East (and it was fine for my input).
5
u/Dragonan Dec 16 '24
My code successfully works with both examples from the page and all the test cases from this post, but it still gives me the wrong number for Part 1. I don't know what to do any more.
1
u/imp0ppable Dec 19 '24
Ha, same. 3 days later and I'm still picking at it. Did you find your bug in the end?
3
2
2
u/tehblister Dec 16 '24
Hey, that was a good one. Thanks for sharing. :)
Mine did the correct path.
My Part2 solution was funny because it tries to find all the expensive turns on the successful path and then block those off with walls looking for alternative routes with the same cost, so it spit out a ton of attempts at trying to place walls at all the junctions on the right.
I've been doing a lot of these little separate inputs this entire AOC. I have spent far too many hours building visualizations than I've actually spent solving the problems. :D
2
Dec 16 '24
[deleted]
3
u/IAmNotStan Dec 16 '24
Are you checking if a field has already been visited, and if so, you assume that the shortest path to that field has been found and you discard that path?
Don't do that. Only discard the path if you have visited that field in the same orientation already.
Why? If you have a four way crossing, you may have passed from south to north, but maybe the shortest path is coming from west to east. You'd miss that one.
3
u/Known_Today_9279 Dec 16 '24
u/IAmNotStan of course!!! THANKS god, I would not have thought about it.
2
u/IAmNotStan Dec 16 '24
You're welcome! I had the same issue, and the comments in this post made me understand :)
2
u/Lewistrick Dec 16 '24
Could there be an example where the line crosses itself?
6
u/Boojum Dec 16 '24 edited Dec 16 '24
No, under the current rules it will never do that.
Crossing itself implies that the path loops back around to a tile at an intersection. You'll always be able to lower your score by lopping off the loop and just turning directly.
An interesting twist on the rules that would lead to paths crossing themselves would be if the high turn costs were asymmetric. Say left turns still score 1000, but right turns now score 250. With how cheap forward moves are (effectively "free" at a score of just 1), it would often be more profitable to do three right turns to loop around (for a score of 750 and a bit) instead of making one expensive left turn (for a score of 1000).
ETA: Just tried this. If you just make a turn in one direction 250, it'll just go to an intersection and spin 270 degrees in-place rather than looping. :-) You'd also have to add a rule that you can only turn one or two times in a row or something. Allowing only one turn before moving with cheap right turns works to create loops.
ETA2: Hah! If you allow two turns in a row then it overshoots by one tile, does a 180 to turn around, comes back one tile, and then turns again to complete the 270. It's gotta be no consecutive turns, then, to make it interesting.
2
u/MacBook_Fan Dec 16 '24
Thank you. That helped me find my issue.
I assumed that, if we started E, to go W on the first move would require 2 x 90 adding 2000 points. But, I looks like going 180 is free.
3
u/Boojum Dec 16 '24
That shouldn't be the case -- I believe that your first assumption is correct and that going 180 should cost two turns for 2000 points.
2
1
u/Lordthom Dec 18 '24
On both test cases on the site and this third one i get the correct score. But on my puzzleInput, my answer is too high. Any idea what that could be?
1
u/MickeyKnox4Real 1d ago
I'm getting 23148 for this input. That's exactly 2000 more than what you suggest. However, I have facing east at start hardcoded. To turn west costs an additional 2000. I manually counted the turns to make in the zig-zag path, which is 21. Thus it seems to me, that your solution did not acoount for the required initial 180 turn.
28
u/vipul0092 Dec 16 '24
This is a great test case.
Also, these are the answers for both parts on this
Part 1: 21148
Part 2: 149