Clojurians Log v2

I disagree

yes, it’s terse. It’s not much nicer than a top level defn (or def)

I did this for day 3:

(map (comp #(Integer/parseInt %)
            (memfn trim)))

I did this for the padded numbers:

(defn to-int [s]
  (Integer/parseInt
    (if (= (.charAt s 0) "0")
      (.substring s 1)
      s)))

surprised that my char to string comparison worked

Is (reduce + ... any faster?

Looks like yes

user=> (time (apply + (repeat 10000000 1)))
"Elapsed time: 526.222753 msecs"
10000000
user=> (time (apply + (repeat 10000000 1)))
"Elapsed time: 656.773543 msecs"
10000000
user=> (time (reduce + (repeat 10000000 1)))
"Elapsed time: 178.887459 msecs"
10000000
user=> (time (reduce + (repeat 10000000 1)))
"Elapsed time: 47.995412 msecs"
10000000
user=> (time (reduce + (repeat 10000000 1)))
"Elapsed time: 39.555085 msecs"
10000000

(= \0 "0") ;=> false So, your function is equivalent to (Integer/parseInt s)

good to know

(Integer/parseInt "09")
=> 9

accidentally on purpose

Anyone getting subsecond timings on part 1?

I’m basically bashing on a StringBuilder in a loop/recur and coming up w/ ~4 sec.

seriously no idea how I could speed that up

but I hear of others in the ms range

Not having state is making these puzzles really difficult for me. 😅

You should join the twitch stream! That’s part of why I’m doing it!

alas, I’ve devolved into a PLOP animal to get sweet speed

Are the videos saved?

yep!

https://www.twitch.tv/timpote/videos

I couldn't get speed this time at all: https://gitlab.com/randall.mason/advent-of-code/blob/master/src/advent_of_code_2018/day05.clj Ended up with 845 seconds for all tests on my Pixel Slate.

that’s some cond 🙂

lol, yes!

ah atom bashing as well I see

Yeah, that shouldn't be needed, but I get a smaller answer without it.

yeah I didn’t know what else to do for this one besides bash some memory around

I'll refine it on the train tomorrow.

wow i went through a lot of pain there, i had a newline at the end and I was off by 1 for #5 🤦 that said, I switched from a functional approach to using an ArrayList to make removal easier, and was able to run the algorithm in < 1s on my mac https://github.com/rymndhng/advent-of-clojure/blob/master/src/advent_2018/05.clj

Elapsed time: 32991.632126 msecs -- https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle05.clj#L43

Not the fastest 🙂

Make it work, make it right, make it fast, right? Except I won't make it right or fast because it's just a kata...

totally haha, it's pretty cool to see the different approaches folks went for

Honestly the main source of ugliness in my solution is the lack of cond-let in clojure.core

I went for a pure function, which is never going to be super fast for this type of problem

i agree with you for the pure functional part -- I ended up going with an arraylist because removing elements by index via subvec + concat is too cumbersome

I ended up setting them to nil and skipping over nils when considering neighbors

this is my day5 🙂 https://github.com/Heliosmaster/advent-of-code-2018/blob/master/src/adventofcode/2018/day5.clj

it's not super fast but i'm happy i got to use partition-all 😛

My day5: "Elapsed time: 7839.507737 msecs" https://github.com/genmeblog/advent-of-code-2018/blob/master/src/advent_of_code_2018/day05.clj

guys, have you maybe got a regexp that I could check against my results?

something’s wrong in that I’ve got too many characters, but I can’t tell what. superficial examples seem fine.

fwiw (since my result is incorrect) locally my solution works in ~100 msec

Two string builders acting as stacks. “Right” initialised to original string, “left” empty. Action consists of examining heads of stacks and then: - if reducible, remove both - if non-reducible, move char from “right” to “left” Repeat until “right” is empty.

I really enjoyed reading @mfikes solution for day4. A few things that stuck out: - the concision of naming a map in the domain space: guard-id->minutes - learned a new trick: destructuring in a let block when extracting the key and value of interest - how much this approach reads like a proof

Also check out the reduce, reduced, reductions for part 2 of day 1 of @bhauman https://github.com/bhauman/advent-of-clojure/blob/master/src/advent-2018/day01.clj#L18

trim :woman-facepalming:

…so yeah, I forgot to trim the input 🙂 now it works.

(it’d probably be even more performant if I was operating at the last element of the “left” sb)

I finally got mine working.

One string builder - 40ms.

My solution for Day 5 https://github.com/athos/advent-of-code-2018/blob/master/src/advent_of_code_2018/day05.clj

So I did eventually find a way to get part 1 down to ~40ms.

The combination of sorted-map and subseq works very nicely 😃

took a few minutes tho

Clojure:

Testing aoc.y2018.d05.borkdude
part-2 took 5546.88 msecs
part-1 took 160.69 msecs

Testing aoc.y2018.d05.borkdude
part-1 took 107.00 msecs
part-2 took 1896.00 msecs

funny enough, Node is faster than the JVM here…

deleting from the middle is efficient?

my code: https://github.com/borkdude/advent-of-cljc/tree/master/src/aoc/y2018/d05

@athos really fast solution... nice

@athos where can we see the time for your solution?

StringBuilder is mutable, so it mostly doesn’t matter.

til: subseq

On my MBP:

user=> (time (day05/solve1 (slurp (io/resource "input05.txt"))))
"Elapsed time: 414.086682 msecs"
9238
user=> (time (day05/solve2 (slurp (io/resource "input05.txt"))))
"Elapsed time: 1936.757214 msecs"
4052

cool.

oh you’re using pmap. no can do in cljs

…right, well, it matters how the memory is actually allocated

with pmap I get on clj:

Testing aoc.y2018.d05.borkdude
part-2 took 2900.71 msecs
part-1 took 160.96 msecs

👍

but it sounds like it works just fine 😄 thanks!

Hmm, I see one of my tests get killed now regularly on CircleCI:

Testing aoc.y2018.d04.dfuenzalida
part-2 took 2706.55 msecs
Killed

could be a memory issue.

Advent of code 2018, day05
Part 1 "Elapsed time: 107.586455 msecs"
Part 2 "Elapsed time: 2453.459493 msecs"

https://git.sr.ht/%7Eihabunek/aoc2018/tree/master/clojure/src/aoc2018/day05.clj

now to look what everyone else did, cause I'm certain this can be faster

i'm half tempted to solve it using a transient vector but not sure i want to

@ihabunek cool, our solutions are almost identical

yeah, just wanted to comment 🙂

pop and peek would make mine less verbose

i first did mine in elixir, and used regex search&replace, but it took 6 minutes for part 2 ^^;

My solution for Day5. https://github.com/benfle/advent-of-code-2018/blob/master/day5.clj

weird... i just tried to optimize by converting the input to list of ints instead of chars which I had my logic was that i wouldn't have to convert to int when checking if two chars react but it takes 4 times as long ...

17ms for part 1 and 350 ms for part 2.

nice!

I think the key to a fast functional solution is to build the reduced polymer in reverse to make the backtracking faster.

ah, right

will try it out

what the devil is subseq?

Clojure's API surface is positively huge

clojure.core/subseq
([sc test key] [sc start-test start-key end-test end-key])
  sc must be a sorted collection, test(s) one of <, <=, > or
  >=. Returns a seq of those entries with keys ek for
  which (test (.. sc comparator (compare ek key)) 0) is true

I used it to find the greatest key that is less than a certain key in a sorted map.

I took @me1740 idea and got 220ms for both using pmap

Hmm. 17ms/350ms is quite fast. My naive solution was way too slow, (I left it running over night, but it probably ended up finishing after an hour or so). I optimized while it was running and got it down to 500ms/20s. But, I guess I still missed something to get those kinds of speeds

without pmap I have around 450ms

https://www.youtube.com/watch?v=9OfLNCWM_yA day 4 visualized

right, if they’re having to shift mem around

So it’s back by System.arrayCopy — so towards the start of the string it’s having to do a fair number of (native) copy operations

@me1740 wtf is this black magic???

divide and conquer + being more careful about data structure when the first approach was too slow

So… @lady3janepl you should look at @me1740’s solution! More in line with what you were saying.

I feel like I just got completely schooled.

Me, a simpleton: “Linked lists aren’t fast.” @me1740: “Hold my beer.”

So you can get similar performance w/o having to reverse if you use a vector as your “reduced queue.”

Yes but I would have had to make sure all my internal operations return a vec 🙂

But it's probably better all vec, yes.

nah, pretty much the same

perhaps even faster as a linked list because there’s never a re-allocation

(guessing)

You can pretty much change that reduced queue at will tho. It’s a local and only uses conj.

criterium says that of [] PersistentQueue/EMPTY and '() — '() is between 30-40% faster

fun stuff

Thanks @me1740! A valuable lesson was taught today.

But conj doesn't behave the same for all those types.

right, so it’s a matter of whether you reverse at the end or not

ok

iiuc

@me1740 Are you timing it multiple times?

I think if you switch from list to vec, you will have a few things to change in the code to make sure all the internal ops return vecs for example.

I ran criterium on it: getting an avg of 9ms on my sample in 66 calls

Just in case anyone else has this issue, there is an extra space (or possibly return char) at the end of their input file. All my tests were working but I was getting the wrong answer and starting to get a bit frustrated before I checked that!

@me1740 ah I did one more thing!

Guess I should've verified my input!

@mroerni No as soon as I get the result in a "reasonable" amount of time, I'm done.

I changed rest and first to pop and peek respectively

so everything returns the same data structure

I am getting 6ms/400ms, but only on later runs (https://github.com/MrOerni/advent-of-code-2018/blob/master/src/advent_of_code_2018/day05.clj)

(just on operations on the reduced variable`)

@mroerni ah so, perhaps because you just return the count instead of allocating a new string?

@potetm good to know

lemme try

nope

it’s just faster

holy moly @mroerni

the quick-bench of yours is 3ms

Using pmap for task 2, halved the time. (on a 2/4 Core machine)

very clever btw

pre-emptive conj on tail, then compare and drop — ensures a single pass across the input

no backtracking

Thank you. 🙂

@me1740 and @mroerni I will be mentioning both of you on Friday’s stream. I’ll probably code Björn’s implementation actually.

:thumbsup:

slightly offtopic, but this solution in elixir is delightful: https://gist.github.com/sasa1977/d70f0986bf72bb94048d37843d11b4a4#file-day5-exs-L21-L28

pure recursion, no "stepping back", under 1 s including VM startup

I’m surprised that Elixir solution doesn’t blow the stack

I must not understand it. It looks like it recurs to the end of the string and unrolls.

found a pythonista that did a reduction version of Björn’s algo

maybe it just has a large stack!

tried doing the same in clojure, but blew the stack

so yeah, large stack i guess

Tail recursion never blows the stack. Did you try to call the function, or did you recur?

I don't think this could be TCO

each stack relies on the result of the next

iiuc

https://happi.github.io/theBeamBook/#_working_memory_a_stack_machine_it_is_not

perhaps why^?

https://i.imgflip.com/2o8hh1.jpg

i'm solving day 5 and it's super slow at the moment (part 1 takes ~30 seconds) + it causes a stack overflow error, even though i'm not sure where i even build up such a large stack. if anybody wants to take a look at it I'd appreciate that https://github.com/heyarne/advent-of-code-2018/blob/86360a4/src/day_5.clj

@arne-clojurians SO can be caused by concat in your case.

yeah, b/c when you recursively construct sequences with concat, it keeps building up unrealized "thunks" of the lazy sequences. It's definitely not something that looks obviously problematic

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

Hah. Seeing all the great timings for this one in the backlog. I may revisit my solution (it is dog slow).

my first solution used trampoline and part 1 took ~9s...

@mfikes The fixed-point thingy is nice. And I found your solution the most readable so far 🙂

But it means you do multiple pass I believe.

Thanks. I'm sitting here pondering the fundamental algorithm, trying to avoid gleaning anything from the above. But yeah, I'm zeroing in on the concept that I'm making way too many multiple passes, without even any ability to backtrack a little.

Ok I shut up 🙂

Mostly, I want to get it to be fast enough to contribute to Advent of CLJC. (Otherwise, it could suck up 5 minutes of CI time.)

My Day 3: https://github.com/potetm/advent-of-code/blob/master/src/advent_2018/day_3.clj

Posting cause I’m not sure I saw anyone w/ that particular approach.

I'm much happier with my 2nd version of day 5, but it is still very slow and still has a bunch of cond: https://gitlab.com/randall.mason/advent-of-code/blob/master/src/advent_of_code_2018/day05.clj

@mfikes my solution ended up very slow as well (33s for part II) - I wouldn't have predicted it

Testing aoc.y2018.d05.bgrabow
part-1 took 33.00 msecs
part-2 took 359.00 msecs

Testing aoc.y2018.d05.borkdude
part-1 took 60.00 msecs
part-2 took 3392.00 msecs

Testing aoc.y2018.d05.mfikes
part-1 took 3505.00 msecs
part-2 took 75629.00 msecs

(on node)

I haven’t looked at bgrabow’s solution yet, but it’s killing all other solutions 😉

on JVM:

Testing aoc.y2018.d05.bgrabow
part-2 took 110.05 msecs
part-1 took 12.13 msecs

Testing aoc.y2018.d05.borkdude
part-2 took 4697.16 msecs
part-1 took 166.39 msecs

Testing aoc.y2018.d05.mfikes
part-2 took 24970.50 msecs
part-1 took 1035.49 msecs

What are the specs on the machine that runs that?

@borkdude Wait, I'm making it faster! Borrowing heavily from the discussion above though.

faster than now? 🙂 wow

@clashthebunny you can click the CircleCI icon on https://github.com/borkdude/advent-of-cljc

It just says 4GB of ram and two vCPU.

that’s all I know

I'm trying to introduce parallelism to part 1, but nothing I'm trying is faster than the single-threaded approach. I'm guessing it's because there are some reducible polymer chains that are very long, so they stretch beyond the boundaries of a parallel chunk.

So there is quite a bit of work to do in joining the chunks, which must be done serially.

@mfikes So I’m learning clojure by reading the advent of code stuff. Had a question about the “:log” in your day 4. also why {:log []} What does that do?

if there is a place you can point me to, that would be great.

There's an accumulator in there which essentially holds several things. When it is running the accumulator will have something like:

{:log [{:guard-id 1 :start 5 :end 12} {:guard-id 7 :start 7 :end 13}]
 :guard-id 3
 :start 12}

So there's a vector under the :log key that grows

got it, so the first (:log kicks off the key.

the {:log [] } is the arg to the reducer. Thanks a bunch

Yep, it just sets it up with a vector in there

Thanks back to work on day5.

I'd considered fork-join for this, but yeah, that'd only be suitable if there's a lot of local adjacent pairs throughout the entire polymer.

I have part 1 around 8ms but part 2 is still up in the 500's....Have some ideas to improve that but not sure if i'll get around to it today.

@adammiller always welcome to make a PR with improvements, even next year

looks like on the latest test it ran part 1 in 7.53ms.... Should definitely be able to improve part 2 since i use part 1 in that.

Hammock time led me to the kernel of single pass idea. That took me a while to see. Presumably others in the backlog are using similar approach. (Will read solns.) https://github.com/mfikes/advent-of-code/blob/master/src/advent_2018/day_05.cljc

interesting that mine was significantly slower than @borkdude and @ben.grabow on the cljs side though

that looks pretty similar to what I had done on part 1 @mfikes

Cool. My part 2 is naive reapplication of part 1.

so is mine

@mfikes clean solution!

https://github.com/akmiller78/AdventOfCode2018/blob/master/src/advent/five.clj

also, used this example to play with the bit- fns

@ben.grabow If you end up optimizing for ClojureScript, == is much faster than = for numerics. (It could help numeric-anti-pair? perf.)

I wonder if Clojure is also faster if using == on numerics... Hrm.

i'm not seeing any speedups if i change my solution to use ==

~120ms for part 1 on my laptop

Thanks @mfikes. I see about 30% speed up across the board with == but who knows how reliable that is across iterations.

Nice trick Ben employed, pre-purging for part 2; makes sense 🙂

The reason == is so much faster in ClojureScript is that it is essentially a macro, letting things compile straight down to direct numeric comparisons in JavaScript.

Oh wow, you're right, you can leapfrog from part 1's solution into part 2

Love the use of reduce in react/`add-unit`.

made pretty big difference in my cljs times....didn't affect my clj times much.

Now I'm hyped to head home and tinker more, that's the biggest macro-level optimization I can think of for what I've got right now

Wow, that pre-purging trick leads to a speedup of 5.6 if applied to my naive aproach. 🙂

i'll be stealing that as well 😄

yes, going to modify mine for that later this evening

I'm sure you could map that onto category theory somehow...

Hah. Yeah, a proof that that is a legitimate optimization is right at the edge of where my mind is.

collapse . filter-unit = collapse . filter-unit . collapse ...

A. collapse is already fixed-point B. filter-unit is structure-preserving, to the extent that you can run it at any point in the process without changing the end result

But I don't have anywhere near the terminology to express what that actually means XD

The single pass idea also could really use a proof. It felt a little sketchy, but I was convinced.

Is that doing a sort of combinatoric split each time you ingest a letter, one with the letter in-place, and the other with it removed?

Starts to remind me of... wait. Pumping lemma? Stack-based automata?

To me the single pass idea feels like adding a stream of single units to the end of a growing/shrinking polymer, doing the reaction as you add each individual unit.

Yeah, it's just a stack-based automata at that point, if even that, given it'd just be one node

Which is what your solution looks like

Yeah, Ben's does some interesting things with two ends and a reverse mixed in there 🙂

Or something with a left and right. I haven't grokked it yet.

Have a link to Ben's?

Ah nvm, I see it in the cljc

@mfikes It's the same thing you're doing but more opaque! My left is your reduce's accumulator.

Yeah; left is the accumulating stack, right is the remaining string stack

Though I don't think the reverse at the end earns you anything, since the answer doesn't call for preserving the order

You could probably prove the single pass leads to a fully reacted polymer by using proof by induction

True! Reverses are not necessary since a polymer reacts the same forwards and backwards. Feels dirty to me to remove them though.

Intuitively, the only information adding a new unit to the end can add is that A. a new element exists, or B. the top element is removed

Even if a new element is re-exposed from that interaction, it's inert still, because it cannot interact with the thing below it on the stack (having already been tested in a prior recursive step)

therefore, it can only react with the following unused element in the remaining input string

The key is that the relative ordering of the 'seen' portion of the string remains the same, and is stable while new elements are added to the end

Yeah, base case (empty polymer) is inert, and each inductive step leads to a new inert polymer.

This is very similar to the type of thing you'd see for validly matching nested bracketed statements 🙂

That's the best way to put it, yeah

inert

https://en.wikipedia.org/wiki/Pushdown_automaton Good ol' days

I refactored to use reduce like @mfikes and got another 20-40% speed up

If we were competing with other languages on perf, Ben’s would be a good candidate :)

It's like the anticipation of Christmas when waiting for CI perf test results to come back 🎄