In this post I'll share my solution to Advent of Code 2024 - Day 5 using F#.

HAMINIONs Members get full access to the project files so you can git clone and run it yourself.

Day 5 - Part 1

Prompt: https://adventofcode.com/2024/day/5

Given:

• Page ordering rules: X|Y
  • If X and Y in list, X must come before Y
• Pages in each update
  • x,y,z

Ask:

• Find the pages in correct order
  • Sum the middle element of each of these

SubProblems

• A: How to tell if stuff is in order or not
  • A.1:
    • Set of numbers to left
    • lookup of number to vals that must be after it
    • iterate over pages - O(n * m)
      • add page to set of numbers to left
      • Lookup number and see if any rules match
      • If they do -> bad
    • If fine - fine

Solutions:

• A: Preprocess input, check if each is in order, sum middle - O(2n + n * m^2), 2n
  • Process input into list of page lists - O(n), n
  • Process input int lookup of X -> [Y, Y, ...] - O(n), n
    • (All page rules saying X comes before Y)
  • Function - is_page_in_order - O(pages length * rule length)
    • Set of pages to left of pointer
    • Iterate over all pages
      • get current page
      • get current page rules for things that come after it
      • if any of those rules include pages to left -> invalid
      • add current page to pages to left
    • return is_valid
  • Iterate over every page list, checking is_page_in_order - O(n * is_page_in_order)
  • Keep only the ones in order
  • Return sum of the middle thing

Code:

type Day5Input = 
    {
        NumberToValuesAfterIt: IDictionary<int, int list>
        Pages: int list list
    }

let read_input 
    (file_name: string)
    : Day5Input
    =

    let lines = 
        Utils.read_all_input_file_lines
            file_name

    let x_to_vals_after_it = 
        lines 
        |> Seq.filter (fun l -> l.Contains("|"))
        |> Seq.map(fun l -> l.Split("|"))
        |> Seq.map(fun vals -> (vals[0], vals[1]))
        |> Seq.groupBy(fun (x, y) -> x)
        |> Seq.map (fun (x, groups) -> 
            let just_ys = 
                groups 
                |> Seq.map (fun g -> int (snd g))
                |> Seq.toList

            ((int x), just_ys)
        )
        |> dict

    let all_pages = 
        lines 
        |> Seq.filter(fun l -> l.Contains(","))
        |> Seq.map(fun l -> l.Split(","))
        |> Seq.map(fun vals -> 
            vals 
            |> Seq.map (fun v -> int v)
            |> Seq.toList)
        |> Seq.toList

    {
        NumberToValuesAfterIt = x_to_vals_after_it
        Pages = all_pages
    }

let is_page_in_order
    (page_to_pages_after_it: IDictionary<int, int list>)
    (pages: int list)
    : bool 
    = 

    let mutable pages_to_left = Set.ofList [pages[0]]
    let mutable is_valid = true 

    for i = 1 to pages.Length - 1 do 
        let current_page = pages[i]

        match page_to_pages_after_it.TryGetValue current_page with 
        | false, _ -> () 
        | true, pages_that_must_come_later -> 
            let page_in_wrong_order = 
                pages_that_must_come_later
                |> Seq.exists (fun p -> 
                    pages_to_left.Contains(p)
                )

            if page_in_wrong_order then 
                is_valid <- false

        pages_to_left <- pages_to_left.Add(current_page)

    is_valid


let solve_part1 
    (file_name: string) 
    =

    printfn "Day 5.1: Solving"

    let input = read_input file_name

    let is_in_order =
        is_page_in_order input.NumberToValuesAfterIt

    let total = 
        input.Pages
        |> Seq.choose (fun page -> 
            match is_in_order (page |> Seq.toList) with
            | true -> Some page 
            | false -> None  
        )
        |> Seq.map (fun valid_pages -> 
            valid_pages[valid_pages.Length / 2]
        )
        |> Seq.sum

    printfn "Day 5.1: Total: %A" total

My Answer -> Accepted

Day 5 - Part 2

Prompt: https://adventofcode.com/2024/day/5

Given:

• Same input as above

Ask:

• Find only incorrect pages
  • Put them in order
  • Then sum up the middle bits

Subproblems:

• A: How to reorder
  • A.1: Just randomize til we find one? -> May never finish
  • A.2: Try all combos of ordering... - O(m^2 * m) -> Permutations so is (n!)
  • A.3: If too slow, could do some sort of topological sort w a graph

Solutions:

• A: Brute force - O(n * m!)
  • I tried to do this but eventually realized (after trying to figure out why my soln wasn't finished after 10+ mins) this leads to a O(n * m!) solution and m! gets REALLY big. My test / debug input finished quickly but the real input never got past even the first page check. On investigation I realized this was smth like 20! which is 2.432902e+18 or 2432901000000000000 which like 2 quintillion or smth. Even at 1000 cals per second we'd take ~2432901000000000 seconds which is like 77k years or smth (my math is probably wrong) but anyway WAY too much time.
• B: Sort this stuff - O(n * mlogm), ~3n
  • If we think ab it, the page ordering rules are just ways to order pages. We already have pretty efficient algorithms for sorting so if we could leverage that then we could potentially order any out-of-order page in ~O(mlogm)
  • Preprocess the input so we have both the X before Y and Y before X rules
  • Then use those rules in a custom comparer to determine ordering. If no set ordering, consider them equal.
  • Caveat: This works if we have a stable ordering. It's possible the page orders we're given have cycles in which case this could be an instable sort and lead to an infinite loop or smth (F# crashes on this). Luckily AOC does seem to give us orderings without cycles so this seems to work okay.

Code:

type Day5Input2 = 
    {
        NumberToValuesAfterIt: IDictionary<int, int Set>
        NumberToValuesBeforeIt: IDictionary<int, int Set>
        Pages: int list list
    }

let read_input2 
    (file_name: string)
    : Day5Input2
    =

    let lines = 
        Utils.read_all_input_file_lines
            file_name

    let all_x_y_pairs = 
        lines 
        |> Seq.filter (fun l -> l.Contains("|"))
        |> Seq.map(fun l -> l.Split("|"))
        |> Seq.map(fun vals -> (vals[0], vals[1]))


    let x_to_vals_after_it = 
        all_x_y_pairs
        |> Seq.groupBy(fun (x, y) -> x)
        |> Seq.map (fun (x, groups) -> 
            let just_ys = 
                groups 
                |> Seq.map (fun g -> int (snd g))
                |> Seq.toList
                |> Set.ofList

            ((int x), just_ys)
        )
        |> dict

    let y_to_vals_before_it = 
        all_x_y_pairs
        |> Seq.groupBy(fun (x, y) -> y)
        |> Seq.map (fun (y, groups) -> 
            let just_xs = 
                groups 
                |> Seq.map (fun g -> int (fst g))
                |> Seq.toList
                |> Set.ofList

            ((int y), just_xs)
        )
        |> dict


    let all_pages = 
        lines 
        |> Seq.filter(fun l -> l.Contains(","))
        |> Seq.map(fun l -> l.Split(","))
        |> Seq.map(fun vals -> 
            vals 
            |> Seq.map (fun v -> int v)
            |> Seq.toList)
        |> Seq.toList

    {
        NumberToValuesAfterIt = x_to_vals_after_it
        NumberToValuesBeforeIt = y_to_vals_before_it
        Pages = all_pages
    }

let create_valid_from_invalid 
    (input: Day5Input2)
    (invalid_pages: int list) 
    : int list 
    =
    invalid_pages 
    |> List.sortWith( fun x y -> 
        if x = y
        then 0 
        else 

        let x_before_y = (
            (match input.NumberToValuesAfterIt.TryGetValue x with 
            | false, _ -> false 
            | true, rules -> 
                rules.Contains(y))
            || (
                match input.NumberToValuesBeforeIt.TryGetValue y with 
                | false, _ -> false 
                | true, rules -> 
                    rules.Contains(x)
            )
        )

        if x_before_y
        then -1 
        else 

        let y_before_x = (
            (match input.NumberToValuesAfterIt.TryGetValue y with 
            | false, _ -> false 
            | true, rules -> 
                rules.Contains(x))
            || (
                match input.NumberToValuesBeforeIt.TryGetValue x with 
                | false, _ -> false 
                | true, rules -> 
                    rules.Contains(y)
            )
        )

        if y_before_x
        then 1
        else 

        0
    )

let is_page_in_order2
    (page_to_pages_after_it: IDictionary<int, int Set>)
    (pages: int list)
    : bool 
    = 

    let mutable pages_to_left = Set.ofList [pages[0]]
    let mutable is_valid = true 

    for i = 1 to pages.Length - 1 do 
        let current_page = pages[i]

        match page_to_pages_after_it.TryGetValue current_page with 
        | false, _ -> () 
        | true, pages_that_must_come_later -> 
            let page_in_wrong_order = 
                pages_that_must_come_later
                |> Seq.exists (fun p -> 
                    pages_to_left.Contains(p)
                )

            if page_in_wrong_order then 
                is_valid <- false

        pages_to_left <- pages_to_left.Add(current_page)

    is_valid

let solve_part2 
    (file_name: string) 
    =

    printfn "Day 5.2: Solving"

    let input = read_input2 file_name

    let is_in_order =
        is_page_in_order2 input.NumberToValuesAfterIt

    let total = 
        input.Pages
        |> Seq.choose (fun page -> 
            match is_in_order (page |> Seq.toList) with
            | true -> None 
            | false -> Some page  
        )
        |> Seq.map (fun invalid_pages -> 
            create_valid_from_invalid
                input 
                invalid_pages
        )
        |> Seq.map (fun valid_pages -> 
            assert is_in_order valid_pages
            valid_pages[valid_pages.Length / 2]
        )
        |> Seq.sum

    printfn "Day 5.2: Total: %A" total

Next

I enjoyed this problem a lot - I haven't run into an IRL situation in awhile where the size of input processing was prohibitively expensive so this was a nice reminder that hey it totally is worth doing the napkin math to make sure you're not doing O(n!) calcs. By the same token though n and n^2 often lead to vastly simpler algorithms and for many data sizes it makes sense to bias simplicity over "optimal". But n! is another matter =)

If you liked this post - please leave a like, comment, and/or share to your network for the algorithm.

You might also like:

• Advent of Code 2024 - Day 4 in F#
• Why you should use snake_case instead of camelCase for variable names
• How Popular is F# in 2024?