This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2018-12-05
Channels
- # adventofcode (246)
- # aleph (5)
- # aws (7)
- # beginners (161)
- # boot (3)
- # calva (42)
- # cider (40)
- # clara (10)
- # cljdoc (7)
- # cljs-dev (40)
- # cljsrn (6)
- # clojure (170)
- # clojure-dev (8)
- # clojure-greece (2)
- # clojure-italy (15)
- # clojure-kc (2)
- # clojure-new-zealand (13)
- # clojure-nl (13)
- # clojure-russia (3)
- # clojure-spec (5)
- # clojure-uk (160)
- # clojurescript (72)
- # clojurex (1)
- # cursive (7)
- # data-science (9)
- # datascript (1)
- # datomic (120)
- # devcards (4)
- # emacs (18)
- # figwheel-main (10)
- # fulcro (34)
- # kaocha (3)
- # luminus (1)
- # lumo (6)
- # music (1)
- # nrepl (23)
- # off-topic (2)
- # pedestal (4)
- # re-frame (42)
- # reagent (36)
- # reitit (10)
- # ring-swagger (21)
- # shadow-cljs (124)
- # spacemacs (6)
- # tools-deps (14)
- # unrepl (3)
- # vim (2)
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
good to know
(Integer/parseInt "09")
=> 9
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.
(it’d probably be even more performant if I was operating at the last element of the “left” sb)
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
So… @U82DUDVMH you should look at @me1740’s solution! More in line with what you were saying.
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.
lol, yes!
Yeah, that shouldn't be needed, but I get a smaller answer without it.
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...
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
My day5: "Elapsed time: 7839.507737 msecs" https://github.com/genmeblog/advent-of-code-2018/blob/master/src/advent_of_code_2018/day05.clj
something’s wrong in that I’ve got too many characters, but I can’t tell what. superficial examples seem fine.
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
My solution for Day 5 https://github.com/athos/advent-of-code-2018/blob/master/src/advent_of_code_2018/day05.clj
Clojure:
Testing aoc.y2018.d05.borkdude
part-2 took 5546.88 msecs
part-1 took 160.69 msecs
CLJS:
Testing aoc.y2018.d05.borkdude
part-1 took 107.00 msecs
part-2 took 1896.00 msecs
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
with pmap I get on clj:
Testing aoc.y2018.d05.borkdude
part-2 took 2900.71 msecs
part-1 took 160.96 msecs
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
Maybe they use some sort of time out?Advent of code 2018, day05
Part 1 "Elapsed time: 107.586455 msecs"
Part 2 "Elapsed time: 2453.459493 msecs"
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 ...
I think the key to a fast functional solution is to build the reduced polymer in reverse to make the backtracking faster.
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
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
divide and conquer + being more careful about data structure when the first approach was too slow
So you can get similar performance w/o having to reverse if you use a vector as your “reduced queue.”
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
@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.
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!
Guess I should've verified my input!
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)
@mroerni ah so, perhaps because you just return the count instead of allocating a new string?
Using pmap for task 2, halved the time. (on a 2/4 Core machine)
pre-emptive conj on tail, then compare and drop — ensures a single pass across the input
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.
slightly offtopic, but this solution in elixir is delightful: https://gist.github.com/sasa1977/d70f0986bf72bb94048d37843d11b4a4#file-day5-exs-L21-L28
I must not understand it. It looks like it recurs to the end of the string and unrolls.
maybe it just has a large stack!
Tail recursion never blows the stack. Did you try to call the function, or did you recur
?
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).
@mfikes The fixed-point thingy is nice. And I found your solution the most readable so far 🙂
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.
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
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 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.
@clashthebunny you can click the CircleCI icon on https://github.com/borkdude/advent-of-cljc
It just says 4GB of ram and two vCPU.
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.
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.
@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?
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}
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

Love the use of reduce
in react
/`add-unit`.
single pass is a very elegant solution 😉 definitely the right choice of data structure influences a good solution
I was interested in how you did lower-case before the set, so I benchmarked it a bit and it seems like it is significant to set twice with a lower-case inbetween:
advent-of-code-2018.day05=> (cr/with-progress-reporting (cr/bench (into #{} (map s/lower-case (into #{} (parse input)))) :verbose))
Warming up for JIT optimisations 10000000000 ...
compilation occurred before 1 iterations
compilation occurred before 390 iterations
compilation occurred before 779 iterations
compilation occurred before 1168 iterations
compilation occurred before 1557 iterations
compilation occurred before 1946 iterations
compilation occurred before 2335 iterations
compilation occurred before 2724 iterations
compilation occurred before 4669 iterations
compilation occurred before 5447 iterations
compilation occurred before 5836 iterations
Estimating execution count ...
Sampling ...
Final GC...
Checking GC...
Finding outliers ...
Bootstrapping ...
Checking outlier significance
x86_64 Mac OS X 10.13.6 8 cpu(s)
Java HotSpot(TM) 64-Bit Server VM 25.192-b12
Runtime arguments: -Dfile.encoding=UTF-8 -Xmx8g -Dclojure.compile.path=/Users/ranmason/code/advent-of-code-2017/target/classes -Dadvent-of-code.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 29640 in 60 samples of 494 calls.
Execution time sample mean : 2.123692 ms
Execution time mean : 2.124454 ms
Execution time sample std-deviation : 96.420077 µs
Execution time std-deviation : 96.989667 µs
Execution time lower quantile : 1.940056 ms ( 2.5%)
Execution time upper quantile : 2.234693 ms (97.5%)
Overhead used : 2.083859 ns
nil
advent-of-code-2018.day05=> (cr/with-progress-reporting (cr/bench (into #{} (map s/lower-case (parse input))) :verbose))
Warming up for JIT optimisations 10000000000 ...
compilation occurred before 154 iterations
compilation occurred before 307 iterations
compilation occurred before 460 iterations
compilation occurred before 1072 iterations
Estimating execution count ...
Sampling ...
Final GC...
Checking GC...
Finding outliers ...
Bootstrapping ...
Checking outlier significance
x86_64 Mac OS X 10.13.6 8 cpu(s)
Java HotSpot(TM) 64-Bit Server VM 25.192-b12
Runtime arguments: -Dfile.encoding=UTF-8 -Xmx8g -Dclojure.compile.path=/Users/ranmason/code/advent-of-code-2017/target/classes -Dadvent-of-code.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 5040 in 60 samples of 84 calls.
Execution time sample mean : 12.258769 ms
Execution time mean : 12.263469 ms
Execution time sample std-deviation : 437.470024 µs
Execution time std-deviation : 443.078234 µs
Execution time lower quantile : 11.783289 ms ( 2.5%)
Execution time upper quantile : 13.224535 ms (97.5%)
Overhead used : 2.083859 ns
Found 3 outliers in 60 samples (5.0000 %)
low-severe 3 (5.0000 %)
Variance from outliers : 22.2472 % Variance is moderately inflated by outliers
nil
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
so is mine
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.)
Thanks @mfikes. I see about 30% speed up across the board with ==
but who knows how reliable that is across iterations.
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
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.
made pretty big difference in my cljs times....didn't affect my clj times much.
Wow, that pre-purging trick leads to a speedup of 5.6 if applied to my naive aproach. 🙂
yes, going to modify mine for that later this evening
Hah. Yeah, a proof that that is a legitimate optimization is right at the edge of where my mind is.
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?
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
@mfikes It's the same thing you're doing but more opaque! My left
is your reduce
's accumulator.
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 🙂
I refactored to use reduce
like @mfikes and got another 20-40% speed up
It's like the anticipation of Christmas when waiting for CI perf test results to come back 🎄