Fork me on GitHub
#adventofcode
<
2018-12-14
>
Ben Grabow00:12:51

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

Ben Grabow00:12:52

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.

misha01:12:25

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

misha01:12:02

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

meikemertsch06:12:11

My part2 examples for day 14 make no sense

quoll06:12:45

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

meikemertsch06:12:03

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

quoll06:12:32

I’ve done part 1

quoll06:12:51

descriptions of what?

meikemertsch06:12:53

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

taylor06:12:08

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

meikemertsch06:12:09

I suspect we have an error.

meikemertsch06:12:42

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

taylor06:12:37

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

meikemertsch06:12:35

🙈 I still don’t get it

taylor06:12:57

It’s not very well described either

taylor06:12:24

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]

meikemertsch06:12:19

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

meikemertsch06:12:25

there’s no 18 there?!

taylor06:12:40

Yeah the examples don’t make sense to me

taylor06:12:54

I didn’t even bother running them

meikemertsch06:12:37

why five digits?

taylor06:12:55

:man-shrugging:

norman06:12:15

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

taylor06:12:22

My input was six digits

meikemertsch06:12:56

what would it look like for an input of 2?

norman06:12:34

The first sequence ending in 2 would be 37101012

norman06:12:47

so it would appear after 7 recipes

meikemertsch06:12:49

oh!!! Backwards!!!

meikemertsch06:12:57

I think I got it now

meikemertsch06:12:05

Thanks for the help!!

quoll06:12:01

is there anything odd about part 2?

quoll06:12:14

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.

norman06:12:33

Your number will be very high

norman06:12:16

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

quoll06:12:26

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

quoll06:12:50

and will my sequence exhaust the heap?

quoll06:12:18

perhaps I rewrite it in C 🙂

baritonehands06:12:19

subvec really sped it up for me

norman06:12:24

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

taylor06:12:58

Part 2 finishes in a few seconds for me using vectors

norman06:12:48

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

norman06:12:52

(Thread/sleep 1000)

norman06:12:09

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

quoll06:12:56

@U3DAE8HMG, are you still here?

fellshard06:12:49

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!

quoll07:12:38

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

quoll07:12:48

and indeed, that was the problem

quoll07:12:00

since my input ended in a 1

fellshard07:12:19

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

meikemertsch06:12:40

Thanks for the help. I understand the problem now

helios09:12:23

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

helios09:12:32

I wonder what more I could do

plexus09:12:34

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

helios09:12:17

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

plexus09:12:30

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.

fellshard09:12:50

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

helios09:12:16

@U1YPTG4UF right, i should check twice to be sure

helios09:12:25

because only the first digit might be sufficient

helios09:12:12

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

borkdude09:12:12

@U07FP7QJ0 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

☝️ 4
plexus09:12:37

I guess you're right!

plexus09:12:39

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

helios12:12:18

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

helios12:12:36

and also map should just operate on two scores

Average-user13:12:38

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

benoit14:12:01

absolutely 🙂

opieop 4
taylor13:12:48

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

misha14:12:17

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

Ben Grabow17:12:19

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.

misha17:12:41

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

Ben Grabow18:12:22

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:

quoll16:12:38

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

quoll17:12:35

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

fellshard19:12:31

That's probably a lot cheaper...

meikemertsch19:12:43

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

potetm19:12:48

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

fellshard19:12:23

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.

pesterhazy19:12:19

Proudly unoptimized

taylor19:12:03

very concise 😚👌

misha20:12:15

but what does all of it mean? kappa

magic_bloat21:12:22

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

magic_bloat21:12:33

And then not fix the bug...

markw21:12:42

@magic_bloat wrong: probably effective: yes

😁 4
markw21:12:58

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

d 4
☝️ 4