day-9.lisp (3178B)
1 (defpackage #:aoc/day-9 2 (:use #:cl #:aoc/utils) 3 (:export #:day-9)) 4 (in-package #:aoc/day-9) 5 6 (defun repeat (item n) 7 (loop repeat n collect item)) 8 9 (defun parse-hdd (input) 10 (loop for cf = (read-char input nil) 11 for ce = (read-char input nil) 12 for file-id from 0 13 until (null cf) 14 nconc (repeat file-id (char-number cf)) into hdd 15 unless (null ce) 16 nconc (repeat nil (char-number ce)) into hdd 17 finally (return (values (coerce hdd 'vector) 18 (1- file-id))))) 19 20 (defun not-eql (a b) 21 (not (eql a b))) 22 23 (defun compact (hdd) 24 (loop for empty = (position nil hdd :start (or empty 0)) 25 for block = (position nil hdd 26 :test #'not-eql 27 :from-end t 28 :end (or block nil)) 29 until (or (or (null empty) (null block)) 30 (< block empty)) 31 do (setf (aref hdd empty) (aref hdd block) 32 (aref hdd block) nil) 33 finally (return hdd))) 34 35 (defun find-empty-space (hdd length end) 36 (declare (optimize debug)) 37 (loop for empty-start = (position nil hdd 38 :start (or empty-start 0) 39 :end end) 40 for empty-length = (and empty-start 41 (- (or (position nil hdd 42 :test #'not-eql 43 :start empty-start) 44 (length hdd)) 45 empty-start)) 46 until (null empty-start) 47 when (>= empty-length length) 48 do (return empty-start) 49 do (setf empty-start (position nil hdd 50 :test #'not-eql 51 :start empty-start 52 :end end)) 53 when (null empty-start) 54 do (return nil))) 55 56 (defun defrag (hdd max-file-id) 57 (loop for file-id from max-file-id downto 0 58 for pos-end = (position file-id hdd 59 :from-end t) 60 for pos-start = (1+ (or (position file-id hdd 61 :test #'not-eql 62 :from-end t 63 :end pos-end) 64 -1)) 65 for block-length = (1+ (- pos-end pos-start)) 66 for fitting-space = (find-empty-space hdd block-length pos-start) 67 when fitting-space 68 do (loop repeat block-length 69 for ep from fitting-space 70 for bp from pos-start 71 do (setf (aref hdd ep) (aref hdd bp) 72 (aref hdd bp) nil)) 73 finally (return hdd))) 74 75 (defun calculate-checksum (hdd) 76 (loop for id across hdd 77 for pos from 0 78 unless (null id) 79 sum (* pos id))) 80 81 (defun day-9 (input) 82 (multiple-value-bind (hdd max-file-id) 83 (parse-hdd input) 84 (values (calculate-checksum (compact (copy-seq hdd))) 85 (calculate-checksum (defrag (copy-seq hdd) max-file-id)))))