Advent of Code day 3
This day’s questions were a lot easier for me than yesterday’s, and i was able to write O(N) code, which really satisfied me. Without any further delay, lets get into the code!
(defn read-input [& [file]]
(line-seq (io/reader (or file "data/dec3.txt"))))
(defn process-input [input]
(let* [lst (map seq input)
nums-lst (map (fn [lst] (map #(Character/digit % 10) lst)) lst)
nums-vec (apply vector (map #(apply vector %) nums-lst))]
nums-vec))
(defn get-max [v start end]
(loop [x -1
val -1
i start]
(cond
(= end i) (list x val)
(> (nth v i) val) (recur i (nth v i) (inc i))
:else (recur x val (inc i)))))
(defn get-max-jolt-bank [bank]
(let [[fi fd] (get-max bank 0 (dec (count bank)))
[si sd] (get-max bank (inc fi) (count bank))]
(+ (* 10 fd) sd)))
(defn solve []
(let [banks (process-input (read-input))]
(apply + (map get-max-jolt-bank banks))))
;; Part 2
(defn get-max-digit-jolt-bank-lst [bank digit]
(loop [num '()
start 0
end (- (count bank) (dec digit))]
(if (= (dec end) (count bank))
num
(let [[index n] (get-max bank start end)]
(recur (conj num n) (inc index) (inc end))))))
(defn get-max-digit-jolt [bank digit]
(loop [curr 0
digits (get-max-digit-jolt-bank-lst bank digit)
base 1]
(if (empty? digits)
curr
(recur (+ curr (* (first digits) base)) (rest digits) (* base 10)))))
(defn solve-part2 []
(let [input (process-input (read-input))]
(apply + (map #(bigint (get-max-digit-jolt % 12)) input))))
Let’s discuss the algorithm for the second part, as you can understand first part’s algorithm from that as well.
Let’s say we have a bank of x digits, and we want the largest n digit number. For finding the first digit, we leave n-1 digits at the end, as we want a minimum of n-1 digits left to make a n digit number. Then we find a max from 0- end-(n-1). Let’s say this number is found at index i. Then to find the next digit, we start looking from i+1. However, this time our end is incremented by 1. We do this recursively. Until we find the 12 digit number.