Fork me on GitHub
#adventofcode
<
2020-12-15
>
Vincent Cantin03:12:05

I may drop from the contest today - life became busy and the AoC is very time consuming when you do it seriously.

❤️ 1
nbardiuk10:12:23

Don't take it seriously 🙂 Maybe some puzzle will grab your attention

Vincent Cantin10:12:57

I will take a look at the problem and try to solve it right before sleeping, maybe.

pez12:12:31

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.

fingertoe18:12:53

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

Vincent Cantin05:12:05

Day 15 answers thread - Post your answers here

solf05:12:01

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

2
👍 2
erwinrooijakkers05:12:46

Keeping all the indexes is probably bit slower

erwinrooijakkers05:12:08

Maybe cleanup after work 🙂

rjray06:12:59

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

1
👍 1
genmeblog11:12:04

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

genmeblog11:12:15

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

alekszelark13:12:33

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

bananadance 2
nbardiuk13:12:34

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

1
👍 1
genmeblog13:12:35

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.

genmeblog13:12:05

Capacity= 16777216
"Elapsed time: 3863.6976 msecs"

misha14:12:21

what's next? implementing in rust?

🙂 1
😀 1
genmeblog14:12:58

Oh come on! It's done in Clojure.

misha14:12:29

same "transient" 13sec with unchecked inc and typehints.

misha14:12:25

it is still in clojure, but is it 1) readable? 2) worth it? it is a good illustration where the time is spent though

genmeblog14:12:35

ad1 - no, ad2 - yes! I learned something about data structures.

benoit16:12:40

Thankfully not too long today (for the human, not the machine): https://github.com/benfle/advent-of-code-2020/blob/main/day15.clj

Ben List16:12:30

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

benoit16:12:40

Yes, arrays are good for mapping on integers 🙂 I don't have the time to improve the performances unfortunately.

pez21:12:04

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

pez22:12:57

I get 12 seconds with a transient map and 5 seconds using a java HashMap.

pez22:12:04

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

👍 1
Joe23:12:35

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

👍 1
misha06:12:02

if anyone wants to have a stab at numerology and series:

misha06:12:56

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 0

markw18:12:55

Congrats @pez on the sponsorship

👍 4
calva 5
pez20:12:42

Hey, thanks! I’m still pinching my arm here.

Vincent Cantin10:12:32

congratz

❤️ 1
R.A. Porter18:12:37

My “efficient” solution to 15-2 is dog slow. Good enough to pass my tests and get mah but terrible. About 25 seconds.

fingertoe03:12:23

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

Average-user18:12:51

I just started reading day 15, I wonder if it has to do with http://oeis.org/A181391

alekszelark19:12:35

Yes, it is, someone said about it today.

parrot 1