aoc-2021/3/submarine.lisp

(defparameter *diagnostics-input* "./input.txt")

(defun read-diagnostics ()
  "Read input file, returning a list of its binary diagnostics."
  (let ((input (open *diagnostics-input* :if-does-not-exist nil))
        (input-diagnostics '()))
    (when input
      (loop for line = (read-line input nil)
            while line do
            (setq input-diagnostics (cons line input-diagnostics)))
      (close input))

    (reverse input-diagnostics)))


(defun get-zero-one-frequencies (input)
  "Determine how many bits have a 1 at this input and how many have a 0."
  (defun all-bits-at-index (index all-readings)
    (map 'list (lambda (byte) (elt byte index)) all-readings))
  (loop for i upto (1- (length (car input))) 
        collecting (count #\0 (all-bits-at-index i input))
          into zeros
        collecting (count #\1 (all-bits-at-index i input))
          into ones 
        finally (return (list zeros ones))))

(defun calculate-gamma (input)
  "Calculate the gamma rate."
  (let* ((frequencies (get-zero-one-frequencies input))
         (zeros (car frequencies))
         (ones (cadr frequencies)))
    (map 'list
         (lambda (zero one)
           (if (> zero one) "0" "1"))
         zeros
         ones)))

(defun calculate-epsilon (input)
  "Calculate the epsilon rate."
  (defun invert (gamma)
    (loop for i in gamma
          if (string= i "0")
            collect "1"
          else collect "0"))
  (invert (calculate-gamma input)))


(defun print-power-consumption-report (input)
  (let* ((gamma (calculate-gamma input))
         (epsilon (calculate-epsilon input))
         (gamma-string (format nil "~{~A~}" gamma))
         (epsilon-string (format nil "~{~A~}" epsilon))
         (gamma-decimal (parse-integer gamma-string :radix 2))
         (epsilon-decimal (parse-integer epsilon-string :radix 2)))
    (format t "gamma:   ~{~a~}~%" gamma)
    (format t "           ~a~%" gamma-decimal)
    (format t "epsilon: ~{~a~}~%" epsilon)
    (format t "           ~a~%" epsilon-decimal)
    (format t "power consumption: ~a~%" (* epsilon-decimal gamma-decimal))))

;; gamma:   001110101111
;;            943
;; epsilon: 110001010000
;;            3152
;; power consumption:  2972336


(defun oxygen-generator-rating (input)
  "Calculate the oxygen generator rating.
Determined by having the most bits in the most-common positions."
  (in-majority-bit-criteria #'remove-if input))

(defun co2-scrubber-rating (input)
  "Calculate the CO2 scrubber rating.
Determined by having the fewest bits in the most-common positions."
  (in-majority-bit-criteria #'remove-if-not input))


(defun in-majority-bit-criteria (filter input)
  "Reduce list to byte contaning the most filtered majority bit criteria."
  (defun iter-filter (measurements index)
    (if (= 1 (length measurements))
        (car measurements)
        (iter-filter
         (funcall
          filter
          (lambda (x) (in-the-bit-majority? x index measurements)) measurements)
         (1+ index))))
  (iter-filter input 0))

(defun in-the-bit-majority? (byte bit-index all-bytes)
  "Is the bit at bit-index of byte in the more popular group of bits at this index in all-bytes?"
  (let* ((bit-frequencies (get-zero-one-frequencies all-bytes))
         (most-popular-bit
           (if (> (elt (car bit-frequencies) bit-index)
                   (elt (cadr bit-frequencies) bit-index))
               #\0
               #\1))
         (current-bit (elt byte bit-index)))
    (char= current-bit most-popular-bit)))

(defun print-life-support-report (input)
  (let* ((oxygen (oxygen-generator-rating input))
         (co2 (co2-scrubber-rating input))
         (oxy-decimal (parse-integer oxygen :radix 2))
         (co2-decimal (parse-integer co2 :radix 2)))
    (format t "oxygen:  ~a~%" oxygen)
    (format t "           ~a~%" oxy-decimal)
    (format t "co2:     ~a~%" co2)
    (format t "           ~a~%" co2-decimal)
    (format t "life support: ~a~%" (* oxy-decimal co2-decimal))))


(print-power-consumption-report (read-diagnostics))

;; gamma:   001110101111
;;            943
;; epsilon: 110001010000
;;            3152
;; power consumption: 2972336


(print-life-support-report (read-diagnostics))

;; oxygen:  111000100010
;;            3618
;; co2:     001110100011
;;            931
;; life support: 3368358