copy pasting the rules from last year’s thread:
Rules: no spoilers.
The other rules are made up aswe go along.
Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.
Day 10. I lied about doing this later, I guess.
p1, 2 I accidentally solved 2. before 1.
My initial code was: for every 9, mark that square with a score of 1. Then: for (I = 8, then 7 … 0) => mark the square with the sum of the scores of the squares around it with a value of i + 1.
Except that gives you all the ways to reach 9s from a 0, which is part 2. For part 1, I changed the scores to be sets of reachable 9s, and the score of a square was the size of the set at that position.
10 commentary
Yeah basically if you were doing DFS and forgot to check if you’d already visited the next node you were solving for pt2, since the rule about the next node always having a value of +1 compared to the current one was already preventing cyclic paths.
10 Code
Hardly a groundbreaking implementation but I hadn’t posted actual code in a while so
(* F# - file reading code and other boilerplate omited *)
let mapAllTrails (matrix : int array2d) =
let rowCount = matrix |> Array2D.length1
let colCount = matrix |> Array2D.length2
let rec search (current:int*int) (visited: HashSet<int*int>) (path: (int*int) list) : (int*int) list list=
let (row,col) = current
let currentValue = matrix.[row,col]
// Remove to solve for 10-2
visited.Add (row,col) |> ignore
// If on a 9 return the complete path
if currentValue = 9 then [List.append path [row,col] ]
// Otherwise filter for eligible neihboring cells and continue search
else
[ row-1, col;row, col-1; row, col+1; row+1,col]
|> List.filter (fun (r,c) ->
not (visited.Contains(r,c))
&& r >= 0 && c>=0 && r < rowCount && c < colCount
&& matrix.[r,c]-currentValue = 1 )
|> List.collect (fun next ->
[row,col]
|> List.append path
|> search next visited)
// Find starting cells, i.e. contain 0
matrix
|> Global.matrixIndices
|> Seq.filter (fun (row,col) -> matrix.[row,col] = 0)
// Find all trails starting from those cells and flatten the result
|> Seq.collect (fun trailhead -> search trailhead (HashSet<int*int>()) [])
"./input.example"
|> Common.parse
|> mapAllTrails
|> Seq.length
|> Global.shouldBe 81
"./input.actual"
|> Common.parse
|> mapAllTrails
|> Seq.length
|> printfn "The sum total of trail rankings is %d"
re:10
Mwahaha I’m just lazy and did are “unique” (single word dropped for part 2) of start/end pairs.
#!/usr/bin/env jq -n -R -f
([
inputs/ "" | map(tonumber? // -1) | to_entries
] | to_entries | map( # '.' = -1 for handling examples #
.key as $y | .value[]
| .key as $x | .value | { "\([$x,$y])":[[$x,$y],.] }
)|add) as $grid | # Get indexed grid #
[
($grid[]|select(last==0)) | [.] | # Start from every '0' head
recurse( #
.[-1][1] as $l | # Get altitude of current trail
( #
.[-1][0] #
| ( .[0] = (.[0] + (1,-1)) ), #
( .[1] = (.[1] + (1,-1)) ) #
) as $np | # Get all possible +1 steps
if $grid["\($np)"][1] != $l + 1 then
empty # Drop path if invalid
else #
. += [ $grid["\($np)"] ] # Build path if valid
end #
) | select(last[1]==9) # Only keep complete trails
| . |= [first,last] # Only Keep start/end
]
# Get score = sum of unique start/end pairs.
| group_by(first) | map(unique|length) | add
