Clojurians Log v2

[["frank" "hello"] [nil "how is everyone?"] ["ethel" "good, you?"]] => [["frank" "hello"] ["frank" "how is everyone?"] ["ethel" "good, you?"]]

something like that

i forget the structure of the input, so that might be nonsensical at this point, but remember feeling like i'd unlocked some kind of secret when i found that

found it:

(defn forward-propagate
  "If the keyword (kw) specified does not exist in the next map in the
  sequence, use the previous value of the keyword (kw).

  Example:
  (forward-propagate :nickname '({:nickname \"Fred\"} {:nickname nil}))
  => ({:nickname \"Fred\"} {:nickname \"Fred\"})"
  [mapseq kw]
  (rest
   (reductions
    (fn [{prev kw} next]
      (update-in next [kw] #(or % prev)))
    {}
    mapseq)))

name suggestions welcome 😄

shame on me for the clever destructuring, shadowing next, a docstring that doesn't show the real true desired behavior, and other things

written before update was a thing, so there's another wart

</bikeshed>

I'm not sure if placing in the top 1000 is any good 😕 I think two years ago I managed to get in the top 50 but perhaps there are a lot more doing it nowadays

it's all by time right? seems like being somewhere such that midnight on the east coast happens at a bright and thoughful hour is key to getting on the leader board

and being smart! 😄

@mfikes I just dumped code while I was on the move earlier, but got it down to 0.7ms w/ a proper benchmark

(sry for the spoiler ya’ll, wasn’t thinking)

Had the same idea 🙂 https://github.com/gomes-work/advent2018/blob/master/src/advent2018/day_2.clj

I used Quil to make a visualization of day 2 part 2 string comparisons https://youtu.be/Y_UuASYf6bM

Today’s was a little more fun imo 🙂

It took a bit to think about a good solution to the first one, and I guessed correctly on what types of information I would need to recover for the second one: https://gitlab.com/randall.mason/advent-of-code/blob/master/src/advent_of_code_2018/day03.clj

Ok I'm ready to make a duplicates transducer now:grin:

Second time it's been an "I wish I had that"

https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/3.clj

I solved the first one in a horribly slow manner, then went back around with an idea I had and rejected the first go 'round and ended up being far more efficient.

First time was brute-force squared, second time was brute-force linear 😛

Oof. And looking at those solutions, I see some obvious places I was still overthinking it. I'm out of shape with Clojure 😅

Peter Tseng is a machine

I feel a little dirty about my solution https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle03.clj#L38

mutable array is perfect for this

doesn't exactly translate into raw speed 🙂

Elapsed time: 16054.534362 msecs

my part2 is slow as hell 😛

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

that's around 3 seconds for both parts, could probably speed it up by using a transient set

The weird thing is that on Node part 2 takes less long than part 1…

=== Running clojure test 2018

Running tests in #{"src"}

Testing aoc.y2018.d03.borkdude
part-2 took 567.30943 msecs
part-1 took 60.775506 msecs

Ran 2 tests containing 2 assertions.
0 failures, 0 errors.

=== Running cljs test 2018

Testing aoc.y2018.d03.borkdude
part-1 took 6239.000000 msecs
part-2 took 1018.000000 msecs

Ran 2 tests containing 2 assertions.
0 failures, 0 errors.

maybe it’s doing something very inefficient in part 1… maybe something to do with lazyiness

Is there anyone doing AoC based on a different paradigm, like Prolog or APL?

@pesterhazy I know someone who does it in Postgres

https://twitter.com/pg_xocolatl

Hi @borkdude can we use reader conditionals in advent-of-cljc or does that defeat the purpose?

@erwinrooijakkers you most definitely can. you can also add (cross platform) libraries

Thanks

@erwinrooijakkers note that there are already two useful functions in aoc.utils

Aha

🙂

@erwinrooijakkers your tests are failing exactly on the functions I already provided in aoc.utils 🙂

you just have to prefix them with u/

I see 🙂

Alright now back to work. Hope to do day 3 this evening.

Nice repository!

29 lines today but slow as hell 😄

I basically limited myself to what resources http://repl.it has so it’s easy to get a timeout once in a while, can’t be bothered to start a new lein project for AoC

@orestis fixed the FAIL output problem in cljs

@erwinrooijakkers merged

My solution: https://github.com/benfle/advent-of-code-2018/blob/master/day3.clj As long as it is under a second I don't look at perf 🙂

mine is basically identical^

except

I used sets

so for the second part, I took a union of all overlaps

and then set/difference from every identifier

@potetm interesting idea, i hadn't thought of that and did the brute-force approach first 😄

oh mine is def brute force

my solution: https://github.com/borkdude/advent-of-cljc/blob/master/src/aoc/y2018/d03/borkdude.cljc

just get to talk about sets so I feel fancy

yeah at the end I tried to use sets for the list of claim ids. It seemed less performant when computing the surface area.

I wonder why my solution is so much slower (>16s): https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle03.clj#L38 - I naively thought that a mutable 2d Java Array would be faster

I also wondered if sets would be better for the fabric instead of vec of vec in case it was sparse but the perf seemed a bit worse too so I gave up perf improvements 🙂

I probably could have made my parse function shorter by using @me1740’s (str/split s #"[ ,:x@#]") instead of multiple steps 🙂

ah, mine a vec of vec of sets

(instead of list in your case)

my data set looks like a list of {:id id :coordinate [x y]}

@borkdude yeah I fully trusted the input to be well-formed 🙂

I usually don't do that in real life 🙂

@borkdude I have done a single re-match and got {:x x :y y :w w :h h} 🙂

re-find would probably also work?

yeah i guess

@helios It was my first idea but I was too lazy to get the regexp right 🙂

nice, I’m going to try that

yeah i was thinking the regex would be a PITA to write but it turned out quite easy

spoiler: https://github.com/Heliosmaster/advent-of-code-2018/blob/master/src/adventofcode/2018/day3.clj#L6

I also, in a sense, trusted the input to be well formed (same amount of spaces, etc)

otherwise you would need to add just a lot more +? everywhere 😛

much better: https://github.com/borkdude/advent-of-cljc/commit/b06d17691b8173c040eeef35e2ce0b1d8784d361

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

@mfikes nice and concise

funny timings. CLJ:

Testing aoc.y2018.d03.borkdude
part-2 took 967.53 msecs
part-1 took 60.77 msecs

Testing aoc.y2018.d03.mfikes
part-2 took 726.61 msecs
part-1 took 602.41 msecs

Testing aoc.y2018.d03.borkdude
part-1 took 6087.00 msecs
part-2 took 1843.00 msecs

Testing aoc.y2018.d03.mfikes
part-1 took 6375.00 msecs
part-2 took 6525.00 msecs

CLJS seems to be 10x slower

Yeah, I saw the same thing locally. I haven’t pinpointed what it is.

Observation: The problem statement only lists that the canvas is at least 1000 inches per side. You're better off not pre-allocating the whole set of cells; that might help, dunno. Using atoms in your array won't be terribly useful, and will just cause overhead unless you're writing all your claims in parallel. As it is, everything's synchronous.

I'm not using atoms in the array

Noticed that after. Still probably not necessary for accumulation, though?

yes, I'd have to replace the doseq's by for's I believe

combined with reduce

part 2 took 26,02 ms (Java)

I decided to use this one to practice a bit with core.matrix. I learned about some interesting gotchas, so I was happy with doing that.

@gklijs nice!

Spoiler

I did a reduce and kept a set of all the id of 'patches' I added, then add the id to all the fields. But before I checked when one of the fields was already taken, in that case I would remove all the founds id's from the set.

similar to what I did

but this is more optimized 🙂

Basically what I did too

Spoiler

You can efficiently tell that two rects overlap when there is overlap in their x-extents and overlap in their y-extents. No need to enumerate all the points inside each rectangle. This also works in the continuous domain.

Also the regex is easier than it looks: #(re-seq #"\d+" %)

except, I added ids to a matrix (using assign! on a submatrix), and did the reduce as an ereduce over the submatrix

I thought about the overlaps that you mention, but don’t you then need to do O(n^2) rectangle comparisons?

Yep. It's a balance between O(n^2) rect comparisons vs O(n) rect processing steps times O(height*width) set insertions. If the rectangles are mostly small and you have many of them then the set approach will win.

Going live soon! Could def use some backup 😄 https://www.twitch.tv/timpote

There are probably optimizations that I'm missing in the set-based approach but it's currently 10x slower than my bounds-checking approach. 1400 ms for set intersection, 170 ms for O(n^2) bounds-checking.

Is anybody going for leaderboard points? Hot tip, I won't be able to do tonights puzzle until tomorrow, so feel free to take the top spot on the adventofcode-clojurians leaderboard!

I decided to take it easy this year — no pressure to solve every day as soon as possible. Very busy at work, and I’m learning a new language in the evenings (human language, not computer language) so suddenly free time is not so plentiful as last year 🙂 Have fun!

@orestis my statement on this year: https://twitter.com/borkdude/status/1069546247034466304 🙂

I need the challenge to incentivize me, but I'm trying to stream this year in order to practice explaining things out loud and build my vocabulary for talking about solutions in Clojure, so the competitive edge is dulled. I've got a lot to learn 🙂

Nice

Last year I focused on FP approaches. That made sense for some puzzles, and others were 50/50 as to whether keeping state would be helpful, but there were a handful of puzzles which cried out to be solved with mutable data structures. Those ones took some effort to stick to “pure” approaches. It was useful practice

Barely anything is impossible to do in an FP way, except sometimes it’s hard to make it fast enough... I think

you’d be surprised at how fast it gets

and yeah, I haven’t found any barriers

except in my approaches

Right. In 2015 I encountered that problem and I needed mutable arrays. It was easier to solve that in Java or Scala but eventually I got it working Clojure just as fast: https://stackoverflow.com/questions/34153369/why-is-this-clojure-program-working-on-a-mutable-array-so-slow

Then I thought: maybe there is something to Scala… but I never needed to do that kind of stuff in my daily work

Especially given that the puzzles haven input->output shape

@potetm I know pure approaches can be fast but the simplest solution is often not the fastest

I’m aware that everything can be done with pure functional programming, which is why I stuck to it. Sometimes it’s not the most elegant approach though. But forcing myself to stick to it often helped me identify elegance that wasn’t immediately apparent

And if all else fails, use a state monad 🤪

Day 02 Part 2 - The problem can be narrowed down using group-by on the first and second halves of the IDs. The subdivided problems are then small enough to quickly brute force with an O(n^2) comparison. I tried also doing the "delete column" approach to attack the subdivided problems, but the perf was about the same. Either way it's about 100x faster than the naive brute force approach.

(ns advent.scratch
  (:require [clojure.string :as str]))

;; Hybrid approach. Group the words by their first half and group them
;; by their second half. Perform a brute force O(n^2) search for
;; almost-duplicates in each group. Take the first pair of almost-
;; duplicates found and extract the common characters.
;;
;; Rationale: A pair of almost-duplicates will have their differing
;; character in either the first half or the second half, meaning
;; either their second half or their first half will be identical.
;; Grouping by first half and by second half guarantees that the
;; pair will end up in a group together. The grouping step also
;; drastically cuts down the number of pairings we need to consider.
;; Searching within the group is O(n^2)

(def day-02 (-> (slurp "resources/day-02/input")
                (str/split-lines)))

(defn differences [x y]
  (filter #(apply distinct? %) (map list x y)))

(defn extract-common-chars
  [pair]
  (->> pair
       (apply map list)
       (filter #(apply = %))
       (map first)
       (apply str)))

(defn find-almost-duplicates [ids]
  (for [lhs ids
        rhs ids
        :when (distinct? lhs rhs)]
    (when (-> (differences lhs rhs)
              count
              (= 1))
      [lhs rhs])))

(defn in-twain [s]
  (let [mid (quot (count s) 2)]
    [(subs s 0 mid)
     (subs s mid)]))

(defn group-by-first-and-second-halves [coll]
  (concat (vals (group-by #(first (in-twain %)) coll))
          (vals (group-by #(second (in-twain %)) coll))))

(time (->> day-02
           group-by-first-and-second-halves
           (filter #(> (count %) 1))
           (map find-almost-duplicates)
           (some first)
           extract-common-chars)) ; 0.8 - 2 msecs

I'm trying to solve today's problem in Rust and Rich's "Maybe Not" talk is echoing in my head as I try and figure out the correct sigils and incantations to make the type checker happy

My problem is the sunk cost issue. I have a hard time not seeing my initial idea through even though I may realize there is a better way half way into it. On problem 3 today I thought it would be simple to convert 2d indexes into 1d array...and it was simple for the first part (if not a bit verbose) but was not terribly helpful to solve the 2nd part.

and then of course I saw @mfikes solutions which was half the length of mine! But I guess that's what this is great for, seeing how others approach the problems!

I use a one-dimensional vector and updating on index as well. I was happy to discover that the performance is about 25 times better than the other solutions 😄:

Testing aoc.y2018.d03.borkdude
part-2 took 805.32 msecs
part-1 took 113.23 msecs

Testing aoc.y2018.d03.iamdrowsy
part-2 took 971.44 msecs
part-1 took 80.25 msecs

Testing aoc.y2018.d03.mfikes
part-2 took 713.25 msecs
part-1 took 605.19 msecs

Testing aoc.y2018.d03.mrmcc3
part-2 took 818.67 msecs
part-1 took 0.43 msecs

Testing aoc.y2018.d03.transducer
part-2 took 15.80 msecs
part-1 took 21.30 msecs

Nice idea

Watching some solution, but so far I don't see anyone else using the 1000 square inch for the solution.

1000 square inch is a specified minimum for the size, hence the caution, I think

Plus given there's some relative sparseness to the rectangles, I think allocating an entire area for the entire expected space isn't as useful as could be hoped (though to be far it would be a one-shot allocation)

a 1d array wouldn't be expandable correctly if you didn't know the size beforehand; a pass of the inputs could give you the max coords, though

it's not really clear, I also kind of cheated by checking there was no id of 0 (initial value of an int)

@erwinrooijakkers Did you see my comment to your PR? > Doing “expensive” computations at top level is something I would like you to avoid, since this cuts of time from the test.

your solution is likely to be faster because of that

Ah I cheated? 😞

I calculate a grid with the counts that I reuse in the second one

Also from my comment: > If you want to re-use the same calculation from solution 1 in solution 2, then you can memoize or use a delay.

Okay

@erwinrooijakkers e.g.: https://github.com/borkdude/advent-of-cljc/blob/master/src/aoc/y2018/d03/borkdude.cljc#L20

Why is that allowed?

@erwinrooijakkers because parsed is a function. the work is done within the test

Ah and it is not actually memoized between tests

?

it is, but at least the work is part of the tests.

Ah I see

That pre-processing work needs to show up in at least one test, basically

right

Oh wait now I see

also when you make an exception, the application won’t work at all anymore

I’ll fix it

Might be good to use deterministic ordering of test execution so that folks' times are comparable

(though I'm guessing you've already got that covered)

I think it is deterministic, but the test runner reverses part 2 and then part 1

Ah, cool

I'll pipe mine through later, hopefully

I’m using https://github.com/cognitect-labs/test-runner for the tests. you may be able to find out why it first does part-2 and then part-1

I got about 0.25 ms and 1ms for the first and the second, but that's with some warm up interation, https://circleci.com/gh/gklijs/advent_of_code_2018/79 probably in the weekend I have time for a similar setup for clojure

Perhaps the Advent of CLJC solutions should avoid defs with inits that calculate or otherwise cache things. It is really easy to make the solutions appear to take zero time otherwise.

@mfikes we were just discussing that yeah. only top level functions, but memoizing is permitted

and maybe top level lazy sequences for parsing the data. those don’t realize outside the tests either

Yeah—a problem is that the second one to run benefits from the realizing done by the first. Hrm.

Yes thanks @borkdude I did in my latest force push 😉

@mfikes I saw this pattern was used last year a lot: the output from part 1 served as input for part 2. I think it makes sense to memoize, because the build time on CI can go up a lot if we double these calculations?

@mfikes the time is a nice gimmick, but the purpose is really to build a corpus to find errors in speculative or measure performance improvements in clj/cljs

Being able to compare valid timings is nice :)

I’ve always been focusing on clear, idiomatic code. But it is also nice to know how much slower that code is when compared to highly optimized solutions.

@mfikes are you arguing for or against memoize?

@pesterhazy @quoll Apologies for my tone earlier. I shouldn’t have commented unless I was willing to really engage. I was in between things at the time and just threw a comment to the ether.

I’m suggesting that, once a test starts, if anything has been calculated prior to it running, it really makes timing comparisons bogus

@mfikes agreed. but can results from part-1 be used in part 2?

Oh, yeah, that seems “fair” IMHO :)

cool. I’ll add this to the README

I’ll just have to hassle you in HipChat

when a test runs in 10ms when most of the solutions run in 200 or 300 ms it’s a smell 😉

so then I check if this is the case

An example of “cheating” would be to

(def xs (doall ,,,))

Oh, are people posting in some central place? I must not have scrolled back far enough in the Slack.

yes. so top level (def data (map parse-int input)) is ok, since it’s lazy. not ok when realized outside the tests

But I tried the 1000x1000 grid. It’s smaller than most images, so I didn’t see a problem with that approach

And it let me practice with core.matrix

https://github.com/borkdude/advent-of-cljc/commit/543763a0f52f1f07bce1622b3bba1967c717c0d9

no worries

@erwinrooijakkers your solution is still fast (although not as fast as measured before), congrats 🙂

Having said all this, ClojureScript was pretty slow on today’s problem.

CLJ
Testing aoc.y2018.d03.borkdude
part-2 took 756.09 msecs
part-1 took 57.66 msecs

Testing aoc.y2018.d03.iamdrowsy
part-2 took 653.79 msecs
part-1 took 83.38 msecs

Testing aoc.y2018.d03.mfikes
part-2 took 673.82 msecs
part-1 took 552.37 msecs

Testing aoc.y2018.d03.mrmcc3
part-2 took 762.67 msecs
part-1 took 0.40 msecs

Testing aoc.y2018.d03.transducer
part-2 took 157.78 msecs
part-1 took 23.40 msecs

CLJS
Testing aoc.y2018.d03.borkdude
part-1 took 5555.00 msecs
part-2 took 1677.00 msecs

Testing aoc.y2018.d03.iamdrowsy
part-1 took 5439.00 msecs
part-2 took 638.00 msecs

Testing aoc.y2018.d03.mfikes
part-1 took 5314.00 msecs
part-2 took 5760.00 msecs

Testing aoc.y2018.d03.mrmcc3
part-1 took 2589.00 msecs
part-2 took 177.00 msecs

Testing aoc.y2018.d03.transducer
part-1 took 639.00 msecs
part-2 took 75.00 msecs

about 4x slower roughly speaking

this channel exists, yay! ❤️

maybe not so yay XD