aoc-2021-day3.lisp

;; naming conventions: 
;; bitstring = "01001" a string of bits
;; binary = (#\0 #\1 #\1) a list of chars representing bits
;; x-list = (x x x) a list of whatever
;; bit = generally just one item, like #\0 

(defun transpose (list-of-list)
  "matrix transpose"
  (apply #'mapcar #'list list-of-list))

(defun count-ones-per-position (binary-list)
  "Given a list of binary values, return a matching count of ones per position
  for instance ((1 0 1) (1 1 1) (0 0 1)) => (2 1 3) "
  (mapcar (lambda (v) (count #\1 v)) (transpose binary-list)))

(defun calculate-common-binary (position-counts listsize)
  "Given a count-of-ones and listsize, return the common value for those columns"
  (mapcar #'(lambda (cnt) ;apply this function to all elements of the list
              (if (>= cnt (/ listsize 2)) #\1 #\0)) 
          position-counts))

(defun find-common-binary (binary-list)
  "Given a list of binary values, find the common bit for each column"
  (calculate-common-binary (count-ones-per-position binary-list) (length binary-list)))

(defun find-least-common-binary (binary-list)
  (binary-complement (find-common-binary binary-list)))

(defun turn-to-binary (position-counts listsize)
  (coerce (calculate-common-binary position-counts listsize) 'string))

(defun binary-complement (binary)
  "given a binary value, return its inverse"
  (mapcar #'(lambda (v) (if (equal v #\1) #\0 #\1)) binary))

(defun bitstring-complement (bitstring)
  (coerce (binary-complement (coerce bitstring 'list)) 'string))

(defun filter-by-bit-criteria (binary-list bit-desired bit-pos)
  "Create a not-matches-criteria, and return a new list, filtering based on criteria"
  (labels ((not-matches-criteria (v) (not (equal (nth bit-pos v) bit-desired))))
    (remove-if #'not-matches-criteria binary-list)))

(defun bitstring-to-binary-list (bitstring-list)
  "Given a list of bitstrings, convert to list of binary"
  (mapcar #'(lambda (word) (coerce word 'list)) bitstring-list))

(defun filter-down-to-one (binary-list bit-position bit-finder)
  "Given a list of binary, recursively call itself and filter based on the 
  binary filter. This is structured like in the problem, where it must
  recursively filter itself based on the position of the binary"
  (if (equal (length binary-list)  1)  ; one value left
    (coerce (car binary-list) 'string) ; return as string
    ;; if we don't have a match, we need to re-evaluate the common binary
    ;; in this list we're given, using the given function, 
    ;; and then filter further on this new list
    (let* ((next-common-bit (nth bit-position (funcall bit-finder binary-list)))
           (new-binary-list (filter-by-bit-criteria binary-list 
                                                    next-common-bit 
                                                    bit-position)))
      (filter-down-to-one new-binary-list (incf bit-position) bit-finder))))

(defun aoc-process-part-2 (theinput) 
  ;; the "LET*" form allows us to define variables in a sequence, that can rely on each other)
  (let* ((binary-list (bitstring-to-binary-list theinput))  ;convert the list to binary
         (oxygen-rating (filter-down-to-one binary-list 0 #'find-common-binary)) ; filter most common
         (co2-rating (filter-down-to-one binary-list 0 #'find-least-common-binary))) ;filter least common
    (fresh-line)
    (princ oxygen-rating)
    (fresh-line)
    (princ co2-rating)
    (fresh-line)
    (* (parse-integer oxygen-rating :radix 2)
       (parse-integer co2-rating :radix 2))))

;; test part 2
(let((testinput '("00100" "11110" "10110" "10111" "10101" "01111" "00111" "11100" "10000" "11001" "00010" "01010")))
  (aoc-process-part-2 testinput))

;; real part 2
(with-open-file (stream "/home/dre/lisp/aoc/3.txt")
  (let (( listitems (loop for line = (read-line stream nil)
                          while line collect line)))
    (aoc-process-part-2 listitems))) 




(defun aoc-process-part-1 (listinput)
  "this is old code, don't bother trying to read it"
  (let  ((binary-gamma (turn-to-binary
                         (count-ones-per-position
                           (mapcar #'(lambda (binary-word)
                                       (coerce binary-word 'list))
                                   listinput)) 
                         (length listinput))))
    (* (parse-integer binary-gamma :radix 2)
       (parse-integer (bitstring-complement binary-gamma) :radix 2)))) 

;; test part 1
(let((testinput '("00100" "11110" "10110" "10111" "10101" "01111" "00111" "11100" "10000" "11001" "00010" "01010")))
  (aoc-process-part-1 testinput))

;; real part 1
(with-open-file (stream "/home/dre/lisp/aoc/3.txt")
  (let (( listitems (loop for line = (read-line stream nil)
                          while line collect line)))
    (aoc-process-part-1 listitems)))