Fork me on GitHub
#adventofcode
<
2018-12-03
>
devn00:12:48

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

devn00:12:49

something like that

devn00:12:00

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

devn00:12:34

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

devn00:12:58

name suggestions welcome 😄

devn00:12:51

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

devn00:12:26

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

devn00:12:51

</bikeshed>

slester14700:12:15

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

dpsutton00:12:07

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

slester14700:12:19

and being smart! 😄

potetm02:12:13

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

potetm02:12:25

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

taylor04:12:40

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

erwinrooijakkers09:12:33

Hahaha this is awesome

erwinrooijakkers09:12:41

Do same for day 3 😛

taylor13:12:41

I did but it’s not very exciting. Just a bunch of multicolor rectangles

taylor16:12:01

Santa’s suit not looking very coherent, can you spot the single patch that doesn’t overlap?! https://i.imgur.com/jV7Atfn.png

borkdude16:12:13

Is it the green one?

taylor16:12:34

haha it’s basically impossible to see without animating it; it’s in the top-right quadrant but I can’t even find it now looking at the still image

rmprescott18:12:16

I'll bet someone could write a program to find it. ;D

potetm05:12:54

Today’s was a little more fun imo 🙂

clashthebunny06:12:08

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

lilactown06:12:28

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

lilactown06:12:01

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

fellshard07:12:14

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.

fellshard07:12:39

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

fellshard07:12:09

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

nmdrenard08:12:40

Peter Tseng is a machine

borkdude08:12:52

mutable array is perfect for this

pesterhazy08:12:48

doesn't exactly translate into raw speed 🙂

Elapsed time: 16054.534362 msecs

helios08:12:05

my part2 is slow as hell 😛

ihabunek09:12:52

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

borkdude09:12:37

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.

borkdude09:12:24

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

pesterhazy09:12:35

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

rmprescott03:12:49

Why do you say APL is a different paradigm? Aside from laziness it's pretty similar - just a very different notation.

pesterhazy06:12:00

Because I don’t know APL :)

borkdude10:12:45

@pesterhazy I know someone who does it in Postgres

erwinrooijakkers10:12:28

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

borkdude10:12:00

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

borkdude10:12:20

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

borkdude11:12:42

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

borkdude11:12:53

you just have to prefix them with u/

erwinrooijakkers11:12:14

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

erwinrooijakkers11:12:37

Nice repository!

nooga11:12:08

29 lines today but slow as hell 😄

nooga11:12:55

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

borkdude11:12:34

@orestis fixed the FAIL output problem in cljs

borkdude11:12:43

@erwinrooijakkers merged

me174012:12:25

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 🙂

potetm12:12:25

mine is basically identical^

potetm12:12:31

I used sets

potetm12:12:43

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

potetm12:12:04

and then set/difference from every identifier

helios12:12:16

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

potetm12:12:32

oh mine is def brute force

potetm12:12:50

just get to talk about sets so I feel fancy

me174012:12:22

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

pesterhazy12:12:35

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

fellshard15:12:48

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.

pesterhazy16:12:25

I'm not using atoms in the array

fellshard16:12:07

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

pesterhazy16:12:12

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

pesterhazy16:12:30

combined with reduce

me174013:12:04

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 🙂

borkdude13:12:52

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

potetm13:12:53

ah, mine a vec of vec of sets

potetm13:12:02

(instead of list in your case)

borkdude13:12:23

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

me174013:12:30

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

me174013:12:45

I usually don't do that in real life 🙂

helios13:12:17

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

borkdude13:12:34

re-find would probably also work?

helios13:12:42

yeah i guess

me174013:12:54

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

borkdude13:12:54

nice, I’m going to try that

helios13:12:47

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

helios13:12:02

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

helios13:12:17

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

pesterhazy15:12:33

@mfikes nice and concise

borkdude15:12:07

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
CLJS:
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

borkdude15:12:06

CLJS seems to be 10x slower

mfikes15:12:18

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

gklijs17:12:59

part 2 took 26,02 ms (Java)

quoll17:12:37

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.

borkdude17:12:49

@gklijs nice!

gklijs17:12:15

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.

borkdude17:12:10

similar to what I did

borkdude17:12:42

but this is more optimized 🙂

quoll17:12:23

Basically what I did too

quoll17:12:05

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

ben.grabow17:12:32

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.

ben.grabow17:12:24

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

quoll17:12:11

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

ben.grabow17:12:00

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.

ben.grabow18:12:02

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.

potetm17:12:25

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

andrew.sinclair18:12:39

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!

orestis19:12:12

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!

fellshard19:12:04

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 🙂

quoll20:12:59

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

pesterhazy20:12:57

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

potetm20:12:29

you’d be surprised at how fast it gets

potetm20:12:35

and yeah, I haven’t found any barriers

potetm20:12:38

except in my approaches

borkdude20:12:08

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

borkdude20:12:30

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

pesterhazy20:12:32

Especially given that the puzzles haven input->output shape

pesterhazy20:12:32

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

quoll20:12:02

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

quoll20:12:51

And if all else fails, use a state monad :zany_face:

ben.grabow20:12:16

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.

ben.grabow20:12:31

(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

lilactown20:12:48

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

adammiller20:12:13

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.

adammiller20:12:55

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!

erwinrooijakkers21:12:04

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

gklijs21:12:01

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

quoll22:12:40

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

quoll22:12:37

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

quoll22:12:04

And it let me practice with core.matrix

regen20:12:24

@quoll there's a link in the topic to a repo with a list of clojurians participating https://github.com/adventofcode-clojurians/adventofcode-clojurians

fellshard21:12:25

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

fellshard21:12:12

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)

fellshard21:12:34

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

gklijs21:12:53

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

borkdude21:12:12

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

borkdude21:12:36

your solution is likely to be faster because of that

erwinrooijakkers21:12:37

Ah I cheated? 😞

erwinrooijakkers21:12:12

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

borkdude21:12:27

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.

erwinrooijakkers21:12:12

Why is that allowed?

borkdude21:12:40

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

erwinrooijakkers21:12:59

Ah and it is not actually memoized between tests

borkdude21:12:48

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

fellshard21:12:41

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

erwinrooijakkers21:12:54

Oh wait now I see

borkdude21:12:02

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

fellshard21:12:12

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

fellshard21:12:31

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

borkdude21:12:41

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

fellshard21:12:58

I'll pipe mine through later, hopefully

borkdude21:12:22

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

gklijs21:12:00

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

mfikes21:12:19

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.

borkdude21:12:23

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

borkdude21:12:22

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

mfikes21:12:25

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

erwinrooijakkers21:12:39

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

borkdude21:12:41

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

borkdude22:12:57

@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

mfikes22:12:09

Being able to compare valid timings is nice :)

mfikes22:12:18

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.

borkdude22:12:56

@mfikes are you arguing for or against memoize?

potetm22:12:23

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

quoll22:12:11

I’ll just have to hassle you in HipChat

mfikes22:12:54

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

borkdude22:12:59

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

mfikes22:12:31

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

borkdude22:12:58

cool. I’ll add this to the README

borkdude22:12:27

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

borkdude22:12:35

so then I check if this is the case

mfikes22:12:33

An example of “cheating” would be to

(def xs (doall ,,,))

borkdude22:12:54

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

borkdude22:12:14

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

mfikes22:12:55

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

borkdude22:12:16

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

borkdude22:12:56

about 4x slower roughly speaking

lady3janepl22:12:51

this channel exists, yay! ❤️

lady3janepl23:12:17

maybe not so yay XD