5.1 Part 1🔗

Ah! Intervals! I’ve seens those in past years. We’re asked to cound how many integers are in a list of intervals. We’ll I’ll start writing some utility functions to work with intervals:

The challenge of the input file is that it provides MANY invertals which intersect a lot. So here come my opus magnus to merge all overlapping intervals in a list of intervals:

(define (merge-overlapping intervals)

(define sorted-by-lower (sort intervals < #:key lower))

(reverse (for/fold ([acc '()])

([current (in-list sorted-by-lower)])

(cond

[(empty? acc) (list current)]

[else

(let ([last-interval (car acc)])

(if (intersects? last-interval current)

(cons (merge last-interval current) (cdr acc))

(cons current acc)))]))))

That a mouthful! And it took me way longer than I would be comfortable to admit. Still, it is not convoluted once you break it down.

First, let’s appreciate that we can only merge intervals which overlap. And overlapping intervals will be those that will be the closest. So we will take lower bounds as projection for this "distance", and we will sort the damn list of intervals!

This is very important because that way, once we encounter a non-overlapping interval, we can consirer the current interval as done and move on. And then, we can complete the merging process in one single pass.

With the sorting sorted out (ha), merging goes like this:

• start with an empty list (accumulator)

• push the first interval in the list

• move to next fold

• merge the current interval with the head of the accumulator if it overlaps, and push the result instead of the head

• ortherwise, just push the current interval a the head of the accumulator

• keep going until the end of the intervals

Since I prepend merged and new intervals into the accumulator, I end with a result that is sorted in reverse. Slap a call to "reverse" then. Call me an impostor.

An the solution to our problem? Well count how many input integers are in any of the merged intervals:

(define (part1 intervals ids)

(for/sum ([id ids])

(if

(ormap (λ (interval) (contains? interval id)) intervals)

1

0)))

(part1 (merge-overlapping intervals) ids)

I could have done it better. See, I’m scanning the full list of intervals with "ormap". That’s silly, because I could stop early: no need to check intervals that start above the tested id. I could even be smarter and sort the list of ids as well to iterate ids and intervals at the same time…

But no. Linear search it is. It’s fast enough.

5.2 Part 2🔗

We are now ask to sum the size of all intervals in the list. Good thing we merged those before, right?

That’s some real wizard-level programming here! That’s actually all I need for this part because all the difficulty was nullified by merging intervals earlier.

(define (part2 intervals)

(for/sum ([interval intervals])

(card interval)))

(part2 (merge-overlapping intervals))

Yay

5.3 Complete implementation🔗

#lang racket

; -----------------------------------------------------------------------------

; Interval utils

(define (interval a b) (cons (min a b) (max a b)))

(define (lower interval) (car interval))

(define (upper interval) (cdr interval))

(define (intersects? x y)

(or

(and (<= (lower x) (lower y)) (<= (lower y) (upper x)))

(and (<= (lower y) (lower x)) (<= (lower x) (upper y)))))

(define (contains? interval n)

(and (<= (lower interval) n)

(<= n (upper interval))))

(define (merge x y)

(if (intersects? x y)

(interval (min (lower x) (lower y))

(max (upper x) (upper y)))

'()))

(define (card interval)

(add1 (- (upper interval) (lower interval))))

(define (merge-overlapping intervals)

(define sorted-by-lower (sort intervals < #:key lower))

(reverse (for/fold ([acc '()])

([current (in-list sorted-by-lower)])

(cond

[(empty? acc) (list current)]

[else

(let ([last-interval (car acc)])

(if (intersects? last-interval current)

(cons (merge last-interval current) (cdr acc))

(cons current acc)))]))))

; -----------------------------------------------------------------------------

; Input

(define input

(if (file-exists? "inputs/day5.txt")

(file->lines "inputs/day5.txt")

(begin

(println "Warning: 'inputs/da54.txt' is not found, using 'samples/day5.txt' instead.")

(file->lines "samples/day5.txt"))))

(define (parse-input lines)

(define split (index-of lines ""))

(let ([part1 (take lines split)]

[part2 (drop lines (add1 split))])

(values

; Intervals

(map

(λ (line)

(match (map string->number (string-split line "-"))

[(list a b) (interval a b)]))

part1)

; Ids

(map string->number part2))))

(define-values (intervals ids) (parse-input input))

(define merged-intervals (merge-overlapping intervals))

; -----------------------------------------------------------------------------

; PART 1

(define (part1 intervals ids)

(define (in-intervals? id)

(ormap (λ (interval) (contains? interval id)) intervals))

(for/sum ([id ids]

#:when (in-intervals? id))

1))

(define solution1 (part1 merged-intervals ids))

(printf "Part 1: ~a~n" solution1)

; -----------------------------------------------------------------------------

; PART 2

(define (part2 intervals)

(for/sum ([interval intervals])

(card interval)))

(define solution2 (part2 merged-intervals))

(printf "Part 2: ~a~n" solution2)