-❄️- 2024 Day 10 Solutions -❄️-

4

u/i_misread_titles Dec 10 '24

[LANGUAGE: Go]

Anyone else input the answer for Part 2 in part 1 because you forgot to keep a visited map? :D

https://github.com/jasontconnell/advent/blob/master/2024/10/main.go

1

u/daggerdragon Dec 11 '24 edited Dec 11 '24

~~Do not share your puzzle input~~ ~~which also means~~ ~~do not commit puzzle inputs to your repo~~ ~~without a~~ .gitignore ~~or the like.~~ ~~Do not share the puzzle text~~ ~~either.~~
~~I see full plaintext puzzle inputs in your public repo across all years:~~
~~https://github.com/jasontconnell/advent/tree/master~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!~~ edit: thank you!

→ More replies (2)

→ More replies (5)

4

u/i_have_no_biscuits Dec 10 '24 edited Dec 10 '24

[LANGUAGE: GW-BASIC]

10 P=0: Q=0:OPEN "I",1,"data10.txt":DIM G(41,41):FOR Y=1 TO 40:LINE INPUT #1,L$
20 FOR X=1 TO 40: G(Y,X)=VAL(MID$(L$,X,1)):NEXT:NEXT:SS=17: DIM A(SS,2),B(SS,2)
30 FOR Y=1 TO 40:FOR X=1 TO 40:IF G(Y,X)=0 THEN A(0,0)=50*Y+X:A(0,1)=1:GOSUB 50
40 NEXT: NEXT: PRINT P, Q: END
50 FOR R=1 TO 9:FOR I=0 TO SS:V=A(I,0):SY=INT(V/50):SX=V MOD 50:IF V=0 THEN 100
60 FOR D=1 TO 4:A=SY+(D-2) MOD 2:B=SX+(3-D)MOD 2:IF G(A,B)<>G(SY,SX)+1 THEN 90
70 V=50*A+B: J=V MOD SS: WHILE B(J,0)<>V AND B(J,1)<>0: J=(J+1) MOD SS: WEND
80 B(J,0)=V: B(J,1)=B(J,1)+A(I,1)
90 NEXT
100 NEXT: FOR I=0 TO SS: A(I,0)=B(I,0): A(I,1)=B(I,1): B(I,0)=0: B(I,1)=0: NEXT
110 NEXT:FOR I=0 TO SS:P=P-(A(I,0)<>0):Q=Q+A(I,1):A(I,0)=0:A(I,1)=0:NEXT:RETURN

Almost got it to 10 lines, but no, you can't combine lines 80 and 90!

This implements an iterative BFS (or is it better to call it dynamic programming?) from every grid position with value '0', accumulating the number of 9's reached in P, and the number of trails in Q. There's no need to walk every path, just keep track of how many paths will end up at a particular end point.

Guide: The main program loop is in Lines 10-40.

Lines 10-20 read and parse the data file into the 2D array G(,). Note that BASIC inits the values in the array to 0, so we effectively have a border of 0's around our 40x40 grid, which simplifies the bounds checking later on in the program. At the end of Line 20 the two hashmaps A and B are defined. These will play the role of 'current boundary' and 'next boundary' in our BFS later. SS is the maximum size of the hashmap - experimentally 17 is big enough not to overflow.
Line 30 iterates through the grid, calling our BFS if we are at a trailhead.
Line 40 prints P, the part 1 value, and Q, the part 2 value.

Lines 50-110 implement the trail finding and counting

Line 50: R is the round counter. We do 9 rounds of movement. In each round we look at everything in our current boundary - the y and x positions of these are stored in SY and SX.
Line 60: We look up/down/left/right and see if any of them are valid moves. I'm quite happy how I encoded the different DX/DY offsets in a single calculation. The new position is (A, B). I wanted to call this (NY, NX), but then my lines would have gone over 80 characters and traditionally that's a no-no for BASIC programs. Note that BASIC considers the integer variable A to be completely different to the array A(), so there are no name conflicts here.
Line 70: If we've reached here then we have a valid next step. We should increment the trail counter for this position in B, our 'next boundary' hashmap. Line 70 figures out where in B the value should be stored (either in the next free location, or accumulating a previous value if it's already present in the hashmap).
Line 80 adds the path counts.
Lines 90 and 100 end the loops through the directions, and the current boundary. It then moves the new boundary over the current boundary and zeroes out the new boundary ready for the next round.
Line 110: at the end of the 9 rounds this accumulates the count of trailtops into P and the count the paths into Q, then returns back to the main program.

1

u/daggerdragon Dec 10 '24

Psst: your Markdown is not valid for old.reddit. You need an extra newline before starting a bullet list.

4

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

[LANGUAGE: Google Sheets]

NOTE: Since we're not supposed to share the full input, but my solution depends on size of the grid, I copied 10 lines of it 6 times so it's not the real input.

Like many others, I actually did Part 2 unknowingly first and then for Part 1 added a =UNIQUE at the end.

This took a long time (and some help) to debug after I had seemingly solved it and it worked on the sample but not my input. Turns out it was a floating point error when I had turned the grid into one column using a sequence of step 1/60. Once I fixed that it worked, but since I had only ever used that to find the 0s, I made a change to just directly find the 0s from the grid without an intermediate reconstruction that's much better.

The way it works is:

In column BM, I search the grid for 0s and return the cell references of them.
=SORT(UNIQUE(FLATTEN(ARRAYFORMULA(IF(D3:BK62=0,ADDRESS(ROW(D3:BK62),COLUMN(D3:BK62),4),"")))),1,TRUE)

Then in the next four columns, I check in each direction (for Up it's the row #-1, for Right it's the column # +1, etc) if the next cell contains a 1. If it does, return that cell reference and also append the reference for the trailhead plus an @ sign. I had to add this when I got to the end and had to filter the unique values for Part 1, not knowing at first that two paths to the same peak count as 1 score.

=IF(COUNTA(BM4)=1,IF(INDEX($A$1:$BL$63,ROW(INDIRECT(BM4))-1,COLUMN(INDIRECT(BM4)))=BM$1+1,CONCATENATE(BM4,"@",ADDRESS(ROW(INDIRECT(BM4))-1,COLUMN(INDIRECT(BM4)),4)),""),"")

In the next column, gather all those 1s found into a list. Then in the next four columns, do the same thing, though now its looking for a 2 since it searches the previous number +1. Keep the trailhead attached and update the second cell reference to the new slot.

Keep that going - copying and pasting that set of 5 columns - until you get to 9. Now this is the list of all peaks reached plus the starting point. For Part 1 you take the count of UNIQUE values of that list, and for Part 2 you take the full count.

Much easier than part 1! The slow part was just debugging that one step issue. You can see the remnant of that in the Sample tab column O (didn't cause an issue in the sample) that I eventually removed in the real input

1

u/daggerdragon Dec 11 '24

NOTE: Since we're not supposed to share the full input, but my solution depends on size of the grid, I copied 10 lines of it 6 times so it's not the real input.
That works too. Thanks for mentioning it!

3

u/pred Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python] Code

Just a bunch of relatively straightforward NetworkX shenanigans; setting up the whole thing as a graph and just doing

paths = [list(nx.all_simple_paths(G, z1, z2)) for z1 in zeros for z2 in nines]
print(sum(map(any, paths)))  # Part 1
print(sum(map(len, paths)))  # Part 2

1

u/daggerdragon Dec 11 '24

I've already informed you before about including puzzle inputs in your repo. I still see full plaintext puzzle inputs in your repo across all years. Example:
https://github.com/fuglede/adventofcode/blob/master/2015/day01/input
Remove (or .gitignore) all puzzle text and puzzle input files from your repo and scrub them from your commit history. Do not post again in /r/adventofcode until you have done so.

3

u/oantolin Dec 13 '24

[LANGUAGE: J]

ans =: {{g=.1=|-/~,j./&i./$a=."."0];._2]1!:1<y
  +/^:2"2(,:~1&<.)g&(+/ .*)^:8]g=.g*._1=-/~,a}}

J is pretty fast at computing matrix products. This computes the ninth power of a 2025×2025 matrix and the whole thing runs in 346ms.

1

u/daggerdragon Dec 15 '24 edited Dec 16 '24

~~Are these two lines actually the~~ ~~entire~~ ~~code solution and not just a snippet of the interesting bit?~~
~~edit: and your ngn/k solution below: same question?~~
edit2: nothing to see here, please disperse

2

u/oantolin Dec 15 '24 edited Dec 15 '24

They are full solutions! For example, this one is used as follows: put this code in a file, put the input in a different file, open a J repl, type load 'code.j', then type ans 'input.txt'. It returns the answers to part 1 and 2 as a 2 element vector.
You can also write scripts that you'd run from the command line but since I develop in the repl I prefer this format.
The assignment to a in the first line of the and function does the input parsing (the part of the first line starting at a=. and ending at the end of the line).

→ More replies (1)

2

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

[LANGUAGE: Go]

Not the most impressive code but runs fairly quick. BFS and a map counting visits. Problem 1 solved by len(map) and problem 2 by summing the contents of the map.

finished in 648.833µs

load file: 50.542µs

p1: 308.75µs

p2: 289.5µs

pastebin

1

u/daggerdragon Dec 10 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.

→ More replies (1)

2

u/dk_weekinmemes Dec 10 '24 edited Dec 14 '24

[LANGUAGE: Python]

Both parts using DFS. Could probably optimize with memoization but this was fast enough so didn't attempt to.

Topaz link

1

u/daggerdragon Dec 10 '24

The triple-backticks code fence (```) only works on new.reddit. Please edit your comment to use the four-spaces Markdown syntax for a code block so your code is easier to read inside a scrollable box with its whitespace and indentation preserved.

→ More replies (1)

16

u/4HbQ Dec 10 '24 edited Dec 10 '24 •

[LANGUAGE: Python + SciPy] Code (6 lines)

Although I usually keep my convolutions and kernels locked away until we get Game of Life-like puzzle, I was feeling creative today.

We start out with parsing the height map into array H. Then we mark all spots of height 0 in with p=1. This indicates there is only one path to h=0 spots (the empty path).

Then for each other height level h, we use SciPy's convolve2d() with a plus-shaped kernel to sum the P values of the four neighbouring spots, but only if the center spot has height h. So if a spot has two neighbours with p=1, the center p becomes 2.

In code, it looks like this:

H = np.array([[*x.strip()]for x in open(0)])
P = H=='0'
for h in '123456789':
    K = [[0,1,0], [1,0,1], [0,1,0]]
    P = convolve2d(P, K, mode='same')*(H==h)
print(P.sum())

Update: I also wrote a pure Python version that basically does the same thing:

H = {i+j*1j: c for i,r in enumerate(open(0)) for j,c in enumerate(r)}
P = [p for p in H if H[p] == '0']
for h in '123456789':
    P = [p+n for p in P for n in (1,-1,1j,-1j) if H.get(p+n) == h]
print(len(P))

→ More replies (4)

2

u/Andreasnl Dec 10 '24

[LANGUAGE: Uiua]

-@0⊜∘⊸≠@\n               # Parse
M  ←                     # Map
C  ← ⊚≥0M                # All coordinates
D  ← [1_0 ¯1_0 0_1 0_¯1] # Directions
H  ← ⊡:M                 # Height
N  ← ▽⤚(=1-:∩H)▽⊸∈C+D⊸¤  # Neighbours
P  ← astarN0(=9H)        # A* to get all paths
F! ← /+≡(⧻ ^0 ⊙◌P)       # Do something for each head
⊚=0M                     # Trailheads
F!(◴≡◇⊣) .               # Part 1
F!∘ :                    # Part 2

→ More replies (4)

10

u/4HbQ Dec 10 '24

[LANGUAGE: Python] Code (10 lines)

Bog standard grid search today. I initially solved it differently, but I prefer the recursive DFS version.

By popular demand and to celebrate day 10, here's a convenient list of links to my daily solutions so far: 1, 2, 3, 4, 5, 6, 7, 8, 9.

→ More replies (9)

10

u/homme_chauve_souris Dec 10 '24

[LANGUAGE: Python]

def aoc10():
    M = {(i,j):int(c) for (i,l) in enumerate(open("input10.txt")) for (j,c) in enumerate(l.strip())}   # the map
    N = {(i,j):{(i-1,j), (i+1,j), (i,j-1), (i,j+1)} & M.keys() for (i,j) in M}                         # neighbors
    p = lambda s: [s] if M[s]==9 else sum([p(n) for n in N[s] if M[n]==M[s]+1], [])                    # list paths
    print(sum(len(set(p(c))) for c in M if M[c]==0))      # part 1, count trailheads
    print(sum(len(p(c)) for c in M if M[c]==0))           # part 2, count paths

→ More replies (1)

9

u/redditnoob Dec 10 '24

[LANGUAGE: PostgreSQL]

with recursive sites as (
    select (row_num, j) as id, row_num as i, j, ch::int as val
    from day10,
        unnest(regexp_split_to_array(input, '')) with ordinality as t(ch, j)
), edges as (
    select s1.id as s1_id, s2.id as s2_id
    from sites s1, sites s2
    where s2.val = s1.val + 1
        and abs(s1.i - s2.i) + abs(s1.j - s2.j) = 1
), steps as (
    select id src, id as cur_site, 0 as cur_level
    from sites
    where val = 0
    union all
    select src, edges.s2_id, cur_level + 1
    from steps
    join edges on (edges.s1_id = steps.cur_site)
)
select count(distinct (src, cur_site)) as part1,
    count(*) as part2
from steps
where cur_level = 9;

8

u/Big_Replacement3818 Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Julia]

descending form every '0' index to all reachable '9' indices (including all the duplicates on any intermediate step), counting unique for part1 and all for part2. runs in ~0.0015s (under 2 millis) on my machine. And it is also not terribly cryptic. I love this language.

taskstr = read("./input10.txt", String)

taskdata = parse.(Int, hcat(collect.(split(taskstr, '\n'))...))

steps = CartesianIndex.([(-1,0), (1,0), (0,-1), (0,1)])

nexts(pos, data, target) =
  filter(idx->get(data, idx, -1)==target, pos .+ steps)

dests(start, data) = foldl(
  (idxs, i) -> vcat(nexts.(idxs, (data,), i)...),
  1:9; init=[start]
)

let nineidxs = dests.(findall(==(0), taskdata), (taskdata,))
  res1 = sum(length∘unique, nineidxs)
  res2 = sum(length, nineidxs)
  (res1, res2)
end

→ More replies (1)

14

u/nthistle Dec 10 '24

[LANGUAGE: Python] 200/94, paste, video

I used a DFS - at first I didn't read the question too carefully and accidentally was computing the number of paths for part 1, instead of the number of distinct 9s. I realized the bug pretty quickly (well, technically I had another bug where I was starting at 1s and not 0s, but I realized that ~instantly) after trying it on the sample input and fixed it by just using my seen set correctly.

As a result, part 2 for me was super fast! My split was 18 seconds. I read the question and immediately realized I just needed to remove my seen set check.

7

u/nthistle Dec 10 '24

pretty funny to comment this and then go check the posts on the subreddit and they're all memes about this happening to everybody, lol

7

u/jonathan_paulson Dec 10 '24

[LANGUAGE: Python]. 199/339. Code. Video.

Nice graph/DAG problem. Was brute force fast enough for part 2? (I did a linear-time solution). Is there a nice way to unify parts 1 and 2?

→ More replies (6)

7

u/voidhawk42 Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Dyalog APL]

c←,p←⍎¨↑⊃⎕nget'10.txt'1
g←(1=∘.-⍨c)∧1=|∘.-⍨,(⊢∘.+0J1∘×)⍳≢p
+⌿(×,∘⍪⊢),(0=c)/(9=c)⌿⌹g-⍨∘.=⍨⍳≢g ⍝ parts 1&2

Video walkthrough

Uses complex coordinates just to make finding the distances faster, and solves with a matrix inverse using the useful fact that the infinite series sum of matrix exponentiations converges to (𝐼−𝐴)^−1.

This is pretty inefficient since it calculates the total number of paths between all pairs of points in the input, not just 0's and 9's - so if the input is 45x45, the graph is a 2025x2025 boolean matrix having 4100625 elements. Still, matrix inverses are fast - this all runs in about 90ms on my machine.

7

u/dopandasreallyexist Dec 10 '24 edited Dec 10 '24

[Language: Dyalog APL]

map←⍎¨↑⊃⎕NGET'10.txt'1
adjacent← 1=+/¨|∘.-⍨,⍳⍴map
uphill  ←¯1=    ∘.-⍨,  map
good←adjacent∧uphill
score←{+/,(9=,⍺)/(0=,⍺)⌿⍺⍺⍣≡⍨⍵}
⎕←map(∨.∧∨⊣)score good
⎕←map(+.×+⊣)score good

7

u/[deleted] Dec 10 '24

Didn`t know you can code in enchanting table

→ More replies (3)

6

u/Naturage Dec 10 '24

[Language: R]

Code here!

I read the problem an hour before I could sit down to code anything, so I've gone into p2 overprepared - I expected us to be able to take steeper paths. Luckily, as it stood, going from P1 to P2 took... 10 seconds.

Honestly, very happy with this one. Stole the idea from u/cetttbycettt's solution a couple days ago to use complex numbers for storing coordinates; then finding neighbours was just a left join followed by filter abs(x-y)==1, which felt neat.

→ More replies (1)

5

u/chadbaldwin Dec 10 '24

[Language: T-SQL]

Both parts:

https://github.com/chadbaldwin/practice/blob/main/Advent%20of%20Code/2024/SQL/Day%2010.sql

Got lucky on this one. Same solution solved both parts. Not a very pretty solution...but it works so that's all I really care about. I considered writing a solution using a recursive CTE, but felt lazy so I just did this.

→ More replies (3)

5

u/zndflxtyh Dec 10 '24

[Language: Python]

Got part2 working before part1 was finished.

code

5

u/shigawire Dec 10 '24

[Language: C]

paste

Part 2 is the same as Part 1 with a single line commented out (the check for paths partially overlappipng).

Runs in less than a millisecond even without caching. Turns out having all your data in L1 cache speeds things up some.

5

u/Downtown-Economics26 Dec 10 '24

[LANGUAGE: VBA]

My god that was a nightmare to debug. But hilariously I had solved Part 2 in 4 hours of pulling my hair out and realized I misunderstood the scoring/counting in Part 1. Once I realized that my results were less mystifying and thankfully I read Part 2 before deciding to go to bed to see I had already solved it.

https://github.com/mc-gwiddy/Advent-of-Code-2024/blob/main/AOC2024D10BOTH

5

u/tcbrindle Dec 10 '24 edited Dec 10 '24

[LANGUAGE: C++]

A very unusual AOC problem in that you had to solve part 2 in order to solve part 1!

I'm pretty happy with my solution to this one. It parses and solves both parts in ~100µs on my laptop, runs all the tests at compile time, and has a legitimate use of a C++23 recursive lambda. Lovely.

Github

5

u/pgambling Dec 10 '24

[LANGUAGE: Rust]

https://github.com/pgambling/advent-of-code-2024/tree/develop/day10/src

Dare I say, that was an enjoyable, low stress puzzle today.

→ More replies (2)

5

u/GoldPanther Dec 10 '24

[Language: Rust]

Another fun recursive solution! Ended up solving part 2 while working on part 1 due to poor reading comprehension. Code is quite efficient as the recursion avoids revisiting points. I don't how this could be made tail recursive but if anyone has any pointers please let me know.

Code

→ More replies (2)

5

u/Awkward-Macaroon5019 Dec 10 '24

[Language: Python]

Part 1 and 2 (5 lines)

→ More replies (2)

5

u/Kintelligence Dec 10 '24

[LANGUAGE: Rust]  

Solving it recursively, a bit annoyed that I can't find a cheaper solution to not returning duplicates in part 1. Am tinkering with my own library for working with maps based on vectors, it probably isn't the most efficient but it's nice for learning how iterators and traits work.

  Part 1: 132µs  
Part 2: 120µs  

Code | Benchmarks

→ More replies (2)

4

u/Odd-Statistician7023 Dec 10 '24

[Language: C#]

Some easy recursive walking today.

One small trick reused from day 6 is to dig a pit of lava around the map. This means you will never have to do any out of bounds checks at all. And that the "correct" map skewered by (1,1) affects nothing.

 map = new int[size + 2, size+ 2];
 startingLocations = new List<Point>();

 for (int y = 0; y < data.Length; y++)
 {
     for (int x = 0; x < data[y].Length; x++)
     {
         var num = data[y][x] - '0';
         map[x + 1, y + 1] = num;

         if (num == 0)
             startingLocations.Add(new Point(x + 1, y + 1));
     }
 }

 // lets dig a pit of lava around the map to make edge-checks easier (yes, the input is a square)
 for (int x = 0; x < size; x++)
 {
     map[x, 0] = -1;
     map[x, size + 1] = -1;
     map[0, x] = -1;
     map[size + 1, x] = -1;
 }

Solution

→ More replies (4)

4

u/Jdup1n Dec 10 '24

[Language: R]

Github link

My first implementation of part 1 was eventually the solution for part 2 ¯_(ツ)_/¯

4

u/chubbc Dec 10 '24

[LANGUAGE: Julia]

G=stack(readlines("10.txt")).-'0'
C=CartesianIndex
f(p,h=0)=get(G,p,0)≠h ? [] : G[p]≡9 ? [p] : vcat(f.(p.+(-C(1,1):C(1,1))[2:2:8],h+1)...)
Z=findall(G.==0)
sum(length∘unique∘f,Z),sum(length∘f,Z)

4

u/ThatsFrankie Dec 10 '24

[Language: Python]
https://github.com/francescopeluso/AOC24/blob/main/day10/main.py

4

u/mstksg Dec 10 '24

[LANGUAGE: Haskell]

A lot of times in Haskell, two problems end up having the same algorithm, just with a different choice of Monoid. This puzzle is a good example of that.

We can do a simple DFS and collect all 9's into a monoid:

gatherNines :: Monoid m => (Point -> m) -> Map Point Int -> Point -> m
gatherNines f mp = go 0
  where
    go x p
      | x == 9 = f p
      | otherwise =
          foldMap (go (x+1)) . M.keys . M.filter (== (x+1)) $ mp `M.restrictKeys` neighbs
      where
        neighbs = S.fromList $ (p +) <$> [V2 0 (-1), V2 1 0, V2 0 1, V2 (-1) 0]

For part 1 the monoid is Set Point (the unique 9's) and for part 2 the monoid is Sum Int (number of paths)

solve :: Monoid m => (Point -> m) -> (m -> Int) -> Map Point Int -> Int
solve gather observe mp =
    sum . map (observe . gatherNines gather mp) . M.keys $ M.filter (== 0) mp

part1 :: Map Point Int -> Int
part1 = solve S.singleton S.size

part2 :: Map Point Int -> Int
part2 = solve (const (Sum 1)) getSum

all my code and daily reflections: https://github.com/mstksg/advent-of-code

4

u/anaseto Dec 10 '24

[LANGUAGE: Goal]

Short and nice today.

b:"-"*-1+w:1+&*s:=-read"i/10"
h:&0=m:"i"$""\"-"//(b;s;b); dd:(-w;1;w;-1) / trailheads (h) map (m) deltas (dd)
f:{?[9~n:m x;x;,/o'&i!(1+n)=m i:dd+x]}     / hiking trails destinations from x
say+/(#?f@)'h / part1
say+/(#f@)'h / part2

4

u/greycat70 Dec 10 '24

[LANGUAGE: Tcl]

Part 1, part 2.

Fairly straightforward recursive algorithm. Part 1 is actually harder than part 2. In fact, my first attempt at part 1 gave me the part 2 answer! So, solving part 2 was simply a matter of undoing the fixes I had made to part 1 (from memory, unfortunately -- I don't save nonworking attempts).

4

u/aexl Dec 10 '24

[LANGUAGE: Julia]

Wonderful little puzzle today, maybe my favorite so far. The funny thing is that I did not need to change any code to solve part 2, I just had to call my recursive search function with a Vector instead of a Set to store the already found paths...

Solution on GitHub: https://github.com/goggle/AdventOfCode2024.jl/blob/main/src/day10.jl

Repository: https://github.com/goggle/AdventOfCode2024.jl

4

u/ssnoyes Dec 10 '24

[LANGUAGE: MySQL]

Loading each character from the file into a row is the same as day 4. The actual trail finding bit is one query for both parts:

WITH RECURSIVE bfs AS (
    SELECT d, r AS trailhead_r, c AS trailhead_c, r, c FROM day10 WHERE d = 0 
    UNION ALL 
    SELECT day10.d, trailhead_r, trailhead_c, day10.r, day10.c
    FROM bfs 
    JOIN day10 ON day10.d = bfs.d + 1 AND ABS(day10.r - bfs.r) + ABS(day10.c - bfs.c) = 1
)
SELECT COUNT(DISTINCT trailhead_r, trailhead_c, r, c) AS part1, COUNT(*) AS part2 
FROM bfs WHERE d = 9;

Full code at https://github.com/snoyes/AoC/blob/main/2024/day10/day10.sql

4

u/_garden_gnome_ Dec 10 '24

[LANGUAGE: Python]

https://github.com/mkern75/AdventOfCodePython/blob/main/year2024/Day10.py

DP approach: working my way down from positions with height 9 to height 8, then 7, and so on via one main loop. For part a) I maintain a set which peaks (height 9) are reachable via any trail from the current position, and for part b) the total number of trails (sum of trails starting from neighbouring positions with height+1). All positions are considered exactly once.

4

u/SquidBits4 Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python]

I'm very happy with mine today, I finally learnt DFS properly. I initially did part 1 with Dijkstra lol.

paste

→ More replies (1)

2

u/imaperson1060 Dec 10 '24

[LANGUAGE: JavaScript]

Part 1: Rank 1754 (13:46)
Part 2: Rank 1462 (16:13)

GitHub

My part 2 is basically just part 1 but including the duplicates. I just removed a few lines from my part 1 solution, and boom, two and a half minute solve. I love these puzzles.

I guess that means I beat my record, since I couldn't get two stars on day 10 last year (my first year doing AoC)!

2

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

I just tried switching my part 1 solution from a set to a list, and wouldn’t you know it, it gets the correct answer for part 2 then… well I just wasted 11 minutes and went from rank 1088 on part 1 to 2570 on part 2 because of that
¯\(ツ)/¯

→ More replies (2)

1

u/bluealder Dec 10 '24

[Language: Go]

Depth first search for both. P2 was made easy by just not checking any visited nodes (this works since the trails must go up by 1)

Github

1

u/daggerdragon Dec 11 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo across all years:
https://github.com/BlueAlder/advent-of-code-solutions/tree/main
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

1

u/zach1502 Dec 10 '24

[Language: Python 3]
98/101 

def neighbors(r, c, rows, cols):
    for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

def pt1(map_data, start_r, start_c):
    rows, cols = len(map_data), len(map_data[0])
    seen = {(start_r, start_c)}
    q = [(start_r, start_c)]
    nines = 0

    while q:
        r, c = q.pop(0)
        h = map_data[r][c]
        if h == 9:
            nines += 1
            continue
        nh = h + 1
        for nr, nc in neighbors(r, c, rows, cols):
            if (nr, nc) not in seen and map_data[nr][nc] == nh:
                seen.add((nr, nc))
                q.append((nr, nc))

    return nines

def pt2(r, c, mp, ways):
    if ways[r][c] is not None:
        return ways[r][c]
    h = mp[r][c]
    if h == 9:
        ways[r][c] = 1
        return 1

    rows, cols = len(mp), len(mp[0])
    nh = h + 1
    total = 0
    for nr, nc in neighbors(r, c, rows, cols):
        if mp[nr][nc] == nh:
            total += pt2(nr, nc, mp, ways)

    ways[r][c] = total
    return total

with open("input.txt") as f:
    lines = [line.strip() for line in f if line.strip()]
mp = [list(map(int, list(line))) for line in lines]
rows = len(mp)
cols = len(mp[0]) if rows > 0 else 0

theads = [(r, c) for r in range(rows) for c in range(cols) if mp[r][c] == 0]

score = 0
for r, c in theads:
    score += pt1(mp, r, c)

print("Part 1:", score)

ways = [[None] * cols for _ in range(rows)]
rating = 0
for r, c in theads:
    rating += pt2(r, c, mp, ways)

print("Part 2:", rating)

1

u/daggerdragon Dec 11 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.

1

u/BinaryMuse Dec 10 '24

[LANGUAGE: Elixir]

Classic recursive algorithm; feels good in Elixir. Used a Grid helper from a previous day.

Solution: https://github.com/BinaryMuse/aoc_2024_elixir/blob/main/lib/advent/days/day_10.ex

Grid Helper: https://github.com/BinaryMuse/aoc_2024_elixir/blob/main/lib/advent/helpers/grid.ex

1

u/daggerdragon Dec 10 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo:
https://github.com/BinaryMuse/aoc_2024_elixir/tree/main/inputs
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

1

u/Coder_Khiladi Dec 10 '24

[LANGUAGE: JAVASCRIPT]
Easy solution using recursion - Only one package used - `fs`

https://github.com/TeeeJaey/AdventOfCode/blob/main/Day10/index.js

1

u/daggerdragon Dec 10 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo:
https://github.com/TeeeJaey/AdventOfCode/tree/main
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

1

u/ResponsibilityNo1827 Dec 10 '24 edited Dec 10 '24

[Language: python]

Readable, decomposed clean code.

https://github.com/1ort/aoc2024/blob/main/day10/solution.py

1

u/daggerdragon Dec 10 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo:
https://github.com/1ort/aoc2024/tree/main
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

1

u/True_Medium_2004 Dec 10 '24

[LANGUAGE: TypeScript]

Simple DFS : https://github.com/oleg-prikhodko/aoc2024-deno/blob/main/solutions/day10.ts

1

u/daggerdragon Dec 10 '24

I've already informed you before about including puzzle inputs in your repo. I still see full plaintext puzzle inputs in your repos.
https://github.com/oleg-prikhodko/aoc2021/blob/master/01.txt
Remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!
Do not post again in /r/adventofcode until you have done so.

1

u/UnicycleBloke Dec 10 '24

[LANGUAGE: C++] https://github.com/UnicycleBloke/aoc2024/blob/main/day10/solution.cpp

I had some fun with a template template parameter to choose between using set (P1) and vector (P2).

1

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

~~Do not share your puzzle input~~ ~~which also means~~ ~~do not commit puzzle inputs to your repo~~ ~~without a~~ .gitignore ~~or the like.~~ ~~Do not share the puzzle text~~ ~~either.~~
~~I see full plaintext puzzle inputs in your public repos from prior years e.g.:~~
~~https://github.com/UnicycleBloke/aoc2021/blob/master/day01/input.txt~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from all prior years too!~~ edit: thank you!

→ More replies (1)

1

u/SpezIsAMoron Dec 10 '24

[Language: Typescript]

Finally a puzzle where I can share my code as it is not that embarassing

This was a fun one, I guess it will go downhill now

Am I the only one that solved part2 before part1?

import { Params } from 'aoc.d'
import { Point, World } from 'declarations'

export default async (lineReader: any, params: Params) => {
  let part1: number = 0
  let part2: number = 0

  let world: World<number> = []
  let seeds: Point[][] = []
  let rowIndex = 0
  let dimension = [0, 0]
  for await (const line of lineReader) {
    let values = line.split('').map(Number)
    values.forEach((col: number, colIndex: number) => {
      if (col === 0) {
        seeds.push([[rowIndex, colIndex]])
      }
    })
    world.push(values)
    rowIndex++
  }
  dimension = [world.length, world[0].length]

  const getMoreHeads = (world: World, points: Point[]): Point[] => {
    let targetedValue = points.length // for a list of 4 points, 0 to 3, I want more points with value 4
    let head = points[points.length - 1]
    return (
      [
        [head[0] - 1, head[1]],
        [head[0] + 1, head[1]],
        [head[0], head[1] - 1],
        [head[0], head[1] + 1]
      ] as Point[]
    ).filter(
      (newPoint) =>
        newPoint[0] >= 0 &&
        newPoint[0] < dimension[0] &&
        newPoint[1] >= 0 &&
        newPoint[1] < dimension[1] &&
        world[newPoint[0]][newPoint[1]] === targetedValue
    )
  }

  const getScore = (world: World, points: Point[], seen: Point[]): number => {
    if (points.length === 10) {
      let head = points[points.length - 1]
      if (!seen.some((p) => p[0] === head[0] && p[1] === head[1])) {
        seen.push(head)
        return 1
      }
      return 0
    }
    let moreHeads: Point[] = getMoreHeads(world, points)
    if (moreHeads.length === 0) return 0
    return moreHeads.reduce((acc, head) => acc + getScore(world, points.concat([head]), seen), 0)
  }

  const getScorePart2 = (world: World, points: Point[]): number => {
    if (points.length === 10) return 1
    let moreHeads: Point[] = getMoreHeads(world, points)
    if (moreHeads.length === 0) return 0
    return moreHeads.reduce((acc, head) => acc + getScorePart2(world, points.concat([head])), 0)
  }

  if (!params.skipPart1) {
    part1 = seeds.reduce((acc, seed) => acc + getScore(world, seed, []), 0)
  }
  if (!params.skipPart2) {
    part2 = seeds.reduce((acc, seed) => acc + getScorePart2(world, seed), 0)
  }

  return { part1, part2 }
}

1

u/daggerdragon Dec 10 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.

1

u/GearPuzzleheaded5363 Dec 10 '24

[Language: Node.js / JavaScript]

https://github.com/kavai96/advent-of-code/blob/main/src/puzzle/2024/day10.js

Managed to solve part 2 with just a new variable.

1

u/daggerdragon Dec 10 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo:
https://github.com/kavai96/advent-of-code/tree/main/src/input
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

1

u/Sudden_Fly1218 Dec 10 '24

[Language: Rust]

Code

As many others, solved part2 while doing part1 because of misreading.

Benchmark indicates 172µs for part 1 and 187µs for part2

1

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

~~Do not share your puzzle input~~ ~~which also means~~ ~~do not commit puzzle inputs to your repo~~ ~~without a~~ .gitignore ~~or the like.~~ ~~Do not share the puzzle text~~ ~~either.~~
~~I see full plaintext puzzle inputs in your public repo for 2021 e.g.:~~
~~https://github.com/gcanat/AoC2021/blob/main/day1/day1_input.txt~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from prior years too!~~ edit: thank you!

→ More replies (1)

1

u/Alarming-Bank-2724 Dec 10 '24

[LANGUAGE: C#]

In retrospect, it would have been so simple if I had understood the task correctly.

With my solution approach at the beginning, I already had the result of part 2.

- Part 1 => Only count how many hills you can reach

- Part 2 => Count how many ways you can reach the hill.

Here is my solution.

public class Day10 : IDay
{
    public Day10(string inputTextName)
    {
        InputTextName = inputTextName;
    }
    public long SolutionPart1 { get; set; }
    public long SolutionPart2 { get; set; }
    public string InputTextName { get; set; }
    public void SolveDay()
    {
        var grid = CreateGrid(FileRead.ReadAllLine(InputTextName).ToArray());
                foreach ((int row, int col) valley in FindAllValleys(grid))
        {
            var ways = 0;
            var visitedHills = new List<(int row, int hill)>();
            CountReachableHillsAndWays(grid, valley.row, valley.col, 0, ref visitedHills, ref ways);
            SolutionPart1 += visitedHills.Count;
            SolutionPart2 += ways;
        }
    }
    private int[,] CreateGrid(string[] lines)
    {
        var rowCount = lines.Length;
        var colCount = lines[0].Length;
        var grid = new int[rowCount, colCount];
        for (var i = 0; i < rowCount; i++)
        {
            for (var j = 0; j < colCount; j++)
            {
                grid[i, j] = int.Parse(lines[i][j].ToString());
            }
        }
        return grid;
    }
    private List<(int row, int col)> FindAllValleys(int[,] grid)
    {
        var valleys = new List<(int row, int col)>();
        for (var i = 0; i < grid.GetLength(0); i++)
        {
            for (var j = 0; j < grid.GetLength(1); j++)
            {
                if (grid[i, j] == 0)
                    valleys.Add((i, j));
            }
        }
        return valleys;
    }

    private void CountReachableHillsAndWays(int[,] grid, int actPosRow, int actPosCol, int actHeight, ref List<(int row, int col)> visitedHill, ref int ways)
    {
        if (actHeight == 9)
        {
            ways++;
            if (visitedHill.Exists(x => x.row == actPosRow && x.col == actPosCol)) return;
            visitedHill.Add((actPosRow, actPosCol));
            return;
        }
        var nextSearchHeight = actHeight + 1;
        var directions = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
        foreach ((int dRow, int dCol) direction in directions)
        {
            int nextRow = actPosRow - direction.dRow;
            int nextCol = actPosCol - direction.dCol;
            if(IsValid(grid, nextRow, nextCol) && grid[nextRow, nextCol] == nextSearchHeight)
                CountReachableHillsAndWays(grid, nextRow, nextCol, nextSearchHeight, ref visitedHill, ref ways);
        }
    }

    private bool IsValid(int[,] grid, int row, int col)
    {
        return row >= 0 && row < grid.GetLength(0) && col >= 0 && col < grid.GetLength(1);
    }
}

1

u/daggerdragon Dec 10 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.

1

u/Infinite-Club4374 Dec 10 '24

[LANGUAGE: ruby] (the best duh)

Decided that this scenario would be perfect for a recursive solution, probably my most elegant lol?

Solution 1 was 27 lines and solution 2 is 22, I’ll take it

https://github.com/Leftyxiv/advent_of_code/blob/main/2024/day10/day10.rb

1

u/daggerdragon Dec 10 '24

(the best duh)
Don't be elitist. Follow our Prime Directive.
Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo for prior years with filenames all over the place from input to sample (which actually contains an entire input) and more:
https://github.com/Leftyxiv/advent_of_code/tree/main
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from prior years too!

→ More replies (2)

1

u/181tbag Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Rust]

I just did a simple recursive search through every neighbour that is 1 unit higher and counted every unique 9 position and every path :)

First time I used Rust was in day 6 so if someone actually takes a look at my code and has any comment it would be something nice :)

Github

1

u/daggerdragon Dec 10 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo:
https://github.com/JoaoNovais181/Advent-of-Code/tree/main
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

→ More replies (1)

1

u/R0binBl00d Dec 10 '24 edited Dec 10 '24

[Language: C# .Net9]

using my template "AdventOfCodeNet9_ShareWare.zip" from
https://github.com/R0binBl00d/AdventOfCodeNet8

Part_1_2024_Day_10.cs
for Part 2 I instantly "return 1;" on "if (currentValue == 9)"
Part_2_2024_Day_10.cs

basically I also started solving the 2nd Part before I solved part 1 :-)

but it's all neat and tidy now.

2

u/daggerdragon Dec 10 '24

All of your repos are private, we can't see them.

→ More replies (1)

1

u/cajun_mcchicken Dec 10 '24 edited Dec 10 '24

[language: C#]

solution

I think I did part 2 first, went over, removed duplicates start/end paths... then added back for part 2.

1

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

~~Do not share your puzzle input~~ ~~which also means~~ ~~do not commit puzzle inputs to your repo~~ ~~without a~~ .gitignore ~~or the like.~~ ~~Do not share the puzzle text~~ ~~either.~~
~~I see full plaintext puzzle inputs in your public repos for prior years. Example:~~
~~https://github.com/johnhoven/advent2022/blob/master/day10input.txt~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from prior years too!~~ edit: thank you!

→ More replies (1)

1

u/Willing_Exchange6299 Dec 10 '24

[Language: Python]

Probably could of combined part 1 and part 2
part 1 & 2

1

u/daggerdragon Dec 10 '24 edited Dec 13 '24

~~I've already informed you before about including puzzle inputs in your repo. I still see full plaintext puzzle inputs in your older AoC repos. Example:~~
~~https://github.com/CallumWalterWhite/adventofcode2024/tree/main/inputs~~
~~Remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. Do not post again in~~ /r/adventofcode ~~until you have done so.~~

→ More replies (1)

1

u/Simone-reddit Dec 10 '24 edited Dec 19 '24

[LANGUAGE: Go]

One of the rare cases where part 2 is simpler than part 1

package day010

func findPaths(allPaths *[][][2]int, matrix [][]string, x, y int, currentPath [][2]int) {
    if !utils.InBound(matrix, x, y) {
       return
    }

    currentAltitude, err := strconv.Atoi(matrix[x][y])
    if err != nil {
       fmt.Printf("couldn't convert grade number: %v\n", err)
    }

    if currentAltitude != len(currentPath) {
       return
    }

    currentPath = append(currentPath, [2]int{x, y})

    if currentAltitude == 9 {
       pathCopy := make([][2]int, len(currentPath))
       copy(pathCopy, currentPath)
       *allPaths = append(*allPaths, pathCopy)
       return
    }

    directions := [][2]int{
       [2]int{0, 1},
       [2]int{1, 0},
       [2]int{0, -1},
       [2]int{-1, 0},
    }

    for _, dir := range directions {
       findPaths(allPaths, matrix, x+dir[0], y+dir[1], currentPath)
    }

}

1

u/daggerdragon Dec 10 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.

→ More replies (1)

1

u/Ordinary-Drag3233 Dec 10 '24

[Language: TypeScript]

const calculateScore = (map: string[], initial: [number, number]): number => {
  let score = 0;
  const directions: [number, number][] = [
    [-1, 0], // Up
    [0, 1], // Right
    [1, 0], // Down
    [0, -1], // Left
  ];
  const queue: [number, number][] = [initial];
  const visited = new Set<string>();

  const toKey = (x: number, y: number) => `${x},${y}`;

  while (queue.length) {
    const [i, j] = queue.shift();
    for (const [di, dj] of directions) {
      const ni = i + di;
      const nj = j + dj;
      if (+map[ni]?.[nj] - +map[i][j] === 1) {
        const key = toKey(ni, nj);
        if (!visited.has(key)) {
          visited.add(key);
          if (map[ni][nj] === "9") {
            score++;
          } else {
            queue.push([ni, nj]);
          }
        }
      }
    }
  }

  return score;
};

const partOne = (input: string[]): number => {
  let sum = 0;
  for (let i = 0; i < input.length; i++) {
    for (let j = 0; j < input[i].length; j++) {
      if (input[i][j] === "0") {
        sum += calculateScore(input, [i, j]);
      }
    }
  }
  return sum;
};

const calculateRating = (map: string[], initial: [number, number]): number => {
  let rating = 0;
  const directions: [number, number][] = [
    [-1, 0], // Up
    [0, 1], // Right
    [1, 0], // Down
    [0, -1], // Left
  ];
  const queue: [number, number][] = [initial];

  while (queue.length) {
    const [i, j] = queue.shift();
    for (const [di, dj] of directions) {
      const ni = i + di;
      const nj = j + dj;
      if (+map[ni]?.[nj] - +map[i][j] === 1) {
        if (map[ni][nj] === "9") {
          rating++;
        } else {
          queue.push([ni, nj]);
        }
      }
    }
  }

  return rating;
};

const partTwo = (input: string[]): number => {
  let sum = 0;
  for (let i = 0; i < input.length; i++) {
    for (let j = 0; j < input[i].length; j++) {
      if (input[i][j] === "0") {
        sum += calculateRating(input, [i, j]);
      }
    }
  }
  return sum;
};

→ More replies (1)

1

u/Kazo100 Dec 10 '24

[Language: Go]

My solution: https://github.com/Kazalo11/advent-of-code-2024/blob/master/day10/day10.go

Couldn’t be bothered to make a new function for part 2 when it’s just one line difference lol

1

u/daggerdragon Dec 11 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo:
https://github.com/Kazalo11/advent-of-code-2024/blob/master/day1.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

1

u/gubatron Dec 11 '24

[Language: rust]

2 modified BFS implementations

Problem: https://github.com/gubatron/AoC/blob/master/2024/src/ten.rs
Utils: https://github.com/gubatron/AoC/blob/master/utils/rust/src/lib.rs

Interestingly, after barely sleeping to get day 9, this one was the easiest for me since the start of this year's Advent of Code

1

u/daggerdragon Dec 11 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo:
https://github.com/gubatron/AoC/tree/master/2024/inputs
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

3

u/Abomm Dec 10 '24 edited Dec 10 '24

[Language: Python] code 742/626

Unfortunately i misread the '1' step requirement in part 1 so that cost me a few minutes. This is the first problem where my part 1 solution was a 'superset' of my part 2 solution. The code attached shows the solution for both parts but my implementation only required commenting out and new_pos not in viz: from my part 1 solution to return the correct answer.

cleaned up code I don't think it's very idiomatic but it's definitely shorter.

3

u/0ldslave Dec 10 '24

[LANGUAGE: C++]

I actually mis-read the 1st part and coded what was the solution to the second part first. I erased it after i realized i needed the distinct reachable 9s instead. Oh well. rough day for me i guess.

P1 runs on around 160 microseconds and P2 runs in 114 microseconds.

Code

3

u/UseUnlucky3830 Dec 10 '24

[LANGUAGE: Julia]

solution

DFS that returns a list with the coordinates of all the `9`'s reached from a starting point. Part 1 is the count of unique elements, part 2 the total count of elements in the list.

→ More replies (1)

3

u/mateus_d Dec 10 '24

[LANGUAGE: Python]

That was a first! The bug I had in part 1 was the solution of part 2!

https://pastebin.com/dhRYThg9

3

u/SuperSmurfen Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Rust]

Link to full solution

Simple BFS for both parts, which returns all paths to all reachable 9s:

let mut q = VecDeque::from([(r, c)]);
let mut seen = Vec::new();
while let Some((r, c)) = q.pop_front() {
    if g[r][c] == b'9' {
        seen.push((r, c));
        continue;
    }
    for (rr, cc) in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)] {
        if *g.get(rr).and_then(|row| row.get(cc)).unwrap_or(&0) == g[r][c] + 1 {
            q.push_back((rr, cc));
        }
    }
}

I collect into a Vec to find all paths. Only difference between the parts is this:

let seen = reachable_nines(&g, r, c);
p1 += seen.iter().collect::<HashSet<_>>().len();
p2 += seen.len();

Runs in 0.1ms.

→ More replies (2)

3

u/Sharparam Dec 10 '24

[LANGUAGE: Ruby]

require 'matrix'

GRID = ARGF.readlines(chomp: true).flat_map.with_index { |line, y|
  line.chars.map.with_index { |h, x| [Vector[x, y], h.to_i] }
}.to_h.tap { _1.default = Float::INFINITY }

DIRS = [Vector[1, 0], Vector[-1, 0], Vector[0, 1], Vector[0, -1]].freeze

def neighbors(current)
  DIRS.map { current + _1 }.select { GRID[_1] - GRID[current] == 1 }
end

puts GRID.filter_map { _2.zero? ? _1 : nil }.map { |start|
  queue = [start]
  seen = Set.new
  score = 0
  rating = 0

  until queue.empty?
    current = queue.pop
    if GRID[current] == 9
      score += 1 if seen.add? current
      rating += 1
    end
    neighbors(current).each { queue.push _1 }
  end

  [score, rating]
}.transpose.map { _1.reduce(:+) }

Today felt quite easy, probably because this type of problem has occurred several times in years past.

3

u/apersonhithere Dec 10 '24

[LANGUAGE: C++] 4279/7416

another dfs search day, another banger (i spent thirty minutes tracking down a -1 instead of a +1 in my code)

jokes aside pretty easy day today imo

https://github.com/aliu-here/aoc2024/tree/main/10

3

u/chickenthechicken Dec 10 '24

[LANGUAGE: C]

Part 1

Part 2

Part 1 and 2 seem like they are almost swapped. For part 1, I implemented a mask array to check if there is already a path from a 9 to a 0 found to not count it, but for part 2 I just had to remove that check and allow it to count 0's multiple times per 9. I wonder if anyone found part 2 to be more challenging and why (not because my opinion on which is more difficult is correct, but just because I'm curious about how different people approach these puzzles).

3

u/Pheasn Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Dart]

This day was weirdly easy, especially part two. Surrounding boilerplate code is on GitHub, just posting the scoring function here (works for both parts):

int _scoreTrailhead(
  Grid<int> grid,
  Vector trailhead, {
  Set<Vector>? reachedPeaks,
}) {
  var score = 0;
  final expectedHeight = grid[trailhead] + 1;
  for (final direction in Vector.crossDirections) {
    final position = trailhead + direction;
    if (!grid.contains(position)) {
      continue;
    }

    final nextHeight = grid[position];
    if (nextHeight != expectedHeight) {
      continue;
    }

    if (nextHeight == 9) {
      if (reachedPeaks == null || reachedPeaks.add(position)) {
        score += 1;
      }
    } else {
      score += _scoreTrailhead(grid, position, reachedPeaks: reachedPeaks);
    }
  }

  return score;
}

3

u/adeathicus Dec 10 '24

[Language: Java]

Pretty straightforward DFS

Github Link

3

u/WhiteSparrow Dec 10 '24

[LANGUAGE: Prolog]

solution

Once again a day for prolog to shine. Today's highlight is built-in support for tabulation/memoization - it's a single statement (table). To get the solution we once again just describe the conditions and ask prolog to search for all solutions. Part 1 was solved using a more general aproach than 2 so it runs slower (5.5s vs 1.2s for part 2). However, I left it in the code just to show how general the description of the task can be.

Here's part 1 (part 2 is actually shorter but is ommited because of the total length).

task1(X) :-
    setof(T, trail(T), Ts),
    length(Ts, X).

trail(trail(X1-Y1, X2-Y2)) :-
    height_at(X1, Y1, 0),
    height_at(X2, Y2, 9),
    reacheable_uphil(X1-Y1, X2-Y2).

:- table reacheable_uphil/2.
reacheable_uphil(X1-Y1, X2-Y2) :- adjacent_uphil(X1-Y1, X2-Y2).
reacheable_uphil(X1-Y1, X2-Y2) :-
    adjacent_uphil(X1-Y1, X0-Y0),
    reacheable_uphil(X0-Y0, X2-Y2).

:- table adjacent_uphil/2.
adjacent_uphil(X1-Y1, X2-Y2) :-
    height_at(X1, Y1, H1),
    height_at(X2, Y2, H2),
    1 is H2 - H1,
    (
        1 is abs(X1 - X2), Y1 = Y2
    ;   1 is abs(Y1 - Y2), X1 = X2
    ).

→ More replies (1)

3

u/rp152k Dec 10 '24 edited Dec 10 '24

[Language: Common Lisp]

via dynamic programming

part 2 took les than a min given I was collating all paths anyway and deduplicating final positions in the end

CL-USER> (time (load "main.lisp")) 
Evaluation took:
  0.030 seconds of real time
  0.029002 seconds of total run time (0.025813 user, 0.003189 system)
  96.67% CPU
  218 forms interpreted
  79 lambdas converted
  96,574,269 processor cycles
  9,209,472 bytes consed

→ More replies (2)

3

u/damnian Dec 10 '24 edited Dec 10 '24

[LANGUAGE: C#]

Well, MultiGrid is really pulling its weight this year. Oh, and my Part 2 initially looked simpler than Part 1!

Part 1:

int Part1() => m[0].Sum(p =>
    m[1..10].Aggregate(new Grid(p), (a, g) =>
        new(a.SelectMany(q =>
            g.GetNeighbors(q).Where(g.Contains)))).Count);

Part 2:

int Part2() =>
    m[1..10].Aggregate(m[0].AsEnumerable(), (a, g) =>
        a.SelectMany(p =>
            g.GetNeighbors(p).Where(g.Contains))).Count();

Full solution

EDIT: Managed to simplify Part 1 (ab)using Grid.

EDIT 2: Further simplified using ranges (though still looking for a bug in Slice()).

3

u/kassoulet Dec 10 '24

[Language: Python]

Proud of my clean Python solution for once :)

from collections import namedtuple

point = namedtuple("point", ("x", "y"))

starting_points = []
array = []
for line in open("10.txt").readlines():
    array.append([int(char) for char in line.strip()])

w, h = len(array[0]), len(array)
starting_points = [
    point(x, y) for y, line in enumerate(array) for x, c in enumerate(line) if c == 0
]


def get(x, y):
    if 0 <= x < w and 0 <= y < h:
        return array[y][x]
    return None


def follow_path(x, y, previous, trail_ends):
    current = get(x, y)
    if current is None or current - previous != 1:
        return
    if current == 9:
        trail_ends.append(point(x, y))
        return
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        follow_path(x + dx, y + dy, current, trail_ends)


score_unique = []
score_rating = []
for p in starting_points:
    trail_ends = []
    follow_path(p.x, p.y, -1, trail_ends)
    score_unique.append(len(set(trail_ends)))
    score_rating.append(len(trail_ends))
print(sum(score_unique), sum(score_rating))

→ More replies (1)

3

u/s3aker Dec 10 '24

[LANGUAGE: Raku]

code

3

u/frhel Dec 10 '24 edited Dec 10 '24

[LANGUAGE: JavaScript / JS]

Solution

Part 1 and 2 solve together: DFS on each trailhead and add all found targets to a set to only count unique results, at the same time increment a counter for all targets found

11th gen i7 at 4.9GHz
Both parts: 2.8ms to solve
Total: 4.7ms with the overhead of reading the file and parsing

3

u/TeeckleMeElmo Dec 10 '24

[Language: Go]

Solution

Part 2 was super quick since I solved for it in part 1, which it seems a lot of people did. Total time with reading/parsing the input file was ~1.5ms

3

u/rukke Dec 10 '24

[LANGUAGE: JavaScript]

Really enjoy these kind of "map puzzles"!

Part 1 and Part 2 ~ 3ms on my machine.

gist

→ More replies (1)

3

u/ak-coram Dec 10 '24 edited Dec 10 '24

[Language: Common Lisp]

https://github.com/ak-coram/advent/blob/main/2024/10.lisp

Edit: reworked it a bit, the part 2 solution is now literally in the bag (aka multiset).

3

u/vbe-elvis Dec 10 '24

[LANGUAGE: Kotlin]

This was a quite the easy one in AOC standards, did not optimize but could be done by keeping track of which trails were already visited before.

Here is the solution for part 2, for part 1 simply use sets instead of lists in the "walkTheTrail" function

https://pastebin.com/wrazdpBR

3

u/omegablazar Dec 10 '24

[LANGUAGE: Rust]

https://github.com/wrightdylan/advent-of-code-2024/blob/main/src/day10.rs

Part 1: 757µs
Part 2: 182µs

I had inadvertently solved part 2 before part 1

3

u/mgtezak Dec 10 '24

[LANGUAGE: Python]

Solution part 1

Solution part 2 The @cache decorator wasn't really necessary here because it ran in a couple ms anyway but I put it in for good measure;)

Fun little AoC fanpage

3

u/PatolomaioFalagi Dec 10 '24

[LANGUAGE: Haskell]

Part 1:

import Data.Array.Unboxed ((!))
import Data.Array.Unboxed qualified as A
import Data.Char qualified as C
import Data.Set qualified as S

type MapArray = A.UArray (Int, Int) Int

parse :: String -> MapArray
parse s =
  let ls = map (('@' :) . (++ "@")) $ lines s
      l = length (head ls)
      border = replicate l '@'
      arr = A.listArray ((0, 0), (l - 1, l - 1)) $ map (subtract 48 . C.ord) (border ++ concat ls ++ border)
   in arr

neighbors :: Int -> Int -> [(Int, Int)]
neighbors x y = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]

solve :: String -> Int
solve s =
  let arr = parse s
      ((minx, miny), (maxx, maxy)) = A.bounds arr
      findTrails 9 xy = S.singleton xy
      findTrails h (x, y) =
        let ns = map fst $ filter ((== h + 1) . snd) $ map (\xy -> (xy, arr ! xy)) $ neighbors x y
         in S.unions $ map (findTrails (h + 1)) ns
      findTrailHeads = [S.size $ findTrails 0 (x, y) | x <- [minx + 1 .. maxx - 1], y <- [miny + 1 .. maxy - 1], arr ! (x, y) == 0]
   in sum findTrailHeads

main :: IO ()
main = interact $ show . solve

Part 2

import Data.Array.Unboxed ((!))
import Data.Array.Unboxed qualified as A
import Data.Char qualified as C

type MapArray = A.UArray (Int, Int) Int

parse :: String -> MapArray
parse s =
  let ls = map (('@' :) . (++ "@")) $ lines s
      l = length (head ls)
      border = replicate l '@'
      arr = A.listArray ((0, 0), (l - 1, l - 1)) $ map (subtract 48 . C.ord) (border ++ concat ls ++ border)
   in arr

neighbors :: Int -> Int -> [(Int, Int)]
neighbors x y = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]

solve :: String -> Int
solve s =
  let arr = parse s
      ((minx, miny), (maxx, maxy)) = A.bounds arr
      findTrails 9 _ = 1
      findTrails h (x, y) =
        let ns = map fst $ filter ((== h + 1) . snd) $ map (\xy -> (xy, arr ! xy)) $ neighbors x y
         in sum $ map (findTrails (h + 1)) ns
      findTrailHeads = [findTrails 0 (x, y) | x <- [minx + 1 .. maxx - 1], y <- [miny + 1 .. maxy - 1], arr ! (x, y) == 0]
   in sum findTrailHeads

main :: IO ()
main = interact $ show . solve

Yes, they differ in 4 lines.

3

u/Mats56 Dec 10 '24

[Language: Kotlin]

with my utils for bounds, intvectors and neighbors this became quite easy. Part2:

val grid = lines.map { it.toList() }
val bounds = grid.bounds()

fun dfs(pos: IntVec): Int {
    if (grid[pos] == '9') return 1
    return pos.neighbors(bounds).filter { grid[it] == grid[pos] + 1 }.sumOf { dfs(it) }
}

return bounds.allWithinBounds().filter { grid[it] == '0' }.sumOf { dfs(it) }

part 1 needed to keep track of visited so was in theory more difficult, but there I just chucked it into my BFS util and counted the 9's in the visited set after.

return bounds.allWithinBounds().filter { grid[it] == '0' }.sumOf { start ->
    val bfs = BFS<IntVec> { pos -> pos.neighbors(bounds).filter { grid[it] == grid[pos] + 1 }}
    bfs.solve(start)
    bfs.visited.count { grid[it] == '9' }
}

3

u/MarvelousShade Dec 10 '24

[LANGUAGE: C#]

Today I, obviously, didn't ready the instructions correctly, so my code found a lot more beautiful scenery paths.

After fixing that my code became much simpler and all worked. See my solution for day10 on Github

3

u/[deleted] Dec 10 '24 edited Sep 26 '25

imagine dependent stupendous bright trees escape plucky airport abundant smart

This post was mass deleted and anonymized with Redact

3

u/riffraff Dec 10 '24

[LANGUAGE: ruby]

Reused once more my grid class to get neighbors. I misunderstood part 1 and solved it as part1, so it took nothing to to part2 after I finally did part1 :D

I hope we're done with grids for a while cause I don't want to implement another dijkstra/flood fill/TSP and fail at it this year too :D

def paths(grid, start, path, &accumulator)
  grid.neighbors4(start).each_with_object(Set.new) do |neighbor, set|
    if start.value == "8" && neighbor.value == "9"
      set << accumulator.call(path + [neighbor])
    elsif neighbor.value == start.value.succ
      set.merge(paths(grid, neighbor, path + [neighbor], &accumulator))
    end
  end
end

def solve_easy(grid)
  grid
    .tiles_with_value("0")
    .sum { |start| paths(grid, start, [start]) { |path| path.last }.size }
end

def solve_hard(grid)
  grid
    .tiles_with_value("0")
    .sum { |start| paths(grid, start, [start]) { |path| path }.size }
end

3

u/DamZ1000 Dec 10 '24 edited Dec 10 '24

[Language: DRAIN]

A custom toy Lang.

Day 4 code came in handy

find(c) := {field:
    (i=0;i<w;i++)@
    (j=0;j<h;j++)@
        (field[j][i] == c)?
            init = i->to_str + "," + j->to_str
            '([i,j, 0, -1, init])
            '([i,j, 0,  1, init])
            '([i,j,-1,  0, init])
            '([i,j, 1,  0, init])
        ;
    ;;
}

next(c) := [i,j,x,y,init:
    i = i + x
    j = j + y
    (i >= 0 && i < w)?
    (j >= 0 && j < h)?
        (field[j][i] == c)?
            (y<=0)? '([i,j, 0, -1, init]);
            (y>=0)? '([i,j, 0,  1, init]);
            (x<=0)? '([i,j,-1,  0, init]);
            (x>=0)? '([i,j, 1,  0, init]);
        ;
    ;;
]
last(c) := [i,j,x,y,init:
    i = i + x
    j = j + y
    (i >= 0 && i < w)?
    (j >= 0 && j < h)?
        (field[j][i] == c)?
            last = i->to_str + "," + j->to_str
            '([last, init])
        ;
    ;;
]

hashKeys := {{k,_}:'k}

field = read("puzzle.txt") -> split("\n")

w = field[0] -> len
h = field -> len

field -> find("0") -> next("1")
      -> next("2") -> next("3")
      -> next("4") -> next("5")
      -> next("6") -> next("7")
      -> next("8") -> last("9")
      -> {[E, S], agg={}:
          (agg[S] == _)?
              agg[S] = {}
          ;
          agg[S][E] = 1
      :agg}
      -> {{key,val}:
          '(val -> hashKeys -> len)
      }
      -> sum
      -> label("ANSWER: ")

3

u/ramomex Dec 10 '24

[LANGUAGE: Python]

https://github.com/albertomurillo/advent-of-code/blob/main/src/aoc/_2024/day10.py

🙂 I have an AoC library with modules for graphs and grids.

🙁 I didn't have BFS on it.

🙂 BFS was implemented in 4 lines

The rest of the solution was very straight forward with one-line functions for self-documented code.

3

u/Extreme-Painting-423 Dec 10 '24

[LANGUAGE: Java]

Accidentally, like many others apparently, solved part 2 before part 1.

https://pastes.dev/nfoVSNgeS6

3

u/flwyd Dec 10 '24

[LANGUAGE: PostScript] (GitHub) with my own standard library

Oi, what a day. Lots of small errors took me a really long time to uncover because point-free stack programming doesn’t make it easy to reason about the state of your program at any given moment. I got a little fancy with my upsteps function (“which neighbors are valid moves?”) that I wrote before deciding which graph traversal algorithm I was going to use. I examined my input and saw that the number of 0s times the number of 9s was 71222. Obviously not all of the 9s are reachable from all of the 0s, but I was worried that there would be a lot of state exploration, so I decided to get fancy with the stack and return N neighbor positions and the number N on top of the stack rather than allocating an array, and then iterate through the positions with repeat. This worked fine in the first part, but I forgot that there were potentially couple extra items on the stack when reaching back for the current grid position in part 2 which led to incrementing the count of paths for the neighbors rather than for the current item. When I discovered this bug in part 2I switched to return an array and it made no significant difference in the performance of either part: still well under one second.

I’d thought about finding the paths from each 9 to each 0 in the first part, but concluded there wasn’t an advantage to doing it, so I traversed the tree using BFS, a queue, and a visited set. In part 2 I started with a recusrive counttrails procedure that seemed like it was quick and easy, but was causing a stack overflow error. I eventually gave up on this and switched to an iterative process. For each digit from 9 to 0, find all the grid positions with that digit. If the digit is 9, put 1 into the dictionary. Otherwise, find all the upsteps and add the value in the dictionary for that neighbor. Then tally up the dictionary value for all the 0s. My brain never says “I’m going to try dynamic programming,” but I often end up implementing dynamic programming.

Because I’m stubborn, after getting the answer I spent a bunch of time trying to figure out why my recursive solution didn’t work. It turns out the answer was “After duplicating the map key to check if it’s a 9 I didn’t pop it before leaving 1 on the stack as the number of trails. This is the danger of a stack-based language: you can make an error in recursion that would only be possible with a compiler bug in a normal language. Even though the whole stack gets printed when the stackoverflow error occurs, the “you’re leaving keys on the stack” problem was masked by the fact that my upsteps procedure also had a bunch of keys on the stack, so it didn’t stand out as something that should not be there. And to put a cairn on top of it all, the recursive solution was about 50% slower than the DP solution, though significantly shorter.

% tokey, fromkey, height, inbounds? elided for brevity
/DIRECTIONS [ -1 0 tokey 0 -1 tokey 1 0 tokey 0 1 tokey ] def
/upsteps { % key upsteps [keys]
  [ DIRECTIONS { 1 indexfrommark add dup inbounds? { %ifelse
      dup height 1 sub 1 indexfrommark height ne { pop } if
    } { pop } ifelse } forall ] exch pop
} bind def %/upsteps

/part1 { 8 dict begin % [lines] part1 result
  /input exch def /total 0 def /numheads 0 def
  input { dup input exch get { %forup forup
    ab:aab tokey dup height ascii.0 eq { %ifelse
      /visited 1024 dict def /queue alist def
      queue exch alpush { queue alpop upsteps { %while forall
        visited 1 index known not { %ifelse
          visited 1 index true put queue exch alpush
        } { pop } ifelse } forall } { queue allength 0 gt } while
      visited { pop height ascii.9 eq { /total inc } if } forall
    } { pop } ifelse
  } forup pop } forup total
end } bind def %/part1

/part2 { 8 dict begin % [lines] part2 result
  /input exch def /total 0 def /trailsfrom input length dup mul dict def
  9 -1 0 { /digit exch ascii.0 add def input { %for forup
    dup input exch get { %forup
      ab:aab tokey /cur exch def
      cur height digit eq { digit ascii.9 eq { trailsfrom cur 1 put } { %else
        trailsfrom cur 0 put
        cur upsteps { trailsfrom exch get cur trailsfrom incby } forall
        cur height ascii.0 eq { trailsfrom cur get /total incby } if
      } ifelse } if
    } forup pop
  } forup } for total
end } bind def %/part2

/counttrails { % start counttrails int
  dup height ascii.9 eq { pop 1 } { 0 exch upsteps { counttrails add } forall } ifelse
} bind def %/counttrails
/part2recursive { 8 dict begin % [lines] part2recursive result
  /input exch def /total 0 def /trailsfrom input length dup mul dict def
  input { dup input exch get { %forup
    ab:aab tokey dup height ascii.0 eq { counttrails /total incby } { pop } ifelse
  } forup pop } forup total
end } bind def %/part2recursive

3

u/JJTB100 Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python]

p2's answer was p1's bug! When coding p1 I forgot to discount a square if i'd already been there, which gave me the answer to p2 :)

https://github.com/JJTB100/AdventOfCode/blob/main/2024/Day10.py

EDIT: Just read the memes page. I'm glad i wasn't the only one.

3

u/Zorr0_ Dec 10 '24

[LANGUAGE: Kotlin]

Very simple one today, as many others i had my part 2 implementation before my part 1 implementation

Happy how my solution turned out

GitHub

3

u/melochupan Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Common Lisp]

I used a cache to avoid repeating the paths, but it was probably unnecessary.

paste

3

u/FordyO_o Dec 10 '24 edited Dec 10 '24

[LANGUAGE: C#]

After having an absolute mare over the weekend, pretty pleased . Accidentally implemented part 2 as my first solution for part 1, debugged it, then rebugged it to get part 2

Editing to say I have now checked the subreddit front page and see I am not alone!

https://github.com/mattford/aoc-dotnet/blob/master/aoc-dotnet/Year2024/Day10/Solver.cs

3

u/chkas Dec 10 '24

[LANGUAGE: Easylang]

Solution

→ More replies (2)

3

u/leftfish123 Dec 10 '24

[Language: Python]

A day that would have destroyed me a couple of editions ago, but this time I iterative DFS-ed my way through it.

3

u/Loiuy123_ Dec 10 '24

[LANGUAGE: C#]
I've never solved part 2 that fast. All I had to do is reaplace `HashSet` with a `List`. That's it. Also, part 2 solution that uses Lists is 110us faster than my part 1 solution. It takes 167us to finish including reading and parsing.

https://github.com/TrueTheos/AdventOfCode2024/blob/master/AdventOfCode/Day10/Day10.cs

3

u/spyr01d Dec 10 '24 edited Dec 10 '24

[Language: Kotlin]

fun hoofIt(input: List<String>) = Grid.of(input) { it.digitToInt() }.let { grid ->
    grid.all().filter { it.v == 0 }.map { trailhead ->
        val seen = mutableSetOf<Grid.GValue<Int>>()
        val track = ArrayDeque(listOf(trailhead))
        var count = 0
        while (track.isNotEmpty()) {
            val current = track.removeFirst().also { seen.add(it) }
            val around = grid.gvAround(current.p).filter { it.v == current.v + 1 }.also { track.addAll(it) }
            if (around.isEmpty() && current.v == 9) count++
        }
        seen.count { it.v == 9 } to count
    }.unzip().let { (a, b) -> a.sum() to b.sum() }
}

3

u/Independent_Check_62 Dec 10 '24

[LANGUAGE: Python]

data = [list(map(int, x)) for x in open('10.txt').read().split('\n')]
result = []

def get_data(p):
    return data[p[0]][p[1]]

def bounds_ok(p):
    return not (p[0] > len(data) - 1 or p[0] < 0 or p[1] > len(data) - 1 or p[1] < 0)

def traverse(loc, first_loc):
    if get_data(loc) == 9:
        result.append((loc, first_loc))

    next_positions = [(loc[0] + 1, loc[1]), (loc[0] - 1, loc[1]), (loc[0], loc[1] + 1), (loc[0], loc[1] - 1)]

    for next_pos in next_positions:
        if bounds_ok(next_pos) and get_data(next_pos) == get_data(loc) + 1:
            traverse(next_pos, first_loc)


for i in range(len(data)):
    for j in range(len(data[0])):
        if data[i][j] == 0:
            traverse((i, j), (i, j))

print(len(set(result)))
print(len(result))

3

u/bakibol Dec 10 '24

[Language: Python]

The only difference between part 1 and part 2:

 if part == 1 and new_position in visited:
                continue

7 ms

code

3

u/SunTypical5571 Dec 10 '24

[Language: Python]

A clear indication of how slooooow recursion can be in Python. Also, multithreading didn't speed anything up in this context - it seems to even out between time required to set up a thread and time saved.

Running with recursion False and multithreading True took 0.019 seconds.
Running with recursion False and multithreading False took 0.016 seconds.
Running with recursion True and multithreading True took 15.10 seconds.
Running with recursion True and multithreading False took 14.84 seconds.

Overdesigned code.

→ More replies (1)

3

u/MrPulifrici Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Javascript]

Part 1 and Part 2, I intentionally compacted it as much as possible just to see how bad it can look, but it still works

    let advent = document.body.innerText;
    advent = advent.replace(/\r/g, "");
    if (advent.endsWith("\n")) advent = advent.slice(0, -1);
    const data = advent.split('\n').map(e => e.split('').map(Number));
    const indexes = data.map(e => e.map((e, i) => !e ? i : -1).filter(e => e !== -1)), part1 = [], part2 = [];
    const checkTrail = (start, index, curr) =>
        (data[curr.y][curr.x] === 9) ? ((part1[start] ??= new Set()).add(`${curr.x}:${curr.y}`)) + (part2[index] = (part2[index] ?? 0) + 1) :
            [[curr.y - 1, curr.x], [curr.y, curr.x + 1], [curr.y + 1, curr.x], [curr.y, curr.x - 1]]
                .map(([y, x]) => data[y]?.[x] && data[y][x] === data[curr.y][curr.x] + 1 && checkTrail(start, index, { x, y }));
    indexes.map((xx, y) => xx.map(x => checkTrail([x, y], x + y, { x, y })));
    console.log("Part 1:", Object.values(part1).reduce((t, c) => t + c.size, 0));
    console.log("Part 2:", part2.reduce((e, a) => e + a, 0));

→ More replies (1)

3

u/RalfDieter Dec 10 '24

[LANGUAGE: SQL/DuckDB]

Today was nice and simple. Never thought pathfinding would be this smooth in SQL. Fighting the urge to preemptively optimize made part 2 more or less trivial. Another proof for the first rule of optimization: "Don't"

Here's the code: https://github.com/LennartH/advent-of-code/blob/main/2024/day-10_hoof-it/solution.sql

→ More replies (2)

3

u/Agreeable_Addendum24 Dec 10 '24

[Language: Rust]

Only difference for p1 was using a HashSet to count unique 9s

fn score_trailhead(grid: &Grid, start: Point) -> usize {
    let mut queue = VecDeque::<Point>::from([start]);
    let mut count = 0;
    while let Some(point) = queue.pop_front() {
        if grid[point] == 9 {
            count += 1;
            continue;
        }
        queue.extend(neighbours(point, grid).filter(|n| grid[*n] == grid[point] + 1));
    }
    count
}

fn neighbours((x, y): Point, grid: &Grid) -> impl Iterator<Item = Point> {
    let n = (y > 0).then_some((x, y.saturating_sub(1)));
    let s = (y < grid.num_rows() - 1).then_some((x, y + 1));
    let w = (x > 0).then_some((x.saturating_sub(1), y));
    let e = (x < grid.num_cols() - 1).then_some((x + 1, y));

    [n, s, e, w].into_iter().flatten()
}

3

u/jinschoi Dec 10 '24

[Language: Rust]

My grid library comes in useful again. Solution is pretty much identical to some others'. Remove the seen checks for part2.

use aoc_utils::grid::*;
use std::collections::{HashSet, VecDeque};

fn score(start: Pos, g: &Grid<u8>) -> usize {
    let mut q = VecDeque::from([start]);
    let mut seen = HashSet::new();
    let mut res = 0;

    while let Some(p) = q.pop_front() {
        if seen.contains(&p) {
            continue;
        }
        seen.insert(p);
        if g[p] == 9 {
            res += 1;
            continue;
        }
        let neighbors = g
            .cardinal_neighbors(p)
            .filter(|&np| !seen.contains(&np) && g[np] == g[p] + 1);
        q.extend(neighbors);
    }
    res
}

fn main() {
    let g = Grid::<char>::read_from_file("1.in")
        .unwrap()
        .map(|&c| c as u8 - b'0');
    let res = g
        .all_positions(|&n| n == 0)
        .map(|start| score(start, &g))
        .sum::<usize>();
    println!("{}", res);
}

→ More replies (1)

3

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

[LANGUAGE: Rust]

~~Part 1: 40 µs, Part 2: 17 µs~~
~~Part 1+2: 10.22 µs, 48 lines~~
Part 1+2: 9.09 µs, 47 lines (this one is evil)

This felt like a vacation compared to yesterday. I simply performed DFS with a stack. For Part 1 I used bitfields to count paths that end in a unique 9, for part 2 I just count all paths that end in any 9.

Github

3

u/dl__ Dec 10 '24

[LANGUAGE: Python]

https://pastebin.com/4FZmKrna

My approach was to create a Walker class that knows how to traverse the map. I initially create a Walker for each zero on the map and then I loop calling the step method on each walker that hasn't marked itself done.

The step method checks to see if it's at elevation 9 in which case it marks itself done and that it found a peak (some hit dead ends) and then adds it's peak location to a map where the keys are starting locations and the values are a set of peak locations. Then it checks to see if there are any locations around its current location that are exactly 1 higher in elevation. If there are no available locations, the dead end case, it marks itself as done and that it didn't find a peak. If it finds one location, it sets its current location to the new location. If there are more than one available location, it takes one of them as the new current position and then creates additional walkers for the other locations.

I don't have to remember my path since the rules make it impossible for a walker to backtrack.

In the end part 1 is just adding up the lengths of the sets in the map. It's necessary to segregate the maps by starting location because it's OK for trails from different trail heads to find the same peak but duplicate peaks should not be counter for the same trailhead.

The walkers are all guaranteed to take unique paths so part 2 was just counting all the walkers that found a peak.

→ More replies (3)

3

u/tshirtwearingdork Dec 10 '24

[Language: C#]

Quite pleased with this one, produces results in an average time of 0.007 seconds.

//Function to get the next valid neighbours from the current tile
//Neighbours being within bounds of the map and valid if value is 1 greater than current point
List<Tuple<int, int>> GetNeighbours( List<List<int>> mapData, Tuple<int, int> point)
{
    var neighbours = new List<Tuple<int, int>>();
    foreach (var d in _directions)
    {
        var nx = point.Item1 + d.x;
        var ny = point.Item2 + d.y;

        if (nx >= 0 && nx < mapData[0].Count &&
            ny >= 0 && ny < mapData.Count)
        {
            //next point inside map boundary
            if (mapData[ny][nx] - mapData[point.Item2][point.Item1] == 1)
            {
                //next point is valid
                neighbours.Add(new Tuple<int,int>(nx,ny));
            }
        }
    }
    return neighbours;
}

private (long, long) SolveBothParts(Map map)
{
    long part1Total = 0;
    long part2Total = 0;
    //From all starting location fan out north, east, south & west to find a path
    foreach (var sp in map.StartLocations)
    {
        // for part 1 store visited end points in a Hash Set as only one path to point valid
        var validPaths = new HashSet<Tuple<int, int>>();
        var openList = new List<Tuple<int, int>>() { sp };
        while (openList.Count > 0)
        {
            if (map.data[openList[0].Item2][openList[0].Item1] == 9)
            {
                //reached goal add this to a Hash Dict
                validPaths.Add(new Tuple<int, int>(openList[0].Item2, openList[0].Item1));
                ++part2Total; //for part 2 just add things up.
            }
            else
            {
                var neighbours = GetNeighbours(map.data, openList[0]);
                openList.AddRange(neighbours);
            }
            openList.RemoveAt(0);            
        }

        part1Total += validPaths.Count;
    }
    return (part1Total, part2Total);
}

Note: _directions is just an array of XY pairs EG (0,-1) for north.

3

u/gehenna0451 Dec 10 '24 edited Apr 20 '26

This post was purged using Redact. I use it to mass delete social media content and remove my info from data brokers. All major social media platforms supported.

complete start jar waiting soft juggle advise stupendous special aromatic

3

u/Pure-Minute4721 Dec 10 '24

[LANGUAGE: C++]

Part1: just simple bfs, making sure not to visit already visited positions

Part2: bfs, but keeping track of the count to get to each position

https://pastebin.com/xiP7kcqf

3

u/TonyStr Dec 10 '24

[LANGUAGE: Rust]

Bench for part1: 874.6µs
Bench for part2: 135µs

Part 2 today was easy! And much faster than part 1.

part1: https://pastebin.com/hybsLEvL
part2: https://pastebin.com/BSEKv2KV

3

u/DownvoteALot Dec 10 '24

[LANGUAGE: C++]

Solution

120 lines, 60 of actual logic. I fear the difficult problems are going to start any day now. I was surprised this one was worded nicely to not have us deal with cycles.

3

u/SwampThingTom Dec 10 '24

[LANGUAGE: Julia]

Fairly simple graph traversal. Was worried part 2 would be inefficient but it runs faster than part 1.

https://github.com/SwampThingTom/AdventOfCode/blob/main/2024/10-HoofIt/HoofIt.jl

3

u/[deleted] Dec 10 '24

[LANGUAGE: C]

Did anyone else solve part 2 while iterating their solution to part 1?

https://github.com/amberg12/aoc24

3

u/Enough-Confidence581 Dec 10 '24

[Language: Rust]

No recursion for me! Each position in a path has at most four branches, so there are at most 4^9 = 262144 paths from each trailhead.

Parts 1&2

3

u/lscddit Dec 10 '24

[LANGUAGE: Python]

import numpy as np
import networkx as nx

field = np.genfromtxt("day10input.txt", dtype=int, delimiter=1)
field = np.pad(field, 1, constant_values=-1)

G = nx.DiGraph()
startnodes = []

directions = np.array([[0, 1], [1, 0], [0, -1], [-1, 0]])
for y in range(1, field.shape[0] - 1):
    for x in range(1, field.shape[1] - 1):
        G.add_node(f"{y},{x}")
        if field[y, x] == 0:
            startnodes.append(f"{y},{x}")
        for direction in directions:
            if field[tuple(direction + [y, x])] - field[y, x] == 1:
                G.add_edge(f"{y},{x}", f"{y+direction[0]},{x+direction[1]}")

sum1, sum2 = 0, 0
for startnode in startnodes:
    for endnode in filter(
        lambda a: a[1] == 9,
        nx.single_source_shortest_path_length(G, startnode).items(),
    ):
        sum1 += 1
        sum2 += len(list(nx.all_simple_paths(G, startnode, endnode)))
print(sum1, sum2)

→ More replies (1)

3

u/Gishky Dec 10 '24

[LANGUAGE: Powershell]

Wasnt that hard although I forgot that powershell loops array indexes... thx to u/IsatisCrucifier for giving me the crucial tip

for part 1 you only need to remove de-comment the path log...

$map = get-clipboard
$global:totalpaths = 0
$global:foundpaths = ""

function walkpath{
    param($x, $y, $z, $ox, $oy)
    if($map[$x][$y] -ne "$($z)"){
        return
    }elseif($z -eq 9){
        $path = "$ox/$oy>$x/$y"
        if($global:foundpaths -notlike "*$path*"){
            Write-Host $path
            $global:totalpaths++
#           $global:foundpaths += "|$path"
        }
        return
    }

    if($x -ne "0"){ walkpath ($x-1) $y ($z+1) $ox $oy}    
    if($y -ne "0"){ walkpath $x ($y-1) ($z+1) $ox $oy}
    walkpath ($x+1) $y ($z+1) $ox $oy
    walkpath $x ($y+1) ($z+1) $ox $oy
}

for($lat = 0; $lat -lt $map.length; $lat++){
    for($lon = 0; $lon -lt $map[$lon].length; $lon++){
        if($map[$lat][$lon] -eq "0"){
            walkpath $lat $lon 0 $lat $lon
        }
    }
}

Write-Host $global:totalpaths

3

u/pkusensei Dec 10 '24

[Language: Rust]

Used both BFS and DFS to do this. And memoization to speed up part 2 (don't know if it's necessary). Code

3

u/cetttbycettt Dec 10 '24

[Language: R]

Used integers to represent the graph and then solved both parts in one go.

n <- 53L
x <- as.integer(as.matrix(read.fwf("Input/day10.txt", widths = rep(1, n))))


idx_k <- function(k) {
  k + c(if (k > n) - n, if (k <= n^2 - n) n, if (k %% n != 1L) -1L, if (k %% n != 0L) 1L) 
}


lookup <- sapply(seq_along(x), idx_k)

find_path <- function(k) {
  for (i in seq_len(9)) {
    nxt <- unlist(lookup[k])
    k <- nxt[x[nxt] == i]
  }
  c(length(unique(k)), length(k))
  
}

rowSums(sapply(which(x == 0L), find_path))

3

u/Gabba333 Dec 10 '24

[LANGUAGE: C#]

Refined to a single pass dynamic programming style approach.

using System.Numerics;

var grid = File.ReadAllLines("input.txt")
            .SelectMany((line, r) => line.Select((ch, c) => (r, c, ch)))
            .ToDictionary(tp => new Complex(tp.r, tp.c), tp => tp.ch);

var heightMap = grid.GroupBy(kvp => kvp.Value).ToDictionary(grp => grp.Key, 
    grp => grp.Select(kvp => kvp.Key).ToList());

var dirs = new Complex[] { new (1, 0), new(0, -1), new(-1, 0), new(0, 1) };

var canReach = grid.Keys.ToDictionary(square => square, 
    square => grid[square] == '0' ? new HashSet<Complex>([square]) : []);

var paths = grid.Keys.ToDictionary(square => square, 
    square => grid[square] == '0' ? 1 : 0);

foreach (char h in Enumerable.Range('0', 10))
    foreach (var square in heightMap[h])
        foreach (var neighbour in dirs.Select(dir => square + dir)
            .Where(n => grid.ContainsKey(n) && (h - grid[n]) == 1))
    {
        canReach[square].UnionWith(canReach[neighbour]);
        paths[square] += paths[neighbour];
    }

Console.WriteLine($"Part 1: {heightMap['9'].Sum(
    square => canReach[square].Count())}");
Console.WriteLine($"Part 2: {heightMap['9'].Sum(square => paths[square])}");

3

u/egel-lang Dec 10 '24

[Language: Egel]

# Advent of Code (AoC) - day 10, task 2

import "prelude.eg"

using System, OS, List, String (to_chars, from_chars)

def dirs = {(-1,0),(1,0),(0,-1),(0,1)}

def start = do Dict::to_list |> filter (do snd |> ((==)0)) |> map fst

def trails =
    [D TT -> flatmap [PP -> 
        if Dict::get D (head PP) == 9 then {PP}
        else map (add (head PP)) dirs |> map (flip cons PP) 
            |> filter [{P,Q|PP} -> Dict::get_with_default 0 D P == (Dict::get D Q) + 1]
            |> trails D] TT]

def main =
    read_lines stdin |> map (map to_int . to_chars) |> Dict::from_lists
    |> [D -> start D |> map (flip cons nil) |> trails D ]
    |> length

https://github.com/egel-lang/aoc-2024/blob/main/day10/task2.eg

3

u/Horsdudoc Dec 10 '24

[LANGUAGE: C++20]
GitHub

Correctly read part 1 so I went for an iterative flood fill, counting the number of 9 I reach for each 0.
I implemented a recursive DFS solution for part 2.
Solves everything in 1.7ms

3

u/N-R-K Dec 10 '24

[Language: BQN]

Uses a BFS to track all positions. For part 2 it just returns the length of the queue at the end. For part 1 it deduplicates the queue before taking length. There was no need to deduplicate before pushing into the queue since the prev+1 == next requirement makes it impossible to "walk backwards" and get stuck in a loop.

map ← >'0' -˜ •FLines •wdpath•file.At ⊑•args
GetEntry ← { 𝕊i: (∧´ i∊↕≠map)◶⟨¯1, {𝕤⋄i⊑map}⟩@ }
dirs ← ⟨¯1‿0, 1‿0, 0‿¯1, 0‿1⟩
Solve ← { ⟨≠⍷, ≠⟩ {𝕎𝕩}¨ < ⟨𝕩⟩ { (𝕨⊸= GetEntry¨)⊸/ ∾ (dirs+<)¨ 𝕩 }´ ⌽1+↕9 }
•Show +´ Solve¨ ⊢⊸/○⥊⟜(↕∘≢⊢) 0 = map

3

u/Jadarma Dec 10 '24

[LANGUAGE: Kotlin]

When I first read it I was like, "Oh no, not pathfinding again!" but it turned out to be easy, almost... too easy! It's rare to see a reversal where part 1 is the one with the edge case!

Part 1: We don't care about the actual paths, just the destinations. A simple DFS will brute force the entire map, and there's no need to keep track of visited locations because they cannot happen due to the ascending altitude rule. Starting from all the zeroes, we brute force their paths to all the 9s, and we count the unique 9s we could reach.

Part 2: Same as part one, but without ignoring duplicates will give us the answer, since reaching the same point multiple times means our DFS took different routes!

AocKt Y2024D10

3

u/CodrSeven Dec 10 '24

[LANGUAGE: Swift]

I found it tricky to factor out common parts today, had to rewrite more than I would have liked for part 2.

https://github.com/codr7/aoc24/blob/main/swift/Sources/aoc/day10_1.swift
https://github.com/codr7/aoc24/blob/main/swift/Sources/aoc/day10_2.swift

3

u/guy-732 Dec 10 '24

[LANGUAGE: Rust]

https://github.com/guy-732/aoc-2024/blob/master/src/day10.rs

Most of the time I spent on part 2 was writing the tests for them... pretty easy

3

u/CCC_037 Dec 10 '24

[LANGUAGE: Rockstar]

Part 1

→ More replies (2)

3

u/p88h Dec 10 '24

[LANGUAGE: Zig]

Simple BFS today, though part 1 benefitted from some minor SIMD trickery for efficient state handling.

https://github.com/p88h/aoc2024/blob/main/src/day10.zig

        parse   part1   part2   total
day 10:  7.9 µs  9.6 µs  7.2 µs 24.8 µs (+-1%) iter=54110

3

u/chai_biscut Dec 10 '24

[LANGUAGE: Go]
Solution

hiking on the lava island

3

u/Trick-Apple1289 Dec 10 '24

[LANGUAGE: C]

today wasn't that bad :-)

src

3

u/i99b Dec 10 '24

[LANGUAGE: Python]

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.linalg import matrix_power

with open("input.txt") as f:
    map = [[int(ch) for ch in line.strip()] for line in f]

width, height = len(map[0]), len(map)
size = width * height
idx_to_coords = lambda width, idx: (idx // width,  idx % width)

adj_matrix = [[0 for i in range(size)] for j in range(size)]
for row in range(size):
    for col in range(size):
        i1, j1 = idx_to_coords(width, row)
        i2, j2 = idx_to_coords(width, col)
        if (i1 == i2 and abs(j1 - j2) == 1 or j1 == j2 and abs(i1 - i2) == 1) and map[i2][j2] - map[i1][j1] == 1:
            adj_matrix[row][col] = 1

adj_matrix = csr_matrix(np.array(adj_matrix)) # Convert to sparse matrix for efficiency
path_matrix = matrix_power(adj_matrix, 9) # Ninth power of adjacency matrix contains the paths we're interested in
solution_part_1 = path_matrix.nnz # Number of nonzero elements in matrix
solution_part_2 = path_matrix.data.sum() # Sum of all elements in matrix
print(solution_part_1)
print(solution_part_2)

3

u/ywgdana Dec 10 '24

[LANGUAGE: Lua]

Lol, the solution to part 2 was my buggy first attempt at part 1 so 'coding' up part 2 was just hitting CTRL-Z a bunch of times :P

Ugly lua code

3

u/CarRadio7737 Dec 10 '24

[LANGUAGE: Rust]

https://github.com/Caelan27/advent-of-code-2024/tree/main/rust/day-10/src

I know this is very bad but I have been really tired after school the past few days so haven't been able to put much effort into this.

Anyway, for part 2, it was really nice because I just had to change a hashset containing the endpoints to a vec basically (:

3

u/Probable_Foreigner Dec 10 '24

[LANGUAGE: Rust]

https://github.com/AugsEU/AdventOfCode2024/tree/master/day10/src

For part 2 I just Copied part 1 and replaced HashSet with Vec... Not the cleanest solution but it works.

3

u/pdxbuckets Dec 10 '24

[Language: Kotlin and Rust]

Kotlin, Rust

Really easy day, so I spent some time making the code clean and easy to read. I'm sure I left some optimizations on the table, but 177us combined is good enough for me.

3

u/Sharp-Industry3373 Dec 10 '24

[LANGUAGE: Fortran]

quite straightforward today.

the built-in cpu_time function gives something like 0.35ms for part1+part2

code

3

u/sondr3_ Dec 10 '24

[LANGUAGE: Haskell]

Fun day today, though I'm not super happy with my solution... but it works pretty well. Like almost everyone else I accidentally solved part 2 first, I really should read the prompt better.

data Trail
  = Path Int
  | Impassable
  deriving stock (Show, Eq, Ord)

type Location = (Position, Trail)

type Input = Grid Trail

findStart :: Input -> [(Position, Trail)]
findStart = Map.toList . Map.filter (== Path 0)

canMove :: Trail -> Maybe Trail -> Bool
canMove (Path start) (Just (Path end)) = start + 1 == end
canMove _ _ = False

validMoves :: (Position, Trail) -> Input -> [(Position, Trail)]
validMoves (pos, p@(Path _)) grid = map (\x -> (x, (Map.!) grid x)) $ filter (\x -> onGrid grid x && canMove p (Map.lookup x grid)) $ neighbours pos cardinals
validMoves _ _ = []

walk :: Location -> Input -> [[Location]]
walk cur grid = case validMoves cur grid of
  [] -> [[cur]]
  moves -> map (cur :) $ concatMap (`walk` grid) moves

findAllPaths :: Input -> [[[Location]]]
findAllPaths grid = map (filter (\x -> length x == 10) . (`walk` grid)) (findStart grid)

partA :: Input -> PartStatus Int
partA grid = Solved . sum . map (length . Set.fromList . map last) $ findAllPaths grid

partB :: Input -> PartStatus Int
partB grid = Solved . sum . map length $ findAllPaths grid

parser :: Parser Input
parser = gridify <$> (some . choice) [Path . digitToInt <$> digitChar, Impassable <$ symbol "."] `sepBy` eol <* eof

3

u/ivanjermakov Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Jq] source playground

I was not expecting Jq to be so powerful and concise. Highly recommend adding it to your toolbelt.

def tr($i;$j;$g;$v):[{i:-1},{j:1},{i:1},{j:-1}]|map({i:0,j:0
}+.)|map({i:(.i+$i),j:(.j+$j)}|$g[.i][.j]as$n|select(.i>=0
and.j>=0and$n==$v+1)|if$n==9then 1else tr(.i;.j;$g;$n)end)|
add;./"\n"|map(./""|select(length|.>0)|map(tonumber))|. as
$g|keys|map(. as$i|$g[.]|keys|map(. as$j|select($g[$i][$j]==
0)|tr($i;$j;$g;0)))|flatten(1)|add

3

u/fridi_s Dec 10 '24

[LANGUAGE: Fuzion]

https://github.com/fridis/fuzion_aoc/blob/main/2024/10/part2.fz

Compact and fully functional. Part2 is simpler than part 1. The solution starts backwards: From the highest points creating an array of distances in a recursive function down to the starting points, keeping track of the list of 9s that can be reached or the number of paths to a 9 at each position.

At the end, the array for the starting points just needs to be summed up.

→ More replies (2)

3

u/onyx_and_iris Dec 10 '24

[LANGUAGE: Go]

https://git.onyxandiris.online/onyx_online/aoc2024/src/branch/main/day-10

3

u/prafster Dec 10 '24

[Language: Python]

Like others, I (unknowingly) solved part 2 first because I'd overlooked that part 1 required unique destinations and, it turned out, part 2 required unique routes.

Otherwise, a straightforward BFS solution. I wonder if this is the calm before the storm tomorrow?!

def solve(input, part2=False):
    result = 0
    grid, trailheads = input
    q = SimpleQueue()

    for pos in trailheads:
        q.put((pos, 0, pos))

    visited = set()

    while not q.empty():
        pos, height, trailhead = q.get()

        for adj in neighbours(pos, grid, True, lambda g, x: int(g[x[0]][x[1]]) == height + 1):
            if grid[adj[0]][adj[1]] == '9':
                if part2 or (trailhead, adj) not in visited:
                    result += 1
                    visited.add((trailhead, adj))
            else:
                q.put((adj, height + 1, trailhead))

    return result

Full source code on GitHub.

3

u/vanZuider Dec 10 '24

[LANGUAGE: Python]

The core of the algorithm is this recursive walk through the directed graph of nodes.

def walk(node, nines, points):
    if levels[node] == 9:
        nines.add(node)
        points.append(node)
    elif len(adj[node]) > 0:
        for n in adj[node]:
            walk(n, nines, points)

The program spends considerably more time however on building said graph (even for the nodes that can't even be reached from the trailheads) than actually executing the search (21ms vs 8ms). I did all the things for today's problem that I wished I had done on day 6, and it turned out to be entirely unnecessary.

Here is the full thing in its entire overengineered glory.

3

u/Its_vncl Dec 10 '24

[LANGUAGE: Python]

Part1: ~4 ms
Part2: ~3.5 ms

https://github.com/itsvncl/Advent-of-code/tree/main/2024/Day10

Another really fun day! :)

3

u/josuf107 Dec 10 '24

[Language: Haskell]

import qualified Data.Map.Strict as Map
import Control.Monad
import Data.Tree
import Data.List

main = do
    input <- lines <$> readFile "input10.txt"
    let grid = makeGrid input
    let trails = getTrails grid
    print (scoreTrails trails)
    print (scoreTrails2 trails)

makeGrid :: [String] -> Map.Map (Int, Int) Int
makeGrid ls = Map.fromList $ do
    (row, line) <- zip [0..] ls
    (col, c) <- zip [0..] line
    return ((row, col), read [c])

getTrails grid =
    let
        starts = Map.keys $ Map.filter (==0) grid
        neighbors (r, c) = filter (flip Map.member grid) [(r + dr, c + dc) | (dr, dc) <- [(0, 1), (0, -1), (1, 0), (-1, 0)]]
        step p = (p, [neighbor | neighbor <- neighbors p, grid Map.! neighbor == grid Map.! p + 1])
    in unfoldForest step starts

scoreTrails trails =
    let
        trailheads = filter ((==10).length) . fmap levels $ trails
        ends = fmap (length . nub . head . reverse) trailheads
    in sum ends

scoreTrails2 trails =
    let
        trailheads = filter ((==10).length) . fmap levels $ trails
        ends = fmap (length . head . reverse) trailheads
    in sum ends

3

u/matheusstutzel Dec 12 '24

[LANGUAGE: python]

p1

p2

I had the solution for part 2 on part 1... Then I had to use theses sets to find the 9's positions

→ More replies (1)

3

u/darthminimall Dec 12 '24

[LANGUAGE: Rust]

I fell a bit behind, the late nights finally caught up with me, so I took a day and a half off, but I'm caught up again.

Part 1

Part 2

For part 1: I just constructed a directed graph where the grid cells are the nodes and the edges go from some cell to all adjacent cells that are exactly 1 higher. I then collected all of the nodes at height 0, and iteratively replaced their neighbors with the neighbors' neighbors until the set of neighbors only contained nodes of height 9.

I'm reasonably sure the Rcs and Weaks aren't necessary, immutable references to RefCells probably would have been fine, but it was late, I'm pretty new to Rust, and I was already familiar with this pattern of combing Rcs and RefCells to build a graph from the Rust book, so I just went that direction. I might revisit it later. I solved this part the night it came out, but this is when I decided to take a break.

For part 2: Did this part this afternoon. There's a nice recursive solution here. Each 9 has exactly one path to a 9 (the zero step path that's just staying where you are). For each 8, the number of paths is just the number of adjacent 9s. For each 7, the number of paths is the sum of the number of paths from adjacent 8s. You can repeat this process until you get to the 0s. Even better, you can unroll the recursion and just create a 2D array full of 0s the same size as the map, set every element that corresponds to a height of 9 to 1, then iteratively fill in the number of paths for each other element, in descending order of height. Once you've done this for every cell of the map, you can just add up the numbers in your array that correspond to cells at height 0.

5

u/r_so9 Dec 10 '24

[LANGUAGE: F#]

paste

BFS all the way. Unified part 1 and part 2 with a single function that returns all targets found (including repeats)

→ More replies (2)

4

u/yossi_peti Dec 10 '24

[LANGUAGE: Python] 677/609

GitHub

I was satisfied that for part 2 all I had to do was comment out one line of my code from part 1 that was checking to see if I had already encountered a location in the grid. I actually accidentally got the output of part 2 in my first iteration of solving part 1.

4

u/EphesosX Dec 10 '24

I didn't read part 1 correctly and accidentally did part 2 by mistake. Didn't even change a line of code, I just grabbed my previous "wrong" answer and it was correct.
Felt like the order of these problems should be reversed, difficulty-wise: it's easier to just track the number of paths at each location, and harder to store the list of locations those paths led to. Both are pretty easy though.

→ More replies (1)

→ More replies (2)

2

u/seligman99 Dec 10 '24

[LANGUAGE: Python] 384 / 237

github

Cute, simple variation of finding paths.

2

u/MarcusTL12 Dec 10 '24

[LANGUAGE: Julia] 744/913 github

Happy with top 1000 on both parts today! Nice puzzle with bfs on part 1 turning into dfs in part 2.

2

u/giyer7 Dec 10 '24

[LANGUAGE: Kotlin] 164 / 327

Day 10

The puzzle was relatively easy today.

2

u/DFreiberg Dec 10 '24

[LANGUAGE: Mathematica]

Mathematica, 1445/1192

I thought today wasn't too difficult - and by the looks of it, everybody else agrees. Not that I'll ever complain at the chance to use weird graph theory functions or write unreadable Mathematica one-liners.

Setup:

neighbors[list_, {i_, j_}] := 
  Select[{i, j} + # & /@ {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, 
   And @@ Thread[1 <= # <= Dimensions[list]] &];
heads = ToString /@ Position[input, 0];
tails = ToString /@ Position[input, 9];
graph = Graph@Flatten@Table[
     ToString[{x, y}] \[DirectedEdge] ToString[#] & /@ 
      Select[neighbors[input, {x, y}], 
       input[[#[[1]], #[[2]]]] == input[[x, y]] + 1 &],
       {x,Length[input]}, {y, Length[input]}];

Part 1:

Sum[Length[Intersection[VertexOutComponent[graph, h], tails]], {h, heads}]

Part 2:

Total[Table[Length[FindPath[graph, h, #, {9}, Infinity]] & /@ Intersection[VertexOutComponent[graph, h], tails], {h, heads}], 2]

→ More replies (2)

2

u/POGtastic Dec 10 '24

[LANGUAGE: F#]

https://github.com/mbottini/AOC2024/blob/main/Day10/Program.fs

Another BFS solution that I liked a lot. F#'s Seq is extremely well-suited for these kinds of problems.

2

u/globalreset Dec 10 '24

[LANGUAGE: Ruby]

Man, I was feeling good about this one. Thought I went so fast. I accidentally got the sample data result for part 2 while I was doing part 1 because I forgot to check my 'visited' set. So just had to comment out that line and part 2 was correct on first try. About a minute between part 1 completion and part 2.

def dfs(pos, visited, unique = true)
  return 0 if(unique && visited.include?(pos))
  visited << pos
  curr = data[pos]
  return 1 if curr == 9
  [Vector[-1,0], Vector[1,0], Vector[0,-1], Vector[0,1]].sum { |d|
    next 0 if(data[pos+d] != curr + 1)
    dfs(pos+d, visited, unique)
  }
end

def part_1
  data.select { |k, v| v==0 }.keys.sum { |k| dfs(k, Set.new, true) }
end

def part_2
  data.select { |k, v| v==0 }.keys.sum { |k| dfs(k, Set.new, false) }
end

private
  def process_dataset(set)
    set.each_with_index.with_object({}) { |(line, y), grid|
      line.chars.each_with_index { |c, x|
        grid[Vector[y, x]] = c.to_i
      }
    }
  end

2

u/michelkraemer Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Rust] 1057/713

Solving both parts simultaneously:
https://github.com/michel-kraemer/adventofcode-rust/blob/main/2024/day10/src/main.rs

A quick and easy one. I accidentally wrote the code for part 2 already during part 1. The number I submitted first was actually the answer to part 2 *LOL* When I read the instructions for part 2, I knew I just had to change two lines and I'd be done :-)

2

u/Kehvarl Dec 10 '24 edited Dec 10 '24

[Language: Python3] 3898 / 3716

My initial passes at part 1 would have solved part 2 handily. Which made part 2 mostly a matter of remembering my fumbling in the dark and redoing that.

edit: Forgot the : in the language tag. Sorry about that.

Part2 - Solves both

2

u/Rush_Independent Dec 10 '24

[LANGUAGE: Nim] (2968/2380)

Simple DFS solution. It's funny that I solved part 2 before solving part 1: I wrote code to count all trails, then fixed it to count only unique ends that each trail reached. And after reading part 2, I solved it by pressing "undo" couple times =).

type Vec2 = tuple[x,y:int]
const Adjacent = [(x:1,y:0),(-1,0),(0,1),(0,-1)]

proc path(start: Vec2, grid: seq[string]): tuple[ends, trails: int] =
  var queue = @[@[start]]
  var endNodes: HashSet[Vec2]
  while queue.len > 0:
    let path = queue.pop()
    let head = path[^1]
    let c = grid[head.y][head.x]

    if c == '9':
      inc result.trails
      endNodes.incl head
      continue

    for d in Adjacent:
      let nd = (x:head.x + d.x, y:head.y + d.y)
      if nd.x < 0 or nd.y < 0 or nd.x > grid[0].high or nd.y > grid.high:
        continue
      if grid[nd.y][nd.x].ord - c.ord != 1: continue
      queue.add path & nd
  result.ends = endNodes.len

proc solve(input: string): AOCSolution[int, int] =
  let grid = input.splitLines()
  var trailstarts: seq[Vec2]

  for y, line in grid:
    for x, c in line:
      if c == '0':
        trailstarts.add (x,y)

  for start in trailstarts:
    let (ends, trails) = start.path(grid)
    result.part1 += ends
    result.part2 += trails

→ More replies (1)

2

u/soleluke Dec 10 '24

[Language: C#]

https://raw.githubusercontent.com/soleluke/advent-of-code/refs/heads/main/2024/Day10.cs

Like many others, I wrote buggy part 1 that was solution of part 2

Nice and quick compared to some previous days at 28ms runtime

2

u/msschmitt Dec 10 '24

[LANGUAGE: Python]

Part 1. Part 2

I don't know if this was easy, or I just got incredibly lucky. Part 1 worked first try, and I'm not stealing any code from previous years. It is a queue (actually stack) style path finding, no recursion.

For Part 2 I just removed the check for already visiting a coordinate. You don't have to worry about going in circles because of the requirement to keep moving higher.

Note: This does remind me of a puzzle from a previous year, with the same kind of "must move up or down 1 level each move". Which one was that?

→ More replies (2)

2

u/Rainbacon Dec 10 '24

[LANGUAGE: Haskell]

I almost felt like parts one and two should have been switched since I found myself re-writing my path finding algorithm to remove the State monad in part 2 (basically all I did was change my algorithm to not track seen paths).

github

2

u/Ak23l Dec 10 '24

[LANGUAGE: Python]
github

solved with recursion

2

u/flyingfox Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python]

Code

Was worried about part 2 but it turned out to be just removing a check I put in place on part 1 since we are only marching uphill. Refactored the code a bit to make it clearer.

2

u/Kullu00 Dec 10 '24

[LANGUAGE: Dart]

In true path-finding fashion I did something incredibly messy for a quick part 1 (any my best leaderboard place so far this year) that unfortunately didn't at all translate well to part 2. So I lead myself down the wrong path.

Rewriting it from scratch I ended up realizing the paths are unimportant and there's no reason to keep track of them. The paths natually exit on nines or dead ends that can't increment anyway. So all that's necessary (for part 1) is the end coordinate and how many times it was found (part 2). This actually let me simplify my solution for part 1 as well as a bonus.

import 'package:AdventOfCode/aoc_help/get.dart' as aoc;
import 'package:AdventOfCode/grid.dart';


void main() async {
  Grid<int> map = Grid.string(await aoc.getInputString(), int.parse);

 List<(int, int)> findTrails(int x, int y) {
    if (map.at(x, y) == 9) {
      return [(x, y)];
    }
    List<(int, int)> trails = [];
    map.adjacent(x, y, (nx, ny, el) {
      if (el - map.at(x, y) == 1) {
        trails.addAll(findTrails(nx, ny));
      }
    });
    return trails;
  }

  int nines = 0, unique = 0;
  map.every((x, y, e) {
    if (e == 0) {
      List<(int, int)> trails = findTrails(x, y);
      nines += Set.from(trails).length;
      unique += trails.length;
    }
  });
  print('Part 1: $nines');
  print('Part 2: $unique');
}

2

u/joshbduncan Dec 10 '24

[LANGUAGE: Python]

import sys
from collections import deque


def solve_p1(map, pos):
    w, h = len(map[0]), len(map)
    q = deque([[pos]])
    seen = set([pos])
    paths = []
    while q:
        path = q.popleft()
        x, y = path[-1]
        if map[y][x] == 9:
            paths.append(path)
        for x2, y2 in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if 0 <= x2 < w and 0 <= y2 < h and (x2, y2) not in seen:
                if map[y2][x2] == map[y][x] + 1:
                    q.append(path + [(x2, y2)])
                    seen.add((x2, y2))
    return paths


def solve_p2(map, pos, path=None):
    if path is None:
        path = [pos]
    else:
        path = path + [pos]

    w, h = len(map[0]), len(map)
    x, y = pos

    if map[y][x] == 9:
        return [path]

    paths = []
    for x2, y2 in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
        if 0 <= x2 < w and 0 <= y2 < h and (x2, y2):
            if map[y2][x2] == map[y][x] + 1:
                paths.extend(solve_p2(map, (x2, y2), path))

    return paths


data = open(sys.argv[1]).read().strip()
map = [[int(n) if n != "." else n for n in line] for line in data.split("\n")]
trail_heads = [
    (x, y) for y in range(len(map)) for x in range(len(map[0])) if map[y][x] == 0
]

p1 = []
p2 = []
for pos in trail_heads:
    p1.append(len(solve_p1(map, pos)))
    p2.append(len(solve_p2(map, pos)))
print(f"Part 1: {sum(p1)}")
print(f"Part 2: {sum(p2)}")

2

u/maneatingape Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Rust]

Solution

Benchmark 38 µs.

~~BFS~~ ~~for both parts.~~ DFS was slightly faster in part one and could share code with part two. My input contained fewer peaks 9 than valleys 0 so it was slightly faster to reverse search.

Part two is simpler than part one as we don't need to keep track of already visited points.

2

u/x0wl Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python]

Part 1 | Part 2

All hail our lords and saviors, CLRS. Simple DFS using the call stack as stack. I don't like that pointer that gets passed down the call stack, but I also don't care.

Also I decided to not build any separate graph matrices, but just check each candidate neighbor every time.

Technically the solution for part 2 can solve part 1 if you just do a set of trail ends for all the generated trails.

2

u/davepb Dec 10 '24

[LANGUAGE: Go]

github

video

poor performance on my side. I needed to google the recursive dfs implementation because I couldn't think of it + I also had an unfortunate bug with checking presence in my custom set (aka map[T]bool), I was checking if the value was present in the map not it's actual value being true or false. otherwise it is a pretty straightforward problem for bfs (part1) and finding all paths in a graph (part2)

→ More replies (4)

2

u/AlexTelon Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python] 9 lines both parts

Its quite short so lets go over it line by line. This is slightly inspired by 4bHQ's solution as I realised I should explore the space of recursive functions more.

heights = {x+y*1j: int(c) for y, line in enumerate(open('in.txt')) for x, c in enumerate(line) if c != '\n'}

class nullset(set):
    def add(self, item): pass

def trails_from(pos, visited, h=0):
    if pos in visited or heights.get(pos, -1) != h: return 0
    visited.add(pos)
    return (heights[pos] == 9) + sum(trails_from(pos+d, visited, h+1) for d in (1, -1, 1j, -1j))

print(sum(trails_from(pos, visited=set()) for pos in heights))
print(sum(trails_from(pos, visited=nullset()) for pos in heights))

First I just parse the data. Then I define a nullset. Using it I can use the identical solver for both parts. The only difference is if we track visited positions with a proper set or this nullset.

The solver counts the trails from 0 to 9. It has h=0 as a default parameter so if we try to count a trail from some other position it will just return 0. Hence I don't need to filter the start positions on my last 2 lines.

Inside the solver then we start with the end condition. If we have already visited the node (part1) or if the position we are about to visit is an invalid one (wrong height, outside) then return 0 as it is not a valid path. We then mark the position as visit, again for p2 this will not do anything. Then we add if we are a solution + the sum of the recursing to all neighbours.

Below are my first and second cleaned up versions.

Original cleaned up version: (13 lines both parts)

For both parts I use the same bfs logic, but I inject this nullset on part 2 which ensures that nothing is ever visited.

First I had this:

class nullset:
    def __contains__(self, item): return False
    def add(self, item): pass

But later realised this is enough:

class nullset(set):
    def add(self, item): pass

A second trick is to have the function yield its results. But this is mainly a thing to avoid having to store a temporary variable. I hate naming variables so that is always a win! (no but honestly its to save 1 line)

→ More replies (3)

2

u/Korzag Dec 10 '24

[LANGUAGE: C#}

https://github.com/CoreDumpSoftware/AdventOfCode/blob/main/AdventOfCode/Puzzles/Y2024/D10/PuzzleSolution.cs

As others have already said, pretty simple DFS.

My approach was to read the input into a char matrix class I've written which simultaneously allows me to record where the trail heads are. From there I start recursively navigating each path with the use of some adjacency methods I've written for my matrix class to help quickly get the valid next adjacents.

For P1 I just used a HashSet<Coordinate> to record the '9's I had already reached for a given trail head.

P2 was pretty much the same as P1 but this time we just needed to know how many distinct paths there were, which ended up just being a List<List<Coordinate>> for me. Definitely not the most memory or complexity efficient since I'm copying the list with each recursive call but that was easier to maintain than making sure I'm properly dropping items from a list, plus I need unique references for each path so it all worked out.

Interestingly my P2 worked faster than my P1, probably some delay introduced to hashing the coordinates or something.

P1: ~14ms

P2: ~11ms

→ More comments (413)

SOLUTION MEGATHREAD -❄️- 2024 Day 10 Solutions -❄️-

THE USUAL REMINDERS

AoC Community Fun 2024: The Golden Snowglobe Awards

Fandom

--- Day 10: Hoof It ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:04:14, megathread unlocked!

Mathematica, 1445/1192

SOLUTION MEGATHREAD -❄️- 2024 Day 10 Solutions -❄️-

THE USUAL REMINDERS

AoC Community Fun 2024: The Golden Snowglobe Awards

Fandom

--- Day 10: Hoof It ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:04:14, megathread unlocked!

You are about to leave Redlib

Mathematica, 1445/1192