Clojurians Log v2

https://gitlab.com/maximoburrito/advent2021/-/blob/main/src/day6/main.clj

(defn parse [input]
  (->> input
       u/parse-comma-separated-list
       (map parse-long)))

(defn next [l]
  {0 (get l 1 0)
   1 (get l 2 0)
   2 (get l 3 0)
   3 (get l 4 0)
   4 (get l 5 0)
   5 (get l 6 0)
   6 (+ (get l 7 0) (get l 0 0))
   7 (get l 8 0)
   8 (get l 0 0)})

(->> (parse #_"3,4,3,1,2"
            (u/get-input 2021 6))
     frequencies
     (iterate next)
     (take (inc 256))
     last
     vals
     (reduce +))

Looking at the other solutions, I realize I didn't have to resort to a recursive memoized solution

(defn step [fish]
  (->> fish
       (reduce (fn [res [k v]]
                 (if (= k 0)
                   (-> res
                       (update 6 (fnil + 0) v)
                       (assoc 8 v))
                   (update res (dec k) (fnil + 0) v)))
               {})))

(defn solve [n input]
  (->> input
       (find-ints)
       (frequencies)
       (nth-iter n step)
       (vals)
       (reduce +)))

(def solve1 (partial solve 80))
(def solve2 (partial solve 256))

https://github.com/jhny/adventofcode2021/blob/main/src/day6.clj

Pretty much the same as others

(def puzzle-input
  (mapv read-string (str/split (input "day6.txt") #",|\n")))

(defn apply-fish-creation [index state]
  (if (= index 0)
    (-> (update state 8 (constantly (get state index)))
        (update 6 (partial + (get state index))))
    state))

(defn update-state [state]
  (->> (reduce (fn [{:keys [state carry-over]} index]
                 {:state      (-> (apply-fish-creation index state)
                                  (update index (constantly carry-over)))
                  :carry-over (get state index)})
               {:carry-over 0
                :state      state}
               (range 8 -1 -1))
       (:state)))

(defn lantern-state [fish-states]
  (reduce (fn [state f-state]
            (update state f-state inc))
          (vec (repeat 9 0)) fish-states))

(defn part-one [puzzle-input days]
  (let [state (lantern-state puzzle-input)]
    (apply + (reduce (fn [s _] (update-state s)) state (range days)))))


(comment
  ;; day1
  (part-one puzzle-input 80)
  ;; day2
  (part-one puzzle-input 256))

@dromar56

(take (inc 256))
     last

(drop 256)
(first)

sigh.. I wasted way too much time reading about exponential growth functions for part 2 before the "aha" moment came.

I wish I implemented @dromar56 solution for speed, simple and gets it done

https://github.com/jreighley/aoc2021/blob/master/src/day6.clj

https://github.com/v-garcia/aoc_2021/blob/main/day_six.clj

I was very happy to find/remember that clojure has memoize, otherwise I would waste another hour caching intermediate results https://github.com/nbardiuk/adventofcode/blob/master/2021/src/day06.clj

this is my solution for today

(def small "3,4,3,1,2")
(def large (slurp "/home/antbbn/aoc_2021/input_6.txt"))

(defn parse [input]
  (as-> input _
    (re-seq #"\d+" _)
    (map #(Integer/parseInt %) _)
    (frequencies _)
    (mapv #(get _ % 0) (range 9))))

(defn step [fishes]
  (conj (update (subvec fishes 1) 6 + (first fishes))
        (first fishes)))


(reduce + (nth (iterate step (parse small)) 80))
(reduce + (nth (iterate step (parse large)) 80))
(reduce + (nth (iterate step (parse small)) 256))
(reduce + (nth (iterate step (parse large)) 256))

was pretty cool to keep thinking of a way to avoid creating the list of fishes 🙂

Great that 1.11.0-alpha3 came right before AoC 🙂 I've been heavily using the new core functions, parse-long , update-keys , update-vals etc. My solution for today: https://github.com/rap1ds/advent-of-code-2021/blob/main/src/day6.clj

This day is a nice little one https://gist.github.com/galuque/25e5adf15976ea36023cf69af43c7310

(ns io.github.galuque.aoc-2021.day-6
  (:require [ :as io]
            [clojure.string :as str]))

(def input (->> "day_6/input.txt"
                io/resource
                slurp))

(def sample-input "3,4,3,1,2")

(def init-ages (into [] (repeat 9 0)))

(defn ages-vec [coll [v f]]
  (update coll v + f))

(defn parse-input [input]
  (->> (str/split (str/trim input) #",")
       (map parse-long)
       frequencies
       (reduce ages-vec init-ages)))

(defn day-passed [ages]
  (reduce conj [(subvec ages 1 7)
                (+ (nth ages 7) (nth ages 0))
                (nth ages 8)
                (nth ages 0)]))

(defn count-fish [days ages]
  (->> ages
       (iterate day-passed)
       (take (inc days))
       last
       (apply +)))

(def part-1 (partial count-fish 80))

(comment 
  
  (part-1 (parse-input sample-input))
  ;; => 5934
  
  (part-1 (parse-input input))
  ;; => 374994
  )

(def part-2 (partial count-fish 256))

(comment

  (part-2 (parse-input sample-input))
  ;; => 26984457539

  (part-2 (parse-input input))
  ;; => 1686252324092

  )

and my solution... I don't know why it's so obfuscated :/, very close to @nbardiuk. Also love @antbbn step function. So clever! https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2021/day06.clj

Almost forgot about memoize https://github.com/zelark/AoC-2021/blob/main/src/zelark/aoc_2021/day_06.clj

https://github.com/benjamin-asdf/advent-of-code-2021/blob/master/src/day6.clj

@https://app.slack.com/team/U01HY37QQUA, I am amazed by your solution 🤩

Another fun one, but I'm sure there's a more elegant to implement the method I tried in part 2: https://github.com/RedPenguin101/aoc2021/blob/main/clojure/src/aoc2021/day06.clj https://github.com/RedPenguin101/aoc2021/blob/main/day06.md

My solution: https://github.com/green-coder/advent-of-code/blob/master/src/aoc_2021/day_6.clj I used the new update-keys function, yeah ^_^ 🎉

i admit to stealing @antbbn’s init-state function, I originally used reduce-kv . my next-gen was original https://github.com/tschady/advent-of-code/blob/main/src/aoc/2021/d06.clj

checkout my coworkers thinking: > This problem can also be done as a matrix multiplication of an “evolution” matrix `M`: > { > {0, 1, 0, 0, 0, 0, 0, 0, 0}, > {0, 0, 1, 0, 0, 0, 0, 0, 0}, > {0, 0, 0, 1, 0, 0, 0, 0, 0}, > {0, 0, 0, 0, 1, 0, 0, 0, 0}, > {0, 0, 0, 0, 0, 1, 0, 0, 0}, > {0, 0, 0, 0, 0, 0, 1, 0, 0}, > {1, 0, 0, 0, 0, 0, 0, 1, 0}, > {0, 0, 0, 0, 0, 0, 0, 0, 1}, > {1, 0, 0, 0, 0, 0, 0, 0, 0}, > } > times a vector `v[0..8]` where `v[i]` indicates how many fish with internal timer value `i`. Then the problem reduces to computing `M⁸⁰⋅v` then summing the elements in the resulting vector. > > That technique is especially interesting if the number of days is super large, because you can raise a matrix to an arbitrary power much more quickly than actually multiplying that many times.

@tws very nice the next-gen with the thread first i also thought about using a let statement to avoid calling first two times, do you think that's better practice?

whenever it helps describe the domain i do it.

ah yeah i'll keep that in mind

@tsulej but with your solution you can now make a nice animation of fishes slowly gestating and giving birth to new fishes :D

not enough pixels 🙂

I initially started with just trying to add to vectors... THis worked for part1 and failed miserably for part 2

(defn puzzle-input []
  (->> (slurp "puzzle-inputs/2021/day6")
       (u/str-split #",")
       (mapv #(Integer/parseInt %))
       (frequencies)
       #_(into (sorted-map))))

(defn reset [idx-to-rest xs]
  (vec (reduce (fn [acc i] (assoc acc i 6)) xs idx-to-rest)))

(defn spawn [to-spawn xs]
  (vec (concat xs (repeat to-spawn 8))))

(loop [input (puzzle-input), day 0]
  (prn day)
  (if (= day 256)
    (count input)
    (let [to-spawn (keep-indexed #(when (zero? %2) %1) input)
          updated (->> input 
                       (mapv dec)
                       (reset to-spawn)
                       (spawn (count to-spawn)))]
      (recur updated (inc day)))))

(loop [stages (puzzle-input)
       days 0]
  (if (= days 256)
    (->> stages
         vals
         (reduce +))    
    (recur {0 (stages 1 0)
            1 (stages 2 0)
            2 (stages 3 0)
            3 (stages 4 0)
            4 (stages 5 0)
            5 (stages 6 0)
            6 (+ (stages 7 0) (stages 0 0))
            7 (stages 8 0)
            8 (stages 0 0)}
           (inc days))))

ALthough seeing the final result, I doubt transients would even help much, the vector would be HUGE

Got it with iterate too, but I don't like this solution as much

(defn update-fish [stages]
  (->> (map (fn [n]
                  (case n
                    8 {8 (stages 0 0)}
                    6 {6 (+ (stages 7 0) (stages 0 0))}
                    {n (stages (inc n) 0)}))
                (range 0 9))
       (into {})))

(->> (puzzle-input) 
     (iterate update-fish)
     (take 257)
     (last)
     (vals)
     (reduce +))

@qmstuart you could (apply comp (repeat 256 f)), but since take is lazy, you’re not actually retaining the full list in memory anyway

there's probably a more lucid shortcut using math, but I got this working quickly and I didn't need to change it for part 2 or clean it up later: https://github.com/euccastro/advent-of-code-2021/blob/main/day6.clj

Has anyone found a solution that runs in O(1)? Or at least in linear time to the number of fish states? I feel like it should be possible.

Just played a bit with @mchampine solution 🤩

(defn step [m]
  (-> (mapv m [1 2 3 4 5 6 7 8 0])
      (update 6 (fnil + 0 0) (m 0))))

(defn fish [input n]
  (let [fish-seq (iterate step (frequencies input))]
    (reduce + (nth fish-seq n))))

@pavlos the matrix solution @tws posted above is O(log(n)) with repeated squaring to do the exponentiation

I think my solution is missing a declare but it worked in the repl because I somehow defined the name to something nonrecursive first? 😛

I like the memoized per-fish solutions, totally different than how I thought about it. My rotating-array solution: https://samadams.dev/2021/12/06/advent-of-code-day-6.html

gave up on trying to do it mathematically and just ran the simulation instead. before the clean up:

(defn one [population]
  (reduce-kv (fn [m k _v]
               (assoc m k
                      (cond (= 6 k) (+ (get population 7)
                                       (get population 0))
                            (= 8 k) (get population 0)
                            :else   (get population (inc k)))))
             {}
             population))

(defn init [m] (merge (zipmap (range 9) (repeat 0)) m))

(reduce + (vals (last (take 257 (iterate one (init (frequencies input)))))))

@qmstuart not that it matters too much in this case but (->> (drop 256) (first)) should be faster than (->> (take 257) (last)) because last is always O(n)

for this use case I have a small helper function which avoids seqs altogether

(defn nth-iter [^long n f x]
  (if (pos? n)
    (recur (dec n) f (f x))
    x))

so (->> seed (iterate f) (drop n) (first)) becomes (->> seed (nth-iter n f))

@zelark > “(mapv m [1 2 3 4 5 6 7 8 0])” Awesome, love it! So clever that your version of the step function works with the output of frequencies AND a vector (because in this case they’re both functions from number to value - and that number can just as well be an index). Very concise code!

Better late than never. https://gist.github.com/borkdude/b5cf0e9d2d8ab7c678d88e27a3357b33#file-aoc21_06-clj

Both run under a millisecond with babashka.

https://github.com/kfirmanty/advent-of-code-2021/blob/main/src/day6.clj starting day6 rather late into a night wasn't good idea as it seems this is the first tricky one advent of code this year wasted a bit time trying to devise a formula of growth of single fish to be then used for others but then somehow clicked that all the fishes behave the same based on their state and not position on the array so it doesn't need to be preserved in whole

as usual I got envious of your frequencies-based solutions, so I did two things: • make a note to ask myself "what would frequencies do?" in every AoC day going forward, and • try and make a frequencies-based solution that rotates only some reference index, not the frequencies data structure itself

so here is it: https://github.com/euccastro/advent-of-code-2021/blob/main/day6b.clj

it borrows liberally from various of the other solutions

pleased with how brief it came out 🙂 https://github.com/kconner/advent-of-code/blob/master/2021/6b.clj

like how to make an efficient algorithm

now I'm trying to think about each fish in isolation, instead of the list of fish. I guess there should be a function f(age,t) -> fish count

The tip is: frequencies

there's an iterative approach that does not require brute-force

The order of the fish doesn’t matter, and there’s only ever 9 types of fish. Which means you don’t have to store all of them individually

my hint: cache is your friend

did something with frequencies that is around 5ms 🙂

https://github.com/benjamin-asdf/advent-of-code-2021/blob/master/src/day6.clj

@benjamin.schwerdtner Nice! Here is my solution, if you are interested: https://github.com/MrEbbinghaus/advent-of-code/blob/master/2021/day06.clj#L26

sick @mroerni

My tip: Don't follow the explanation too literally. And, you can eliminate unnecessary steps if you start with the end result you need to calculate, and build backward toward the input. https://github.com/kconner/advent-of-code/blob/master/2021/6b.clj

maybe a nested map

(defn bingo-mark [board draw]
  (map (fn [row]
         (map
          (fn [[col _]]
            [col (= col draw)])
          row))
       board)) 

Nested vectors are usually not very convenient, perhaps try using a hashmap where the key is a tuple of coords [x y] and the value is the count.

If you want to use a nested vector, something like this will work:

(defn board-coords [n]
  (for [x (range n)
        y (range n)]
    [x y]))

(def coords (board-coords 5))

(defn bingo-mark [board mark]
  (->> coords
       (filter #(= mark (get-in board (vec %))))
       (reduce #(assoc-in %1 %2 true) board)))

But you could do

(for [row (range SIZE)
      col (range SIZE)]
   ...)

The point is that you dont want to rebuild the vector(s) each time (like in the nested map solution)

But yeah, a hash-map is much more convenient!

i ended up doing this instead:

(defn find-draw
  [board draw]
  (let [coords (for [x (range SIZE) y (range SIZE)] [x y])]
    (->> coords
      (filter (fn [[x y]] (= (get-in board [x y 0]) draw)))
      first)))

(defn bingo-mark
  "Given a Bingo board and a drawn number, 'mark' that number on the board."
  [board draw]
  (if-let [[row col] (find-draw board draw)]
    (assoc-in board [row col 1] true)
    board))

seems a bit more idiomatic - not sure about a hashmap, wouldn't it make more sense to have a 1d vector in that case then?

In this case it probably doesn’t matter too much, but in other years on tasks where the “board” can grow in all directions and is usually quite sparse (e.g. the Conway’s game of life type puzzles) a hashmap is much much faster. But probably a matter of taste 🙂

i see, thank you!

for updating nested data structures, i suggest you use a purpose built library. my fav is https://github.com/redplanetlabs/specter . How much time it saves you helps get over the non-clojurey feel: https://github.com/tschady/advent-of-code/blob/main/src/aoc/2021/d04.clj#L17-L20

that navigator says ALL cards, ALL rows, ALL columns, then find our number.

Would you like some hints on how to speed it up?

Not yet, I have an idea of using a hashmap to store the number of fish at each state, e.g. start would be

{0 0
 1 1
 2 1
 3 2
 4 1
 5 0
 6 0
 7 0
 8 0}

I’d say you’re on the right track! 🙂

can you iterate through a hash map to update each val ?

Is their a core function to do this?

you can create a new map

(->> old-map
     (map (fn [[old-key old-val]]
            [new-key new-val]))
     (into {}))

thanks!

or if you want a bit more control over the result, you can use reduce

(->> old-map
     (reduce (fn [new-map [old-key old-val]]
                (assoc new-map ...))
             {})

@qmstuart You can map over a map. Tip:

[3 42] -> {2 42}
[0 13] -> {6 13, 8 13}

see reduce-kv

See solution is a few milliseconds, even in bb. https://twitter.com/mknoszlig/status/1467768132521627648

I was stuck in a foolish solution of exploding the list like it was graphically presented in the puzzle :)

I am renaming the keys in the hashmap. does part 2 in 1.5ms

Eek, the problem description drew me into a brute force solution. But I guess that was its fiendish aim! I was actually mired until I got the frequencies tip here. Bah!

Same

But now both answers run under 1ms in bb :)

What editor is this? I'm guessing it's displaying "f(" for "#("

You can do this in vscode, with prettify symbols plugin. Can setup your own substitutions.

spacemacs with a fancy symbol plugin. an you are right.

source? love to see it.

it's quilclojure2d code with some magic numbers https://github.com/nbardiuk/adventofcode/blob/master/2021/dev/sketches/day06.clj

pogg

Glad you've reached for Clojure2d @nbardiuk Yay!

I am very glad I've migrated to Clojure2d, I could not setup quil to run fast on my machine and Clojure2d just worked. The performance difference was very big. Thank you for the library