Fork me on GitHub
#adventofcode
<
2018-12-01
>
karlis05:12:17

happy advent of code 2018 everyone! 🎉

karlis05:12:02

woke up, made coffee, read the puzzle 1 & wasn't sure if I'm still half asleep or is that really a 1-liner.

fellshard06:12:37

Day one is usually just a warmup. I use the time I'd normally take to get the environment warmed up, etc.

fellshard06:12:12

I have a standard workspace I use now for these, since there's a lot of common core utils - reading from resources file, parsing integers, defining coarsely-curried functions for interpreters, etc.

orestis06:12:51

Happy puzzling! I did today’s in Replete typing on an iPad keyboard :)

nate06:12:16

@orestis wow!

orestis06:12:10

Yeah but it’s tiny :)

orestis06:12:27

I don’t think I will do another, though with some love replete could easily be much more useful. Being able to save some files locally or even better to iCloud, some helpful keys above the keyboard. I wonder if it’s open source.

orestis06:12:02

It is! Perhaps I’ll pivot from AoC this year then.

mfikes15:12:57

Yeah, I maintain Replete. Custom keyboard stuff is always challenging to pull off while preserving the polished feel, but I definitely agree there could be some keyboard improvement. (You can always use a 3rd party keyboard with it.) The ability to save and edit locally or in iCloud would be nice. We can't do this, as it is not allowed http://blog.fikesfarm.com/posts/2015-08-11-loading-clojurescript-into-your-iphone.html but perhaps content created in Replete could be saved without violating any App Store rules.

lilactown06:12:08

I feel like there’s a clever use of lazy seqs in the 2nd part that I’m not seeing

mfikes15:12:56

Here is a way to do it using only lazy seqs, but in the end, I didn't like that approach compared to just a direct reduce to find the dup. https://gist.github.com/mfikes/53c53673f66257878ab82408635f297d

nate06:12:33

Yeah, or using cycle

orestis06:12:57

Given my constraints, I just went with a loop recur for part 2. Not much room for experimenting.

potetm06:12:17

my part 2 was def not 1 line

orestis06:12:13

Yeah, more like 10 in my case. It’s gone now so I can’t count :)

borkdude07:12:28

Submitted my solution for day 1 to Advent of CLJC: https://github.com/borkdude/advent-of-cljc

borkdude07:12:23

curious about your solutions. if you want you can make a PR and add it to the repo

borkdude07:12:19

The fun thing is you can see the timing of every day and user here: https://circleci.com/gh/borkdude/advent-of-cljc/55 when you scroll to the test execution

helios08:12:21

@borkdude where is the private leaderboard? 🙂

mario.cordova.86208:12:27

wow part 2 was a doozy!

mario.cordova.86208:12:46

are we allowed to post solutions here?

borkdude08:12:16

@helios I don’t know if there is a leaderboard. You might want to create one? @mario.cordova.862 You could also submit a PR to the above repo as an alternative of posting your solution here 🙂

borkdude08:12:32

I wouldn’t post your code here directly, a gist would be more appropriate. Of if you’re going to post it, post it only in a thread, so people don’t see the spoiler.

helios08:12:32

57048-763fafc9 is the code for the private leaderboard

helios08:12:00

@borkdude done. also added myself

mario.cordova.86208:12:51

@borkdude Added myself to the readme

borkdude08:12:04

@mario.cordova.862 can you rebase your PR? it has a conflict now

orestis09:12:18

There used to be an adventofcode-clojurians leaderboard, but I don’t have the invitation code. Perhaps clojurians slack log might have it?

karol09:12:47

Created pull request for adventofcode-clojurians. Also slightly offtopic does anyone else has a internal conflict of writing things in a simple way vs smart? I ask because as a developers I feel that we are constantly judged on quality of our code and how "smart" it is but when reading other people code I like things rather simple.

borkdude09:12:38

@karol Sometimes there’s a balance between keeping it simple and hacking it for performance

karol09:12:58

of course, and that is why I like advent of code because usually the first part can be done without optimization and you need to be clever in second part 😉 but I am fan of optimize only when needed and don't introduced layers of abstraction "for future", because I saw few clojure codebases that look like Java EE with parentheses but it is morning here so I might be just complaining 😄

borkdude10:12:00

I found the old leaderboard code, updated the topic (cc @helios)

borkdude10:12:36

didn’t know the leaderboards could be re-used over multiple years

helios10:12:32

i have no idea how AoC works, are points based on time as well?

borkdude10:12:55

the faster you solve the problem, the higher your score in the leaderboard

magic_bloat10:12:46

And its nothing to do with when you start solving! Time starts for everyone when the problem appears.

borkdude10:12:34

@denis.fuenzalida @dandorman thanks for contributing to advent of cljc https://github.com/borkdude/advent-of-cljc

orestis10:12:02

I just realized what advent-of-cljc is, I’ll be forking that as well.

orestis10:12:14

Should we add more inputs there?

borkdude10:12:14

no, the author of advent of code explicitly forbids it

borkdude10:12:50

So we’ll have to do with the input of whoever does the first PR

borkdude10:12:32

updated the README to reflect this

orestis11:12:27

Worth to do the runs at least a few times to ensure warm up for the timings etc?

borkdude11:12:20

Maybe. I’m not sure how this will work out if multiple users contribute all of their days. If it gets too slow on CI, I might filter the tests only for that user. So running tests multiple times might be something you want to do locally

orestis11:12:03

I guess not too important at this point, the corpus is the important thing. Great initiative!

orestis11:12:12

I’ve submitted my PR. I’ll use this for this years puzzles.

borkdude11:12:21

Thanks! Merged.

andofryn12:12:56

My repl is timing out on my part 2 solution.. 😅

andofryn13:12:27

Would anyone have some time to help me? My process keeps running for part 2 with the puzzle input and just never ends, if I use one of the examples as the input though it does seem to work... (I'll post my code as a thread to this message so spoiler alert!)

andofryn13:12:16

(def input (mapv read-string (str/split (slurp "./input") #"\n")))

(defn step [{:keys [frequency-changes current-index frequencies]}]
  (let [
        new-index (mod (inc current-index) (count frequency-changes))
        last-frequency (or (last frequencies) 0)]
    {
     :current-index new-index
     :frequencies (conj frequencies (+ last-frequency (get frequency-changes current-index 0)))
     :frequency-changes frequency-changes
     }))

(defn last-item-double [l]
  (and (> (count l) 1) (> (.indexOf (butlast l) (last l)) -1)))


(defn part2 [frequency-changes] (last (:frequencies (step (last (take-while
 (fn [state] (not (last-item-double (:frequencies state))))
 (iterate step {
        :frequencies []
        :frequency-changes frequency-changes
        :current-index 0
        })))))))

(part2 input)

orestis15:12:44

You are using a very inefficient algorithm to check for an already seen item. Using .indexOf etc etc means every time this run means it has to “walk” all the previous steps again and again.

orestis15:12:06

Consider keeping the previously seen frequencies in a set instead.

orestis15:12:55

As an aside, also consider formatting your code a little bit better as it can be really hard to follow 😄

andofryn20:12:08

thanks for the feedback! I got it to work way faster with a different approach, using loop/recur and a set as you suggested

andofryn20:12:21

though my initial solution did end after 1h40 or so 🙈

andofryn20:12:40

regarding code formatting, is there a general coding guideline for clojure and a linter like there is for python?

orestis21:12:33

There is the clojure style guidelines by Bbatsov, and a few linters. There’s a big discussion right now going on in ClojureVerse about this so you can find more info there (sorry, on mobile so can’t paste links easily)

andofryn21:12:09

I'll have a look at them, thanks for your help!

ihabunek14:12:51

i'm actually doing it in clojure and elixir in parallel, but pretty sure i won't have the time or willpower to do it all the way through in both languages

ihabunek14:12:07

@me1740 using state, le gasp 😄

me174015:12:10

Simplified to use cycle. I forgot about this function. Thanks. Yes state is debatable here but since it improves readability and reusability I opted for it 🙂

potetm15:12:44

I think this problem is going to be a lot of fun on the stream.

potetm15:12:03

I can think of a bunch of different ways to solve it offhand — none of them will take particularly long.

ihabunek15:12:24

Who is streaming?

potetm15:12:21

M-F @ 12:00 CST (UTC-6)

mario.cordova.86215:12:22

How would day 2 be solved if we had memory constraints?

potetm16:12:01

we have a cheater! 😛

mario.cordova.86216:12:34

Sorry Day 1 Part 2

me174016:12:07

Are people ok with discussing solutions here? What is the assumption about spoilers?

nate16:12:33

Maybe put the spoiler code in a thread?

mfikes16:12:18

I tend to not even read this channel until I'm done with my solution. Otherwise you might see solution strategies being discussed.

mfikes16:12:26

For example, you can't help from seeing cycle being mentioned. 🙂

me174016:12:15

🙂 yeah I realized that after the fact. Sorry.

mfikes16:12:50

To be honest, I enjoy seeing solution strategies being discussed. (Otherwise, where would they be, all in side threads?)

nate16:12:52

Good idea to stay away.

mfikes16:12:42

Also, the ability to look at other people's solutions and other ideas is the main value I get out of this. Much more than solving the problems myself. 🙂

me174016:12:11

So to answer Mario. I think if you stream in the changes and stream out the frequency in a sorted file you could solve it while just keeping one number in memory. But I didn't bother doing this 🙂

mfikes16:12:15

There have been some incredibly clever solutions in the past. 🙂

mario.cordova.86216:12:16

I tend to solve it first then come on here but I am guessing at later days when it becomes more difficult Ill be coming here for pointers :P

mfikes16:12:14

Yeah, there's a problem where you are stuck and want a little help, without seeing the solution. 🤔

nate16:12:59

Heh. Separate channel? #adventofcode-help ?

potetm16:12:12

:moar_channels:

mfikes16:12:31

One thing I see now is that, even though my solution works on my data, I have a defect in it 🙂

mfikes16:12:51

My solution gives the wrong answer for this input: [5 10 20 -35]. I suspect this will be a common mistake.

me174016:12:58

My first solution was not handling the case when there is no duplicate either 🙂

borkdude16:12:06

Thanks for submitting your solution to https://github.com/borkdude/advent-of-cljc @mfikes!

mfikes16:12:08

Wastl even gives a simpler example of [+1 -1] in the page

bhauman16:12:58

@mfikes good catch

mfikes16:12:19

I only learned about this when I saw another solution catering to that case.

bhauman16:12:40

TRY ALL THE EXAMPLES

bhauman16:12:51

that is the lesson I learn every year

bhauman16:12:00

cause I forget

taylor16:12:18

feeling pretty cheeky about (drop-while #(apply not= (swap-vals! seen conj %))) :man-juggling:

clashthebunny17:12:46

I also have the same issue with my solution. I wish there was a reduce-until function or something like that.

taylor17:12:27

like reduced?

clashthebunny17:12:08

Damn, time to refactor!!!

nate18:12:07

oh man, the reduced function!! TIL

clashthebunny16:12:23

I do wish somebody would make a data oriented source of the examples. I just want to pull in a mapping of input to output.

mario.cordova.86216:12:09

@taylor wow! Learned something new with reductions, reduced 👍

taylor16:12:52

nice! it seems a lot of people reached the same conclusion for part 2, though I shamelessly went with atoms for my first attempt

mfikes17:12:43

I really wanted to find a way to reuse distinct. Here is one way, but I'm wondering if there is some other clever way to reused the underlying capability in the core lib. https://gist.github.com/mfikes/53c53673f66257878ab82408635f297d

taylor17:12:49

I thought about making a variation of distinct transducer like while-distinct or something

taylor17:12:42

(defn while-distinct []
  (fn [rf]
    (let [seen (volatile! #{})]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
         (if (contains? @seen input)
           (reduced (rf result input))
           (do (vswap! seen conj input)
               (rf result input))))))))

(->> (cycle values)
     (reductions +)
     (eduction (while-distinct))
     (last))
though that name isn’t great because it includes the first non-distinct value :man-shrugging:

borkdude17:12:07

I’m not sure why people are using reductions?

me174017:12:34

To get a sequence of the frequencies after applying the changes.

potetm17:12:45

To generate a list of accumulations, instead of manually managing in reduce

potetm17:12:21

less efficient, but breaks part of the computation out

ryan.russell01117:12:20

is it less efficient since it is lazy? (I'm asking because I genuinely don't know)

potetm17:12:32

it generates another data structure (the laziness only helps with efficiency).

potetm17:12:59

It’s honestly not something you should think about all the time. But I like running through various levels of efficiency in my head.

potetm17:12:34

so, using cycle+reductions+reduce -> (seq of cycle) + (seq of reductions) + #{set of reduce}

ryan.russell01117:12:55

my thought was that pretty much either way a new data structure needs to be generated at least from the solutions I've seen thus far, so I wasn't sure if using reductions was actually less efficient than managing the computations and what has been seen in a reduce.

potetm17:12:56

reduce is only (seq of cycle) + #{set of reduce}

ryan.russell01117:12:10

hmm.. I think I understand that

potetm17:12:39

but it’s evaluated lazily, so you only do the computational work that you must

pesterhazy18:12:35

I'm curious how much room for difference there is in a simple task like this

potetm18:12:51

off the top of my head, I’ve got ~5 diff ways to go about it

potetm18:12:53

I’ll ping back here after the stream with a link to github if you just want to review results.

mfikes18:12:12

It seems like most solutions involve a reduce or a direct loop / recur to essentially walk the sequence looking for the first dup.

pesterhazy18:12:57

@mfikes I saw your tweet and couldn't resist 🙂

clashthebunny18:12:08

I thought a bit about how to just calculate it analytically, but didn't see anything easy. Did anybody come up with a way?

mfikes18:12:11

Excellent. 🙂

pesterhazy18:12:44

Of course I spent 90% of the time setting up the clj tool with nREPL and the Corfield Comma

pesterhazy18:12:40

@mfikes your idea of using two reductions on top of each other is clever

pesterhazy18:12:14

other than that mine is identical almost to a character

dpsutton18:12:21

reduce the reductions you mean?

pesterhazy18:12:45

is that a common FP pattern? I wasn't aware

dpsutton18:12:13

i did something similar. the data to investigate is the reduction. seems not necessarily FP but just this problem to me

mfikes18:12:43

Paulus, does your solution handle the sequence [+1 -1]? (This is a common defect.)

pesterhazy18:12:50

reduce is a great abstraction (obviously!) because you can swap in reductions and get a nice debugging output for free. Plus if the sequence doesn't terminate, you can lazily take n

dpsutton18:12:03

(first-duplicate (drop 1 (reductions + 0 (cycle values)))) yeah something similar

rmprescott18:12:26

Why the drop 1? This is probably related to why I disagreed with [+1 -1] => 0 rather than 1. But I still don't see why.

dpsutton18:12:32

yes it gets rid of the 0 sum for the sequence of length 0. i originally didn't have it

mfikes18:12:39

Maybe some could be used to mechanize the linear scan?

mfikes18:12:00

Your predicate would be stateful 😞

pesterhazy18:12:56

My solution uses a "composite accumulator", in this case a vector [acc-freq acc-seen]. I find myself reaching for composite accumulators often for less-than-simple reduces but I wonder if it's a good pattern

potetm18:12:32

that’s^ normal — although there’s often other ways of going about it

dpsutton18:12:05

i do that all the time. i only get annoyed because it usually requires a step to pluck apart the composite accumulator at the end

pesterhazy18:12:26

The (->> xs (reductions step-1 init-1) (reduce step-2 init-2)) pattern avoids the composite acc

pesterhazy18:12:12

@dpsutton right, although when you know that you're going to end with reduced, you won't need it

pesterhazy18:12:27

it would be interesting to compare performance as well. reductions must incur some performance cost

dpsutton18:12:43

I always feel a little bad using reduced. The short circuit makes me feel like I'm abusing reduce

mfikes18:12:09

Yeah, it always makes you feel like you failed, in some way. 🙂

mfikes18:12:46

It is like an inclusion an an otherwise perfect diamond.

borkdude18:12:49

@pesterhazy I have the same pattern

pesterhazy18:12:47

@borkdude ours are practically identical

dpsutton18:12:56

I've seen reducing functions defined outside of the reduce call where they include reduced and I have no idea what reduced does if it is not in a reducing context

pesterhazy18:12:48

it just returns a special Java class, clojure.lang.Reduced

pesterhazy19:12:07

@me1740's stateful predicate is interesting: https://github.com/benfle/advent-of-code-2018/blob/master/day-1.clj#L16 - I'm not sure how I feel about that

mfikes19:12:38

Right, keep's docstring is at odds with that approach

mfikes19:12:41

Perhaps, close to that idea, but safer, would be to take the source of distinct and produce an opposite function named duplicates, and then take the first from that

potetm19:12:21

that’s what I did^ for one of mine

potetm19:12:28

can use as a transducer

mfikes19:12:41

Yeah, and a nice little reusable fn falls out of the effort 🙂

potetm19:12:03

I was hoping to do a big unveil on stream then post back here w/ the code!

mfikes19:12:51

Hah. It is still a very nice solution. Especially if the transducer version is fast.

potetm19:12:02

yeah I might benchmark them all for fun as well

potetm19:12:08

good point that

pesterhazy19:12:33

I guess a stateful sequence processing function (like distinct) is safer than a stateful predicate

potetm19:12:11

but stateful transducers are more idiomatic

pesterhazy19:12:37

"safer" in the sense that using a stateful predicate for filter or keep is violating its contract

potetm19:12:06

but you could generate a lazy-seq of dups

pesterhazy19:12:08

whereas the contract of sequences has no such provision

potetm19:12:09

that would be fine

pesterhazy19:12:19

so the idea would be a while-distinct function?

potetm19:12:46

just (duplicates coll) the same as (distinct coll)

pesterhazy19:12:37

does the name duplicates make sense though?

me174019:12:57

@mfikes good catch. not sure why keep needs to be free of side effect though.

pesterhazy19:12:14

we're looking for the opposite of duplicates, r ight?

potetm19:12:20

I think so? “I want all of the duplicates in this seq.” As opposed to, “I want the duplicates removed from this seq.”

potetm19:12:35

oh for the problem

potetm19:12:41

yeah it depends on how you’re going about it!

pesterhazy19:12:20

gotcha, you'd use (->> xs duplicates first)

pesterhazy19:12:29

actually while-distinct would work only if it was inclusive of the dupe (which makes little sense)

pesterhazy20:12:40

It’s cool to see to which degree thought processes converge

mfikes19:12:59

@me1740 Trying to come up with an example:

cljs.user=> (def x (eduction (keep (duplicate?)) [1 2 3 2 4 2 3]))
#'cljs.user/x
cljs.user=> (into [] x)
[2 2 3]
cljs.user=> (into [] x)
[1 2 3 2 4 2 3]

me174019:12:45

Oh ok I see, thanks. Also explain why you should initialize your state inside a transducer function.

me174019:12:19

So I had to rewrite that as a transducer with the state inside it:

(defn duplicates
  []
  (fn [xf]
    (let [seen (volatile! #{})]
      (fn
        ([] (xf))
        ([result] (xf result))
        ([result input]
         (if (contains? @seen input)
           (xf result input)
           (do
             (vswap! seen conj input)
             result)))))))

taylor19:12:38

haha I’m playing w/Quil to visualize the solution as it’s calculated, but then I just figured out it’ll take ~40 minutes to finish @ 60fps

bhauman20:12:58

having both reductions and duplicates transducers would be interesting, I wonder if I would remember to use the duplicates one

potetm20:12:49

cgrand has it in xforms

potetm20:12:02

reductions that is

potetm20:12:09

I don’t think duplicates is there

borkdude21:12:51

xforms is also available in advent-of-cljc, just sayin’ 🙂

helios22:12:04

@borkdude I just updated the invite code for the leaderboard, I deleted the ones I created this afternoon

borkdude22:12:31

who owns this advent-of-clojurians repo, I think @thegeez? can you add more people with PR merge rights? It seems I’m the only one doing that right now

adammiller22:12:35

Probably not the ideal use, but I used NextJournal to do the day 1 challenges. Link if anyone wants to remix it with other styles: https://nextjournal.com/akmiller/advent-of-code-2018--day-1

lilactown23:12:31

I decided to do the first day in both CLJ and Rust. https://github.com/Lokeh/advent-2018/tree/master/day1

lilactown23:12:08

we’ll see how far I get before succumbing to my lack of Rust knowledge (and frustrations with the type system) and just do the rest in CLJ :P

lilactown23:12:48

I think I might update my CLJ solution with a duplicates xf - wanted to in the moment but it was very late for me last night

mfikes23:12:49

I like how you name the predicate seen?, even though it is implemented using a set. Nice.

mfikes23:12:55

It is a predicate that doesn't return a Boolean value, but maybe that's OK.

lilactown23:12:15

Yeah I thought it felt nice. I often do that when using sets as predicates