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.

    • Architeuthis@awful.systemsOP
      link
      fedilink
      English
      arrow-up
      1
      ·
      edit-2
      23 days ago

      tl;dr: Day 5 was most perfectly fine code thrown out for me, because I ran face first into eliminating imaginary edge cases instead of starting out simple.

      5-1 commentary

      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.

      5-2 commentary and some code

      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.