Advent of Code 2022 day 4

    Day 4 was an exercise in interval relationships, something I've used before in the day job.


    This followed the problem. An Assignment is a new data type; I represent pairs of Assignments as, well, pairs: 2-tuples. Reading and parsing the datafile is straightforward.

    data Assignment = Assignment Int Int deriving (Show, Eq)
    type Pair = (Assignment, Assignment)
    pairsP = pairP `sepBy` endOfLine
    pairP = (,) <$> assignmentP <* "," <*> assignmentP
    assignmentP = Assignment <$> decimal <* "-" <*> decimal

    Interval relations

    We can say a few things about relations between intervals (assignments).

    Inverval p contains interval q if p starts no later than q and p finishes no earlier than q.

    Interval p is wholly before interval q if p finishes before q starts.

    contains (Assignment lower1 upper1) (Assignment lower2 upper2) =
      (lower1 <= lower2) && (upper1 >= upper2)
    before (Assignment _lower1 upper1) (Assignment lower2 _upper2) = (upper1 < lower2) 

    A pair of intervals (p, q) has a containment if p contains q or q contains p.

    A pair of intervals (p, q) is disjoint if p is before q or q is before p. p and q overlap if they are not disjoint.

    hasContainment (assignment1, assignment2) = 
      (assignment1 `contains` assignment2) || (assignment2 `contains` assignment1)
    disjoint (assignment1, assignment2) = 
      (assignment1 `before` assignment2) || (assignment2 `before` assignment1)
    overlaps = not . disjoint


    With these definitions in place, the solutions are just filtering the list of assignment pairs depending on the relations we want.

    part1 = length . (filter hasContainment)
    part2 = length . (filter overlaps)

    See also

    The intervals library includes all these relations built-in.


    You can get the code from my locally-hosted Git repo, or from Gitlab.

    Neil Smith

    Read more posts by this author.