This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2021-12-06
Channels
- # adventofcode (106)
- # aleph (1)
- # announcements (1)
- # asami (14)
- # babashka (120)
- # beginners (54)
- # calva (106)
- # chlorine-clover (33)
- # clj-kondo (5)
- # cljdoc (3)
- # cljs-dev (3)
- # clojure (92)
- # clojure-android (1)
- # clojure-australia (2)
- # clojure-europe (24)
- # clojure-italy (3)
- # clojure-nl (5)
- # clojure-uk (16)
- # clojuredesign-podcast (1)
- # clojurescript (29)
- # code-reviews (58)
- # conjure (16)
- # core-logic (4)
- # cursive (9)
- # datalevin (2)
- # graphql (20)
- # gratitude (7)
- # jackdaw (11)
- # java (9)
- # jobs (2)
- # lsp (23)
- # minecraft (1)
- # missionary (28)
- # off-topic (5)
- # polylith (5)
- # react (1)
- # reagent (12)
- # releases (1)
- # remote-jobs (4)
- # reveal (7)
- # shadow-cljs (8)
- # slack-help (1)
- # tools-deps (11)
- # vim (6)
🧵Day 6 answers thread: post your answers here
(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))
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))
sigh.. I wasted way too much time reading about exponential growth functions for part 2 before the "aha" moment came.
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 @U076FM90B. Also love @U01HY37QQUA 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://app.slack.com/team/U01HY37QQUA, I am amazed by your solution :star-struck:
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 @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
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.
@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?
ah yeah i'll keep that in mind
@U1EP3BZ3Q but with your solution you can now make a nice animation of fishes slowly gestating and giving birth to new fishes :D
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.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 +))
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?@U013YN3T4DA 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 @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))))
@UEQPKG7HQ the matrix solution @U1Z392WMQ 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)))))))
@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)
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))
@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!
Better late than never. https://gist.github.com/borkdude/b5cf0e9d2d8ab7c678d88e27a3357b33#file-aoc21_06-clj
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
pleased with how brief it came out 🙂 https://github.com/kconner/advent-of-code/blob/master/2021/6b.clj
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 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
@U02CV2P4J6S Nice! Here is my solution, if you are interested: https://github.com/MrEbbinghaus/advent-of-code/blob/master/2021/day06.clj#L26
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)]
...)
edit: oh, jinxThe point is that you dont want to rebuild the vector(s) each time (like in the nested map solution)
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 🙂
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
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...
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}
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?I’d say you’re on the right track! 🙂
you can create a new map
(->> old-map
(map (fn [[old-key old-val]]
[new-key new-val]))
(into {}))
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 ...))
{})
@U013YN3T4DA You can map over a map. Tip:
[3 42] -> {2 42}
[0 13] -> {6 13, 8 13}
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 :)
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!
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.
The exponential growth. Brightness represents internal timer of a fish, new fishes are added to the tail of spiral
it's quilclojure2d code with some magic numbers https://github.com/nbardiuk/adventofcode/blob/master/2021/dev/sketches/day06.clj
Glad you've reached for Clojure2d @U076FM90B Yay!