Knowit Julekalender 2020 https://julekalender.knowit.no/luke/

julekalender-2020.clj

(ns core)

(def not-nil? (complement nil?))
(def prime?
  (memoize
    #(.isProbablePrime (BigInteger. (str %)) 100)))


(def char-to-int
  (memoize
    (fn [^java.lang.Character c]
      (Character/getNumericValue c))))


(defn try-parse-int [n]
  (try
    (Integer/parseInt n)
    (catch NumberFormatException e nil)))


(defn permutations [s]
  (lazy-seq
    (if (seq (rest s))
      (apply concat
             (for [x s]
               (map #(cons x %)
                    (permutations (remove #{x} s)))))
      [s])))


(defn byte-seq [^java.io.Reader rdr]
  (lazy-seq
    (let [ch (.read rdr)]
      (if (neg? ch)
        (.close rdr)
        (cons ch (byte-seq rdr))))))


(comment
  (->> "https://julekalender-backend.knowit.no/challenges/1/attachments/numbers.txt"
    (clojure.java.io/reader)
    (byte-seq)
    (map char)
    (reduce (fn [acc n]
              (if (= \, n)
                (conj acc [])
                (conj (rest acc)
                      (conj (first acc) n))))
            [[]])
    (map (partial apply str))
    (map try-parse-int)
    (set)
    (last)))


;; 1

(comment
  (clojure.set/difference
    (->> (range 1 100001)
      (map str)
      (set))
    (-> (slurp "https://julekalender-backend.knowit.no/challenges/1/attachments/numbers.txt")
      (clojure.string/split #",")
      (set))))


;; 2

(comment
  (defn prime-sieve [[xs ps]]
    (let [[p & more] xs]
      [(remove #(zero? (rem % p)) xs) (cons p ps)]))


  (defn primes [n]
    (if (< n 2)
      #{}
      (->> [(range 2 (inc n)) nil]
        (iterate prime-sieve)
        (drop-while #(<= (ffirst %) (Math/sqrt n)))
        (first)
        (apply concat)
        (apply sorted-set))))

  (def ps (primes 5433000)))

;; 2

(defn prime-seq
  ([] (prime-seq (BigInteger. "2")))
  ([p] (let [next-p (.nextProbablePrime p)]
         (cons next-p (lazy-seq (prime-seq next-p))))))


(def primes (prime-seq))


(defn closest-prime [n]
  (->> primes
    (take-while #(<= % n))
    (last)))


(defn contains-seven? [x]
  (->> x
    (str)
    (map char)
    (some #{\7})))


(defn packages-delivered [n]
  (->> n
    (inc)
    (range)
    (reduce (fn [[acc skip] n]
              (cond
                (pos? skip)         [acc (dec skip)]
                (contains-seven? n) [acc (closest-prime n)]
                :else               [(inc acc) 0]))
            [0 0])
    (first)))


(comment
  (map packages-delivered [10 20 10000 5433000])) ; 7 9 32 69


;; 3

(defn transpose [m]
  (apply mapv vector m))


(defn mirror [m]
  (map #(reverse %) m))


(defn row-str [m]
  (map #(apply str %) m))


(defn horizontal-rows [m]
  (concat (row-str m)
          (row-str (mirror m))))


(defn vertical-rows [m]
  (->> m
    (transpose)
    (horizontal-rows)))


(defn join-rows [rows]
  (->> (repeat "|")
    (interleave rows)
    (drop-last)
    (apply str)))


(def zip (partial map vector))


(defn lookup-per-row [indices m]
  (map (fn [[idx row]] (nth row idx))
       (zip indices m)))


(defn dim [m] (count (first m)))


(defn diagonal-tl-br [m]
  (let [indices (map #(range % (dim m)) (range (dim m)))] ;; ((0 1 2) (1 2) (2))
    (map (partial apply str)
         (concat (map #(lookup-per-row % m) indices)
                 (map #(lookup-per-row % (transpose m)) indices)))))
(defn diagonal-tr-bl [m] (diagonal-tl-br (mirror m)))
(defn diagonal-br-tl [m] (diagonal-tl-br (reverse m)))
(defn diagonal-bl-tr [m] (diagonal-tl-br (mirror (reverse m))))

(defn combinations-str [m]
  (let [combos (juxt horizontal-rows vertical-rows diagonal-tl-br diagonal-tr-bl diagonal-br-tl diagonal-bl-tr)]
    (->> m
      (combos)
      (apply concat)
      (set)
      (join-rows))))


(defn containing-words [m words]
  (let [combo (combinations-str m)]
    (filter #(clojure.string/includes? combo %) words)))


(defn missing-words [m words]
  (->> words
    (containing-words (map seq m))
    (clojure.set/difference words)
    (sort)
    (clojure.string/join ",")))

(comment
  (missing-words
    (-> (slurp (str "https://gist.githubusercontent.com/knowitkodekalender/d277d4f01a9fe10f7c1d92e2d17f1b31/"
                    "raw/49da54e4372a83f4fc11d7137f19fc8b4c58bda6/matrix.txt"))
      (clojure.string/split #"\n"))
    (-> (slurp (str "https://gist.githubusercontent.com/knowitkodekalender/9e1ba20cd879b0c6d7af4ccfe8a87a19/"
                    "raw/b19ae9548a33a825e2275d0283986070b9b7a126/wordlist.txt"))
      (clojure.string/split #"\n")
      (set))) ;; "askepott,marsipangris,pinnekjøtt"
  )


;; 4


(defn parse-row [s]
  (->> s
    (seq)
    (remove #{\space})
    (partition-by #{\, \:})
    (filter #(> (count %) 1))
    (map (partial apply str))
    (partition 2)
    (map vec)
    (map (juxt (comp keyword first) (comp #(Integer/parseInt %) second)))
    (into {})))


(def ingredients
  (->> (-> "https://julekalender-backend.knowit.no/challenges/4/attachments/leveringsliste.txt"
         (slurp)
         (clojure.string/split #"\n"))
    (map parse-row)
    (apply merge-with +)))


(def one-cake {:sukker 2 :mel 3 :melk 3 :egg 1})

(comment 
  (loop [ingredients ingredients
         cakes       0]
    (let [remainder (merge-with - ingredients one-cake)]
      (if (some zero? (vals remainder))
        (inc cakes)
        (recur remainder
               (inc cakes)))))) ;; 1458014


;; 5

(comment 
  (->> "https://julekalender-backend.knowit.no/challenges/5/attachments/rute.txt"
    (slurp)
    (seq)
    (reduce (fn [[[x y] :as acc] move]
              (conj acc
                    (condp = move
                      \O [x (inc y)]
                      \H [(inc x) y]
                      \N [x (dec y)]
                      \V [(dec x) y])))
            (list [0 0]))
    (partition 2 1)
    (reduce (fn [acc [[ax ay] [bx by]]]
              (+ acc ; shoelace formula
                 (- (* ax by)
                    (* bx ay))))
            0)
    (* 0.5)
    (Math/abs)
    (int))) ; 118000

(comment
  (require '[oz.core :as oz])
  (oz/start-server!)
  (oz/view! {:width    800
             :height   500
             :mark     "circle"
             :data     {:values (->> points (map (fn [[x y]] {:x x :y y})) vec)}
             :encoding {:x {:field "x" :bin {:maxbins 10000}}
                        :y {:field "y" :bin {:maxbins 10000}}}}))
;; https://share.getcloudapp.com/eDuw1x6o


;; 6


(comment
  (->> (-> "https://julekalender-backend.knowit.no/challenges/6/attachments/godteri.txt"
         (slurp)
         (clojure.string/split #","))
    (map #(Integer/parseInt %))
    (reductions + 0)
    (reverse)
    (drop-while #(-> % (mod 127) zero? not))
    (first)
    (* 1/127))) ;; 952


;; 7


(def trees (str 
             "
                          #              
                         ###             
                        #####            
                       #######           
      #               #########          
     ###                 ###             
    #####                #####           
   #######             #######           
  #########           #########          
 ###########             ###             
#############           #####            
     ###               #######           
    #####             #########          
   #######               ###             
  #########             #####            
 ###########           #######           
#############    #    #########    #     
     ###        ###      ###      ###    
    #####      ### #    #####    # # #   
   #######      ###    #######    ###    
  #########    #####  #########  #####   
 ###########    ###      ###      ###    
#############  #####    #####    #####   
      #          #        #        #     
      #          #        #        #     ")) 



(defn divide [line]
  (let [len  (count line)
        half (/ len 2)]
    [(take (if (odd? len) (dec half) half) line)
     (drop half line)]))


(defn symmetric? [line]
  (let [[a b] (divide line)]
    (or (and (empty? a) (empty? b))
        (and (= a (reverse b))
             (->> a frequencies count pos?)))))


(defn empty-row? [row]
  (every? (partial = \space) row))


(defn separate-trees [trees] 
  (->> trees 
    (partition-by empty-row?)
    (map #(remove empty-row? %))
    (remove empty?)))


(defn transpose [matrix]
  (apply mapv vector matrix))


(defn tree-symmetric? [tree]
  (every? symmetric? tree))


(comment 
  (->>
      (-> (slurp "https://julekalender-backend.knowit.no/challenges/7/attachments/forest.txt")
        (clojure.string/split #"\n"))
    (map seq)
    (separate-trees)
    (map transpose)
    (map separate-trees)
    (apply concat)
    (map transpose)
    (map tree-symmetric?)
    (frequencies))) ; {false 2658, true 5534}


;; 8

(comment
  (def abs #(Math/abs %))
  (defn try-parse-int [n]
    (try
      (Integer/parseInt n)
      (catch NumberFormatException e nil)))

  (defrecord Loc [name x y time])

  (def coords
    (->> (clojure.java.io/reader
           "https://julekalender-backend.knowit.no/challenges/8/attachments/input.txt")
      (line-seq)
      (reduce (fn [acc l]
                (if-let [[_ name x y] (re-matches #"(.*): \((.*),(.*)\)$" l)]
                  (update acc :locs conj (Loc. name (try-parse-int x) (try-parse-int y) 0))
                  (update acc :steps conj l)))
              {:locs  []
               :steps []})))

  (defn manhattan [x y x1 y1]
    (->> [(- x1 x) (- y1 y)]
      (map abs)
      (reduce +)))

  (defn steps-to [n target]
    (if (< n target)
      (range n target)
      (range n target -1)))

  (defn between? [n a b]
    (and (>= n a) (< n b)))

  (defn move [steps locs x y]
    (reduce
      (fn [acc loc]
        (let [d (manhattan x y (:x loc) (:y loc))]
          (update loc :time
                  (cond
                    (< d 5)              0.25
                    (between? d 5 20)    0.5
                    (between? d 20 50)   0.75
                    (and (= x (:x loc))
                         (= y (:y loc))) 0
                    :else                1))))
      locs
      steps))


  (def zip (partial map vector))

  (defn run [coords]
    (loop [locs           (:locs coords)
           [step & steps] (:steps coords)
           x              0
           y              0]
      (if step
        (let [[target-x target-y] ((juxt :x :y) step)]
          (move (zip target-x (steps-to x target-x)) locs x y)
          ;; TODO her
          (recur locs steps 0 0))
        (println "done")))))



;; 9


(def zip (partial map vector))

(defn matrix-sum [mms nns]
  (map (fn [[ms ns]] (map + ms ns))
       (zip mms nns)))

(defn limit [mms]
  (for [ms mms]
    (map (partial min 1) ms)))

(def bool->int {true 1 false 0})

(defn sick-at [elves [x y]]
  (-> elves
    (nth y [])
    (nth x 0)
    (pos?)))

(defn sick-neighbors? [elves x y]
  (->> [[(dec x) y]
        [(inc x) y]
        [x (dec y)]
        [x (inc y)]]
    (map (partial sick-at elves))
    (map bool->int)
    (apply +)
    (< 1)
    (bool->int)))

(defn sick-next-round [elves]
  (map-indexed
    (fn [y-idx ys]
      (map-indexed
        (fn [x-idx xs]
          (sick-neighbors? elves x-idx y-idx))
        ys))
    elves))

(defn spread [elves]
  (loop [n     0
         elves elves]
    (let [spread (->> elves
                   (sick-next-round)
                   (matrix-sum elves)
                   (limit))]
      (if (= elves spread)
        (inc n)
        (recur (inc n) spread)))))

(comment 
  (->> (-> "https://julekalender-backend.knowit.no/challenges/9/attachments/elves.txt"
         (slurp)
         (clojure.string/split #"\n"))
    (map seq)
    (map #(map { \F 0 \S 1 } %))
    (spread))) ; 158



;; 10


(defn split-by [what coll]
  (->> coll
    (partition-by (partial = what))
    (filter (partial not= (list what)))))

(comment 
  (->> "https://julekalender-backend.knowit.no/challenges/10/attachments/leker.txt"
    (slurp)
    (seq)
    (split-by \newline)
    (into [] (comp
               (map (partial split-by \,))
               (map (partial map (partial apply str)))
               (map (partial map-indexed vector))
               (map (juxt count identity))
               (map (fn [[total elves]]
                      (for [[points elf] elves]
                        [elf (- total (inc points))])))
               (map (partial into {}))))
    (apply merge-with +)
    (sort-by val)
    (last)
    (interpose "-")
    (apply str))) ; "ti-7776"


;; 11

(defn transpose [m]
  (apply mapv vector m))


(defn range-closed [start end]
  (range start (inc end)))


(def alphabet
  (->> [\a \z]
    (map int)
    (apply range-closed)
    (map char)))


(def alphabet-idxs
  (->> alphabet
    (map vector (range (count alphabet)))
    (map reverse)
    (map vec)
    (into {})))


(def rotate
  (memoize
    #(->> alphabet
       (cycle)
       (drop-while (partial not= (char %2)))
       (drop %1)
       (first))))


(defn scramble [hint]
  (->> (seq hint)
    (drop 1)
    (map (partial rotate 1))
    (map alphabet-idxs)
    (map vector (map alphabet-idxs (seq hint)))
    (map (partial apply +))
    (map (partial nth (cycle alphabet)))
    (apply str)))


(defn pad [n what s]
  (->> n
    (range)
    (map #(nth s % what))
    (apply str)))


(defn passwords [hint]
  (->> hint
    (iterate scramble)
    (take-while not-empty)
    (map (partial pad (count hint) \space))
    (transpose)
    (map (partial remove #{\space}))
    (map (partial apply str))
    (set)))


(defn hint-for? [pw hint]
  (-> (apply str (passwords hint))
    (clojure.string/includes? pw)))


(->> "https://julekalender-backend.knowit.no/challenges/11/attachments/hint.txt"
  (clojure.java.io/reader)
  (line-seq)
  (map (partial apply str))
  (filter (partial hint-for? "eamqia"))
  (first)) ; metropolitan


;; 12


(def capitalized
  (->> [\A \Z]
    (map int)
    (apply range)
    (map char)
    (set)))

(->> "https://julekalender-backend.knowit.no/challenges/12/attachments/family.txt"
  (slurp)
  (seq)
  (reduce (fn [[level scores] c]
            (cond
              (= c \()        [(inc level) scores]
              (= c \))        [(dec level) scores]
              (capitalized c) [level (update scores level (fnil inc 0))]
              :else           [level scores]))
          [0 []])
  (second)
  (apply max)) ; 5965


;; 13


(->> "https://julekalender-backend.knowit.no/challenges/13/attachments/text.txt"
  (slurp)
  (drop-last)
  (reduce (fn [[seen acc] c]
            (let [index (->> [c \a] (map int) (reduce -))
                  seen  (update seen c (fnil inc -1))]
              [seen (if (= (seen c) index)
                      (conj acc c)
                      acc)]))
          [{} []])
  (second)
  (apply str)) ; "aebdhgcfijmqolpnvutkzsxryw"


;; 14


(def primes
  (-> (->> "https://github.com/srmalins/primelists/blob/master/someprimes.txt?raw=true"
        (clojure.java.io/reader)
        (line-seq)
        (drop 2)
        (map clojure.string/trim)
        (remove empty?)
        (map #(Integer/parseInt %))
        (set))
    (conj 2)))


(->> (range 2 (inc 1800813))
  (reduce
    (fn [[[_ snd :as acc] seen] n]
      (let [op        (if (or (neg? (- snd n))
                              (seen (- snd n)))
                        + -)
            conj-both (juxt (partial conj acc)
                            (partial conj seen))]
        (conj-both (op snd n))))
    ((juxt seq set) [1 0]))
  (first)
  (filter (partial primes))
  (count)) ; 67321


;; 15


(defn lines [url]
  (->> url
    (clojure.java.io/reader)
    (line-seq)
    (set)))

(defn glue-words [word-list prefix suffix]
  (reduce (fn [acc w]
            (if (clojure.string/starts-with? w prefix)
              (let [glue (->> w (drop (count prefix)) (apply str))]
                (if (and (not= glue w)
                         (word-list glue)
                         (word-list (str glue suffix)))
                  (conj acc glue)
                  acc))
              acc)) #{} word-list))

(def word-list
  (lines "https://julekalender-backend.knowit.no/challenges/15/attachments/wordlist.txt"))

(->> (lines "https://julekalender-backend.knowit.no/challenges/15/attachments/riddles.txt")
  (map #(clojure.string/split % #", "))
  (reduce #(apply conj %1 (glue-words word-list (first %2) (second %2))) #{})
  (map count)
  (reduce +)) ; 278


;; 15


(defn divisors [n]
  (flatten
    (for [x     (->> n (Math/sqrt) (Math/ceil) (range 1))
          :when (->> x (rem n) (zero?))]
      [x (/ n x)])))

(defn square-diff? [n divisors]
  (let [diff (- (reduce + divisors) (* 2 n))
        d    (Math/sqrt diff)]
    (and (pos? d)
         (zero? (rem d 2)))))

(comment
  (->> (range 1 1000000)
    (pmap #(if (square-diff? % (divisors %)) 1 0))
    (reduce +))) ; 704, so close..


;; 16


;; 17


;; 18


(defn pali-nesten-drom? [s]
  (and
    (< 2 (count s))
    (not= (seq s) (reverse s))
    (->> s
      (reverse)
      (map vector s)
      (reduce
        (fn [[acc prev] pair]
          (if (not prev)
            [acc pair]
            (if (and (not= pair prev)
                     (= (set pair) (set prev))) ;; utelater ("aass" "eggcelle" "innsokki" "treffsikkert")
              [acc nil]
              [(conj acc prev) pair])))
        [[] nil])
      (apply conj)
      (remove nil?)
      (filter #(not= (first %) (second %)))
      (empty?))))


(->> "https://julekalender-backend.knowit.no/challenges/18/attachments/wordlist.txt"
  (clojure.java.io/reader)
  (line-seq)
  (filter pali-nesten-drom?)
  (count)) ; 252


;; 19


(defn parse-line [line]
  (let [[_ rule steps elves-str] (re-matches #"^([0-9]+) ([0-9]+) \[(.*)\]$" line)]
    [(Integer/parseInt rule) (Integer/parseInt steps) (clojure.string/split elves-str #", ")]))

(defn remove-at [idx coll]
  (let [coll (vec coll)]
    (concat (subvec coll 0 (min idx (count coll)))
            (subvec coll (min (inc idx) (count coll))))))

(defn remove-middle [coll]
  (let [cnt  (count coll)
        half (/ cnt 2)]
    (if (= 2 cnt)
      (drop 1 coll)
      (if (even? cnt)
        (->> coll
          (remove-at (Math/floor half))
          (remove-at (dec (Math/floor half))))
        (remove-at half coll)))))

(defn rotate-right [n coll]
  (->> coll (reverse) (cycle) (drop n) (take (count coll)) (reverse)))

(def rules
  {1 (fn [elves _         state] [(drop 1 elves) state])
   2 (fn [elves num-elves state] [(remove-at state elves) (-> state (inc) (mod (dec num-elves)))])
   3 (fn [elves _         state] [(remove-middle elves) state])
   4 (fn [elves _         state] [(drop-last elves) state])})

(defn run [[rule-n steps elves]]
  (loop [elves elves state 0]
    (if (= 1 (count elves))
      (first elves)
      (let [[elves state] ((rules rule-n) (rotate-right steps elves) (count elves) state)]
        (recur elves state)))))

(->> "https://julekalender-backend.knowit.no/challenges/19/attachments/input.txt"
  (clojure.java.io/reader)
  (line-seq)
  (map parse-line)
  (map run)
  (frequencies)
  (sort-by #(second %))
  (last)) ; ["Spencer" 12]


;; 20

(def sep #"🎄")

(defn split-sep [s]
  (clojure.string/split s sep))

(defn add-sep [s]
  (str s sep))

(defn join-sep [coll]
  (clojure.string/join sep coll))

(def data
  (-> "Athena
Demeter
Hades
Hades🎄Hypnos
Athena🎄Icarus
Hades🎄Nyx🎄Zagreus🎄Medusa
Athena🎄Orpheus
Athena🎄Icarus🎄Poseidon🎄Cerberus
Hades🎄Nyx🎄Zagreus
Athena🎄Icarus🎄Poseidon"
    (clojure.string/split #"\n")))

(defn combinations [s]
  (->> s
    (split-sep)
    #_(drop 1)
    (reductions conj [])
    (remove empty?)
    (map (partial clojure.string/join (str sep)))))

(combinations (nth data 5))

(def set-elves
  (->> data
    (reduce conj #{})))

(defn set-retired [data]
  (->> data
    (map combinations)
    (flatten)
    (filter #(not (set-elves %)))
    (set)
    (map (comp last split-sep))
    (set)))

(defn leaders [es]
  (if (= 1 (count es))
    (first es)
    (->> es drop-last rest)))

(defn workers [es]
  (if (= 1 (count es))
    nil
    (last es)))

(let [retired (set-retired data)]
  (->> data
    (map (fn [line]
           (reduce (fn [acc retired-elf]
                     (clojure.string/replace acc retired-elf ""))
                   line
                   (map add-sep retired))))
    (map split-sep)
    #_(map (juxt leaders workers))
    #_(tree-elves)
    (map group)
    (into {})
    (clojure.pprint/pprint)))

(defn all-elves [data]
  (->> data
    (map #(clojure.string/split % sep))
    (reduce (partial apply conj) #{})))

(->> "Hades🎄Nyx🎄Zagreus🎄Medusa"
  combinations)

(all-elves data)

(defn tree-elves [data]
  (->> data
    (map split-sep)
    (reduce (fn [acc elves]
              (update-in acc elves conj))
            {})))

;; 21


(defn fifo-priority-queue []
  (java.util.PriorityQueue.
    (fn [[pri-a time-a] [pri-b time-b]]
      (if (= pri-a pri-b)
        (compare time-a time-b)
        (compare pri-a pri-b)))))

(loop [treated             0
       time                0
       queue               (fifo-priority-queue)
       [line & rest-lines] (->> "https://julekalender-backend.knowit.no/challenges/21/attachments/input.txt"
                             (clojure.java.io/reader)
                             (line-seq)
                             (map #(clojure.string/split % #",")))]
  (if (= (count line) 2)
    (let [[elf pri] line]
      (recur treated
             (inc time)
             (doto queue (.add [(Integer/parseInt pri) time elf]))
             rest-lines))
    (if (= (last (.poll queue)) "Claus")
      treated
      (recur (inc treated) time queue rest-lines)))) ; 557


;; 22

(defn parse-line [line]
  (let [[_ letters names] (re-find #"([^ ]+)+ \[(.*)\]" line)]
    [letters (-> names (clojure.string/lower-case) (clojure.string/split #", "))]))

(defn extract-name [letters name]
  (loop [[l & ls]         letters
         [c & cs :as ccs] name
         acc              []]
    (if (nil? l)
      (as-> (nil? c) match
        [match (if match (apply str acc) letters)])
      (if (= l c)
        (recur ls cs acc)
        (recur ls ccs (conj acc l))))))

(defn names-in-letters [letters names]
  (loop [matches     []
         letters     letters
         [name & ns] names]
    (if (nil? (first name))
      matches
      (as-> (extract-name letters name) [match rest-letters]
        (if match
          (recur (conj matches name) rest-letters ns)
          (recur matches letters ns))))))

(->> "https://julekalender-backend.knowit.no/challenges/22/attachments/input.txt"
  (clojure.java.io/reader)
  (line-seq)
  (map #(->> % (parse-line) (apply names-in-letters) (count)))
  (map-indexed vector)
  (sort-by second)
  (last)) ; [688, 16]


;; 23


;; 24

(->> "https://julekalender-backend.knowit.no/challenges/24/attachments/rute.txt"
  (slurp)
  (seq)
  (map char)
  (reduce
    (fn [[food houses] c]
      (if (zero? food)
        (reduced houses)
        [((if (= c \1) inc dec) food) (inc houses)]))
    [10 0])) ; 3333490