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.

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"

Principal Skinner moment

“Did I miscopy the input?”

“No, it is my algorithm that is wrong”

kinda satisfying to figure out I was correct all along.

Part 2 is not as fast as I’d like (14s), but faster than it was. People on reddit are wittering on about search trees, me I just sling Perl hashrefs around

https://github.com/gustafe/aoc2024/blob/main/d09-Disk-Fragmenter.pl

Eric added some 0s in the grid which fucked up my existence code, sneaky devil

#include <string>
#include <iostream>
#include <sstream>

int main() {
  int safe = 0;
  std::string s;
  while (std::getline(std::cin, s)) {
    std::istringstream iss(s);
    int a, b, c;
    if (!(iss >> a >> b)) {
      safe++; continue;
    }
    if (a == b || std::abs(a-b) > 3) continue;
    bool increasing = b > a;
    while (iss >> c) {
      if (b == c || std::abs(b-c) > 3) goto structuredprogrammingisfornerds;
      switch (increasing) {
        case false:
          if (c < b) { b = c; continue; }
          goto structuredprogrammingisfornerds;
        case true:
          if(c > b) { b = c; continue; }
          goto structuredprogrammingisfornerds;
      }
    }
    safe++;
    structuredprogrammingisfornerds:;
  }
  std::cout << safe << std::endl;
}

I got bit by the input being more than one line. Embarrasing.

One of the lines of my input had a don’t() first, but I got bit by it being more lines as well.

I went straight into a rabbit hole of doing graph traversal to find all implicit rules (i.e. 1|2, 2|3, 3|4 imply 1|3, 1|4, 2|4) so I could validate updates by making sure all consequent pairs appear in the expanded ruleset. Basically I would depth first search a tree with page numbers for nodes and rules for edges, to get all branches and recombine them to get the full ruleset.

So ideally 1|2, 2|3, 3|4 -> 1|2|3|4 -> 1|2, 2|3, 3|4, 1|3, 1|4, 2|4

Except I forgot the last part and just returned the branch elements pairwise in sequence, which is just the original rules, which I noticed accidentally after the fact since I was getting correct results, because apparently it was completely unnecessary and I was just overthinking myself into several corners at the same time.

The obvious cornerstone was the comparison function to reorder the invalid updates, this is what I came up with:

let comparerFactory (ruleset: (int*int) list) :int -> int -> int = 
    let leftIndex = 
        ruleset 
        |> List.groupBy fst 
        |> List.map (fun (key,grp)-> key, grp |> List.map snd)
        |> Map.ofList

    fun page1 page2 -> 
        match (leftIndex  |> Map.tryFind page1) with
        | Some afterSet when afterSet |> List.contains page2 -> -1
        | _ -> 1

The memoization pattern is for caching an index of rules grouped by the before page, so I can sort according to where each part of the comparison appears. I started out with having a second index where the key was the ‘after’ page of the rule which I would check if the page didn’t appear on the left side of any rule, but it turned out I could just return the opposite case, so again unnecessary.

Same, except in 4-1 I used a recursive function to traverse each direction according to the offset decided by the selected direction (like SW is row++,col–) , due to functional programming induced brain damage.

Would have been pretty useful too if 4-2 turned out to be about finding longer patterns, instead of smaller and in half the directions.

Inlined some stuff to fit everything in one function:

let rec isXmas (row:int) (col:int) (dir:int) (depth:int) (arr: char array2d) : bool =
    let value = arr.[row,col]
    if depth = 3
    then value = 'S'
    else if  [|'X';'M';'A';'S'|].[depth] = value
    then
        let (nextRow, nextCol) =
            match dir with
            | 1 -> row + 1, col - 1
            | 2 -> row + 1, col
            | 3 -> row + 1, col + 1
            | 4 -> row, col - 1
            | 6 -> row, col + 1
            | 7 -> row - 1, col - 1
            | 8 -> row - 1, col
            | 9 -> row - 1, col + 1
            | _ -> failwith $"{dir} isn't a numpad direction." 

        let rowCount = arr |> Array2D.length1
        let colCount = arr |> Array2D.length2
       
        if nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount
        then isXmas nextRow nextCol dir (depth+1) arr
        else false
    else false

Then you run this for every appropriately pruned ‘X’ times every direction and count the trues.