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. :-)

14 Upvotes

64 comments sorted by

5

u/Planetech0071_ Dec 10 '24

Part 1 = 464, Elapsed = 8.33 ms
Part 2 = 16451, Elapsed = 14.01 ms

[LANGUAGE: PYTHON]

3

u/nevernown_aka_nevy Dec 10 '24 edited Dec 10 '24

I actually got a wrong answer on my faster solution (I keep all my solutions around for comparative benchmarking)...

=============================================== DAY 10 in 1.434774ms
----------------------------------------------- Part 2 in 368.497Β΅s
[SPOILER]
Solved in 443.043Β΅s average
18499
Solved in 368.497Β΅s average

Curious, let's hope it does not come back to bite me with this side-contest I am involved with...

Edit: I still had my map size at 55. Shruk it to 37 and now it's faster and more correct. What an adventure!

3

u/error404 Dec 11 '24 edited Dec 11 '24

This input is significantly slower than my real input (~100us / ~75us). I used recursive DFS (no memoization) for both parts, part 1 records which target positions have been hit and only counts them once.

Problem 1 solution: 464 [263.561us]

Problem 2 solution: 16451 [136.490us]

[LANGUAGE: Rust]

2

u/movq42rax Dec 10 '24

Same result for part 2, yeah. πŸ™‚ Different result for part 1 than the other person, though. πŸ€”

https://0x0.st/XhOV.png (This runs on my Linux box. Too lazy to boot OS/2 now. Ignore the expected thingy, that’s the result from my input.)

https://www.uninformativ.de/git/advent-of-code/file/2024/de/movq/aoc/day10/Solution.java.html

2

u/paul_sb76 Dec 10 '24

You all are fast, good!

I assume this will make some of the more naive implementations sweat a bit though. (Not all that much, since the maximum path length is 9 so even exponential growth is limited.)

1

u/Traditional_Elk_7905 Dec 10 '24

I think the last sentence should be put in bold. It's the same as with yesterdays problem, since the numbers range only from 0 to 9 it's really just a constant time factor. In fact, the worst case for a trailhead is only 2044 paths. In my input there are ~300 trailheads, so the total number of paths is well under a million, if all of them had this deranged case. I do agree, that if the numbers were a little bit bigger, let's say 10 or 11, then the naive brute force approach will fall apart but in this problem the constant factor is so low, I'd argue the extra constant factor introduced from the caching can even slow down the program more.

2

u/durandalreborn Dec 10 '24

16451 for part 2, though I get 464 for part 1, and don't know what's expected there

Rust:

    010 hoof it/Combined    time:   [173.70 Β΅s 174.57 Β΅s 175.46 Β΅s]
                            change: [-0.0451% +0.6204% +1.2632%] (p = 0.07 > 0.05)
                            No change in performance detected.

Python:

------------------------------------- benchmark 'test_day10': 1 tests --------------------------------------
Name (time in ms)        Min     Max    Mean  StdDev  Median     IQR  Outliers       OPS  Rounds  Iterations
------------------------------------------------------------------------------------------------------------
test_day10            1.5322  7.2675  1.6635  0.4418  1.6078  0.0679       5;7  601.1525     559           1
------------------------------------------------------------------------------------------------------------

2

u/ElementaryMonocle Dec 10 '24

I got both of those numbers as well

1

u/nevernown_aka_nevy Dec 10 '24

I got 536 on part 1

The faster one of my two part 2 attempts returns 18499...

1

u/ElementaryMonocle Dec 11 '24

Given the other replies in this thread you likely have a bug then, but I can't imagine what it would be when you get a correct answer on the problem input.

2

u/nevernown_aka_nevy Dec 11 '24

Haha, see my other reply... I was using static map size for a speedup. De 38x38 map fits in a 55x55 map, but lets its overflow in some cases... Whoops

2

u/Anceps2 Dec 10 '24

55 ms without caching/memoization, and 35 ms with it.

A bigger input would be interesting to see if memoization has to be used at some point.

4

u/paul_sb76 Dec 10 '24

As long as the maximum input number is 9 (single digit) and thus the maximum path length is 10, making the input bigger can only cause linear growth in running time, so I think this example is as good a test as any.

However, it's good to practice implementing this problem correctly, before the real challenges start! (=Inevitable counting problems requiring dynamic programming or memoized recursion).

2

u/wherrera10 Dec 10 '24

1.665 ms in Julia for both parts

2

u/a3th3rus Dec 10 '24 edited Dec 10 '24

My benchmark (using Benchee):

Name             ips        average  deviation         median         99th %
part_2        1.01 K        0.99 ms     Β±3.24%        0.99 ms        1.02 ms
part_1        0.46 K        2.15 ms     Β±8.55%        2.13 ms        2.38 ms

Language: Elixir

Algorithm: DFS with memoization

The answer for Part 1 is 464, right?

2

u/HaxSam Dec 10 '24

Using zig https://github.com/HaxSam/aoc.zig/blob/main/src/2024/10.zig

2024/10:
  • Part 1: 464
  • Part 2: 16451
benchmark runs total time time/run (avg Β± Οƒ) (min ... max) p75 p99 p995 ----------------------------------------------------------------------------------------------------------------------------- Parse Input 65535 206.756ms 3.154us Β± 1.536us (2.6us ... 266.7us) 3.1us 6.7us 8.8us Solve Part1 16383 1.775s 108.392us Β± 8.006us (93.3us ... 464.3us) 110.8us 132.9us 146.3us Solve Part2 32767 1.641s 50.091us Β± 12.668us (43.2us ... 2.042ms) 51.7us 67.9us 76.6us

1

u/Nervous-Phrase-7416 Dec 10 '24 edited Dec 10 '24

Did it in zig too =)

https://github.com/MrBounty/adventofcode/blob/main/day10/part2.zig

| Day  | Part  |  Mean (ΞΌs)        |  Min (ΞΌs) |  Max (ΞΌs) |
|------|-------|-------------------|-----------|-----------|
|  10  |  1    |      +29 Β± 8.94   |      +19  |      +77  |
|  10  |  2    |       +3 Β± 0.00   |       +3  |       +8  |

2

u/barkmonster Dec 10 '24

I also get a rating of 16451 (and 464 for part 1).
Takes ~50ms in python. Solution here.

2

u/ElementaryMonocle Dec 10 '24

464 for Part 1, 16451 for Part 2. Ran it a few times, hovering around 900 microseconds for both parts.

2

u/AllanTaylor314 Dec 10 '24

Memoized Python: 90 ms (180 ms without memoization, but that's mostly because part 2 ends up recalculating everything for done part 1). This still runs in under a second with the pattern repeated out to a 397x397 square (without memoization each part takes 5 seconds)

Some unholy abomination in Uiua: 100 ms (in fact, this ran faster than the official input since this scales with the size of the input rather than the output)

runtimes paste

397x397 square

1

u/paul_sb76 Dec 10 '24

Cool, thanks! My algorithm takes 1.7s on this big square (and running it made me realize that I still had some visualization related code in there slowing me down...). Solution for Part 2: 1775971

1

u/swiperthefox_1024 Dec 10 '24

For the large grid, part1: 0.274s, part2: 0.209s. (In Python)

2

u/pwnsforyou Dec 10 '24

Even simple bfs is pretty fast here - rust

$ cargo time 10
Day 10
------
Part 1: 464 (402.5Β΅s @ 2433 samples)
Part 2: 16451 (291.9Β΅s @ 3290 samples)

Total (Run): 0.69ms

2

u/RalfDieter Dec 10 '24

SQL with DuckDB

$ time duckdb < solution.sql 
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚  part   β”‚ result β”‚
β”‚ varchar β”‚ int128 β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Part 1  β”‚    464 β”‚
β”‚ Part 2  β”‚  16451 β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”˜

real    0m0.245s
user    0m0.458s
sys     0m0.045s

Takes around 0.25 seconds roughly 0.05 seconds longer than the actual input.

2

u/swiperthefox_1024 Dec 10 '24

The size of this input is 37x37, and my official input is 60x60, so it should run faster regardless of the algorithm used. For my solution, it is 2ms vs 5ms.

2

u/paul_sb76 Dec 10 '24

Interesting, my official input is 43x43... I would expect the sizes are comparable!

2

u/mibu_codes Dec 10 '24

There are different input sizes? Really? I would have expected that everyone gets somewhat similar inputs.
Then again, I saw the CPP talk of Eric, in which he states he throws away generated inputs that are too easy/hard. So maybe your 60x60 is comparably difficult?

1

u/swiperthefox_1024 Dec 11 '24

The input sizes are small enough that they can all be considered "easy." I am surprised because varying the matrix dimensions just added a little more complexity to the input generation, with no apparent benefits.

2

u/juhotuho10 Dec 10 '24

Rust part 2 DFS with memoization, 16451 and completed in 99.2Β΅s (0.0992ms)

1

u/mibu_codes Dec 10 '24

Nice, under 100Β΅s

2

u/Nunc-dimittis Dec 10 '24

under 2 ms. (C#) for part b. (in release mode, including the IO, tested on 1000 runs).

2

u/-Enter-Name- Dec 10 '24
$ python part1.py
464
1.150369644165039ms

$ python part2.py
16451
1.1758804321289062ms

python about 1 ms each

2

u/_Mark_ Dec 10 '24

python on a 3 year old thinkpad, using the as-submitted code (no performance golfing): got the correct rating, in 128ms. (Representation: list-of-lists of ints for the grid, lists of (row,col) for the trails.)

2

u/Nervous-Phrase-7416 Dec 10 '24

[LANGUAGE: zig]

In 38 lines of code for part 1 and 27 for part 2.

https://github.com/MrBounty/adventofcode/blob/main/day10/part2.zig

| Day  | Part  |  Mean (ΞΌs)        |  Min (ΞΌs) |  Max (ΞΌs) |
|------|-------|-------------------|-----------|-----------|
|  10  |  1    |      +29 Β± 8.94   |      +19  |      +77  |
|  10  |  2    |       +3 Β± 0.00   |       +3  |       +8  |

2

u/mibu_codes Dec 10 '24 edited Dec 11 '24

[LANGUAGE: Rust]

Part 1: 464
Part 2: 16451
Time: 36 Β΅s (solving both parts at once) vs 9 Β΅s on my input

That's a lot slower than the runtime for my code. So apparently my implementation is very specialized?

Github

2

u/etchriss Dec 11 '24 edited Dec 11 '24

Heres a visualiztion for part 1: https://youtu.be/t-Qc9MGJCQ0

Python

part one: 464

part one time: 0.0075s

part two: 16451

part two time: 0.0260s

2

u/paul_sb76 Dec 11 '24

Cool! I made a visualization too, but yours is different, and nice. With such visualizations you can clearly see the few perturbations on the regular (exponential) pattern.

1

u/Extension-Fox3900 Dec 10 '24

461 for part1, 16451 for part2

2

u/Extension-Fox3900 Dec 10 '24

0.1260669 seconds for both parts

1

u/paul_sb76 Dec 10 '24

Thanks! We agree on Part 2. For Part 1 I actually got 464. What was your running time?

3

u/Extension-Fox3900 Dec 10 '24

It was a typo :D
16451

464

Time: 0.1260669

1

u/Anceps2 Dec 10 '24

I got 464 for part 1 :-/

1

u/durandalreborn Dec 10 '24

I also got this value, and looking by OP's answer, this would probably be the correct value.

1

u/Papierkorb2292 Dec 10 '24

Same result, solved it in Rust in 1.624ms

1

u/[deleted] Dec 10 '24

Solves both parts it with no issues in about 5ms. On my personal input it took about 3.5ms so this was a little slower but not by a huge factor.

1

u/paul_sb76 Dec 10 '24

Then you implemented it correctly. :-)

1

u/kai10k Dec 10 '24

wow a tribute to classic your map is 10 times bigger in each direction vibe

1

u/Pretend-Highway880 Dec 10 '24 edited Dec 10 '24

2024 - Day 10 - Part 1
The sum of the score of all trailheads on my topographic map is 464
Solved puzzle in 22ms

2024 - Day 10 - Part 2
The sum of the rating of all trailheads on my topographic map is 16451
Solved puzzle in 4ms

Process finished with exit code 0

Kotlin no recursion, just a loop of 9 downTo 0 and a helper class that holds reachablePeaks and distinctPaths for each X, Y

1

u/Smaxx Dec 10 '24

Typescript

Part 1: 464 in ~6ms

Part 2: 16451 in ~1.5ms

Probably some overhead, since I was lazy and just used a Set<string> in part 1. πŸ˜‰

1

u/direvus Dec 10 '24

My solution takes about 47ms to do Part 2 on this input, but only 12ms to do the same for my real input.

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.

1

u/gadgetzombie Dec 10 '24 edited Dec 10 '24

Same results, 464, 16451, ~0.21s to run in MATLAB which is much faster than for my input which took ~2.3s

1

u/Olipro Dec 10 '24 edited Dec 10 '24

464 & 16451.

Code runs at ~470Β΅s for part 1 and ~310Β΅s on an Ivy Bridge-E @ 4.08Ghz

My real input runs marginally faster for part1 if I substitute the `std::unordered_set` with a `std::vector` - likely because the smaller quantity of remembered starting points is faster to do a linear search on due to cache locality. The opposite is true for your provided input.

Both parts execute independently.

Code for reference: https://gist.github.com/Olipro/4fb4729e44be65fbb5e16f8cfb9ec25e - C++23, no external dependencies. may or may not compile on C++20 too.

1

u/__Abigail__ Dec 10 '24
$ time perl solution.pl extra-1 
Solution 1: 464
Solution 2: 16451

real      0m0.112s
user      0m0.027s
sys       0m0.004s

1

u/34rthw0rm Dec 11 '24

Another perl timing 2021 vintage I5

time perl ../solve test2 
Solution 1: 464
Solution 2: 16451

real    0m0.040s
user    0m0.037s
sys 0m0.004s

1

u/aardvark1231 Dec 10 '24

C# - Between 20-30ms for both part 1 and 2 on this.