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.

❤️ 3
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)))

6
👍 6
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

3
👍 3
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 6
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

3
👍 3
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?

🙂 3
😀 3
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)))))

👍 3
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

👍 3
misha05:12:52

. "Elapsed time: 19815.950142 msecs" d "Elapsed time: 13638.142432 msecs" with transient map

👍 6
misha05:12:32

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

misha06:12:30

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

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

Vincent Cantin14:12:46

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

👍 3
Vincent Cantin14:12:05

It's a reduce, don't get misdirected by my simple example.

timcreasy14:12:00

Ah, I dig it!

nbardiuk15:12:27

What would be syntax for reduce without acc-init ?

Vincent Cantin15:12:57

(red [acc elm coll] expr)

Vincent Cantin15:12:26

That was an easy question. What is the part2? 😉

😆 3
Vincent Cantin15:12:14

The idea of red is to follow the chronology of thoughts.

Vincent Cantin15:12:37

It's like my comp-> macro

Mno15:12:11

I’m hoping your next macro is called blue for the simplest of reasons.

😂 3
Vincent Cantin15:12:35

How about green?

Mno15:12:08

I’d totally be on board with that as well 😂

benoit16:12:56

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.

kenj17:12:54

keystroke count aside, I think this format is way easier to read and understand after the fact

kenj17:12:30

I guess the only downside is you would have to wrap it in another function to use in a ->> macro

3
Vincent Cantin02:12:25

In this aspect, it's like for vs map

markw18:12:55

Congrats @pez on the sponsorship

👍 12
calva 15
pez20:12:42

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

Vincent Cantin10:12:32

congratz

❤️ 3
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 3