Advent Of Code 2022 - Day 04

Summary: In a list where each line has two ranges, count for how many lines the ranges are completely overlapping Example input:

2-9,5-6
1-2,3-4

Find the full description here.

Another problem that can be solved with sets today. The numbers may be larger than the single digits examples, but not so large that using sets becomes prohibitive. Checking range overlap isn't that difficult though, so I wrote my own solution.

A range overlaps another range completely if the lowest value of that range is equal to or lower than the lowest value of the other range, and the highest value is higher than or equal to the highest value of the other range.

If we represent the range as a pair of integers, here's what that looks like:

let isFullyOverlapping range1 range2 =
    match (range1, range2) with
    | ((l1, h1), (l2, h2)) when l1 <= l2 && h1 >= h2 -> true
    | ((l1, h1), (l2, h2)) when l2 <= l1 && h2 >= h1 -> true
    | _ -> false

Then we can simply count the lines for which this is true.

Parsing the ranges may seem a bit daunting, as there's a lot of fluff in the input. Thinking for a

Parsing the ranges may seem a bit daunting, as there's a lot of fluff in the input. This happens in many Advent of Code of problems. My personal preference for parsing such input would be something that behaves like C's scanf (without its issues). F# doesn't have that. For now, though, we can just split the line on the two fluff characters and convert the result to integers.

let parse (line: string) =
    match line.Split([|',';'-'|]) with
    | [|a;b;c;d|] -> ((Int32.Parse(a), Int32.Parse(b)),
                      (Int32.Parse(c), Int32.Parse(d)))
    | _ -> failwith $"Invalid input: {line}"

Combining this:

let solve1 (input: string list) =
    input
    |> List.map parse
    |> List.filter (fun (r1, r2) -> isFullyOverlapping r1 r2)
    |> List.length

Summary: For part two we are asked to also count pairs of ranges that partially overlap.

This is precisely the same as part 1 except for the function that determines overlap. Determine a partial overlap is a bit more complex than determining a full overlap.

Two ranges overlap if one range begins or ends in the other. In code, here's how that looks:

let isPartlyOverlapping range1 range2 = 
    match (range1, range2) with
    | ((l1, h1), (l2, h2)) when l1 <= l2 && l2 <= h1 -> true // range2 begins in range1
    | ((l1, h1), (l2, h2)) when l1 <= h2 && h2 <= h1 -> true // range2 ends in range1
    | ((l1, h1), (l2, h2)) when l2 <= l1 && l1 <= h2 -> true // range1 begins in range2
    | ((l1, h1), (l2, h2)) when l2 <= h1 && h1 <= h2 -> true // range1 ends in range2
    | _ -> false

Part two becomes easier once we realize that we can also look for pairs of ranges that have no overlap at all and negate that condition.

Two ranges have no overlap at all if the highest value of range a is lower than the lowest value of range b, or vice versa.

Feeling like there must be a better way than writing all those List.map's, I grouped a few of them a single function.

let isDisjoint range1 range2 =
    match (range1, range2) with
    | ((l1, h1), (l2, h2)) when h2 < l1 -> true
    | ((l1, h1), (l2, h2)) when h1 < l2 -> true
    | _ -> false

The problem today wasn't very difficult, but I didn't really like the parsing part. This is something I run into almost every year. The languages I've picked make parsing more cumbersome than I'd like. Sure, regular expressions and back references are more robust than scanf, but (to me) Advent of Code is not about writing a robust parser, it's about solving the problems.

I had sort of decided to look into using a parser generator to parse today, but I could not find the motivation to do so. Better luck next time!