Advent of Code '23 - Day 5

Table of Contents

This was a tough one… save for the datamanament that took a lot of time to figure out, I kind of got to the first answer pretty quickly… Then I refactored to suit part 2, which worked for the example, but would probably have taken days to brute force his way through the data. In the end I solved it by going the other way around; find the first location that has a seed assigned to it. This still took pretty long, but it was less than 30 minutes so good enough.

Input

Example

seeds: 79 14 55 13

seed-to-soil map:
50 98 2
52 50 48

soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15

fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4

water-to-light map:
88 18 7
18 25 70

light-to-temperature map:
45 77 23
81 45 19
68 64 13

temperature-to-humidity map:
0 69 1
1 0 69

humidity-to-location map:
60 56 37
56 93 4

Part 1

(defun aoc23/parse-seeds (string)
  (let* ((seeds (cadr (string-split string ":" nil " ")))
         (seeds (string-split seeds " ")))
     (mapcar 'string-to-number seeds)))

(defun aoc23/parse-ranges (string)
  (let* ((input (mapcar 'string-to-number (string-split string " ")))
         (src-b (car input))
         (src-a (cadr input))
         (length (caddr input)))

    `(((,src-a . ,(+ src-a (1- length)))
       (,src-b . ,(+ src-b (1- length)))))
    ))

(defun aoc23/parse-type (string)
  (car (string-split string " ")))

(defun aoc23/build-almanak (string)

  (let ((lines (string-split string "\n"))
        (state 'init)
        (almanac '())
        (type nil)
        (data nil))

    (dolist (line lines)
      (unless (string= line "")
        (cond ((string-search "seeds:" line)
               (setq seeds (aoc23/parse-seeds line)))
              ((string-search "map:" line)
               (when type
                 (setq almanac (append almanac `((,type . ,data)))))
               (setq data '())
               (setq type (aoc23/parse-type line)))
              (t
               (message "adding to %s" type)
               (setq data (append data (aoc23/parse-ranges line)))))))

    (when (and data type)
      (setq almanac (append almanac `((,type . ,data)))))

    `((:seeds . ,seeds)
      ,almanac)))

(defun aoc23/parse-step (step src alamanak)
  (let ((ranges (cdr (assoc step (cadr almanak))))
        (result nil))
    (dolist (r ranges)
      (let* ((s-range (car r))
             (d-range (cadr r))
             (diff (- (car d-range) (car s-range))))
        (when (and r
                   (>= src (car s-range))
                   (<= src (cdr s-range)))
          (message "%S between %d and %d (diff %d)" src (car s-range) (cdr s-range) diff)
          (setq result (+ diff src))
          )))
    (message "found %s: %d > %d" step src (or result src))
    (or result src)))

(let* ((almanak (aoc23/build-almanak input))
       (seeds (alist-get :seeds almanak))
       (steps '("seed-to-soil"
                "soil-to-fertilizer"
                "fertilizer-to-water"
                "water-to-light"
                "light-to-temperature"
                "temperature-to-humidity"
                "humidity-to-location"))
       (ranges (cadr almanak))
       (src nil)
       (locations '())
       (lowest nil))
  (dolist (seed seeds)
    (setq src seed)
    (message "parsing seed: %d" seed)
    (dolist (step steps)
      (setq src (aoc23/parse-step step src almanak)))
    (setq locations (append locations `((,seed . ,src))))
    (when (or (eq nil lowest)
              (< src lowest))
      (setq lowest src)))
  lowest)

Part 2

This part isn't the best solution, But I kinda don't think its worth it at this moment to try any harder to fix it… it gave the right answer, so it's good enough. 

(defun aoc23/parse-seeds (string)
  (let* ((seeds (cadr (string-split string ":" nil " ")))
         (seeds (string-split seeds " "))
         (seeds (mapcar 'string-to-number seeds))
         (result '()))

    (while (car seeds)
      (let ((seed (car seeds))
            (length (cadr seeds)))
        (setq result (append result `((,seed . ,length)))))
      (setq seeds (cddr seeds)))
    result))


(defun aoc23/parse-ranges (string)
  (let* ((input (mapcar 'string-to-number (string-split string " ")))
         (src-a (car input))
         (src-b (cadr input))
         (length (caddr input)))

    `(((,src-a . ,(+ src-a (1- length)))
       (,src-b . ,(+ src-b (1- length)))))
    ))

(defun aoc23/parse-type (string)
  (car (string-split string " ")))

(defun aoc23/sort (a b)
  (> (caar b) (caar a)))

(defun aoc23/build-almanak (string)

  (let ((lines (string-split string "\n"))
        (state 'init)
        (almanac '())
        (type nil)
        (data nil))

    (dolist (line lines)
      (unless (string= line "")
        (cond ((string-search "seeds:" line)
               (setq seeds (aoc23/parse-seeds line)))
              ((string-search "map:" line)
               (when type
                 (sort data 'aoc23/sort)
                 (setq almanac (append almanac `((,type . ,data)))))
               (setq data '())
               (setq type (aoc23/parse-type line)))
              (t
               (message "adding to %s" type)
               (setq data (append data (aoc23/parse-ranges line)))))))

    (when (and data type)
      (sort data 'aoc23/sort)
      (message "%S" data)
      (setq almanac (append almanac `((,type . ,data)))))

    `((:seeds . ,seeds)
      ,almanac)))

(defun aoc23/parse-step (src almanak)
  (let ((ranges (cdr almanak))
        (result nil))
    (catch 'result
      (dolist (r ranges)
        (let* ((s-range (car r))
               (d-range (cadr r))
               (diff (- (car d-range) (car s-range))))
          (when (and (>= src (car s-range))
                     (<= src (cdr s-range)))
            (setq result (+ diff src))
            (throw 'result "found")
            ))))
    (or result src)))

(defun aoc23/is-seedp (seed seeds)
  (let ((found nil))
    (catch 'found
      (dolist (line seeds)
        (when (and (>= seed (car line))
                   (<= seed (+ (car line) (1- (cdr line)))))
          (setq found t)
          (throw 'found "found"))))
    found))


(let* ((almanak (aoc23/build-almanak input))
       (seeds (alist-get :seeds almanak))
       (steps `(,(assoc "humidity-to-location" (cadr almanak))
                ,(assoc "temperature-to-humidity" (cadr almanak))
                ,(assoc "light-to-temperature" (cadr almanak))
                ,(assoc "water-to-light" (cadr almanak))
                ,(assoc "fertilizer-to-water" (cadr almanak))
                ,(assoc "soil-to-fertilizer" (cadr almanak))
                ,(assoc "seed-to-soil" (cadr almanak))
                ))
       (ranges (cadr almanak))
       (seed 0)
       (locations '())
       (lowest nil))
  (catch 'found
;  (dolist (seedr seeds)
;    (dotimes (i (cdr seedr))
    (while t
      (let* ((src seed))
        (dolist (step steps)
          (set 'src (aoc23/parse-step src step)))
;        (setq locations (append locations `((,seed . ,src))))
                                        ;        (message "processed seed %d: %d" seed src)
        (when (and src
                   (aoc23/is-seedp src seeds))
          (setq lowest seed)
          (message "found something at %d: %S" seed src)
          (throw 'found "found"))
        (setq seed (1+ seed)))))

  lowest)