Day 10: Hoof It
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
- sjmulder ( @sjmulder@lemmy.sdf.org ) 3•1 month ago
C
Tried a dynamic programming kind of thing first but recursion suited the problem much better.
Part 2 seemed incompatible with my visited list representation. Then at the office I suddenly realised I just had to skip a single if(). Funny how that works when you let things brew in the back of your mind.
Code
#include "common.h" #define GZ 43 /* * To avoid having to clear the 'seen' array after every search we mark * and check it with a per-search marker value ('id'). */ static char g[GZ][GZ]; static int seen[GZ][GZ]; static int score(int id, int x, int y, int p2) { if (x<0 || x>=GZ || y<0 || y>=GZ || (!p2 && seen[y][x] == id)) return 0; seen[y][x] = id; if (g[y][x] == '9') return 1; return (g[y-1][x] == g[y][x]+1 ? score(id, x, y-1, p2) : 0) + (g[y+1][x] == g[y][x]+1 ? score(id, x, y+1, p2) : 0) + (g[y][x-1] == g[y][x]+1 ? score(id, x-1, y, p2) : 0) + (g[y][x+1] == g[y][x]+1 ? score(id, x+1, y, p2) : 0); } int main(int argc, char **argv) { int p1=0,p2=0, id=1, x,y; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); for (y=0; y
- lwhjp ( @lwhjp@lemmy.sdf.org ) 2•1 month ago
I bet that search would look cool visualized.
- sjmulder ( @sjmulder@lemmy.sdf.org ) 2•1 month ago
Here it is! https://sjmulder.nl/2024/aoc-day10.mp4
- lwhjp ( @lwhjp@lemmy.sdf.org ) 1•1 month ago
Oooh! Pretty!
- janAkali ( @janAkali@lemmy.one ) English3•1 month ago
Nim
As many others today, I’ve solved part 2 first and then fixed a ‘bug’ to solve part 1. =)
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
- lwhjp ( @lwhjp@lemmy.sdf.org ) 3•1 month ago
Haskell
A nice easy one today: didn’t even have to hit this with the optimization hammer.
import Data.Char import Data.List import Data.Map (Map) import Data.Map qualified as Map readInput :: String -> Map (Int, Int) Int readInput s = Map.fromList [ ((i, j), digitToInt c) | (i, l) <- zip [0 ..] (lines s), (j, c) <- zip [0 ..] l ] findTrails :: Map (Int, Int) Int -> [[[(Int, Int)]]] findTrails input = Map.elems . Map.map (filter ((== 10) . length)) $ Map.restrictKeys accessible starts where starts = Map.keysSet . Map.filter (== 0) $ input accessible = Map.mapWithKey getAccessible input getAccessible (i, j) h | h == 9 = [[(i, j)]] | otherwise = [ (i, j) : path | (di, dj) <- [(-1, 0), (0, 1), (1, 0), (0, -1)], let p = (i + di, j + dj), input Map.!? p == Just (succ h), path <- accessible Map.! p ] main = do trails <- findTrails . readInput <$> readFile "input10" mapM_ (print . sum . (`map` trails)) [length . nub . map last, length]
Rust
Definitely a nice and easy one, I accidentally solved part 2 first, because I skimmed the challenge and missed the unique part.
#[cfg(test)] mod tests { const DIR_ORDER: [(i8, i8); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)]; fn walk_trail(board: &Vec>, level: i8, i: i8, j: i8) -> Vec<(i8, i8)> { let mut paths = vec![]; if i < 0 || j < 0 { return paths; } let actual_level = match board.get(i as usize) { None => return paths, Some(line) => match line.get(j as usize) { None => return paths, Some(c) => c, }, }; if *actual_level != level { return paths; } if *actual_level == 9 { return vec![(i, j)]; } for dir in DIR_ORDER.iter() { paths.extend(walk_trail(board, level + 1, i + dir.0, j + dir.1)); } paths } fn count_unique(p0: &Vec<(i8, i8)>) -> u32 { let mut dedup = vec![]; for p in p0.iter() { if !dedup.contains(p) { dedup.push(*p); } } dedup.len() as u32 } #[test] fn day10_part1_test() { let input = std::fs::read_to_string("src/input/day_10.txt").unwrap(); let board = input .trim() .split('\n') .map(|line| { line.chars() .map(|c| { if c == '.' { -1 } else { c.to_digit(10).unwrap() as i8 } }) .collect::>() }) .collect::>>(); let mut total = 0; for (i, row) in board.iter().enumerate() { for (j, pos) in row.iter().enumerate() { if *pos == 0 { let all_trails = walk_trail(&board, 0, i as i8, j as i8); total += count_unique(&all_trails); } } } println!("{}", total); } #[test] fn day10_part2_test() { let input = std::fs::read_to_string("src/input/day_10.txt").unwrap(); let board = input .trim() .split('\n') .map(|line| { line.chars() .map(|c| { if c == '.' { -1 } else { c.to_digit(10).unwrap() as i8 } }) .collect::>() }) .collect::>>(); let mut total = 0; for (i, row) in board.iter().enumerate() { for (j, pos) in row.iter().enumerate() { if *pos == 0 { total += walk_trail(&board, 0, i as i8, j as i8).len(); } } } println!("{}", total); } }
- SteveDinn ( @SteveDinn@lemmy.ca ) 2•1 month ago
C#
using System.Diagnostics; using Common; namespace Day10; static class Program { static void Main() { var start = Stopwatch.GetTimestamp(); var sampleInput = Input.ParseInput("sample.txt"); var programInput = Input.ParseInput("input.txt"); Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}"); Console.WriteLine($"Part 1 input: {Part1(programInput)}"); Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}"); Console.WriteLine($"Part 2 input: {Part2(programInput)}"); Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}"); } static object Part1(Input i) => GetTrailheads(i) .Sum(th => CountTheNines(th, i, new HashSet(), false)); static object Part2(Input i) => GetTrailheads(i) .Sum(th => CountTheNines(th, i, new HashSet(), true)); static int CountTheNines(Point loc, Input i, ISet visited, bool allPaths) { if (!visited.Add(loc)) return 0; var result = (ElevationAt(loc, i) == 9) ? 1 : loc.GetCardinalMoves() .Where(move => move.IsInBounds(i.Bounds.Row, i.Bounds.Col)) .Where(move => (ElevationAt(move, i) - ElevationAt(loc, i)) == 1) .Where(move => !visited.Contains(move)) .Sum(move => CountTheNines(move, i, visited, allPaths)); if(allPaths) visited.Remove(loc); return result; } static IEnumerable GetTrailheads(Input i) => Grid.EnumerateAllPoints(i.Bounds) .Where(loc => ElevationAt(loc, i) == 0); static int ElevationAt(Point p, Input i) => i.Map[p.Row][p.Col]; } public class Input { public required Point Bounds { get; init; } public required int[][] Map { get; init; } public static Input ParseInput(string file) { using var reader = new StreamReader(file); var map = reader.EnumerateLines() .Select(l => l.Select(c => (int)(c - '0')).ToArray()) .ToArray(); var bounds = new Point(map.Length, map.Max(l => l.Length)); return new Input() { Map = map, Bounds = bounds, }; } }
- SteveDinn ( @SteveDinn@lemmy.ca ) 2•1 month ago
Straightforward depth first search. I found that the only difference for part 2 was to remove the current location from the HashSet of visited locations when the recurive call finished so that it could be visited again in other unique paths.
- ystael ( @ystael@beehaw.org ) 2•1 month ago
J
Who needs recursion or search algorithms? Over here in line noise array hell, we have built-in sparse matrices! :)
data_file_name =: '10.data' grid =: "."0 ,. > cutopen fread data_file_name data =: , grid 'rsize csize' =: $ grid inbounds =: monad : '(*/ y >: 0 0) * (*/ y < rsize, csize)' coords =: ($ grid) & #: uncoords =: ($ grid) & #. NB. if n is the linear index of a point, neighbors n lists the linear indices NB. of its orthogonally adjacent points neighbors =: monad : 'uncoords (#~ inbounds"1) (coords y) +"1 (4 2 $ 1 0 0 1 _1 0 0 _1)' uphill1 =: dyad : '1 = (y { data) - (x { data)' uphill_neighbors =: monad : 'y ,. (#~ (y & uphill1)) neighbors y' adjacency_of =: monad define edges =. ; (< @: uphill_neighbors"0) i.#y NB. must explicitly specify fill of integer 0, default is float 1 edges} 1 $. ((#y), #y); (0 1); 0 ) adjacency =: adjacency_of data NB. maximum path length is 9 so take 9th power of adjacency matrix leads_to_matrix =: adjacency (+/ . *)^:8 adjacency leads_to =: dyad : '({ & leads_to_matrix) @: < x, y' trailheads =: I. data = 0 summits =: I. data = 9 scores =: trailheads leads_to"0/ summits result1 =: +/, 0 < scores result2 =: +/, scores
- sjmulder ( @sjmulder@lemmy.sdf.org ) 2•1 month ago
For some reason the code appears to be HTML escaped (I’m using the web interface on https://lemmy.sdf.org)
- ystael ( @ystael@beehaw.org ) 2•1 month ago
Yes. I don’t know whether this is a beehaw specific issue (that being my home instance) or a lemmy issue in general, but < and & are HTML escaped in all code blocks I see. Of course, this is substantially more painful for J code than many other languages.
- Gobbel2000 ( @Gobbel2000@programming.dev ) 2•1 month ago
Rust
This was a nice one. Basically 9 rounds of Breadth-First-Search, which could be neatly expressed using
fold
. The only difference between part 1 and part 2 turned out to be the datastructure for the search frontier: TheHashSet
in part 1 unifies paths as they join back to the same node, theVec
in part 2 keeps all paths separate.Solution
use std::collections::HashSet; fn parse(input: &str) -> Vec<&[u8]> { input.lines().map(|l| l.as_bytes()).collect() } fn adj(grid: &[&[u8]], (x, y): (usize, usize)) -> Vec<(usize, usize)> { let n = grid[y][x]; let mut adj = Vec::with_capacity(4); if x > 0 && grid[y][x - 1] == n + 1 { adj.push((x - 1, y)) } if y > 0 && grid[y - 1][x] == n + 1 { adj.push((x, y - 1)) } if x + 1 < grid[0].len() && grid[y][x + 1] == n + 1 { adj.push((x + 1, y)) } if y + 1 < grid.len() && grid[y + 1][x] == n + 1 { adj.push((x, y + 1)) } adj } fn solve(input: String, trailhead: fn(&[&[u8]], (usize, usize)) -> u32) -> u32 { let grid = parse(&input); let mut sum = 0; for (y, row) in grid.iter().enumerate() { for (x, p) in row.iter().enumerate() { if *p == b'0' { sum += trailhead(&grid, (x, y)); } } } sum } fn part1(input: String) { fn score(grid: &[&[u8]], start: (usize, usize)) -> u32 { (1..=9) .fold(HashSet::from([start]), |frontier, _| { frontier.iter().flat_map(|p| adj(grid, *p)).collect() }) .len() as u32 } println!("{}", solve(input, score)) } fn part2(input: String) { fn rating(grid: &[&[u8]], start: (usize, usize)) -> u32 { (1..=9) .fold(vec![start], |frontier, _| { frontier.iter().flat_map(|p| adj(grid, *p)).collect() }) .len() as u32 } println!("{}", solve(input, rating)) } util::aoc_main!();
Also on github
- Ananace ( @ace@lemmy.ananace.dev ) 2•1 month ago
Nice to have a really simple one for a change, both my day 1 and 2 solutions worked on their very first attempts.
I rewrote the code to combine the two though, since the implementations were almost identical for both solutions, and also to replace the recursion with a search list instead.C#
int[] heights = new int[0]; (int, int) size = (0, 0); public void Input(IEnumerable lines) { size = (lines.First().Length, lines.Count()); heights = string.Concat(lines).Select(c => int.Parse(c.ToString())).ToArray(); } int trails = 0, trailheads = 0; public void PreCalc() { for (int y = 0; y < size.Item2; ++y) for (int x = 0; x < size.Item1; ++x) if (heights[y * size.Item1 + x] == 0) { var unique = new HashSet<(int, int)>(); trails += CountTrails((x, y), unique); trailheads += unique.Count; } } public void Part1() { Console.WriteLine($"Trailheads: {trailheads}"); } public void Part2() { Console.WriteLine($"Trails: {trails}"); } int CountTrails((int, int) from, HashSet<(int,int)> unique) { int found = 0; List<(int,int)> toSearch = new List<(int, int)>(); toSearch.Add(from); while (toSearch.Any()) { var cur = toSearch.First(); toSearch.RemoveAt(0); int height = heights[cur.Item2 * size.Item1 + cur.Item1]; for (int y = -1; y <= 1; ++y) for (int x = -1; x <= 1; ++x) { if ((y != 0 && x != 0) || (y == 0 && x == 0)) continue; var newAt = (cur.Item1 + x, cur.Item2 + y); if (newAt.Item1 < 0 || newAt.Item1 >= size.Item1 || newAt.Item2 < 0 || newAt.Item2 >= size.Item2) continue; int newHeight = heights[newAt.Item2 * size.Item1 + newAt.Item1]; if (newHeight - height != 1) continue; if (newHeight == 9) { unique.Add(newAt); found++; continue; } toSearch.Add(newAt); } } return found; }
- jdnewmil ( @jdnewmil@lemmy.ca ) 1•1 month ago
Python
Sets of tuples and iteration for both first and second parts. A list of tuples used as a stack for the conversion of recursion to iteration. Dictionary of legal trail moves for traversal. Type hints for antibugging in VSCode. Couple of seconds runtime for each part.
https://github.com/jdnewmil/aocpy/blob/master/aocpy%2Faoc2024%2Fday10.py
- hades ( @hades@lemm.ee ) 1•1 month ago
C#
using QuickGraph; using QuickGraph.Algorithms.Search; using Point = (int, int); public class Day10 : Solver { private int[][] data; private int width, height; private List destinations_counts = [], paths_counts = []; private record PointEdge(Point Source, Point Target): IEdge; private DelegateVertexAndEdgeListGraph MakeGraph() => new(AllPoints(), GetNeighbours); private static readonly List directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]; private bool GetNeighbours(Point from, out IEnumerable result) { List neighbours = []; int next_value = data[from.Item2][from.Item1] + 1; foreach (var (dx, dy) in directions) { int x = from.Item1 + dx, y = from.Item2 + dy; if (x < 0 || y < 0 || x >= width || y >= height) continue; if (data[y][x] != next_value) continue; neighbours.Add(new(from, (x, y))); } result = neighbours; return true; } private IEnumerable AllPoints() => Enumerable.Range(0, width).SelectMany(x => Enumerable.Range(0, height).Select(y => (x, y))); public void Presolve(string input) { data = input.Trim().Split("\n").Select(s => s.Select(ch => ch - '0').ToArray()).ToArray(); width = data[0].Length; height = data.Length; var graph = MakeGraph(); for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { if (data[j][i] != 0) continue; var search = new BreadthFirstSearchAlgorithm(graph); Point start = (i, j); Dictionary paths_into = []; paths_into[start] = 1; var destinations = 0; var paths = 0; search.ExamineEdge += edge => { paths_into.TryAdd(edge.Target, 0); paths_into[edge.Target] += paths_into[edge.Source]; }; search.FinishVertex += vertex => { if (data[vertex.Item2][vertex.Item1] == 9) { paths += paths_into[vertex]; destinations += 1; } }; search.SetRootVertex(start); search.Compute(); destinations_counts.Add(destinations); paths_counts.Add(paths); } } } public string SolveFirst() => destinations_counts.Sum().ToString(); public string SolveSecond() => paths_counts.Sum().ToString(); }
- Quant ( @Quant@programming.dev ) English1•1 month ago
Uiua
After finally deciding to put aside Day 9 Part 2 for now, this was really easy actually. The longest was figuring out how many extra dimensions I had to give some arrays and where to remove those again (and how). Then part 2 came along and all I had to do was remove a single character (not removing duplicates when landing on the same field by going different ways from the same starting point). Basically, everything in the parentheses of the
Trails!
macro was my solution for part 1, just that the^0
was◴
(deduplicate). Once that was removed, the solution for part 2 was there as well.Run with example input here
Note: in order to use the code here for the actual input, you have to replace
=₈
with=₅₀
because I was too lazy to make it work with variable array sizes this time.$ 89010123 $ 78121874 $ 87430965 $ 96549874 $ 45678903 $ 32019012 $ 01329801 $ 10456732 . Adj ← ¤[0_¯1 0_1 ¯1_0 1_0] Trails! ← ( ⊚=0. ⊙¤ ≡(□¤) 1 ⍥(⊙(≡(□^0/⊂≡(+¤)⊙¤°□)⊙Adj ≡(□▽¬≡/++⊃=₋₁=₈.°□)) +1⟜⊸⍚(▽=⊙(:⟜⊡)) )9 ⊙◌◌ ⧻/◇⊂ ) PartOne ← ( # &rs ∞ &fo "input-10.txt" ⊜∵⋕≠@\n. Trails!◴ ) PartTwo ← ( # &rs ∞ &fo "input-10.txt" ⊜∵⋕≠@\n. Trails!∘ ) &p "Day 10:" &pf "Part 1: " &p PartOne &pf "Part 2: " &p PartTwo
- the_beber ( @the_beber@lemm.ee ) 1•1 month ago
Kotlin
- Clean ❌
- Fast ❌
- Worked first try ✅
Code:
fun main() { /** * The idea is simple: Just simulate the pathing and sum all the end points */ fun part1(input: List): Int { val topologicalMap = Day10Map(input) val startingPoints = topologicalMap.asIterable().indicesWhere { it == 0 } val directions = Orientation.entries.map { it.asVector() } return startingPoints.sumOf { startingPoint -> var wayPoints = setOf(VecNReal(startingPoint)) val endPoints = mutableSetOf() while (wayPoints.isNotEmpty()) { wayPoints = wayPoints.flatMap { wayPoint -> directions.map { direction -> val checkoutLocation = wayPoint + direction checkoutLocation to runCatching { topologicalMap[checkoutLocation] }.getOrElse { -1 } }.filter { nextLocation -> val endPointHeight = topologicalMap[wayPoint] if (nextLocation.second - 1 == endPointHeight && nextLocation.second == 9) false.also { endPoints.add(nextLocation.first) } else if (nextLocation.second - 1 == endPointHeight) true else false }.map { it.first } }.toSet() } endPoints.count() } } /** * A bit more complicated, but not by much. * Main difference is, that node accumulates all the possible paths, thus adding all the possibilities of * its parent node. */ fun part2(input: List): Int { val topologicalMap = Day10Map(input) val startingPoints = topologicalMap.asIterable().indicesWhere { it == 0 } val directions = Orientation.entries.map { it.asVector() } return startingPoints.sumOf { startingPoint -> var pathNodes = setOf(Node(VecNReal(startingPoint), topologicalMap[VecNReal(startingPoint)], 1)) val endNodes = mutableSetOf() while (pathNodes.isNotEmpty()) { pathNodes = pathNodes.flatMap { pathNode -> directions.map { direction -> val nextNodeLocation = pathNode.position + direction val nextNodeHeight = runCatching { topologicalMap[nextNodeLocation] }.getOrElse { -1 } Node(nextNodeLocation, nextNodeHeight, pathNode.weight) }.filter { nextNode -> nextNode.height == pathNode.height + 1 } }.groupBy { it.position }.map { (position, nodesUnadjusted) -> val adjustedWeight = nodesUnadjusted.sumOf { node -> node.weight } Node(position, nodesUnadjusted.first().height, adjustedWeight) }.filter { node -> if (node.height == 9) false.also { endNodes.add(node) } else true }.toSet() } endNodes.sumOf { endNode -> endNode.weight } } } val testInput = readInput("Day10_test") check(part1(testInput) == 36) check(part2(testInput) == 81) val input = readInput("Day10") part1(input).println() part2(input).println() } class Day10Map(input: List): Grid2D(input.map { row -> row.map { "$it".toInt() } }) { init { transpose() } } data class Node(val position: VecNReal, val height: Int, val weight: Int = 1)
- Rin ( @Rin@lemm.ee ) 1•1 month ago
TypeScript
Maaaannnn. Today’s solution was really something. I actually got so confused initially that I unknowingly wrote the algorithm for part 2 before I even finished part 1! As an upside, however, I did expand my own Advent of Code standard library ;)
Solution
import { AdventOfCodeSolutionFunction } from "./solutions"; import { Grid } from "./utils/grids"; import { LinkedPoint } from "./utils/structures/linkedPoint"; import { makeGridFromMultilineString, SumArray } from "./utils/utils"; class TrailPoint extends LinkedPoint { constructor(x: number, y: number, item: number, grid: Grid) { super(x, y, item, grid); } lookAroundValid(): Array { return this.lookAround().filter(v => v.item == this.item + 1); } findAllValidPeaks(): Array { if (this.item == 9) return [this]; // filter for distinct references (this theoretically saves time) return [...(new Set(this.lookAroundValid().flatMap(v => v.findAllValidPeaks())))]; } findAllValidPeaksWithReps(): Array { if (this.item == 9) return [this]; // don't filter return this.lookAroundValid().flatMap(v => v.findAllValidPeaksWithReps()); } } export const solution_10: AdventOfCodeSolutionFunction = (input) => { const map: Grid = makeGridFromMultilineString(input) .map((row) => row.map((item) => item != "." ? Number(item) : -1)) .map((row, y) => row.map((item, x) => new TrailPoint(x, y, item, undefined!))); map.flat().forEach((v) => v.grid = map); // promise is a promise const startNodes: Array = map.flat().filter(v => v.item == 0); const part_1 = SumArray(startNodes.map(v => v.findAllValidPeaks().length)); const part_2 = SumArray(startNodes.map(v => v.findAllValidPeaksWithReps().length)); return { part_1, // 557 part_2, // 1062 } }