Fork me on GitHub
#adventofcode
<
2021-12-06
>
alekszelark04:12:20

🧵Day 6 answers thread: post your answers here

solf05:12:42

(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 +))

🔥 1
norman05:12:17

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

mikelis05:12:18

(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))

👍 1
Mario C.06:12:53

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))

misha06:12:15

@U7S5E44DB

(take (inc 256))
     last
->
(drop 256)
(first)

AC06:12:06

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

peterc07:12:43

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

❤️ 1
nbardiuk08:12:47

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

nice 4
bananadance 1
👏 3
Antonio Bibiano08:12:33

this is my solution for today

Antonio Bibiano08:12:43

(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))

👍 5
👌 2
1
2
😮 1
👏 2
Antonio Bibiano08:12:30

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

Mikko Koski10:12:14

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

nice 1
gabo11:12:58

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

  )

genmeblog11:12:04

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

alekszelark12:12:29

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

❤️ 1
1
Vincent Cantin13:12:53

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 ^_^ 🎉

👍 1
tschady13:12:30

i admit to stealing @U01HY37QQUA’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

👍 1
tschady13:12:09

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.

🤯 7
❤️ 5
👌 2
✔️ 1
Antonio Bibiano13:12:27

@U1Z392WMQ 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?

tschady13:12:43

whenever it helps describe the domain i do it.

Antonio Bibiano13:12:54

ah yeah i'll keep that in mind

Antonio Bibiano13:12:25

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

🐟 2
genmeblog13:12:49

not enough pixels 🙂

Stuart14:12:52

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)))))
I then tried to use transients, but I couldn't get this to work at all. I kept getting type mismatches between lazy-seq and transients. I couldn't understand why, so gave up with this. I need to learn more about transients. Then I realised I could just keep track of the number of fishes at each life stage in a hash-map like others here have done.
(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))))
Couldn't figure out a way to do this with reduce-kv , so just did it the long winded way.

Stuart14:12:46

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

Stuart15:12:37

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 +))
I don't like the take 257, is their a way to do this where you "overwrite" the stages each time and dont end up with a big list. Like a function that keeps a function f over and over n times and feeds its output back in as its input, without making the collection?

Callum Oakley15:12:22

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

👍 1
euccastro16:12:43

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

pavlosmelissinos16:12:24

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.

alekszelark16:12:11

Just played a bit with @U06B54Y95 solution :star-struck:

(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))))

👏 5
Callum Oakley16:12:04

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

👍 2
euccastro17:12:46

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

Sam Adams17:12:43

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

Felipe Cortez18:12:36

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)))))))

mikelis18:12:39

@U013YN3T4DA 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)

👍 3
mikelis18:12:09

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))

mikelis18:12:27

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

mchampine18:12:58

@U067R559Q > “(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!

🙌 1
borkdude22:12:04

Both run under a millisecond with babashka.

karol23:12:22

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

🙌 1
euccastro00:12:22

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

euccastro00:12:08

it borrows liberally from various of the other solutions

Benjamin09:12:15

can somebody give a tip for day6 part2

🙌 1
Benjamin09:12:07

like how to make an efficient algorithm

Benjamin10:12:04

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

Björn Ebbinghaus10:12:48

The tip is: frequencies

5
peterc10:12:31

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

mikelis10:12:41

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

☝️ 1
genmeblog11:12:54

my hint: cache is your friend

Benjamin12:12:26

did something with frequencies that is around 5ms 🙂

kevinc04:12:58

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

Antonio Bibiano10:12:45

maybe a nested map

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

mikelis10:12:05

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.

✔️ 2
peterc10:12:51

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)))

💯 2
mikelis10:12:23

But you could do

(for [row (range SIZE)
      col (range SIZE)]
   ...)
edit: oh, jinx

peterc10:12:46

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

peterc10:12:37

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

1
hanyuone11:12:51

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))

hanyuone11:12:02

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?

mikelis11:12:28

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 🙂

hanyuone11:12:11

i see, thank you!

tschady13:12:14

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

tschady13:12:02

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

Stuart10:12:44

OH dear, my sln for part 2 is running very, very slowly. It was fastish up to day 110 ish, then started really creeping along at day 120ish, now its ticking up a day every 10 seconds or so...

mikelis11:12:29

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

Stuart11:12:52

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}
THen update each val by dec, then spawn just can update the number of 8s to the number of zeros each time. Is this dumb?

mikelis11:12:13

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

Stuart11:12:36

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

Stuart11:12:42

Is their a core function to do this?

mikelis11:12:17

you can create a new map

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

mikelis11:12:31

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 ...))
             {})

Björn Ebbinghaus13:12:55

@U013YN3T4DA You can map over a map. Tip:

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

tschady14:12:04

see reduce-kv

borkdude20:12:20

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

borkdude20:12:12

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

sebastian21:12:17

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

lread23:12:52

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!

borkdude23:12:33

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

babashka 2
🚀 1
rmprescott01:12:36

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

Stuart01:12:13

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

sebastian07:12:54

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

nbardiuk14:12:06

The exponential growth. Brightness represents internal timer of a fish, new fishes are added to the tail of spiral

6
bellissimo 1
🎣 1
🐡 2
wow 7
partywombat 2
🍥 1
🐬 1
🐟 1
tschady14:12:20

source? love to see it.

genmeblog20:12:27

Glad you've reached for Clojure2d @U076FM90B Yay!

nbardiuk20:12:00

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

bananadance 1