Clojurians Log v2
adventofcode 2020-12-15
@euccastro has joined the channel
I may drop from the contest today - life became busy and the AoC is very time consuming when you do it seriously.
Don't take it seriously 🙂 Maybe some puzzle will grab your attention
I will take a look at the problem and try to solve it right before sleeping, maybe.
I regret taking a look at the problem before work today. My mind is not at work, like it should be. 😃 Tomorrow I will wait with that.
I’ve been down to one star a day, most days Maybe I will catch up later. I find that if I take a stab at it, I ‘build the buckets’ in my brain to absorb “Oh, that’s how that should have beens solved!” at a later date.. If I don’t store the question, I have no context to understand the answer when I see it. Made it a lot further than the last few years. Thanks to everybody for the code samples. I learn a lot from all of you..
Day 15 answers thread - Post your answers here
Today's part1 worked without changes for part2, in stark contrast with day 13. Which makes my first solution just brute force. I'll spend some time thinking about the smart way, but there's less incentive when you've got the solution already.
(loop [vals (into {} (map-indexed (fn [i n] [n (list i i)]) data))
last (last data)
n (count data)]
(let [prev (take 2 (get vals last))
i-diff (apply - prev)]
#_(println n last prev)
(if (< n 30000000)
(recur
(update vals i-diff
(fn [idxs]
(if (seq idxs)
(conj idxs n)
(list n n))))
i-diff (inc n))
last)))
Yes, 13 sec for Part 2 https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_15.clj
Mine takes 70 seconds instead: https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day15.clj
Keeping all the indexes is probably bit slower
Maybe cleanup after work 🙂
My part 2 took about 37-40s to run, using the same brute-force approach as I used for part 1. Can't wait to see what clever math-trick I completely overlooked... https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day15.clj
My solution (nothing special, really) https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_15.clj
@rjray appararently there’s no clever math trick known. The sequence is called the https://oeis.org/A181391. See this thread: https://old.reddit.com/r/adventofcode/comments/kdfvec/2020_day_15_theory_behind_the_problem/
With an int-array and aget/`aset` it's about 2.5s for part2. https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day15.clj
(t/deftest part-3e7
(t/is (= 175594 (time (sut/game [0 3 6] 30000000))))
(t/is (= 2578 (time (sut/game [1 3 2] 30000000))))
(t/is (= 3544142 (time (sut/game [2 1 3] 30000000))))
(t/is (= 261214 (time (sut/game [1 2 3] 30000000))))
(t/is (= 6895259 (time (sut/game [2 3 1] 30000000))))
(t/is (= 18 (time (sut/game [3 2 1] 30000000))))
(t/is (= 362 (time (sut/game [3 1 2] 30000000)))))"Elapsed time: 2433.3227 msecs"
"Elapsed time: 2473.1943 msecs"
"Elapsed time: 2424.8357 msecs"
"Elapsed time: 2471.1161 msecs"
"Elapsed time: 2410.6786 msecs"
"Elapsed time: 2440.9612 msecs"
"Elapsed time: 2407.1532 msecs"A bit refactored, also added a fast version which uses int-array and unchecked- operations. About 800 ms on my machine. The slow version runs 13 secs.
https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_15.clj
I've reached the same time of 700ms with int-array and loop/recur on my machine. The same code with java HashMap was 6 times slower 4.5s and clojure maps where another 7 time slower 30s
Reimplemented using this data structure: http://java-performance.info/implementing-world-fastest-java-int-to-int-hash-map/ It's 2x slower than int-array approach uses half of the memory.
Capacity= 16777216
"Elapsed time: 3863.6976 msecs"😆
Oh come on! It's done in Clojure.
same "transient" 13sec with unchecked inc and typehints.
it is still in clojure, but is it 1) readable? 2) worth it? it is a good illustration where the time is spent though
ad1 - no, ad2 - yes! I learned something about data structures.
Thankfully not too long today (for the human, not the machine): https://github.com/benfle/advent-of-code-2020/blob/main/day15.clj
yea my part 1 solution worked for part 2. takes about 50 seconds but not feeling super motivated to optimize it this time around https://github.com/listba/advent-of-code-2020/blob/master/clojure/src/aoc_2020/days/15.clj
Yes, arrays are good for mapping on integers 🙂 I don't have the time to improve the performances unfortunately.
15s:
(->> input
(parse)
((fn [starts]
(loop [i (dec (count starts))
spoken (into {} (map-indexed (fn [i n] [n i]) (butlast starts)))
last (last starts)]
(if (< i end-t)
(let [t (spoken last)
say (if t
(- i t)
0)]
(recur (inc i) (assoc spoken last i) say))
last)))))I get 12 seconds with a transient map and 5 seconds using a java HashMap.
So 5s:
(->> input
(parse)
((fn [starts]
(loop [i (dec (count starts))
spoken (java.util.HashMap. (into {} (map-indexed (fn [i n] [n i]) (butlast starts))))
last (last starts)]
(if (< i end-t)
(let [t (. spoken get last)
say (if t
(- i t)
0)]
(recur (inc i) (do (. spoken put last i) spoken) say))
last)))))
42 seconds with my vanilla hashmap. Optimized with an int-array...278 seconds. Think I might be using that wrong. 😄
https://github.com/RedPenguin101/aoc2020/blob/main/day15.clj
About 14s for my part 2: https://github.com/Dexterminator/advent-of-code-2020/blob/main/src/day15/core.clj
. "Elapsed time: 19815.950142 msecs" d "Elapsed time: 13638.142432 msecs" with transient map
(defn f [input n]
(loop [turn (count input)
hist (zipmap input (range 1 ##Inf))
prev (peek input)]
(if (= n turn)
prev
(recur
(inc turn)
(assoc hist prev turn)
(if-let [last (get hist prev)]
(- turn last)
0)))))(defn f [input n]
(loop [turn (count input)
!hist (transient (zipmap input (range 1 ##Inf)))
prev (peek input)]
(if (= n turn)
prev
(let [prev* (if-let [last (get !hist prev)]
(- turn last)
0)
!hist (assoc! !hist prev turn)]
(recur (inc turn) !hist prev*)))))if anyone wants to have a stab at numerology and series:
p2 answer here is 6428
idx num
65373 0
65374 5
65375 26
65376 275
65377 300
65378 4185
65379 2757
65380 1109
65381 6428
65382 42157
65383 0
71782 0
71783 7
71784 12
71785 45
71786 1111
71787 1927
71788 6428
71789 6407
71790 35727
71791 0
81793 0
81794 4
81795 4
81796 1
81797 19
81798 561
81799 6428
81800 10011
81801 0
137474 0
137475 6
137476 34
137477 6
137478 2
137479 215
137480 331
137481 6428
137482 55682
137483 0
205147 0
205148 7
205149 7
205150 1
205151 31
205152 707
205153 6428
205154 67672
205155 0
236727 0
236728 6
236729 32
236730 200
236731 3313
236732 6428
236733 31579
236734 0I just had an idea of a new format for typing less during the AoC, in case you need:
;; Fast to type
(red [acc acc-init
elm coll]
(conj acc elm))
;; The `red` macro expands to the regular reduce below.
(reduce (fn [acc elm]
(conj acc elm))
acc-init
coll)
Sounds like into 🙂
https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L6902
It's a reduce, don't get misdirected by my simple example.
Ah, I dig it!
What would be syntax for reduce without acc-init ?
(red [acc elm coll] expr)
The idea of red is to follow the chronology of thoughts.
It's like my comp-> macro
I’m hoping your next macro is called blue for the simplest of reasons.
How about green?
I’d totally be on board with that as well 😂
There is a trade off here between readability and how fast it can be typed 🙂 I usually tend to be careful with syntactic sugar. It has to be worth the cost of learning it.
keystroke count aside, I think this format is way easier to read and understand after the fact
I guess the only downside is you would have to wrap it in another function to use in a ->> macro
In this aspect, it's like for vs map
Hey, thanks! I’m still pinching my arm here.
My “efficient” solution to 15-2 is dog slow. Good enough to pass my tests and get mah ⭐ but terrible. About 25 seconds.
I got you beat at 33 seconds. 😉. My original solution was going to take a couple days, I think.. repeatedly (count seq) and (drop last) are horrible. I improved it to terrible, but functional..
@upgradingdave has joined the channel
I just started reading day 15, I wonder if it has to do with http://oeis.org/A181391