NotAwfulTech

385 readers

3 users here now

a community for posting cool tech news you don’t want to sneer at

non-awfulness of tech is not required or else we wouldn’t have any posts

founded 1 year ago

MODERATORS

[email protected]

Advent of Code 2024 - Historian goes looking for history in all the wrong places (adventofcode.com)

submitted 3 weeks ago by [email protected] to c/[email protected]

54 comments fedilink hide all child comments

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.

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 2 points 2 weeks ago* (last edited 2 weeks 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.