day17.clj

(ns aoc.day17)

(def input ">>><<<<>><<<<>>>><<><<<<>><><<<><<<<>>><<<<><<>>>><<<<>><<<<>><<<>><>><<<>><>><<>>><<>><<<>>><<<<>>><<<<>>><<<<><<<<><>>><<<>>>><<>><<<><<<<><<<>>><<<<>>>><<<><<<><>>><<><>><<<<>>><>>>><<>>>><<<<><<<<><<<<>>><<>><><<<>><<<><<>>><<>>><>><>>><>>>><<<<>><<>>><<<>><<><<>><<<<>>><>><><>>>><<<<><>><<>><>>>><<>>><<>>><<>>><><<<<>>><<<>>><><<>>>><<<>><<<>>>><<>><<<>><<<>>>><>>>><<>><<<<>><<<>>><<>>><<>><<<>>>><<>><<<>><>>>><>><<<>>>><><<>>><<>>>><>><><<<<>>><<>><<>><<<<>><>>>><<<<>>>><<<>>><<<<>><<<<>>><<<<>>><<>>>><<>><>>><<><<<>>>><<<<>><<>><><<<<>>>><<<<><<<>><><<<><<>><>><<<<>><<><<<>><>><>><>>>><<<><>>><>>>><<<<>>><<<>>>><>>><>>><<<><<<>>><<<<>>><<><<<<>>>><<<<><<>>>><<>><<<<>>>><>>>><<>><<>><<><>>>><><><<<<>>><<<>>><<<<>>>><<>>><<<<>>>><><<><<<<>>><<<<>>>><<<>><>><<<<>>>><><>>>><>>><<><<<<>><<<<>>>><<>>><<>>>><>>><<>>><><<<<>>><<<>><>>>><<<><<<<>>>><<<<>><>><<>>>><<><>><>>><<>>>><<<<>>><<<<>>><<<>><<>><<>>><>><>><<<<>><<<>><><<<>><<<>>>><<<<><<<<>>><><<<><<>>><<<>>><<<<>>><<>>><<<><<>>><<<>>>><<<<>>><>>>><<>><>><<<<>><<<<>>>><<>><<<<><>><<<<>>>><>>><<<<>>><>><<<<><<<><<<>><><<<>>>><><<<>><>>><<<<>>>><<<<>>>><<>><<<<>><<<><<>>>><<<>>><<<><<><<<<>>>><<><<>><<>>>><<<<><><<<<>>>><<<<>><>>><<<>>><<<>><<<>><<>><<<<>>><<<<>>>><<<><>>>><<>><<>>>><<<><>>><><><<<>><<><<<><<<<>>>><<<>>><<<>>><<<<><><<<>>><<<<>>>><<>>>><<>><<>>><>>><<<>><<<<>>><<<<>><<<<>>><<><<<>>><<<>><<><<><<<<>>>><>>>><<>>><<<<>>>><<<<>><<<>><<<<>>>><<<>>>><<><<<><<<>>>><<<<>>><<<<>><<>>>><>><><<<>>><<<>>>><<<<>><<>>><><>><<<>>><<<>>>><<>>>><<<<><><>>>><<>><<<>><<<<>>><<<>>><<<>>><<<>>>><<>>><<>>>><><><>><<<<>>><<<<>>>><<<><><<<<><<>><<<<>><<><<<><<<>><<><<<>>>><>><><>><<<>>><<<<>>>><<<<>><<>><><<<>>><>>>><>>><<<<>>><><<<><>>>><<<><<>><<<>><>>><><<<<>><<>>>><<>>><<<>>><<<<>><>>><>>><<<>>>><<>>><><<<><<<>>><<<>>><<<<>>>><<<>><>>>><<<<>>>><<<>>>><<>>>><<<><<<<>><<<<><<><<>>>><<<<>><><>>><<>>>><>>><<<<>>><<<<>><<<><<<>>><<><<>>><<>><<<>>>><>>><<<<>>><<<>>><>>>><<<<>>><<<<>>><><<<<>>><><<<><<<>>>><<><<>><><<<<>>>><<<<>><<>>>><<><<<<>>>><<<<>>>><>>><<<>>>><<<<><>><<><<<>>><<<<><<<<>>>><>><>>><<<>>>><><<<<><<<<>><<<>><<<<><<<>>><><<<<>><<>><<<>><<<>>><<><<<>>><<><><<<<>>>><<>><<<><>>>><>>>><<>>><>><><<<>>><>>>><><<<<><>>><<>>>><<>><<>>>><<<>>>><<<<>>>><<<>><<<<>><<><<<>>><>>><<<>>><<<<>><<>>>><>>><<>>><<<>>><>><>>><<>><<<<>>><>><<>>>><<<<><<<<>>><<<><><><>>><<>>><<<<>>>><<<<>><>><<<<>>><<>><>>><<<>>>><<<<>>>><><><<<>>>><><<<>>><<<<>>>><<>>>><<<>>>><<><<<>>><<<<>>><<>>>><><>>><><>>><<<<>>>><<<>><<>>>><<><<>>><>><><>>><<<<>>><<>>><<<<>>><<<>>><>><<>>><<<>><>>>><<<>>><>>><<<>>>><<<<>>>><<<<><<<>>>><<<>>><<>>>><<<<><<<<>>><<<>><<<><<<>>><<<<>><<>><<<>>>><>>>><<<<><<<<>><<>><<>><<<><<<<>><<<>><<<<>>>><>>>><>><><<>>>><<<<>><<>>>><>>><<>>><<<<>>><<<>>><<<>>>><<>>>><>>>><><>><<<>><<<<><<<<>>>><<<>>>><>>><<<><<>>>><<<>>><>>>><<><<<><<<<>><<>>>><<<>><<<<><<><>>><>><>><>>>><<<>>><<>><<<<>>><<<>><<<<>>>><><<><<<>>>><<>>><<<><<><<<><<<<><>>><>><<<><<<>><<<><<>><<<<>>><<>>><<>>><<<<><>><<><<<<>><<<<>><<<<><>>><<<<>><<>>>><>><>>>><<<<>>><<<<>><><<<>><<>>>><>>>><<>>><><<>>>><<><<>><<<>><>>>><<<<>><<<><<><<>><<<>><<<>><>><>>>><<<<>>><<<<>>><<<>>>><>><<<>>>><<<<><>>><>>>><<>><<<<>><<<<>>><<<<>>><<<<><<<>>>><>>>><<<>>><<<>>>><<<>>>><<<<>>><<<<>>><<<><>>><<<<>>>><<<<><>>>><<>><<<>>>><<><<<<><>><><<>>><<<<>>><<<<>>>><<<<>>>><<>><<<<>>><<<<>>>><<>>>><<<>>><<<<>>>><<<><<<<><<>><<<<>>><<<<>>><>>>><>><<<<><<<>>><>>>><><<<><<<>><>>><<>><>><<<><>>><<><<<>>><>>><<<<><>>><<><<><<<<><<<>>><<<<>>><>>>><>><<<<>><<>><<<<>>><<<>><>><<<><>>>><>><<><><>>>><<<<><>>><<><<<<>><<<<><>>>><<>>><<<>><<<>>>><<>>><>>>><<<>>>><<>>><<<>>>><<<>><>>>><<><>>>><>>><>>>><<<>>>><<<<>>>><<>>><<>>><<<<>>>><>>>><<><>><<<<>>><><<<><<<<>>>><<<<>>>><<>>><<<>><<<>><<<>>>><<<<>>>><<<<>><<>>><<><<>>>><>><>><>>><<>><<<>>><<<<>><<>><<<<>>><>>>><<<<><<<>>>><>>><<>><>>>><>>>><><<<<>><<<><<<<>>>><<<>>><<<<>>>><<<<>>><<<>>><>>><<<>>>><>>>><<<<>>><<<<><<><<<<><<<<><>>>><<><>>>><<>><<<>><>>><<<<>><>><<<><<>>>><<>>>><>>><<<><<<>><>>><><<>>><<><<>>><<<>>>><<<<>><<><<<<>>>><<<<>>>><<<<><<<<>>><<<<><<<><>>><<>>>><<>>>><<<<>>><<<>>><<<>>>><<<<>>><>>><<>>>><<<<>>>><<<>><<<>>>><<<>><><<<>><><<<>>><><<<><>>>><<>><<<<>>>><<<>>>><<>>><<<<><<<<>>>><<>>><<<<>>>><>>><<<>>><<<<>>>><<>>><<>>><<>>><<<>><<><<>><><>><>>>><<<<>>><<<<>>>><<<><<>>><<<><<<>>>><<<<>>><<<<>>><<<<>><<<<>>><<<<>>><<<><<<><<<<><<>>><><<<>>><<>>>><<>>><>>>><<<>>>><<<<>>><>>>><<>><<<>>><<<>><>><<><>>><<<><<<<>>>><<>><<<>><>>>><<<>><<>><<>>>><><>><>>>><<<><<<<><><>>>><<>>>><<<>>><><<>><<<<><<<<>>><>>><<>><<<>>>><<<<>>>><><<<<>><<<<>><<><<>>>><<><<<<><>>>><<>><<<>><>><<<<><>>>><>><<>><<>>>><<<<>>><<<<>>>><<>>>><<<<>>><<<>>><><<<>>>><><>>><<<><<><<<<><<<>>><<>>><<>>>><<<><<<<>>>><<<>>>><<><<<<>>>><<<<>>><<<>>><<>>><><>>><<<<>>>><<><<<>>>><<<<><<><><<><<<<>><<<><<<<>><<>><<>>><>><>><<<<>>>><>>><><<>>>><<<>>><<<<>>>><<<<><>>>><<<>><>>><<<<>>>><<><<>>><<><>>><<>><<<<>><<<>><<>><<<><<>>>><<>><>>><>>><<<>><<<<>><<<><<>><<<<>>>><<<<>>><><<<<>>>><<><>>><<<>>>><<><>>>><<<<>><>><<<>><<>><<<<>>>><<<>>>><<<>><>>>><>>>><>>>><<<<>>>><<>>>><<<><<>>>><<><<<><<<>>>><<<<>>>><<<<>><>>>><>>><<><<<><>><<>>><>>>><<>>>><<<<>>>><>>><>><<>><<<>><<<><><<<<>>><<<<><<>>>><>>><<>><<>><<<<><<<<><<<>><<<<>>>><<><<<><<<<>>><<<>>>><<<<>><>><<<><><<<<>><<<<>><>>>><<<<>>><>>>><>><<>>>><<<>>><<>>><>>>><>><>>><>>><<><<>>><<>><<<>><<<>><<<>>><><>>><>>>><<>>>><<<<>><>>>><>>>><>><<>>><<<<>>>><<>><><<>>><<<>>><<<>>>><<><<<<><>>>><>>><<<>>><<<><<<<>>><>>>><<>>><<>>>><><<>><<>>><>>><>>><<><<<><>><<<>>><>><<<><<>>>><<<>>><<<<>><<>>>><>>>><<<<>>><<<<><<<<>><<<><<>>>><><<<<>><<<><<<>>>><<<>><<<<>>><<<><<<>>>><<><>>><<<>><<<<><<<>>><<<>><>><<<>>>><>>><<><<>>><<<>>>><<<<>>><<<<>>><<<<><><><<>>><<>><<<>>>><<<>>>><><<<>>>><>>><<>><<>><>>><><<>><<<<>><<<<>>><<><<>>><<>>><<><<<<><<<>><><<>>>><<<<>>><<<>>><<<<><<<<><<>><<<><<>>>><>>><<<>>>><<<>>>><>>><>><<>><<>>><<>><<<<>><<>><<<>>><<<<><>>><>><<<><<>><<<<><<<><<>><<>>>><>>>><<><<><<>><>>>><><><<<<>>><><<>>>><<<><<<<>><<<<>><><<<><>>>><<<>>>><<>><<<>>><<>>>><<<<>>>><><<<>>><<<<><<<><<<><<<<>>>><>><<<<>>>><>>>><<<<>>><>>>><<<<>><<<>>>><<<<>>>><<>>>><<>><<<<>><<<><<<<>>><>><<<<>><>>><<<>>><<<<>>>><>><<><<>><><<<<>>>><<<<>><>>>><<<>>>><<>>>><>>>><<><>>>><<<<>>>><<<<>><<<<>>><><<><<<><<<<>>><>><<>>><<>>>><<<>>>><<>>><<<>>>><<><>>>><<<><><<<><<<>><<<><<<<>>><<><<<<>><>>><>>><>>><><>><<>>><<<<>>><>>><<<<><<<>>>><<>><<<<>>>><<<>><><<<<><<<<>>>><<>><<>>>><<>>>><><<<<>>><>>><<>><<<<>>>><>>>><<<<>><<>>><<<>>><>>>><<<>>>><<<><<><<><<<>>>><>>><<<>><<<>><<<<>>>><<<>><<<<>>><<>>><<<>>>><><<>>>><<<>>><<<>>>><<<<>><<>>><<<<>><<>>><>>><<<<><>>>><<<><>>>><<<<>><<<<><>>>><<<<>><>><<<<><<>>><<<<>>><><<<<><>>>><<<<><<<<>><<<<>>><<>>><<<<><>>>><<>>>><><<<>>>><>><<<>>><<<<><<>>>><<<<>>><><>>><>><<<>><<<<>>>><>>>><<<<>>><<<<>>><<>><<<>>>><<<>>><<>><>><><><<<><><<<>>><<<<>><<<<>><>>>><<>><><<>><<<<>>>><>><>>><>>><<<>>><<><>><><<<><<>>>><<<<>>>><>>><<<<>><<<>>><><<<<><<<>><<><<<><<>>><<<>>><<<>>>><><<>>><<<<><<<>>>><<>>><>><<<<>>>><<<<>>>><<>>><<>>>><<<<>><<<<>>>><<<<>><<>><>>><<>>><<>>>><<>>>><<<>>>><<<<>>>><<<><<<>>>><<<<>>>><<>>>><<<<>>>><<<><><>>><<>><<<<>>><<<<>>><><<><<<<><<><<<<>>><>>><<<<>>><<<<>><<<<>>>><<><<>><<>><<<<>>>><<<<>><><<>><>>>><>><><>>>><<<><<>>><<>>>><<><<<<><<>><>>>><>>>><<<<>>>><<<>>><<>><<<><<<>>><<>><<<><>>>><>>>><<>><>>>><<>><<<<>><>>><<>><<>>><<<<>>><<<><<<<>>><<<<>>><<<>><<>>><<<<>>><><<<<>>><<<<>>>><<<<>>>><><<>>>><<>>>><<<<>>>><>>><<<<><<>><<<>>><<<<>>>><>>><<<><<>>>><<<<>><<<><>>>><<<<>>><<<>>>><>>><<><>>>><<<<><<<<>>><<<>><<<><<<>>>><>>>><<<<><<>><<<><<>>>><<<>>>><>><<>>><<<><<<>><>>>><<>><<>>>><<<<><<<>><<<<><<>>><>><<<>>><<>><<><<<>>>><<<<>>><><<<<>><<>>>><<<<>>><>><<>><<>>>><<<><<>>>><<>>><<<>>><<<<><<<>><<<<>>><<>>><<<>><<<><<<<>>>><<<><<>><<<>><<>>><>>>><<<>>>><<>><<>>>><<>><<<<><>>>><<<>>>><<>>>><<<>><<<<><<<<>><<<<>>><<<<><<<<><<<><<<<>><<<<>>>><<<<>>><<<<>>><>><><><<>>><<>><<<<>><>>>><>><<<>>><>><>>><<<><<<><>>>><<><>><<>><><<>><<><<<>><<<>>><<>><<<><><<>><<<>><<<><<<>><>>><<<>>><<<>>><>>>><>>>><<<><>><<>><<<<><<<<>><<<<>><<<>>><<<>><<><<><<>><<><<><>>>><<<><<><<>>><<<>><<<>><<>>><<<<><<<<>>><<<<>><<><>><<>><<><<<><<<>>><<>>>><>><<<<><<<<>>>><<<<>>><>>><<>>>><<>>>><<>>><<<>><<<><<<<><<<<><<<<>>><<<>>>><<<<>><>><<<>>><<>>><<<<><>>>><<>>><<<<>>><<>><><<>>>><><<<>><>>><<><<<>>>><<<>>><<<><<<>>><>><<<><<<<>><<<<><<><<>>>><><<<<>>>><>><<>><<><<<><<<<>>><><<><<<<>>>><><<<<>>>><<>><<<>>>><>>>><<<<>>><<>>><><<<<>>>><><>>><<>><<<<>>><<<<><<<<><><<<<>>><<<<>>>><<><<>>>><<<>>><<>>><<><<<<><<>><>>><<<>>>><<<><<<<>>><<<>>>><<<<>><<<<>><<<<>><<<<><<<<>>>><<<<>>>><<<>>><<<>>><<<<>><><<<<>><>>>><<<<><>>>><<<<>><<>>><>><<<><<<<>>>><><<<><<>>>><<<<><<<><>>><<><>>>><<<<><<>>><<>>><<>>><<<>>><>>>><<<>>>><><<<<>>><<<<>>><<<<>>>><<<>>>><<>>><<>>>><<<<><>>>><>><<<<>>><<<<>>>><<<>>><<<>><<<>><<<>><>><>>>><>><<>><<<<><>>><<<<>>><>>><>>>><<<<>>><>>>><<><<<>>><>>><<<<>><<<>><<<<>><<<>>>><>>>><<<>>><<<<>>>><<<<>>>><<<>>>><><<<><<<>>>><<<><<<<>>>><<<>>>><>>><<<<><<<>><<<><<>><<>><<<<><<>>>><<<>>>><<<<>><>><>>>><>><<<><<><<<>>><<<<>>><<>><<<<>><><>><>><<>><>>>><<>>>><<>>><<<><>>><<<>>>><>><>>>><<<<><<>>><<<>>><<>>><>><><<<<>><><>>>><>><<<>><<<><<><>>><<<<><<<<>>><<>>>><<><<<<>>><<<>><<<<>>><<>>>><<>>>><<>><<<<>><<><<<><<<<>>>><><<>>><<<>>>><>>>><<><<<<>>>><<<>><>>><<<<>><<<<>>><<<><>>><<<>>><>>><<<<>><>>>><<<<>>><<><<<<>><<><<<<><<>><<<>>>><<<>><<<>>><<<>>>><<<<><<<>><<>>>><<>>>><>><<<<>>>><>>><<<><<>>><<<><<>>>><<<>>><<<>>><>><<<>>><<<<>><<>>>><<>>><<>>><<<>>><><<<>>><<>>>><>>><<>>><<>><<<><>>>><<>>>><<<<>><<>>><<<<>><<>><<>><<<>><<><>>><><<<>>>><><<>>><<>>><<<>>><<><><<<<>>><<<<><<>>>><<>><<<>>><<<>>>><>>><<<>>><<<<><<<>>><<<>><>><<><<<<>>><<>>>><<>><><<<<>>><<<<>>><<<<>>><<>><<>><<>><>><<<><>>><><>>>><<<>>><>>><<>>><<<><<>>>><<<><<<<>>><<<><<<><<<<>><<<<>><>>>><<<>>><<<><<<<>><<<<>><><<<<><<<<><<<>><<<>>>><>><<<>>><<>>><>><<<<>><<<><><<<<>>>><<<<>><<<>>>><<<<><<<>>>><<<<>>><<<>>><<>>>><>>>><<<<>><<<<>><<><<>><>>>><<>>>><<>><>>><<>>>><><<><>>><<><<<<>>>><<>>><<<<>><>>><<<<>><<<>><>>>><<<><<><<<>>><>>>><>>><<<>>><<>>><<<<><<<>>><>>><><<<>><<<>>><<<<>><<>>><<<<><>><>><><>>><<>><<")

(defn parse-input [input]
  {:jets      (vec (map {\> 1, \< -1} input))
   :jet-idx   0
   :shape-idx 0
   :max-y     0
   :rocks     #{}})

(def shapes
  [[[0 0] [1 0] [2 0] [3 0]]
   [[1 2] [0 1] [1 1] [2 1] [1 0]]
   [[2 2] [2 1] [0 0] [1 0] [2 0]]
   [[0 0] [0 1] [0 2] [0 3]]
   [[0 1] [1 1] [0 0] [1 0]]])

(defn free? [world [x y]]
  (and (>= x 0)
       (< x 7)
       (> y 0)
       (not (contains? (:rocks world) [x y]))))

(defn visualize
  ([world]
   (visualize world #{}))
  ([world coords]
   (let [max-y (max (->> (map second coords)
                         (#(conj % 0))
                         (reduce max))
                    (->> (map second (:rocks world))
                         (#(conj % 0))
                         (reduce max)))
         coords-set (set coords)]
     (doseq [y' (range 0 (inc max-y))
             x (range -1 8)
             :let [y (- max-y y')]]
       (print
         (cond
           (and (= y 0) (or (= x -1) (= x 7))) "+"
           (= y 0) "-"
           (or (= x -1) (= x 7)) "|"
           (contains? coords-set [x y]) "@"
           (free? world [x y]) "."
           :else "#"))
       (when (= x 7)
         (println))))
   (println)))

(defn place [world]
  (let [shape-idx (:shape-idx world)
        shape (get shapes shape-idx)
        dx 2
        dy (+ (:max-y world) 4)
        original-max-y (:max-y world)]
    (loop [coords (map (fn [[sx sy]]
                         [(+ sx dx) (+ sy dy)])
                       shape)
           {jets    :jets
            jet-idx :jet-idx
            rocks   :rocks
            :as     world} (assoc world :shape-idx (mod (inc shape-idx) (count shapes)))]
      (let [push-coords' (map (fn [[x y]]
                                [(+ x (nth jets jet-idx)) y])
                              coords)
            push-coords (if (every? #(free? world %) push-coords')
                          push-coords'
                          coords)
            fall-coords (map (fn [[x y]]
                               [x (dec y)])
                             push-coords)]
        (if (every? #(free? world %) fall-coords)
          (recur fall-coords
                 (-> world
                     (assoc :jet-idx (mod (inc jet-idx) (count jets)))
                     (assoc :max-y (max original-max-y
                                        (->> (map second fall-coords)
                                             (reduce max))))))
          (-> world
              (assoc :jet-idx (mod (inc jet-idx) (count jets)))
              (assoc :rocks (into rocks push-coords))))))))

(defn part1 []
  (let [world (parse-input input)]
    (:max-y (nth (iterate place world) 2022))))

(defn world-hash [world]
  (let [max-y (:max-y world)]
    (hash (for [x (range 0 8)
                y (range (- max-y 100) max-y)]
            (free? world [x y])))))

(defn part2 []
  (let [year 1000000000000]
    (loop [world (parse-input input), states {}, n 0]
      (let [world' (place world)
            state-key [(:jet-idx world') (:shape-idx world') (world-hash world')]]
        (if (contains? states state-key)
          (let [first-occurrence (get states state-key)
                cycle-start (:n first-occurrence)
                cycle-length (- n cycle-start)
                cycle-height (- (:max-y world) (:max-y first-occurrence))
                missing-places (mod (- year cycle-start) cycle-length)
                missing-height (- (:max-y (nth (iterate place world) missing-places))
                                  (:max-y world))]
            (+ (:max-y first-occurrence)
               (* cycle-height (long (/ (- year cycle-start) cycle-length)))
               missing-height))
          (recur world'
                 (assoc states state-key {:n     n
                                          :key   state-key
                                          :max-y (:max-y world)})
                 (inc n)))))))