Advent of Code 2023 - Day 5: Seeds

:: programming, puzzle, racket

1
2
 
#lang iracket/lang #:require racket
(require "../advent.rkt")

Day 5 involves a typical Advent of Code scenario where Part 1 is easy, and a naive modification to Part 1 to get Part 2 is easy; however, the naive Part 2 solution will take far too long to run! :)

After solving Part 1 to get a star, I re-implemented the code to solve Part 2, and then Part 1 was simply making the Part 1 input conform to what Part 2 needed, and call Part 2.

The “trick” for Part 2 was to process the seed ranges as ranges, and not attempt to convert the seed ranges into lists of individual seeds.

As always, the first step is parsing, and choosing suitable data structures for this step can make later steps much easier. We’ll obtain 3 values from our parsing:

  1. seeds1 (for Part1) is a list of seed numbers
  2. seeds2 (for Part2) is a list of seed ranges [ begin, end )
  3. categories is a list of “maps” (delta (begin . end)) where:
    • delta is the amount to increment the source range
    • begin is the inclusive beginning of the source range
    • end is the exclusive ending of the source range

The following is the parsing code with some sample output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
(define-values (seeds1 seeds2 categories)
  (let* ([ lines (parse-aoc 5 #:sep "\n\n" #:print-sample #f) ]
         [ seeds (cdr (atoms (car lines)))                    ])
    (values seeds
            (map (λ (pair)
                   (match-let ([ (list beg len) pair ])
                     (cons beg (+ beg len)))) (chunk 2 seeds))
            (map (λ (l)
                   (map (λ (l)
                          (match-let ([ (list dst src len) l ])
                            (list (- dst src) (cons src (+ src len))))) (chunk 3 (drop (atoms l) 2))))
                 (cdr lines)))))

(take seeds1 3)

’(515785082 87905039 2104518691)

1
 
(take seeds2 3)

’((515785082 . 603690121) (2104518691 . 2607668534) (720333403 . 1105567596))

1
 
(take (car categories) 3)

’((–1851428871 (3876763368 . 3893492948)) (–154574372 (2032519622 . 2127606082)) (–679167893 (679167893 . 1060342823)))

The first function we’ll code accepts a seed range and a single map from a category. It needs to compute the intersection of the seed range with the map’s source range. There are six possible cases. Here is the order you’ll see in the code:

  1. Seed range is left of source range - no intersection
  2. Seed range is a superset of source range
  3. Right portion of seed range intersects source range
  4. Seed range is right of source range - no intersection
  5. Seed range is subset of source range
  6. Left portion of seed range intersects source range

The algorithm is to partition the seed range into two sets, the first set is either empty (no intersection), or it contains a single range that entirely matches the source range, and it has been incremented by the delta (see above). The second set is a list of ranges that have no intersection with the source range. Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
(define (convert-map seed cat)
  (define (increment-range delta pair)
    (cons (+ delta (car pair)) (+ delta (cdr pair))))

  (match-let ([ (cons seed-beg seed-end)           seed ]
              [ (list delta (cons cat-beg cat-end)) cat  ])
    (if (< seed-beg cat-beg)
        (cond [ (<= seed-end cat-beg)
                (values #f (list seed)) ]
              [ (> seed-end cat-end)
                (values (increment-range delta (cons cat-beg cat-end))
                        (list (cons seed-beg cat-beg)
                              (cons cat-end seed-end))) ]
              [ else
                (values (increment-range delta (cons cat-beg seed-end))
                        (list (cons seed-beg cat-beg))) ])
        (cond [ (>= seed-beg cat-end)
                (values #f (list seed)) ]
              [ (<= seed-end cat-end)
                (values (increment-range delta seed) '()) ]
              [ else
                (values (increment-range delta (cons seed-beg cat-end))
                        (list (cons cat-end seed-end))) ]))))

(convert-map (second seeds2) (second (first categories)))

’(1949944319 . 1973031710)

’((2127606082 . 2607668534))

Next, we’ll need a function to process a single seed range against an entire category of maps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
(define (convert-category seed category)
  (if (null? category)
      (list seed)
      (let-values ([ (seed remaining) (convert-map seed (car category)) ])
        (let ([ lst (apply append (map (λ (s) (convert-category s (cdr category))) remaining)) ])
          (if seed
              (cons seed lst)
              lst)))))

(convert-category (second seeds2) (first categories))

’((1949944319 . 1973031710) (1973031710 . 2025334497) (3247991211 . 3324095721) (3780457892 . 4067445375) (2487930716 . 2552598388))

Lastly, we’ll need a function to process a single seed range through all of the categories:

1
2
3
4
5
6
7
8
 
(define (convert-categories seed categories)
  (if (null? categories)
      (list seed)
      (apply append (map (λ (s)
                           (convert-categories s (cdr categories)))
                         (convert-category seed (car categories))))))

(convert-categories (second seeds2) categories)

’((4287508490 . 4294967296) (3299611124 . 3315239709) (472220788 . 475007602) (3315239709 . 3328285208) (2094199611 . 2097696890) (2583604014 . 2616577209) (701783262 . 711128092) (374784574 . 395248650) (2559661894 . 2567225216) (1457470217 . 1495209180) (3014768818 . 3015762137) (4103928361 . 4110633186) (3686138511 . 3687305674) (3367707747 . 3421416680) (4110633186 . 4115726396) (1767145617 . 1846746193) (1387390964 . 1432950830) (3547841085 . 3561084334) (4072589975 . 4073355764) (120247692 . 121678607) (647749131 . 686302108) (41222968 . 42024284) (1974296651 . 1996039366) (3053802222 . 3072418171) (2133436297 . 2158819357) (2543777270 . 2553156039) (3000344129 . 3014768818) (686302108 . 701783262))

With the above support functions, Part 2 is now just the following:

  1. Call convert-categories for each of the seed ranges
  2. Append all the results together
  3. Find the minimum range beginning
1
2
3
4
 
(define (part2 seeds)
  (list-min (map car (apply append (map (λ (s) (convert-categories s categories)) seeds)))))

(part2 seeds2)

41222968

In somewhat of a backwards manner, we now define Part 1 by simply converting Part 1’s list of seed numbers into a list of ranges of length 1, and then call Part 2:

1
2
3
 
(define (part1 seeds) (part2 (map (λ (s) (cons s (add1 s))) seeds)))

(part1 seeds1)

457535844