Clojurians Log v2

@pesterhazy https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle13.clj#L139-L147 :opieop:

I'm not sure if I had more than 2 carts headed to the same point on the same tick, but I did have a bug when a moving cart collides with a cart that hasn't yet moved on the current tick. (The not-yet-moved cart was not being deleted correctly.)

You might try using group-by and (map count carts-generations) to verify that the cart collection cleanly removes exactly 2 carts instead of 1 or 3 at a time.

> moving cart collides with a cart that hasn't yet moved just fixed that one :opieop:

I just did loop/recur, could not come up with anything readable but not excessively wasteful with seq api

looks reply https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/2018/day13.clj

I think Is pretty readable, and not that long: https://github.com/Average-user/adventofcode-clj-2018/blob/master/src/adventofcode_clj_2018/day13.clj

Day 13: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2018/day_13.cljc

https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/13.clj

day 13 animated https://www.youtube.com/watch?v=hnDNNvy8gww

Nice

My part2 examples for day 14 make no sense

mine make sense, and I can pass them, but I can’t make it work on my puzzle input

Does someone have part1 solved and can send me just the descriptions please??

I’ve done part 1

descriptions of what?

part 1 and 2. The thing is that I probably need your part 1 input to understand the part 2 input because I guess we have different examples

DM

Thanks a lot

This one didn’t feel too hard, except it took me a while to understand part 2 objective

I suspect we have an error.

Could you explain part2? My examples just give me the 5 five digits of each of the 10 digits from part two. That doesn’t seem right

You have to keep generating recipes until the sequence of individual digits from your input appear as scores

🙈 I still don’t get it

It’s not very well described either

If your input is 1982, then you have to keep generating recipes until your sequence of recipes contains a subsequence of [1 9 8 2]

one of my examples is “92510 first appears after 18 recipes.”

there’s no 18 there?!

Yeah the examples don’t make sense to me

I didn’t even bother running them

why five digits?

:man-shrugging:

@meikemertsch what it means is that the sequence ending “92510” has 18 prior recipe numbers

My input was six digits

what would it look like for an input of 2?

is there anything odd about part 2?

The first sequence ending in 2 would be 37101012

so it would appear after 7 recipes

I ran my attempt over the 4 digits sequences in the examples, and it works fine. I run it over my 6 digit puzzle input, and it’s still going.

Your number will be very high

oh!!! Backwards!!!

I think I got it now

I’m still running part2, and I’m debating making more optimization or just waiting

yeah… but it’s a very tight loop, and it’s been going an hour

and will my sequence exhaust the heap?

Thanks for the help!!

perhaps I rewrite it in C 🙂

Thanks for the help. I understand the problem now

subvec really sped it up for me

I’m not sure how far. I’m tempted to look at other peoples number for guidance

21s

Part 2 finishes in a few seconds for me using vectors

hmm - I must be making a serious mistake in something. I’m only getting about 10k iterations/sec

(Thread/sleep 1000)

that’s my debugging sleep so I can inspect the output

ha

🙈

@taylor, are you still here?

Keep in mind you can have up to two digits appended to the end; you can't just check the very end of the vector for the pattern!

yes, I’d remembered that, but my 1am coding made a mistake with it. So while I was checking for more than just the very end, I wasn’t doing it right

and indeed, that was the problem

since my input ended in a 1

Yeah, I did a dumb with that as well, a slipped paren

hm, also for me part2 is taking long. I'm using subvec and I'm also not repeating the lookup in the middle of the vector, but only at the end

I wonder what more I could do

@helios you want to share what you have? I can take a quick look

sure

(ns adventofcode.2018.day14)

(def day-input 846601)
(def day-input-vec [8 4 6 6 0 1])

(set! *unchecked-math* true)

(def initial-state {:workers #{0 1}
                    :table   [3 7]})


(defn iteration [{:keys [workers table]}]
  (let [scores (map (partial nth table)
                    workers)
        recipe-sum (reduce + scores)
        new-recipes (if (< recipe-sum 10) [recipe-sum]
                                          [(quot recipe-sum 10) (rem recipe-sum 10)])
        new-table (reduce conj table new-recipes)]

    {:workers (mapv (fn [index] (mod (+ index (inc (nth table index)))
                                     (count new-table)))
                    workers)
     :table   new-table}))


(defn compute-score-after [n]
  (subvec (->> (iterate iteration initial-state)
               (drop-while #(< (count (:table %))
                               (+ 10 n)))
               first
               :table)
          n (+ n 10))
  )


(defn contains-sequence-at-end? [table sequence]
  (let [c1 (count table)
        c2 (count sequence)]
    (and (>= c1 c2)
         (= sequence (subvec table (- c1 c2)))))
  )


(defn solution2 [input]
  (->> (nth (iterate iteration initial-state) (count input))
       (iterate iteration)
       (drop-while (comp not #(contains-sequence-at-end? (:table %) input)))
       first
       :table
       (drop-last (count input))
       (count)))

@plexus a gist is better maybe: https://gist.github.com/Heliosmaster/4971270311f00f3f8af1ccb7c0d29adf

Looking at it from Visualvm it seems your bottleneck is in iteration. table is always a vector, right? In that case you should avoid nth, as it will treat the vector as a seq and walk it element by element. Use get instead.

You're testing for the pattern at the end, but you're adding not just one, but possibly two digits at the end.

@fellshard right, i should check twice to be sure

because only the first digit might be sufficient

thanks

and also when that happens, I was off-by-1 with the final solution 😄

@plexus Is that right, I thought nth on vector is comparable to an array lookup: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentVector.java#L161

I guess you're right!

it's still spending a lot of its time in those first few lines of iteration, just doing the map+`reduce` to compute the score...

the reduce on the scores should be very fast (it's just two values)

and also map should just operate on two scores

Mine takes 34s w/ subvec 😞 https://github.com/benfle/advent-of-code-2018/blob/master/day14.clj

Is (set! *unchecked-math* true) really necessary?

I’m getting ~10s for part 2 w/vectors, subvec, loop, recur

"Elapsed time: 36315.651048 msecs" not optimized for performance p2 (somewhat readable though)

https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/2018/day14.clj#L53-L72

not relevant, but this could be just def https://github.com/benfle/advent-of-code-2018/blob/master/day14.clj#L14-L17

absolutely 🙂

I got 4.3s in the end (2am) 😳 I had an optimization to only look when one of the last 2 digits matched the final digit of my input, and I messed it up, which is what kept me up late. But when it worked, it was fast

@quoll nice

I wanted to avoid unnecessary subvecs, so I finished my loop with something like this pseudocode:

(if (= last-input-digit last-digit-added)
  (test-the-trailing-subvec recipes input)
  (if (> last-value-added 9) ;; we know that the final input digit is 1
    (test-the-second-last-trailing-subvec recipes input)
    (recur recipes first-elf second-elf)))

I stole your adjust-idx function and it gave me a 10x speed up. Seems like my run cost was dominated by the rem function call to wrap the index back into the correct range. Successive subtraction is far cheaper. Now I get 2-3 seconds for part 2, down from 25-30 seconds.

nice time! adjust-idx probably could be a bit faster with loop in it instead of seqs, but I didn't bother to test it out

https://www.twitch.tv/timpote

I retract everything! I introduced a typo when using adjust-idx that resulted in my algorithm finding the wrong answer, which appeared much earlier in the sequence. So the execution overhead didn't change significantly, I was just running through 1/10th the iterations. I'm back above 20 seconds! :man-facepalming:

:opieop:

That's probably a lot cheaper...

One idea I had, that may be vaporware - you can 'replay' strings you've seen before, up to the point where one of the elves wrapped around to the beginning. Since those substrings have already been seen, the pattern could only show up at the boundary between that memoized string and the current recipe string. This would probably accelerate as you got further down the line... Then again, might be the cost of holding all that in memory / calculating all these strings would be inordinately costly. Managing them would certainly be a pain.

My day 14: https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle14.clj

Proudly unoptimized

very concise 😚👌

Dang I missed it. But I also needed a day off programming. Did today’s part 2 literally at work so I would have the evening free while I was waiting for a build (several times) containing some fixes from one of my devs. This was my last working day today so there was no pressure to start anything new

Nice! Yeah I’ve had to take a few days from AoC myself. Glad to have a little lead time before the stream 🙂

but what does all of it mean? :kappa:

Is it wrong that my first response to being told that my answer is too big is to try (dec answer) ?

And then not fix the bug...

@magic_bloat wrong: probably effective: yes

note to self... if you use (take-last) on day 14, you're gonna have a bad time.