Fork me on GitHub
#adventofcode
<
2017-12-12
>
minikomi06:12:42

That was a neat problem!

grzm06:12:21

Used a core function I hadn't before šŸ™‚

minikomi06:12:02

guessing disj

grzm06:12:19

tree-seq

grzm06:12:47

Soon. I'm cleaning up my cljs port

minikomi06:12:53

haha no problem

minikomi06:12:48

nice, similar to mine but I did it manually šŸ˜›

grzm06:12:29

I'm not too strong at graph work. I took some time to look for something that could do it for me šŸ™‚

spfeiffer06:12:10

Its amazing and terrifying at the same time what clojure core has to offerā€¦

grzm06:12:37

I'm working through the Anki deck to try to keep it at hand.

grzm06:12:49

Like peek and pop in @minikomiā€™s solution: wouldn't use it because they're not something I'm readily aware of.

minikomi06:12:44

oh, guess we can just assume that all programs have an entry

minikomi06:12:55

no need to join in the right hand side

grzm06:12:19

Yeah, that was a double-edged sword, I think. You could end up walking in a circle if you didn't keep track of what you'd already seen.

minikomi06:12:20

I wonder if there's a better idiom for (filter #(not some-set %) items)

grzm06:12:53

(remove some-set items)

minikomi06:12:02

oh yeah lol

grzm06:12:27

Only 22 hours remainingā€¦

borkdude07:12:33

Today was easy (although mine isnā€™t as fast as @grzmā€™s!)

borkdude07:12:06

I may have killed an elve who was sitting on my CPU today.

fellshard08:12:44

There is a useful data structure that makes this almost trivial!

fellshard08:12:37

If you want to dig deeper but don't want full spoilers, I'd recommended reading up on Connected Components in graph theory

fellshard08:12:53

It's not too rough, thankfully šŸ™‚

fellshard09:12:27

Yep, found the exact functions that will answer these questions in seconds flat

borkdude10:12:22

Btw, @fellshard, did you perhaps mean data-prioritymap?

orestis08:12:34

I didnā€™t implement my own graph for this; ubergraph for the rescue. https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day12.clj

orestis08:12:21

I have to implement a hairy layout algorithm for work today; donā€™t have the time to actually implement a graph algorithm!

borkdude08:12:32

@orestis Cool, didnā€™t know about ubergraph. Thanks.

orestis08:12:57

Iā€™ll time my solution, just for laughs.

orestis08:12:28

150-200ms to the answer for part 2, which is then a filter away to give the answer to part 1.

borkdude08:12:53

pretty good

orestis08:12:33

To my shame, I admit I tried various functions of ubergraph.alg until I found something that seemed to a useful result.

minikomi09:12:13

advent.2017.day12> (c/quick-bench (solve2 input-raw))
Evaluation count : 78 in 6 samples of 13 calls.
             Execution time mean : 8.241557 ms

fellshard09:12:18

Guh. The documentation for jgrapht is abysmal.

fellshard09:12:27

No more time to spend on that tonight. Never mind, got it worked out. Pseudograph is sufficient.

fellshard10:12:15

Always highlight the entrance points to your library in big, bold letters. Same issue I had when I was working with Google Dataflow / Apache Beam for a client.

borkdude10:12:25

@fellshard link to your solution?

borkdude11:12:10

@thegeez cool! is it fast?

thegeez11:12:50

fast enough, part 1 224ms, part 2 1.4seconds. both including parsing input, but not slurping input

bhauman12:12:57

@minikomi (filter (complement myset) stuff)

mfikes14:12:01

The definition of remove is essentially (filter (complement pred) coll)

bhauman12:12:52

I find complement set comes in pretty handy, as well

borkdude13:12:23

@bhauman just out of curiosity, how fast is your part 2?

bhauman13:12:03

oh like 800ms

bhauman13:12:23

a tiny optimization

borkdude13:12:46

It seems the input didnā€™t have x -> y z x?

bhauman13:12:03

my input did

bhauman13:12:16

x -> x y z

borkdude13:12:17

ah, it did? hmm I should look into mine then

bhauman13:12:47

it really doesn't need to be there, as it doesn't have a big affect, it only doubles the leaf step

borkdude13:12:00

ah yes, there are many of them, now I printed them, e.g. 1991 (439 1991)

borkdude14:12:45

SPOILER in thread

borkdude14:12:57

@bhauman I didnā€™t know tree-seq could do this, amazing.

borkdude14:12:14

(tree-seq
   (constantly true)
   {0 #{2 3}
    2 #{4 5}
    3 #{6 7}}
   0)
how does it see this as a tree? I donā€™t understand it yet.

minikomi14:12:41

The second function converts a value to children 0 comes in, you get children 2 and 3 2 and 3 come in, they give 4 and 5; and 6 and 7 respectively.

borkdude14:12:45

ah, so the second arg is also a function, letā€™s see

borkdude14:12:19

so normally you pass in a tree, but now only the number 0 is used as the ā€œrootā€ of the tree. then children are looked up in this ā€œtreeā€ by (children 0) which is then the tree which is walked. This is brilliant.

bhauman14:12:38

sorry, was making breakfast but yeah tree-seq is powerful

borkdude14:12:26

yeah. we are relying on the fact here that branch? can be side-effecting (to do the atom bookkeeping), but itā€™s probably a safe assumption

borkdude14:12:31

tree-seq really a short/simple function

grzm14:12:07

@borkdude the quick-bench for part-2 was wrong. copy-paste error late at night. I get 25-29ms for part-2.

borkdude14:12:05

My mind is blown by @bhaumanā€™s solution. šŸ’”

mfikes14:12:31

@grzm Nice solution! Only suggestion I'd make is to use a volatile instead of atom in prog-group.

grzm14:12:22

Thanks! And thanks for the pointer.

grzm14:12:18

@bhauman I like how you pulled seen into the tree-seq branch? function

grzm14:12:58

@mfikes Doesn't seem to do much in terms of performance, at least for this problem.

grzm14:12:40

Would there be another reason to prefer volatile over atom?

bhauman14:12:35

I used a volatile for a second but then thought that there is no reason that tree-seq couldn't be run in parallel and so preferred atom

grzm14:12:47

Maybe next year I'll focus on reducers/fork instead of transducers šŸ™‚

grzm14:12:57

Just to learn/reinforce another area of the library. To be able to choose the right tool for the job I at least need to know what tools are out there. Right now I've got big holes in my knowledge of the core library.

grzm14:12:31

Are these times right? Are people really solving this in less than 3 minutes? http://adventofcode.com/2017/leaderboard/day/12

mfikes15:12:18

@grzm Nah, volatile is only better than atom for perf reasons. So it may become an idiom to use volatiles for local function state and atoms for defs. (Essentially a thing where you don't think about it.)

grzm15:12:40

That makes sense.

mfikes15:12:03

For those curious, the algorithm I'm using comes in at 10.6 ms for part 1 and 11.4 ms for part 2 if you exclude the I/O and parsing (and apply the algorithm to parsed data)

mfikes15:12:27

(It is easy to convert that algorithm from a functional one to an imperative one that bashes on a mutable array and I think that works much more quickly.)

mfikes15:12:44

I didn't invent the algorithm. It is a popular one from 1964.

borkdude15:12:24

@fellshard Is jgrapht any faster than the others?

fellshard15:12:34

I haven't benched anything yet šŸ˜…

fellshard15:12:30

I'd expect union-find to be fastest, if only by dint of skipping the graph entirely. Union-find has inverse-Ackermann amortized performance.

fellshard15:12:45

AKA 'effectively constant'

mfikes15:12:00

If you do a mutable union-find, part 1 comes in at 539 Āµs for me and part 2 at 1.12 ms.

mfikes15:12:21

Here is the code that I benchmarked to produce those numbers: https://gist.github.com/mfikes/fc2e94db229b53d68f243cd7b8c253b5

mfikes16:12:09

As above, this excludes the I/O and parsing

fellshard16:12:19

Yeah, that's one thing I noted - the union-find library I picked up has no capacity to leverage the bind-to-root optimization you'd normally use. So I suppose that makes its perf more like log(n).

mfikes16:12:04

Union-find seems like a good example of an imperative algorithm from the 60s-70s which is difficult to efficiently express in a functional way.

mfikes16:12:39

(I haven't found a way to write it in "normal" Clojure that runs as fast as bashing on arrays.)

fellshard16:12:10

You could always pass the tree back with every operation. Perhaps hiding it behind an atom would allow you to make modifications that are 'effectively immutable'?

fellshard16:12:53

Trust the contract to hold properties, I guess, with a dash of testing for certainty

mfikes16:12:23

@fellshard I am passing the tree back. Perhaps it is the case that I have a functional version that has the same computational complexity and Iā€™m just seeing a constant overhead associated with working with persistent data structures. Iā€™m going to scrutinize it a bit more. Here it is for reference https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_12.cljc#L19-L37

mfikes16:12:13

Iā€™m going to see if that can be written with transients instead.

mfikes18:12:45

Well, the good news is that it is possible to get part from 10.6 ms down to 1.35 ms by using transients, which compares well to the imperative version that runs in 539 Āµs. https://gist.github.com/mfikes/c4cf04d10bbfc8c2862fe15a58642501

grzm18:12:22

crikey, @mfikes. (Or should I say fikey?) That's impressive.

borkdude19:12:44

@mfikes what is the name of the 1964 algorithm?

borkdude19:12:22

cool, thanks. you learn a lot from these nerd snipes šŸ™‚