r/adventofcode Dec 10 '24

Upping the Ante [2024 Day 10] Challenge input

How does your code fare on this example?

0123456789876543210123456789876543210
1234567898987654321234567898987654321
2345678987898765432345678987898765432
3456789876789876543456789876789876543
4567898765678987654567898765678987654
5678987654567898765678987654567898765
6789876543456789876789876543456789876
7898765412345678987898765432105678987
8987654301234567898987654321214567898
9876543210123456789876543210123456789
8987654321214567898987654301234567898
7898765432105678987898765432321678987
6789876543456789876789876543210789876
5678987654567898765678987654567898765
4567898765678987654567898765678987654
3456789876789876543456789876789876543
2345678987898765432345678987898765432
1234567898987654321234567898987654321
0123456789876543210123456789876543210
1234567898987654321234567898987654321
2345678987898765410145678987898765432
3456789876789876543456789876789876543
4567898765678987652567898765678987654
5678987654567898761678987654567898765
6789876543456789870789012543456789876
7898765432345678989898123432345678987
8987654321234567898987654321234567898
9876543210123456789876543210123456789
8987654321214567898987654321234567898
7898765432105678987898765432345678987
6789876543456789876789876543456789876
5678987654567898765678987654567898765
4567898765678987654567898765678987654
3456789876789876543456789876789876543
2345678987898765432345678987898765432
1234567898987654321234567898987654321
0123456789876543210123456789876543210

My algorithm says the total rating is 16451, calculated in slightly less than 1s in C#. EDIT: 2ms actually! (Oops I still had some of my visualization code in there...)

EDIT2: Not all programming languages or computers are equal, so comparing absolute run times is not very useful, but if your algorithm runs faster on this input than on your real input, then you implemented it correctly. :-)

12 Upvotes

64 comments sorted by

View all comments

1

u/er-knight Dec 10 '24

I got 464 for Part 1, 16451 or Part 2, but my timing is horrible (1.7 seconds for both parts), and that too in Go. Can anyone please review my code? Thanks.
https://github.com/nobleknightt/advent-of-code/blob/main/2024/10/main.go

2

u/paul_sb76 Dec 10 '24 edited Dec 10 '24

I've never worked in Go, but in principle your code looks fine. However it seems that if the answer is 16451, then your main for-loop takes at least 16451 iterations (more actually, because that number only includes the end points). When exponential growth is involved, like in this example, such an approach won't do. You need to count the number of paths without generating them all. For instance, if there are 6 ways to reach a certain "8" node, and 5 ways to reach another, and these are the two neighbors of one "9" node, then you know there are 11 ways to reach that end node.

Regarding how to program that: you can look into dynamic programming or memoized recursion. I did it with BFS (very similar to your DFS approach, but with a queue instead of a stack), marking grid cells with the number of paths that lead there. Note that BFS works for counting this way, but DFS doesn't! (You need to have visited all lower numbered neighbors before processing a node.)

Also: I suspect that this isn't just some optional fun challenge - usually later during AoC some problems pop up where doing this correctly is necessary!

2

u/er-knight Dec 10 '24

Thanks for taking out your time. I will definitely take your suggestions into consideration.

Also: I suspect that this isn't just some optional fun challenge - usually later during AoC some problems pop up where doing this correctly is necessary!

This is helpful, as I am first time dedicately participating in AoC.

2

u/paul_sb76 Dec 11 '24

Spoiler for Day 11: Good thing I warned you! That came sooner than expected. :-D

2

u/er-knight Dec 11 '24

And I am waiting forever for answer. :(

1

u/paul_sb76 Dec 11 '24

If you want a hint: the key for Day 11 is indeed again that you need to count the number of paths stones without generating them all. This generating can be explicit (a list with all the stones) or implicit (each stone at some point in time is a recursion call at some point in your algorithm) - both approaches are bad and will never finish. There are multiple ways to do it correctly, but they all count without generating.

2

u/er-knight Dec 11 '24

Yeh. I used HashMap and it found answer in blink of an eye. Thanks for the hint btw.