Clojurians Log v2

That was a neat problem!

Used a core function I hadn't before 🙂

which one?

guessing disj

tree-seq

ooh nice

link?

Soon. I'm cleaning up my cljs port

haha no problem

https://github.com/grzm/advent-of-cljc/blob/master/src/main/com/grzm/advent_of_code/advent_2017/day_12.cljc#L22-L29

nice, similar to mine but I did it manually 😛

https://github.com/minikomi/advent-of-code/blob/master/src/advent/2017/day12.clj#L27-L34

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

Its amazing and terrifying at the same time what clojure core has to offer…

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

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

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

no need to join in the right hand side

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.

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

(remove some-set items)

oh yeah lol

Only 22 hours remaining…

Today was easy (although mine isn’t as fast as @grzm’s!)

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

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

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

It's not too rough, thankfully 🙂

http://jgrapht.org/ 😉

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

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

@orestis Cool, didn’t know about ubergraph. Thanks.

I’ll time my solution, just for laughs.

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

pretty good

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

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

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

https://github.com/sciyoshi/advent-of-rust-2017/blob/master/src/day12/mod.rs wow, rust has funky tools to use

Guh. The documentation for jgrapht is abysmal.

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

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.

@fellshard link to your solution?

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

Day 12 with Datascript: https://github.com/thegeez/clj-advent-of-code-2017/blob/master/src/advent/day12.clj

@thegeez cool! is it fast?

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

https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day12.clj

@minikomi (filter (complement myset) stuff)

I find complement set comes in pretty handy, as well

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

oh like 800ms

and why did you need disj here? https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day12.clj#L16

a tiny optimization

It seems the input didn’t have x -> y z x?

my input did

x -> x

x -> x y z

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

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

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

SPOILER in thread

@bhauman I didn’t know tree-seq could do this, amazing.

(tree-seq
   (constantly true)
   {0 #{2 3}
    2 #{4 5}
    3 #{6 7}}
   0)

My day 12: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_12.cljc

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.

ah, so the second arg is also a function, let’s see

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

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.

very nice

My mind is blown by @bhauman’s solution. 💡

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

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

Thanks! And thanks for the pointer.

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

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

Would there be another reason to prefer volatile over atom?

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

I wonder if @fellshard was referring to this one https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Maybe next year I'll focus on reducers/fork instead of transducers 🙂

@grzm why?

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.

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

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

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

tree-seq really a short/simple function

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

That makes sense.

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)

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

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

https://github.com/armstnp/advent-of-code-2017/blob/master/src/advent_of_code_2017/day-12.clj https://github.com/armstnp/advent-of-code-2017/blob/master/src/advent_of_code_2017/day-12-union-find.clj https://github.com/armstnp/advent-of-code-2017/blob/master/src/advent_of_code_2017/day-12-jgrapht.clj

@fellshard Is jgrapht any faster than the others?

I haven't benched anything yet 😅

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

AKA 'effectively constant'

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

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

As above, this excludes the I/O and parsing

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

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.

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

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'?

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

@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

I’m going to see if that can be written with transients instead.

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

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

https://xkcd.com/356/

@mfikes what is the name of the 1964 algorithm?

I call it union-find, but it has other names https://en.wikipedia.org/wiki/Disjoint-set_data_structure

cool, thanks. you learn a lot from these nerd snipes 🙂