Fork me on GitHub
#adventofcode
<
2017-12-13
>
minikomi02:12:53

Nice.. I went from 10ms to 3ms using (and working around) a transient set in the hot loop

mikelis.vindavs05:12:33

I wonder if there’s a nice O(n) solution to part2

grzm06:12:49

I suspect there is. I think I need to sleep before I finish part 2 😕

minikomi07:12:56

yeah there's a better way to do this I think.. it's taking a loooong time otherwise

minikomi08:12:16

ooh, came up with a relatively quick answer using not-any? and some

minikomi08:12:29

I bet there's a way you can just generate the answer using LCD's

fellshard08:12:27

I was thinking the same thing, except I'm not sure that gets you the right answer still

fellshard08:12:29

It could certainly help you find one point in time at which all the scanners would be at zero at the time your packet arrives, but I'm not sure that would be useful information, nor would it be guaranteed to be the minimum possible result

orestis08:12:04

OK, this is the first time in AoC 2017 that my fans are spin-spin-spinning and I get no response from second part.

orestis08:12:48

Time to do the simplest optimizations.

orestis08:12:45

I’m sure there’s an algebraic way to solve this with no code whatsoever…

orestis08:12:33

Using cycle was probably not a good idea 🙂

orestis09:12:07

“Elapsed time: 536598.496201 msecs”

minikomi10:12:24

Execution time mean : 1.755792 sec

orestis10:12:10

I dropped it to 8500msec and I need to get to real work 🙂

orestis10:12:00

…but I do have to look at @minikomi’s code first 🙂

orestis10:12:58

@minikomi I think we arrived at the same logic but your version is a bit more “unrolled” than mine.

minikomi10:12:20

yeah, not-any? was the key thing i did to speed it up

orestis10:12:28

What’s your answer? Mine is close to 4 million…

minikomi10:12:43

As soon as there's a zero-case. you can go onto the next one.

orestis10:12:11

I think that some should be equivalent in terms of performance with not-any? though.

mfikes14:12:00

I wonder if there is an efficient solution to part 2 using some variation of the Chinese remainder theorem.

bhauman15:12:59

6673ms for part 2

bhauman15:12:08

@mfikes very nice solution for day13!

mfikes15:12:50

Thanks! It luckily seems to perform well (around 800 ms for my data)

bhauman15:12:39

@mfikes yeah you really don't have any intermediate data structures

bhauman15:12:59

except for the last call to some

mfikes15:12:33

Interesting. I didn't even think about that aspect. I just wrote it for readability / concision.

bhauman15:12:07

our solutions are similar, you moved the logic a step deeper which eliminated the need to pass data around

bhauman15:12:44

oh and I'm wasting cycles iterating through the count of the structure

grzm17:12:06

\mutters read the instructions. read the instructions. read the instructions

mfikes17:12:16

Don’t get caught ignoring the instructions.

grzm17:12:14

Well played, sir. Well played.

grzm18:12:42

Well, down from 21 seconds to 900ms for part 2. Now to see what solutions you guys came up with.

orestis19:12:59

Where does some-fn come from?

orestis19:12:38

Oh dear, it’s a core function…

orestis19:12:02

I got thrown by the home-fn naming 🙂

grzm18:12:04

@mfikes is there a way you're preventing the github banner thing from displaying when you paste a link? That's really nice and tidy.

grzm18:12:09

Wow, that's a nice, concise solution.

borkdude20:12:19

ok, finally done…

borkdude20:12:36

2s for part 2

mfikes20:12:12

@grzm After pasting a link, you’ll see a little delete button next to the GitHub banner.

grzm20:12:53

@mfikes cheers.

grzm20:12:55

@borkdude did your util/find-first function miss the commit?

mfikes20:12:13

(I didn’t see it in there either FWIW.)

grzm20:12:42

I like reading what others find useful to abstract away.

borkdude20:12:28

@mfikes Sorry, fixed. See comment at the bottom why I used it.

borkdude21:12:49

No idea why some was slower for me than that custom function

borkdude21:12:17

(defn find-first
  [pred vals]
  (reduce
   (fn [_ v]
     (when (pred v)
       (reduced v)))
   nil
   vals))
(time (some       identity (repeat 10000000 nil))) ;; 250 ms
(time (find-first identity (repeat 10000000 nil))) ;; 40 ms

borkdude21:12:36

(time (some #(when (> ^long % 10000000) %) (range))) ;; 558 ms
(time (find-first #(> ^long % 10000000)    (range))) ;; 95 ms

bhauman21:12:59

calls seq on every iteration

bhauman21:12:10

calls (when (seq coll)) on every iteration to detect the end of the sequence

borkdude21:12:12

I guess one more reason reduce is faster because many collections know how to reduce themselves

borkdude21:12:41

but would there be a reason not to rewrite some using reduce so it’s faster?

chad21:12:44

Hello! Im using Advent of Code as a way of learning Clojure and have just created a repo of what I have so far. Thought id post it incase anyone was interested 😃 https://github.com/sandemchad/clj-advent-of-code-2017

chad22:12:27

Awesome will do 🙂

borkdude21:12:07

@mfikes holy crap, I just saw yours and it’s so concise

bhauman21:12:14

@borkdude I changed my some implementation to reduce and nothing changed

mfikes21:12:25

@chad Nice solutions, especially given you are learning

chad22:12:38

Thank you 🙂 I am really enjoying using Clojure solving these problems have been a really good way of learning.

borkdude21:12:44

@bhauman what if you execute above snippet? same timing?

mfikes22:12:21

@borkdude Honestly, I think I just got lucky. I wrote what seemed straightforward, and by luck of the dice, it was short and fast. Doesn’t happen all the time. 🙂

bhauman22:12:35

@borkdude I get similar results and it makes sense now that I look at your example

bhauman22:12:42

more closely