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.

  • @swlabr
    link
    English
    35 days ago

    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.

    • @ArchiteuthisOP
      link
      English
      25 days ago
      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"
      
      • @gerikson
        link
        English
        45 days ago
        re: 10 commentary

        apparently “everyone” did this. Me too

        • @zogwarg
          link
          English
          14 days ago
          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