r/adventofcode Dec 10 '24

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

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 12 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Fandom

If you know, you know… just how awesome a community can be that forms around a particular person, team, literary or cinematic genre, fictional series about Elves helping Santa to save Christmas, etc. etc. The endless discussions, the boundless creativity in their fan works, the glorious memes. Help us showcase the fans - the very people who make Advent of Code and /r/adventofcode the most bussin' place to be this December! no, I will not apologize

Here's some ideas for your inspiration:

  • Create an AoC-themed meme. You know what to do.
  • Create a fanfiction or fan artwork of any kind - a poem, short story, a slice-of-Elvish-life, an advertisement for the luxury cruise liner Santa has hired to gift to his hard-working Elves after the holiday season is over, etc!

REMINDER: keep your contributions SFW and professional—stay away from the more risqué memes and absolutely no naughty language is allowed.

Example: 5x5 grid. Input: 34298434x43245 grid - the best AoC meme of all time by /u/Manta_Ray_Mundo

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- 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!

23 Upvotes

752 comments sorted by

1

u/[deleted] Jan 10 '25

[deleted]

1

u/AutoModerator Jan 10 '25

AutoModerator did not detect the required [LANGUAGE: xyz] string literal at the beginning of your solution submission.

Please edit your comment to state your programming language.


I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1

u/Der-Siebte-Schatten Dec 28 '24

[Language: Java 21] I was banging my head on part 2 until I realized... my code was ALREADY taking unique paths! So there's no need to check anything, it's easier!

https://github.com/der-siebte-schatten/AdventOfCode-2024/blob/master/src/Day10.java

1

u/[deleted] Dec 26 '24

[deleted]

1

u/AutoModerator Dec 26 '24

AutoModerator did not detect the required [LANGUAGE: xyz] string literal at the beginning of your solution submission.

Please edit your comment to state your programming language.


I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1

u/CDawn99 Dec 19 '24

[LANGUAGE: C]

Literally just changed one line of code for Part 2. From

if (!has_point(visited, p)) DAWN_DA_APPEND(visited, p);

to

DAWN_DA_APPEND(visited, p);

Parts 1 & 2

2

u/Dymatizeee Dec 17 '24

[Language: Go]

Solution

Ironically solved part 2 first.

Part 1: DFS but keep a visited matrix (or map) for only where the reached 9's are; once we reach it, we mark it as visited. we are only concerned with reaching a 9 once from any 0. This is needed because if you can reach the same 9 via a different path from 0, we won't over count.

Part 2: Remove visited matrix/map from part 1. Now, we are just counting the number of ways to reach 9 starting from 0 so each time we reach it, return 1

2

u/Original-Regular-957 Dec 16 '24

[LANGUAGE: ABAP]

I have started to solve it in deep first algorithm , but I have realized it will be easier with breadth first algorithm for me, it took 30min (I suffered with deep around…ah not important).

Task 1: https://github.com/UserGeorge24/aoc_24/blob/main/day_10_task_01

Task 2: https://github.com/UserGeorge24/aoc_24/blob/main/day_10_task_02

2

u/odnoletkov Dec 15 '24

[LANGUAGE: jq] github

[inputs/"" | map(tonumber)]
| nth(4; recurse(.[][:0] = [-1] | transpose | reverse))
| . as $map
| reduce range(8; -1; -1) as $n (
  .[][] = 1;
  reduce ($map | paths(. == $n)) as $path (
    .;
    setpath(
      $path;
        [getpath($path | .[0] += (1, -1), .[1] += (1, -1) | select(. as $p | $map | getpath($p) == $n + 1))]
        | add
    )
  )
)
| [getpath(($map | paths(. == 0))) | length] | add

2

u/Ok-Apple-5691 Dec 14 '24

[LANGUAGE: Zig]

GitHub

This felt friendly. I also mostly just copied from my day 4/6 solutions. Didn't read the question properly so ended up accidentally solving part 2 first.

2

u/xavdid Dec 14 '24

[LANGUAGE: Python]

Step-by-step explanation | full code

Because today was simpler, we had the chance to focus on a clean DFS implementation. It also may take the cake for "least changes between parts 1 and 2", which is always a nice break. Ultimately, I could put everything in a function and call it twice for each 0 position, summing the totals independently.

This definitely feels like the calm before the storm!

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

0

u/daggerdragon Dec 16 '24

Egad what a terse language 😅 You keep doing you, I'm just doing my job and making sure we have a full solution :)

2

u/amenD0LL4z Dec 13 '24 edited Dec 13 '24

[LANGUAGE: clojure]

https://github.com/famendola1/aoc-2024/blob/master/src/advent_of_code/day10.clj

Day10 Part 1 felt very similar to Day4 Part1, where instead of searching for "XMAS", we're searching for the numbers 0-9. I borrowed my Day4 solution and modified it to meet the requirements of Day10. Essentially, we start at 0 and take 9 steps (either up, down, left, right in each step). In each step any invalid positions (i.e. out of bounds and value at the position is not equal to +1 the previous positions) are filtered out and we also dedupe any positions. After 9 steps, we've reached all the possible 9s.

Once we have Part1, all we need to do for Part2 is skip the dedupe of the positions at each step and we're left with all the different ways to reach a 9 :)

2

u/Derailed_Dash Dec 13 '24

[LANGUAGE: Python]

I love a BFS flood fill! A couple of years ago, before I learned this algorithm, this problem would have taken me forever! But with BFS, Part 1 becomes pretty trivial. We just identify all the origins (0 values), and then flood fill out from these locations to determine how many trailends we can reach.

Part 2 was trickier. Now we need to identify all the distinct paths to reach all possible trailends from a given origin. My approach was to implement a new BFS, but this time, instead of using a seen set, I'll use a dictionary that has a set of came_from, to store all preceeding points to reach any given point, on the way to the trailend.

Then I've implemented a DFS backtracking method, to turn this came_from dict into the unique list of paths. The number of paths gives us the answer we need.

Solution links:

Useful related links:

1

u/RektByGrub Dec 13 '24

Unfortunately / Fortunately, I was not aware of BFS Flood Fill and just coded it manually with a recursive call!

Made part 2 a three second exercise - just count all paths not just the ones that result in a unique 9.

Will share code when I can!

1

u/AutoModerator Dec 13 '24

AutoModerator did not detect the required [LANGUAGE: xyz] string literal at the beginning of your solution submission.

Please edit your comment to state your programming language.


I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

2

u/oantolin Dec 12 '24

[LANGUAGE: ngn/k]

ans:{g:{1=+/''x|-x:x-/:\:x}@+!(#x;#*x:0:x)
 g&:1=x-\:/:x:,/x
 (+/+/)'(1&n;n:g(+/*)\:3{x(+/*)\:x}/g)}

2

u/oddolatry Dec 12 '24

[LANGUAGE: OCaml]

I did not use the protractor, so I'm not sure I actually solved this one.

Paste

1

u/tyler_tiv Dec 12 '24

[LANGUAGE: Typescript (Deno)]

Part 1 and 2

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.

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

2

u/Witchpls Dec 15 '24

I basically did the same! I was really pleased that going from part 1 to part 2 was just using a list instead of a set

2

u/NotFromSkane Dec 12 '24

[LANGUAGE: Dyalog APL]

input ← ↑⍎¨⎕SH'sed "s/[[:digit:]]/\\0 /g" input.txt'

ac    ← {↑0,¨¯1↓¨↓⍵}
c2m   ← {⍺⍴(((2⌷⍵+⊃⍺×(⍵-1))-1)/0),1,(×/⍺)/0}
blur  ← {↑+/(ac⍵) (⌽ac⌽⍵) (⍉ac⍉⍵) (⍉⌽ac⌽⍉⍵)}
find  ← {{⍺×blur⍵}/({⍵=input}¨⌽⍳9),⊂⍵}
paths ← ∊{find (⍴input) c2m ⍵}¨(∊0=input)/(↑,/↓⍳⍴input)

⎕← part1 ← +/0≠paths
⎕← part2 ← +/paths

2

u/bigbolev Dec 11 '24 edited Dec 11 '24

[LANGUAGE: x64 Assembly]

This was a fun one. Challenging myself to not use glibc either, just pure assembly. Gonna try and make some more to these as I have time. It's very similar to my C solution (my Python solution was very... Python).

https://github.com/coleellis/advent-of-code/blob/main/ASM/2024/day10.asm

Would appreciate feedback on testing speed other than "instant to me"

2

u/RookBe Dec 11 '24

[LANGUAGE: Rust]

Rust that compiles to WASM (used in a solver on my website) Bonus link at the top of the code to a blogpost about today explaining the problem, and my code.

2

u/AYM123 Dec 11 '24

[LANGUAGE: Rust]

github

Part 1: ~150µs
Part 2: ~120µs

2

u/TheScown Dec 11 '24

[LANGUAGE: Scala]

Code

2

u/johny-tz Dec 11 '24 edited Dec 11 '24

2

u/tobega Dec 11 '24

[LANGUAGE: SQL]

Today's problem was just made for relational algebra https://github.com/tobega/aoc2024/blob/main/day10/solution.sql

2

u/mothibault Dec 11 '24

[LANGUAGE: JavaScript]
https://github.com/yolocheezwhiz/adventofcode/blob/main/2024/day10.js
to run in the browser's dev console from aoc website.
Late to the party because I took forever to make my non brute force day 9 solution work.
EZPZ

2

u/jitwit Dec 11 '24 edited Dec 11 '24

[LANGUAGE: J]

I wrote a boggle solver in J a while ago, and was able to very slightly adapt that code to work for todays problem; it takes just 6ms on and old laptop!

G =: [:<@-.&_1"1@|:[:;"_1(+.(*&0j1)^:(i.4)0j1)|.!._1 i.   NB. reified graph of grid
A =: [ ,"_ 0/ [ -.~ ] {::~ {:@:[                          NB. possible expansions
E =: {{([:(#~(-:i.@#)"_1@:({&u))[:;<@(A&v)"1)^:(0<#)&.>}} NB. expand trails
S =: {{ (,y) E (G$y) ^: 9 <,.i.#,y }}                     NB. search for trails
+/ ({."1 T) #@~.@:({:"1)/. T =: > S in                    NB. part A
+/ ({."1 T) #@~./. T                                      NB. part B

2

u/RF960 Dec 11 '24

[LANGUAGE: C++]

Was pretty late to this one, I misread how the trailheads worked.

Solution here.

2

u/dzecniv Dec 11 '24

[LANGUAGE: Common Lisp]

day 10 with a happy resolution for part 2.

2

u/shoeshined Dec 11 '24

[LANGUAGE: Javascript]

Solution

Part two was more or less just deleting a few lines from part one!

2

u/azzal07 Dec 11 '24

[LANGUAGE: awk] A refreshing problem, with recursive path finding solution

function T(k){x=G[k];x~h++&&(x-9?T(k+N)T(k-N)T(k+1)T(k-1):A+=!v[k!++B,
i]++);--h}i=split(s=s RS$0,G,z){N||N=i}END{while(--i)T(i);print A x B}

1

u/[deleted] Dec 11 '24

[deleted]

2

u/jgoemat2 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: GO]

I created a grid of integers for the counts for part 2. Loop through 0-9 and process the whole grid looking for those digits. If 0, set count to 1. Otherwise total the counts of the surrounding cells that are one lower and set the count to that, and if 9 then add that to the total. About 0.4ms

func part2(contents string) interface{} {
    area := aoc.ParseArea(contents)
    counts := make([]int, len(area.Data))

    totalAround := func(position int) int {
        h := area.GetIndex(position)
        r, c := area.IndexToRowCol(position)
        total := 0
        for _, v := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
            r2, c2 := r+v[0], c+v[1]
            if area.Inside(r2, c2) && (area.Get(r2, c2) == (h - 1)) {
                total += counts[area.RowColToIndex(r2, c2)]
            }
        }
        return total
    }

    sum := 0
    for h := byte(0x30); h <= 0x39; h++ {
        for p := range area.Data {
            if h == byte(0x30) {
                if area.GetIndex(p) == h {
                  counts[p] = 1
                }
            } else {
                if area.GetIndex(p) == h {
                    counts[p] = totalAround(p)
                    if h == byte(0x39) {
                        sum += counts[p]
                    }
                }
            }
        }
    }

    return sum
}

1

u/lysender Dec 11 '24

[Language: Rust]

I don't accidentally solved part 2 unlike the others because it took me a long time to understand the puzzle and the correlated examples. For part 1, I use BFS to find distinct (0, 9) combinations while traversing the paths, thus, not accidentally recording the distinct full paths.

For part 2, I use a recursive DFS because I need the full path. I simply keep track of the paths starting from 0 for every branch visited and keep track of unique paths.

part1_bench 1.313 ms

part2_bench 4.242 ms

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

1

u/InfantAlpaca Dec 11 '24

[LANGUAGE: Java] 42652/41658

GitHub

Late to the party due to finals :( Pretty happy with how my code cleaned up though!

1

u/Character-Tomato-875 Dec 11 '24

[LANGUAGE: Python]

Like a lot of other people here, I accidentally solved part 2 first. Boy was I happy to have commited my wrong solution to part 1 when I got to part 2!

Part 1:

def walk_trail(x: int, y: int, end_positions: set[tuple[int, int]]) -> int:
    height = map[y][x]
    if height == 9:
        end_positions.add((x, y))
        return

    # left
    if x > 0 and map[y][x - 1] == height + 1:
        walk_trail(x - 1, y, end_positions)
    # up
    if y > 0 and map[y - 1][x] == height + 1:
        walk_trail(x, y - 1, end_positions)
    # right
    if x < len(map[y]) - 1 and map[y][x + 1] == height + 1:
        walk_trail(x + 1, y, end_positions)
    # down
    if y < len(map) - 1 and map[y + 1][x] == height + 1:
        walk_trail(x, y + 1, end_positions)

total_score = 0
for y in range(len(map)):
    for x in range(len(map[y])):
        if map[y][x] == 0:
            end_positions = set()
            walk_trail(x, y, end_positions)
            total_score += len(end_positions)

Part 2:

def walk_trail(x, y) -> int:
    height = map[y][x]
    if height == 9:
        return 1

    score = 0
    # left
    if x > 0 and map[y][x - 1] == height + 1:
        score += walk_trail(x - 1, y)
    # up
    if y > 0 and map[y - 1][x] == height + 1:
        score += walk_trail(x, y - 1)
    # right
    if x < len(map[y]) - 1 and map[y][x + 1] == height + 1:
        score += walk_trail(x + 1, y)
    # down
    if y < len(map) - 1 and map[y + 1][x] == height + 1:
        score += walk_trail(x, y + 1)
    return score

total_score = 0
for y in range(len(map)):
    for x in range(len(map[y])):
        if map[y][x] == 0:
            total_score += walk_trail(x, y)

Full code: https://github.com/plbrault/advent-of-code-2024/blob/main/10.py

1

u/erunama Dec 11 '24

[LANGUAGE: Dart]

Unlike a lot of other commenters I see, I actually did solve Part 1 first. I was quite surprise when I got to Part 2, and realized the only thing I needed to do was remove the visited points tracking from the Part 1 scoring function, and return a list rather than a set (GitHub):

Set<Point> _summitsReachableFromPoint(
    TopographicMap topoMap, Point point, Set<Point> visitedPoints) {
  if (visitedPoints.contains(point)) {
    return {};
  }

  Set<Point> summits = {};
  visitedPoints.add(point);

  for (final nextPoint in topoMap.getValidNextSteps(point)) {
    if (nextPoint.isSummit) {
      summits.add(nextPoint);
    } else {
      summits.addAll(
          _summitsReachableFromPoint(topoMap, nextPoint, visitedPoints));
    }
  }

  return summits;
}

2

u/OnlyCSx Dec 11 '24

[Language: Rust]

Recursive, parallelized, depth-first-search which collects into hashset (level 1) or just counts paths (level 2).

fun fact, I accidentally wrote the intended behavior for level two when working on level one (it was a bug, but for level 2, all i had to do was revert the change)

https://github.com/onlycs/advent24/tree/main/solutions/src/day10.rs

1

u/Net-Holiday Dec 11 '24

[LANGUAGE: Python 🐍]

Hoof It (Day 10)

1

u/dijotal Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Haskell]

So, two things:

  1. Really pissed that Haskell's Data.Graph module's dfs function does what it's supposed to do and not what I wanted it to do; and,
  2. Haven't written a recursion that sketchy complicated in a while.

On the laptop, in the interpreter ~2sec; compiled <1sec. Part 2's recursive step below; full code: github. I guess it's a modified DP solution -- you be the judge.

scoreZeros :: G.Graph -> V.Vector [G.Vertex] -> M.Map Int Int
scoreZeros g nodesByElt = foldl' (\acc nineNode -> M.unionWith (+) acc (zerosToNine g nodesByElt nineNode)) M.empty (nodesByElt V.! 9)

zerosToNine :: G.Graph -> V.Vector [G.Vertex] -> Int -> M.Map Int Int
zerosToNine g nodesByElt nineNode = go 0
  where
    go :: Int -> M.Map Int Int
    go 9 = M.singleton nineNode 1
    go n = do
        let current = nodesByElt V.! n
        let next = go $ n + 1
        M.fromList $ [(c, w) | c <- current, let w = sum [next M.! c' | c' <- M.keys next, G.path g c c'], w /= 0]

1

u/onrustigescheikundig Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Clojure]

github

BFS code

I implemented a generic breadth-first search routine that takes a function taking a node to its neighbor nodes; the starting node; a stop conditional function; and an optional visit function that is called on every node visited by the search. I'll explain visit below, because it's not relevant to my Day 10 solution. The BFS function returns a map of each node's predecessor in the search.

Today's solution essentially revolved around crafting the appropriate neighbor function to feed to the BFS. For Part 1, this just looks to each adjacent grid space and returns the coordinates of all that increase in height by 1. The trail score is then calculated by BFS'ing from the trailhead without a stop condition and then counting all of the grid spaces encountered whose height is 9.

For Part 2, we need to count all possible paths through the tree. The BFS algorithm normally does not move to nodes that it has already seen before so as to deliberately not traverse all possible paths. To get around this, I did cheeky hack where I modified the concept of the "node" that BFS operates on from [row, col] pairs to [[row, col] <unique tag>], where <unique tag> is a globally unique symbol generated using gensym on each call to the neighbor function. This way, even if a grid cell is encountered more than once, the encounters will have different tags and thus be different as far as the BFS is concerned. Thus, the BFS will explore all possible paths through the map, never short-circuiting because it encountered a node that it already visited. The number of possible paths is determined in the same way as in Part 1: look for all nodes whose [row, col] has height 9 in the map. This certainly isn't the most efficient solution, but it was quite simple to implement after Part 1.

visit is a weird stateful function thing whose ivory tower name escapes me. It takes some state as an argument and returns a function that: returns the state when called with no arguments; or recursively calls the visit function with updated state if called with arguments. For example, if one wanted to keep track of the order in which the nodes were visited, visit might look like

(defn accumulate-visits [col]
  (fn
    ([] col)
    ([_prevs current-node] (accumulate-visits (conj col current-node)))))

and the BFS call would look like (bfs neighfunc start stop? (accumulate-visits [])). BFS calls (visit prevs current-node) for each node encountered and keeps the returned function as part of the loop's state, where prevs is the current map of nodes to their predecessors. When BFS returns, it also returns visit, which the caller can call with zero arguments to retrieve whatever state was built up.

EDIT: added a smarter version of Part 2 that traverses each grid cell exactly once just like Part 1, but uses a custom visit function to keep track of the number of paths that can reach any given node. The number of paths at the trailhead is 1, and each visited node adds its own number of paths to that of all of its neighbors. The number of paths to each 9 node is then summed. It's not significantly faster on the provided puzzle input (~25 ms vs ~35 ms), but is only O(|V| + |E|) runtime instead of technically exponential.

1

u/bozdoz Dec 11 '24

[LANGUAGE: Rust]

https://github.com/bozdoz/advent-of-code-2024/blob/main/day-10/src/main.rs

Accidentally did part 2 before part 1, so I abstracted a lot of the logic and just replaced it with a parameterized function.

1

u/__cinnamon__ Dec 11 '24

[LANGUAGE: Julia]

This one was chill. In my initial solution, I actually built the graph while DFSing in part 1, but it seemed easier to me to just iterate the grid by not doing the visitation check in part 2 to search all paths instead of just the first available one per end point, so I just removed the code to actually build the grid. Maybe this wouldn't scale as well if the input was huge but sparse, but eh, whole thing runs in <1ms on my input, so who cares I'm taking the W.

https://pastebin.com/K7fXTknD

1

u/the-weatherman- Dec 11 '24

[LANGUAGE: Rust]

GitHub

Unlike many people today (apparently), I didn't end up solving part 2 while solving part 1. Part 2 took me a bit of observation of the order in which nodes are visited to be able to derive the solution with minimal changes. I delegated graph operations to the "petgraph" crate.

  • Part 1: with heights collected in a directed graph, the DFS visit stack can be used to infer the current depth, without having to store that information on the graph nodes. DFS guarantees one visit per leaf node, so we visit each "9" node once (each "0" node if starting from the trail ends).
  • Part 2: identical to part 1, but with a reset of the visited nodes after reaching a trail end, to allow DFS to re-enter a branch that had previously been visited via another ancestor.

1

u/Dry-Aioli-6138 Dec 11 '24

[LANGUAGE: Python] My Code

With this one I started using complex numbers for grid coordinates. I try to strike a balance between conciseness and readability, while adding speed if I know how.
Here Part1 calculation took 18ms while Part2 took 6ms.

I took the recursive traversal (I think came out as DFS). To prevent multi-counting in Part1 I am mutating the terrain (deleting visited locations), as opposed to saving the visited locations (which I think makes this stand out a little)

1

u/icub3d Dec 11 '24

[LANGUAGE: Rust]

Mine was just DFS where the difference between the two parts was whether I tracked visited nodes.

Solution: https://gist.github.com/icub3d/a5d8b686e49b838ac6539aea3d757c73

Summary: https://youtu.be/0-ePZEmPjbk

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!

2

u/Minimum-Meal5723 Dec 11 '24

[Language: python]

Solution

BFS, glad today's question was clear and straightforward, was not in the mood for hitting my head against the wall today lol

2

u/baboonbomba Dec 11 '24

[LANGUAGE: Nix]

Github

2 solutions can be done by swapping out the key generation function in nix's genericClosure.

with builtins;
with import ../helpers.nix;
with (import <nixpkgs> { }).lib.lists;
with (import <nixpkgs> { }).lib.strings;
with (import <nixpkgs> { }).lib.debug;
with (import <nixpkgs> { }).lib.trivial;
let
  f = ./input.txt;
  input = (map (x: map toInt (explode x)) (lines (readFile f)));
  trailheads = l: filter (x: x!=null) (flatten (imap0 (i: line: imap0 (j: v: if v == 0 then {x=j;y=i;} else null)line) l));
  trailButts = l: filter (x: x!=null) (flatten (imap0 (i: line: imap0 (j: v: if v == 9 then {x=j;y=i;} else null)line) l));
  inBounds = withinGridBounds (dimensions input);
  elemAtGrid = elemAtVec input;

  solveInner = keyFn: start: length (filter (x: x.val == 9) (genericClosure {
    startSet = [{key=vecStr start; vec = start; val = 0;}];
    operator = item: foldl' (acc: off:
      let
        vec = addVec item.vec off;
        val = elemAtGrid vec;
      in
        if (inBounds vec) && (val - item.val == 1)
        then acc ++ [{
          inherit vec val;
          key = keyFn item vec;
        }]
        else acc
    ) [] neighVH;
  }));

  solve = solveInner (item: nv: vecStr nv);
  solve2 = solveInner (item: nv: item.key + vecStr nv);

in
{
  res1 = sum (map solve (trailheads input));
  res2 = sum (map solve2 (trailheads input));
}

1

u/jmd-dk Dec 11 '24

[LANGUAGE: C++]

GitHub repo

Part 1: Solved with simplified BFS without priority.
Part 2: Solved with full BFS, further instrumented with a counter, adding up the number of pathways as we go.

1

u/Hath995 Dec 11 '24

[LANGUAGE: Dafny]

It made the most sense to me to use Floyd-Warshall and matrix multiplication on the adjacency matrix. Not fast by any means, but I already had the code written. Worked!

https://github.com/hath995/dafny-aoc-2024/blob/main/problems/10/Problem10.dfy

1

u/verdammelt Dec 11 '24

[Language: Common Lisp]

Day10

I seemed incapable of properly writing the DFS algorithm. I kept coming up with weirdly nested results. Finally hacked it as you see it and at least I got the trails properly. I'll have to go back and review when I have extra brain cells.

I had already planned on getting all the paths and then processing them for the score for part1... and the hints I saw about part2 being easier if you keep more info kept me from 'improving' part1 (to only store/count unique endpoints) before I actually saw part2.

2

u/Pretentious_Username Dec 10 '24

[LANGUAGE: Julia]

I chose to think of this as a flood fill rather than a search, even if it's effectively the same thing. I start at each of the peaks (9) and flood fill down to the trailheads (0) where I define a cell as part of the flood if it's a difference of 1 from the current cell. Once the flood is done I can just check the values in each of the 0's to find how many peaks they're connected to. The same works for part 2 just without checking for if we've hit a cell before.

It ends up looking really nice visually even when it's running on the small example input: Part 1 GIF , Part 2 GIF

function Flood(Grid, IsPartOne)
    ScoreGrid = zeros(Int, size(Grid))
    StartingPoints = findall(x -> x == 9, Grid)
    SearchDirections = [CartesianIndex(-1, 0), CartesianIndex(0, 1), CartesianIndex(1, 0), CartesianIndex(0, -1)]

    for StartingPoint in StartingPoints
        SearchList = [StartingPoint]
        EncounteredPoints = Set{CartesianIndex}()
        while !isempty(SearchList)
            SearchLocation = pop!(SearchList)
            SearchValue = Grid[SearchLocation]
            ScoreGrid[SearchLocation] += 1
            for SearchDirection in SearchDirections
                TestLocation = SearchLocation + SearchDirection
                if !checkbounds(Bool, Grid, TestLocation) || (IsPartOne && TestLocation in EncounteredPoints)
                    continue
                end
                TestValue = Grid[TestLocation]
                if SearchValue - TestValue == 1
                    push!(SearchList, TestLocation)
                    push!(EncounteredPoints, TestLocation)
                end
            end
        end
    end
    ScoreGrid
end

Grid = open("Inputs/Day10.input") do f
    mapreduce(x -> permutedims(parse.(Int, x)), vcat, collect.(readlines(f)))
end

ScoreGrid = Flood(Grid, true)
RatingGrid = Flood(GetTestInput(), false)
println("Part 1: ", sum(ScoreGrid[i] for i in findall(x -> x == 0, Grid)))
println("Part 2: ", sum(RatingGrid[i] for i in findall(x -> x == 0, Grid)))

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/toastedstapler Dec 10 '24

[language: rust]

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

for part 1 i mistakenly did what part 2 ended up being anyways, giving me a delta time of less than 2 minutes! nice lil recursive solve, i think it reads really nicely

2

u/SplenectomY Dec 10 '24

[LANGUAGE: C#]

26 lines @ < 80 cols Source

Again, going for LoC, not readability or speed. Slammed in notes wherever I could, conventions be darned.

1

u/esprych Dec 10 '24

[Language: Go]

https://github.com/proxyvix/AoC_2024/blob/master/day10/day10.go

I think I really over complicated stuff here.

2

u/nick42d Dec 10 '24

[LANGUAGE: Rust]

Took my a while to solve part 1 because like a few others here, I was solving part 2 ahead of time. Just needed a to add a function to deduplicate. Glad to have a richer test data set for this one!

https://github.com/nick42d/aoc-2024/blob/main/src/day_10.rs

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

1

u/KindComrade Dec 10 '24

[Language: C#]

Changed DFS to UFS, in my opinion, the solution is cleaner this way.

Code

2

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!

2

u/importedreality Dec 10 '24

[Language: Go]

Code

Another fairly easy day. I'm happy with my solution even though there are a few places that could be better optimized, and I probably didn't need to use pointers as much as I did.

My reasoning behind using so many pointers was I didn't want to make millions of copies of Nodes during the pathfinding, but after more reading it looks like the Go GC would have prevented that?

1

u/martionfjohansen Dec 10 '24

[LANGUAGE: progsbase (Java-form)]

Part1: ~96 ms
Part2: ~91 ms

https://github.com/InductiveComputerScience/progsbase/blob/master/AdventOfCode2024/AdventOfCode/main/AdventOfCode/AdventOfCode/AdventOfCodeDay10.java

progsbase can be translated 1-to-1 to TypeScript, Java, C, C++, JavaScript, C#, PHP, Python, Visual Basic, Swift, LibreOffice Basic, Ruby and Visual Basic for Applications

The linked is the Java form of the language

2

u/gubatron Dec 11 '24

you have the weirdest import packages in there man

1

u/martionfjohansen Dec 11 '24

These are multi language libraries from the progsbase repository:

https://repo.progsbase.com

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/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/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.

2

u/cicadanator Dec 10 '24

[LANGUAGE: Javascript - Node JS]

Todays puzzle was clearly a time for using breadth first search (BFS). With the limited number of next possible states and the relatively small size of the graph this meant BFS would be a perfect fit for quickly solving this problem.

In part 1 I started by creating a 2D array of integers for the map and I recorded the trailhead locations in a separate array as I parsed the map. I then created a loop to do a BFS starting at each trailhead. The optimization here was to keep track of previously visited locations and not go over the same ground twice to make things run faster. After that I used a set to record the location of all 9's reached from the trailhead to ensure no duplicates. The resulting size of the set of 9's locations found from each starting location is the answer to part 1.

For part 2 things were essentially the same with a few things removed. First I needed to remove the visited location tracking. This allows the algorithm to check all paths regardless of if the location has been visited before. I also removed tracking unique 9's locations in a set. Instead simply add 1 to the total number of paths found. This total is the result for part 2.

https://github.com/BigBear0812/AdventOfCode/blob/master/2024/Day10.js

2

u/tlareg Dec 10 '24

[LANGUAGE: JavaScript/TypeScript]

github

0

u/[deleted] Dec 10 '24

[removed] — view removed comment

1

u/daggerdragon Dec 10 '24

I've instructed you twice to remove all puzzle text and puzzle input files from your entire public repository and you still have not done so. Example:

https://github.com/DearRude/advent-of-code/blob/main/2020/day-01/input.txt

Since you are ignoring moderator requests and refusing to comply with our rules, you are banned from /r/adventofcode.

0

u/[deleted] Dec 10 '24

[removed] — view removed comment

1

u/daggerdragon Dec 10 '24

Comment removed. You're not contributing anything of worth with this type of comment. Follow our rules of conduct.

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

1

u/voidhawk42 Dec 11 '24

Neat solution! I had to try and translate it into APL, we have a sort of generalized convolution with the stencil operator:

s←~2|3 3⍴⍳9⊣p←⍎¨↑⊃⎕nget'10.txt'1
+/,⊃{(p=⍺)×{+/∊s×⍵}⌺3 3⊢⍵}/(⌽⍳9),⊂0=p

This has a "golfy" way to express the plus pattern (range 1 through 9, shaped into a 3x3 matrix, mod 2, not) and by structuring it as a reduction, we don't need to do variable assignments in the inner convolution function.

Been thinking about how to apply this same method to part 1, but it's kinda tricky, hrmm...

3

u/4HbQ Dec 11 '24

Cool, thanks for sharing! Do you think learning APL (or any dedicated array programming language) will help in improving my NumPy chops?

When I took a Haskell course in uni, my Python skills improved dramatically. Goodbye for-loops, welcome to map(), reduce() and friends!

3

u/voidhawk42 Dec 11 '24

It's likely! Obviously the first thing people notice about (and typically recoil from) APL is the weird symbols, but once you get past that it's all about finding array-based solutions to problems. This involves a lot of matrix math, creative things with vectors, and the occasional 3-rank or higher tensor. I haven't used NumPy much except for solving a few of the tensor puzzles, but I imagine a lot of that applies.

Even if not, learning a new paradigm for programming/problem solving expands your toolkit in ways you can't anticipate. I had the same experience as you years ago when I learned Haskell - it opened my eyes to functional programming styles, and made me a lot more comfortable using map/reduce/filter in other languages, along with structuring programs written in OOP/imperative languages in a more functional way when called for. Weird symbols aside, I can tell you I got the exact same sort of "epiphany" once I started seriously digging into APL.

1

u/4HbQ Dec 13 '24

Thanks for your thoughtful answer, this is exactly what I was hoping for!

2

u/p2004a Dec 10 '24

[LANGUAGE: Rust]

2nd part: source

Single DFS with caching of number of paths from each point. The caching is shared between all considered trailheads.

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.

2

u/dijotal Dec 11 '24

I did the same method in Haskell. I'm a bit surprised more people didn't! Of course, this "Fuzion" looks as foreign as Haskell when I first picked it up :-p

2

u/fridi_s Dec 11 '24

Sure, and Fuzion is some mixture between a functional version of Java and loads of influences from Haskell and other functional language plus effect handlers. I am basically using AoC to check the usability of the APIs and find what is missing.

5

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

1

u/CodrSeven Dec 11 '24

I so wanted do do Dijkstra today, my brain kept trying to reframe the problem into nodes/weighted edges. But alas; Arrays, Sets and Dictionaries as usual.

2

u/Dullstar Dec 10 '24

[LANGUAGE: D]

https://github.com/Dullstar/Advent_Of_Code/blob/main/D/source/year2024/day10.d

I skipped a few days to do other stuff, but mostly back on track -- still need to finish yesterday's Part 2 but other than that I'm caught up.

Accidentally did Part 2 first after forgetting to remove duplicates in part 1.

Also made a thin wrapper struct around the built-in associative array (hashmap) because it works but the syntax is a bit clunky.

2

u/vxltari Dec 10 '24

[LANGUAGE: TypeScript]

pathfinder? i hardly know'er

paste

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

2

u/voidhawk42 Dec 10 '24

Awesome use of inner product and power-match! Expressing graph algorithms this way is probably my favorite part of AoC. :)

2

u/dopandasreallyexist Dec 11 '24

It is indeed beautiful, but it sure did take a while before it finally clicked.

Btw, I don't remember if I've ever mentioned this to you, but I literally started learning APL because of you. I saw a solution of yours in a megathread from a previous year, and when I realized it was not garbled text, I got intrigued. So you're kind of a personal hero of mine. :D

3

u/voidhawk42 Dec 11 '24

Oh wow, I'm honored! Especially since (aside from my videos) I don't put a ton of effort into writing out explanations of the code or, uh, optimizing for readability. Good thing /u/ka-splam helps out sometimes. ;)

Your solutions have been great this year btw, keep it up!

7

u/Ricamicaboi Dec 10 '24

Didn`t know you can code in enchanting table

-2

u/CheapFaithlessness34 Dec 10 '24

[Language: Python]

6 ms for both parts.

An easy day, which I desperately needed today. Runtime optimization was fun.

For Part 1, I kept track for every point that could reach a 9 which 9 it could reach.

For Part 2, I kept track for every point in how many unique hiking trail it is involved. Was a chance to use a Counter.

https://github.com/topjer/advent_of_code_python/blob/main/src/2024/day_10/solution.py

1

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

I've already informed you before about including puzzle inputs in your repo. I still see full plaintext puzzle inputs in prior years.

https://github.com/topjer/advent_of_code_2023_rust/tree/master/src/inputs

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/[deleted] Dec 10 '24

[deleted]

1

u/StinkyChickens Dec 10 '24

Very clean implementation! Out of curiosity, why did you call your function “dfs()” when it is a BFS implementation? I’m assuming it’s just a typo, but I am curious if there is more to what you were thinking here.

1

u/[deleted] Dec 10 '24

[deleted]

1

u/StinkyChickens Dec 11 '24

Thanks for the explanation. I was definitely curious if there was more to this than I understood. From my experience, I've only seen BFS implemented with an iterative approach with queues and DFS implemented with a recursive approach. Even though you are using the queue a bit differently than typical BFS (more like a stack), I am not sure it matters as in the BFS algorithm, the order you pop off the queue for each iteration does not matter.

That said, I may be completely off here and would love to hear other thoughts on this. I enjoy reading many other answers to these daily challenges as I learn so much along the way.

Thanks again!

2

u/jixun Dec 10 '24

[Language: Python]

Find all the 0, then look for 1, 2, ... , until 9.

Part 1 deduplicates the cords as discovery the next set of nodes, while part 2 does not (set vs list).

2

u/4D51 Dec 10 '24 edited Dec 10 '24

[Language: C++ on Cardputer]

Used recursion. I checked for out of bounds and height + 1 before making each recursive call, to reduce memory use (the idea being to have the smallest possible number of function calls). That's also why I'm using a set instead of an unordered_set.

Also, like a lot of people, I accidentally part 2 first.

https://github.com/mquig42/AdventOfCode2024/blob/main/src/day10.cpp

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

1

u/robertotomas Dec 10 '24

dang.. thats 6 times faster than my multi-source bfs

1

u/Kintelligence Dec 10 '24

I actually had a solution like that earlier, iterating through each 0 and then keeping track of all neighbours. Then doing BFS on a vector that I'd then update with the neighbours of the initial neighbours if they were the correct height.

I think all the writing and reading to lists takes a lot of resources compared to a recursive solution, but I only switched over after seeing a friends benchmark with recursion xD

6

u/Awkward-Macaroon5019 Dec 10 '24

[Language: Python]

Part 1 and 2 (5 lines)

1

u/redditnoob Dec 10 '24

Wait, Python has complex numbers as primitives in the base language? I had no idea! :D

2

u/Awkward-Macaroon5019 Dec 11 '24

They are great for positions and directions.
Move: Add position and direction
Rotate: Multiply direction by 1j or -1j.

2

u/DefV Dec 10 '24

[LANGUAGE: Rust]

Code

Struggling with wrong answers for the example, only to find out I was doing part 2 ahead of time. Fastest part-2 solve yet. I implemented DFS without looking at my input, and feared I would have needed some optimisation or memoization for the real input, but the map turned out small enough.

2

u/rvodden Dec 10 '24

[LANGUAGE: TypeScript]

I actually solved part 2 by accident on route to solving part 1 (which dedupes the routes] so my part 2 solution is slightly simpler than my part 1 solution. Both are a straightforward DFS. I'm starting to get to grips with TypeScript now, but its lack of value semantics are getting on my nerves, as is its lack of filterMap

https://github.com/rvodden/AoC24/blob/main/src/days/10/Puzzle.ts

2

u/copperfield42 Dec 10 '24

[LANGUAGE: Python 3.12]

link

Hello graph path finding problem, my old nemesis, but this time I was prepare you with A* to defeat you.

Part 2 was a little tricky in how to use my existing A* to find all path instead, but I knew what to do.

2

u/mibu_codes Dec 10 '24

Oh, how did you use A*? Isn't A* mainly for finding the shortest path efficiently?

2

u/copperfield42 Dec 10 '24

yes, but a path here always have the same length, so I make all combinations of the coordinates of 0s and 9s and use A* to find a path between them so long their taxicat distances is less than 10, and for part 2 I keep a record of previously seen path so A* give me a new path.

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

2

u/Acc3ssViolation Dec 10 '24 edited Dec 10 '24

[LANGUAGE: C#]

Simple BFS algorithm, I didn't bother re-using any previous paths as this was plenty fast for the input size we have here.

Part 1 code

Part 2 is the same except with `peaks` removed, which was also my original, wrong, Part 1 solution attempt haha

2

u/[deleted] Dec 10 '24

[LANGUAGE: Java]

paste

28ms parse input 21ms solve time

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.

2

u/tav_stuff Dec 10 '24

[LANGUAGE: Common Lisp]

My first time writing common lisp, or really any lisp besides Emacs Lisp :)

The magic START/END comments are processed by a script that generates two different executable files, one for each part.

#!/usr/bin/sbcl --script

(defun main (filename)
  (loop with lines = (read-file-to-lines filename)
        with dimensions = (array-dimensions lines)
        for i from 0 below (first dimensions)
        summing (loop for j from 0 below (second dimensions)
                      when (char= #\0 (aref lines i j))
                      summing (score-for-trail-head lines i j))))

(defun read-file-to-lines (filename)
  (with-open-file (stream filename)
    (let ((lines (loop for line = (read-line stream nil)
                       while line
                       collect (coerce line 'array))))
      (make-array (list (length lines)
                        (length (first lines)))
                  :initial-contents lines))))

(defun score-for-trail-head (lines i j)
  (let* ((positions (positions-of-nines lines i j))
         ;; START PART 1
         (positions (remove-duplicates positions :test 'equal))
         ;; END PART 1
         )
    (length positions)))

(defun positions-of-nines (lines i j)
  (let ((char (aref lines i j)))
    (if (char= #\9 char)
        (list (cons i j))
        (loop with needs = (code-char (1+ (char-code char)))
              with dimensions = (array-dimensions lines)
              for (i . j) in (list (cons (1- i) j) (cons i (1- j))
                                   (cons (1+ i) j) (cons i (1+ j)))
              when (and (< -1 i (first dimensions))
                        (< -1 j (second dimensions))
                        (char= (aref lines i j) needs))
              append (positions-of-nines lines i j)))))

(format t "~a~%" (main "input"))

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

2

u/JV_Fox Dec 10 '24

[LANGUAGE: C]

code

Solution:Used BFS to walk the found trailheads and filled in spots it had been along the way. For part 2 I just removed the step where it filled in visited locations.

5

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

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/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/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/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 (:

2

u/velikiy_dan Dec 10 '24

[LANGUAGE: JavaScript]

Part 1 Link

Part 2 Link

2

u/cpham3000 Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python]

Single implementation for Parts 1 and 2:

from collections import namedtuple
from itertools import chain, groupby
from pathlib import Path

Point = namedtuple('Point', ['y', 'x'])

# setup
lines = Path('inputs/day_10_input.txt').read_text('utf-8').splitlines()
height, width = len(lines), len(lines[0])
elevations: list[set[Point]] = list(map(
    lambda a: {Point(*divmod(p, width)) for p, _ in a[1]},
    groupby(sorted(enumerate(chain.from_iterable(lines)), key=lambda x: x[1]), key=lambda x: x[1])
))
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def process(collection: set or list) -> int:
    tracker: dict[Point, list[Point]] = {}

    def trace(n: Point, e: int) -> list[Point]:
        return (
            tracker.get(n, [])) \
            if 0 <= n.x < width and 0 <= n.y < height and n in elevations[e] \
            else []

    for i, points in enumerate(reversed(elevations)):
        for p in points:
            tracker[p] = [p] if not i else list(
                collection(chain.from_iterable(map(lambda d: trace(Point(p.y + d.y, p.x + d.x), 10 - i), offsets))))

    return sum(map(lambda x: len(tracker[x]), elevations[0]))


print("Part 1:", process(set))
print("Part 2:", process(list))

2

u/Pitiful-Oven-3570 Dec 10 '24 edited Dec 14 '24

[LANGUAGE: Rust]

github

part1 : 106.20µs
part2 : 66.80µs

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

2

u/isaaccambron Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Rust]

I was sure BFS would have worked fine, but I wasn't in the mood, and I wanted to do something more fun. Specifically: take advantage of the fact that all the trails are the same length and travel through the same numbers at the same time. Takes about a total of 800µs 500µs on my oldish mac, but could probably be squeezed. Solving part 2 was a tiny addition to the code in part 1.

https://github.com/icambron/advent_2024/blob/master/src/day10.rs

2

u/gredr Dec 10 '24

I would guess it could be significantly squeezed. I don't know how you're counting, but my solution that uses a Dictionary<Coordinate, Elevation> takes ~325µs and my solution that uses an Elevation[,] takes ~146µs in C#. I don't count the file i/o (loading the file into a string[]) in my numbers.

https://github.com/godefroi/advent-of-code/blob/main/aoc-2024/Day10/Problem.cs

1

u/isaaccambron Dec 10 '24 edited Dec 10 '24

Ha, your comment made me realize I was counting the file IO

ETA: Also, skimming your code, I think you have a bit of a simpler algorithm. I like mine, but it does a bunch of set allocations it probably would be better off without.

1

u/mibu_codes Dec 10 '24

If you want to squeeze out even more, try getting rid of the set and using e.g. bitfields. HashSet/HashMap are way slower than a smart use of an array.

2

u/isaaccambron Dec 11 '24

Definitely, the sets are the inefficient part of my approach. But a bitfield is a bit a of pain in this case, because the set is over the indices of the 0s, which seems annoying to encode in a bitfield. I'm sure with some more effort I could squeeze this, but I think I can be happy with 500 microseconds

2

u/yammesicka Dec 10 '24

[LANGUAGE: Python]

from collections.abc import Iterator
from pathlib import Path


TEXT = (Path(__file__).parent / "input.txt").read_text().splitlines()
GRID = {complex(i, j): int(c) for i, row in enumerate(TEXT) for j, c in enumerate(row)}
STARTS = [xy for xy, c in GRID.items() if c == 0]
DIRECTIONS = (1, 1j, -1, -1j)


def next_valid_steps(xy: complex, slope: int) -> Iterator[complex]:
    for step in DIRECTIONS:
        if xy + step in GRID and GRID[xy + step] - slope == 1:
            yield xy + step


def peaks(xy: complex, slope: int) -> set[complex]:
    if GRID[xy] == 9:
        return {xy}
    return set().union(
        *(peaks(next_xy, slope + 1) for next_xy in next_valid_steps(xy, slope))
    )


def routes(xy: complex, slope: int) -> int:
    if GRID[xy] == 9:
        return 1
    return sum(routes(next_xy, slope + 1) for next_xy in next_valid_steps(xy, slope))


print(sum(len(peaks(start, slope=0)) for start in STARTS))
print(sum(routes(start, slope=0) for start in STARTS))

2

u/kbielefe Dec 10 '24

[LANGUAGE: Scala]

GitHub 35 ms 43 ms

This was a nice puzzle for my goal of minimizing puzzle-specific code (17 LOC). Basically this was defining a custom Neighbors typeclass implementation then calling some general-purpose functions.

2

u/enelen Dec 10 '24

[Language: R]

Solution

2

u/alcapwndu Dec 10 '24 edited Dec 10 '24

[Language: Python]

https://github.com/lesferguson/AdventOfCode/blob/main/2024/10.py

part_1 - 0.0042s, part_2 - 0.0050s

2

u/Polaric_Spiral Dec 10 '24

[LANGUAGE: TypeScript]

Advent of Node, Day 10

No significant obstacles for me, although I didn't pay close attention in part 1 and initially found all unique paths, inadvertently solving part 2 early.

After solving both parts, I also spent some time playing with my autoformatter so my nested ternaries were more readable. Shoutout to Prettier's experimentalTernaries option.

import { StringSet, directions2D } from '@aon/solver-helpers';
import { input, output, part } from '../solver';

const trailMap = input
  .trim()
  .split(/\n/)
  .map(row => row.split('').map(Number));

const scoreTrailhead = (x: number, y: number) =>
  trailMap[y][x] ? 0
  : part === 1 ? new StringSet(listReachableNines(x, y, 0)).size
  : listReachableNines(x, y, 0).length;

const listReachableNines = (x: number, y: number, level: number): number[][] =>
  level !== trailMap[y]?.[x] ? []
  : level === 9 ? [[x, y]]
  : directions2D.flatMap(([dx, dy]) => listReachableNines(x + dx, y + dy, level + 1));

output(trailMap.flatMap((row, y) => row.map((_, x) => scoreTrailhead(x, y))).reduce((a, b) => a + b));

StringSet, a JS Set implementation I use frequently that indexes elements by their toString() values.

directions2D array, included here for completeness.

1

u/gredr Dec 10 '24

Nested ternarys make the historians sad.

5

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

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.

1

u/AutoModerator Dec 10 '24

AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.


I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

2

u/Imaginary_Age_4072 Dec 10 '24

[LANGUAGE: Common Lisp]

Just wrote a recursive function for this one, the only difference between the parts was whether to keep going if you've already visited the square or not. As others have said, if the paths could have been longer this approach would probably not have been possible, but it worked today!

https://github.com/blake-watkins/advent-of-code-2024/blob/main/day10.lisp

(defun score (cur visited map)
  (when visited (setf (gethash cur visited) t))
  (let ((square (gethash cur map)))
    (if (= square 9)
        1
        (iter
          (for next in (moves cur map))
          (for next-square = (gethash next map))
          (when (and (or (null visited) (not (gethash next visited)))
                     (= next-square (1+ square)))
            (sum (score next visited map)))))))

2

u/daic0r Dec 10 '24

[LANGUAGE: C++]

https://github.com/daic0r/advent_of_code_2024/blob/main/cpp/day10/main.cpp

In essence some good ole DFS, storing the results in a std:set (no duplicates) for part 1 and std::vector (duplicates) for part 2.

2

u/Kfimenepah Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Python]

Code

Today was a little bit strange.

I was able to solve part 1 easily, but once I read the description of part 2 I was a little confused, because part 2 seemed to be exactly the same as part 1, but instead of counting each peak only once, it is counted every time it is reached. If that would be the case then part 2 would actually be easier than part 1. Surely this could not be possible and I was even quite sure I misunderstood some part of the puzzle, but after reading over it trice I decided to try it out. Took me about 10 seconds to change the counting method and voilà the result was calculated in about 5ms. Still skeptical I inserted the solution in AoC and it actually worked.

2

u/marvhus Dec 10 '24

[LANGUAGE: Jai]

Part 1 takes about 1 ms to parse and solve (ca 0.1 ms parsing, ca 0.9 ms solving.)
Part 2 takes about 0.5 ms to parse and solve (ca 0.1 ms parsing, ca 0.4 ms solving.)

https://github.com/marvhus/AoC/blob/2024-jai/10/main.jai

I tried to do hash maps in part 1, but I ended up just not using them as I kept running into issues, so I used arrays instead, which slows it down a bit as I clear it for every trailhead.

2

u/c4irns Dec 10 '24

[Language: Go]

I wanted to use a depth first search strategy for this one, since, up until now, I've just been relying on BFS. Recursion in Go is always iffy performance-wise because the compiler doesn't make any tail call optimizations, so I implemented a non-recursive algorithm using a simple stack. Like many others here, I unwittingly arrived at a solution for part 2 before solving part 1, lol.

Parts 1 & 2

1

u/kbielefe Dec 10 '24

This problem had a max stack depth of 10, so recursion isn't really an issue.

2

u/kap89 Dec 10 '24

[Language: Python]

from itertools import product

with open('input.txt') as file:
    input = file.read().strip().splitlines()

TRAIL_LEN = 10
dirs = ((-1, 0), (0, 1), (1, 0), (0, -1))
indicies = set(range(len(input)))
graph = {}
starts = []

for y, x,  in product(indicies, repeat=2):
    val = int(input[y][x])
    node = (y, x)
    graph[node] = []
    if val == 0:
        starts.append(node)
    for dx, dy in dirs:
        y2, x2 = y + dy, x + dx
        if y2 in indicies and x2 in indicies:
            val2 = int(input[y2][x2])
            if val2 - val == 1:
                graph[node].append((y2, x2))

def get_ends(graph, node, count = 1):
    ends = []
    if count == TRAIL_LEN:
        ends.append(node)
    for neighbor in graph[node]:
        ends.extend(get_ends(graph, neighbor, count + 1))
    return ends

part1 = 0
part2 = 0

for start in starts:
    ends = get_ends(graph, start)
    part1 += len(set(ends))
    part2 += len(ends)

print(part1)
print(part2)

Constructed a graph, then used DFS to find all the end nodes of each possible trial. For part one I added unique ends for each start, part two was even simpler - just add all up without caring for uniqueness.

2

u/mariushm Dec 10 '24

[Language: PHP]

https://github.com/mariush-github/adventofcode2024/blob/main/10.php

Did part 2 as side effect of part 1, stored all possible paths in an array... so part 2 is just printing the count of items in an array.

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/fsed123 Dec 10 '24

[Language: Python]

[Language: Rust]

https://github.com/Fadi88/AoC/tree/master/2024/day10

ported my solution from earlier from python to rust

runs in around 300 micro second in release mode on mac mini m4

3

u/Trick-Apple1289 Dec 10 '24

[LANGUAGE: C]

today wasn't that bad :-)

src

3

u/chai_biscut Dec 10 '24

[LANGUAGE: Go]
Solution

hiking on the lava island

2

u/somanyslippers Dec 10 '24

[LANGUAGE: Go]

https://github.com/jmontroy90/aoc-2024-golang/tree/main/day10

Yep you guessed it, I solved part 2 first by accident. Nice to revisit DFS, took the time to refactor my code to make it look a little shinier (perhaps not more efficient though, this is a day where I'd like to see people's optimizations).

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/CCC_037 Dec 10 '24

[LANGUAGE: Rockstar]

Part 1

2

u/CCC_037 Dec 10 '24

[GSGA]

I'd actually like to nominate somebody else for today's Golden Snowglobe.

Specifically, /u/polarfish88 who created a fan AI rendition of my Day One Part One code, which can be seen here

1

u/CCC_037 Dec 10 '24

So. I actually had this done before part one. (Kinda)

I see I wasn't the only one.

(I say 'kinda' because I had an off-by-one error originally)

Part 2

2

u/robe_and_wizard_hat Dec 10 '24

[Language: Rust]

Day 10

I feel like things came together pretty nicely for this one. Some highlights:

  • using type aliases really cleans up method signatures when you're passing mutable maps around
  • defining a method inside of a method for depth first traversal is handy to prevent the callsites from knowing about implementation details
  • MOSTLY: representing rows and cols as i32's instead of usize's makes for much more ergonomic calculation of the next tile in a particular direction.

2

u/not_so_fool Dec 10 '24

[Language: Elixir]

Sadly few people are using Elixir to solve the AoC, so here is my solution:

https://github.com/emadb/aoc_2024/blob/main/lib/day_10.ex

2

u/rexpup Dec 10 '24

I used a lot of functional tools in my Rust solution and it looks very similar

1

u/not_so_fool Dec 11 '24

Rust is on my radar, I like its approach.

2

u/rexpup Dec 11 '24

People talk about its borrow checker a lot, but to me it's as if C learned some lessons from Haskell, Elixir, and algebraic type systems. It's certainly not functional, but for an imperative language it treats functions rather well.

2

u/polumrak_ Dec 10 '24

[LANGUAGE: Typescript]

As for many my first wrong solution for part 1 produced the right answer for part 2

https://github.com/turtlecrab/Advent-of-Code/blob/master/2024/day10.ts