Clojurians Log v2

Never really used reduced before.. useful!

how about (drop max-idx (take (+ max-val max-idx) (cycle (range memory-length))))

Cool. Nice way to avoid mod 🙂

@minikomi Yes (cycle (range num-memory-banks)) is better than (mapcat identity (repeat (range num-memory-banks))). Now that I know about cycle I won't have to coerce it from other functions. Thanks @mfikes 🙂

cycle can also be useful in the day 1 problem, where the problem definition indicates "The list is circular"

Got a banana and my cup of tea. Ready.

done yet?

nope lol

I'm about to start

no pressure 🙂

oops.. emacs locked up when i pasted in the input lol

I think all the parenthesis messed with it

stuck on part 2 😕

Getting the "right" answer for the test input, but being denied on my actual input

crikey

it's a good one

yeah, I need practice with trees 🙂

I managed to get the correct solution partially "by hand", now I'm going back to finish the code

to part2 that is

got it but ... but what a mess lol

"Elapsed time: 3.052496 msecs" ... quick though

heh, mine's about 3x slower

but I'm OK with that

ah, input probably different haha

good point

can you send me your input private message?

i'll give it a whirl

https://bitbucket.org/balefrost/adventofcode2017/src/b2cef87b589ce1c94998afc5aeefe9b95da164a3/resources/day7_input.txt?at=master&fileviewer=file-view-default

also works 😜

okay. I think I'm going for the most baroque solution

Today's problem with DataScript + ex-info: https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2017/day07.clj

ooh nice!

Solved the problem, but have to clean up the code. Also used ex-info 🙂

https://github.com/minikomi/advent-of-code/blob/master/src/advent/2017/day7.clj here's my loop-de-loop solution

I bet there's a good way to use some kind of walk here

ah -- tree-seq was what i wanted

FWIW, my code for day 7: https://github.com/borkdude/aoc2017/blob/master/src/day7.clj

I discovered tree-seq and went crazy with it on my refactor hahaha

To keep it sustainable, I’ll try not to think about this puzzle and to tweak things all day 😉

yeah, you know how it is when you find a new tool though 😉

right 😉

I had a very bad night sleep so I solved part 2 almost by hand.

This is one I would like to go back to and see how trees work in clojure!

this is mine: https://repl.it/repls/KaleidoscopicOrangeTragopan

it’s ugly and I forgot about tree-seq existence

but it seems to work 😄

my goal with these is to arrive at the solution asap, without too much tinkering with performance and algorithmic elegance

Well that was the first actual challenge of this years calendar for me

Getting to try some libs that make it easy to solve the problems can be a good value add too. Working on last year's problems, I've been able to use Clara Rules for example

Looking through your datascript solution now, never applied datascript or datomic to any advent problems yet

Frankly, for this problem, DataScript turned out to be more overkill than I hoped.

still, quite comfortable for representing graphs.

I thought I would need a delay construction like with 2015's day 7, but this problem didn’t require it because of the regularity in the graph

nice viz of today: http://raevnos.pennmush.org/images/day07.svg

Fun useless fact: both part 1 and 2 run at about 6.8 ms (using criterium)

All you needed to parse this one was clojure.edn/read-string and destructuring (SPOILER in thread) 🙂

[[name [weight]
    & [arrow & names]]]

I like what thegeez did with the underscore for the arrow, to emphasize this is just a separator

My day 7 solutions are up https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_07.cljc

Nice parsing approach @borkdude I like it!

@mfikes Ah, set/mapinvert and oh yes, .indexOf

@mfikes Nice solution again!

I too had difficulty with part 2, trying perhaps 3 incorrect solutions until I figured out what was needed. And I did that part by hand, and backfilled the code 🙂

This year my extra challenge is to finish before coffee, so I wasn’t too concerned of making it the most beautiful

has anyone tried an approach with inverting the whole tree?

I don’t know about inverting the whole tree, but I keep a map of name -> ancestors and I’ve inverted that one in the second part

in part 1 i iteratively pruned off all leaves and references to them until only the root is left

right, well that’s essentially inverting it i guess

in part 1 I simply found the name without any ancestors

that’s simpler

set/difference as mfikes did

didn’t think of that

the puzzles publish at 7am local time 😅

local time, really?

for me part 2 is an ugly solution with println which kinda works like throw in some of the other solutions

i rewrote it to use reduced but it’s uglier than the throw variant

yeah, exceptions really helped me too 😉

ex-data ftw

sometimes that’s really nice for an early return

For me, I started with reduced for early return, and then went with some

i’m hoping to try a solution with walk

can you explain more?

did you get rid of the reduced and replaced it with some, or used both?

(let [[w tops] (get tower root)
        top-res (group-by #(find-unbalanced tower %) tops)]
    (or (some (comp #(when (reduced? %) %) first) top-res)

but I haven’t spent much time trying to make it prettier

since in the morning I wasted around 20 minutes because my parsing regex was using (....) for the name part since in the test input all names were 4 chars long

and I thought I had an error in the solution itself which I couldn’t find… until i fixed the regex to be ([^ ]+)

I started by reduceing over the data, but I had a nil (and ignored) accumulator, and had it stop with reduced when it found the unbalanced bit. I then took this reduce, and took the accumulator out of the reducing function, and essentially turned it into a predicate for some. Example:

(reduce (fn [_ x] (when (odd? x) (reduced x))) nil [2 4 2 7 2])

(some (fn [x] (when (odd? x) x)) [2 4 2 7 2])

I'm curious about people using Spec to parse this one. Digging through the solutions now...

I found spec a bit overkill for this one

Yes, I like your destructuring

haha, even using the mapping from "(20)" to 20 by first 😉

or (nth 0) is what destructuring is using

Yes. I couldn't figure out how to get Spec to do that for me.

Sometimes things just map co-incidentally well to edn

Hmm. A lot of silver stars right now. I wonder if that is normal for this time of day.

If you have kids and have to start early at work, I can imagine this is not something you do on the bus

Yeah. Perhaps part 2 is challenging. I found the spiral more challenging.

I found this one more challenging, but when I found out about the squares at the bottom right, I felt really dumb

Yeah, I'm not like Gauss. I would have started adding 1, 2, 3...

Ulam’s spiral, it’s a thing

Yep, Ulam is what immediately came to mind for me as well 🙂

Never heard of it before. These are not typical problems you run into in day to day coding

But now I love it. Will never forget Ulam again 😛.

Do the AoC problems get progressively more difficult over the month?

(Like 4Clojure?)

I hope not. 😛

@mfikes @borkdude From what I saw in AoC 2016, they do get more difficult 😛

I recall some of the 4Clojure problems getting into the 4-hour range near the end

(only did a subset of AoC 2016)

Interestingly, if you look at tentamen's part 2 solution (https://github.com/tentamen/adventofcode/blob/master/src/adventofcode2017/day7.clj), you can see that the input resulted in the unbalanced node being at the root of the tree, and if you are lucky with such a data set, you can skip some coding. (If I try that code on my input, it exhausts the stack somewhere in it)

Since we've been talking a lot about performance lately: I've been working on problem 23 of AoC 2016, in which performance ends up being rather critical. (The problem is to implement an interpreter about a very basic assembly that self-modifies code: https://adventofcode.com/2016/day/23) I first did a "Clojure-idiomatic" solution, with immutable state and multimethods (https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2016/day23.clj#L44). Then I saw it tooks at least 30min to run on part 2, and did a second version that uses more primitive Java stuff (arrays, primitive, enums): See https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2016/day23.clj#L165 and https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/java/aoc2016/Day23.java The second version turned out to be about 100 times faster (16 seconds instead of 20 minutes).

Thought people might find this interesting

Yeah, @val_waeselynck it seems like this assertion might be true: "If you solve any problem with Clojure, you can come up with a succinct, maintainable, readable solution. If you need perf, there is often an order of magnitude or more available by switching to lower level constructs, and you can often get away with going down that path for the perf-critical portion of your code."

One a large project I was on recently (where overall perf was critical), it felt like 80–90% of the code could be Clojure, and the rest could still be "Clojure", but really Java in disguise.

I think this assertion is true for the ClojureScript compiler, in a sense. Most of it is normal code, but the hot spots have been optimized in ways that deviate from "normal"

@mfikes Totally agree with that. It should also be noted that even if I had started with the Java thing, it would have taken me more time overall to debug it and run it, given the time it took me to debug it 🙂 (granted, that may be because my Java is a little rusty)

Also, lots of the highly-performant and desirable algorithms that were invented in the 60s and 70s heavily rely on mutation. Perhaps that caused a lot of what I saw when working on the large project.

However, I saw Martin Odersky say in a talk that a compiler typically has no hot spots - but that may be more true of compilers that have to do a fair amount of static inference

(Literature is thin on functional algorithms.)

Hmm. Very odd. The ClojureScript compiler seems like any other program to me. It has bits that are very hot compared to others. Martin is a genius so perhaps I'll dig up that talk.

@mfikes I would argue SQL query engines are examples of highly-performant functional algorithms - i.e they yields highly performant programs that manipulate only immutable values

Good point. I wonder if they are functional on the outside but inside it is like "transient city"

I believe they totally are transient inside - but it's a good testimony that being declarative makes a lot of room for global optimizations

The virtual DOM is another such example

This entire subject is, of course, important. If it weren't for the availability of these tradeoffs, you really couldn't use Clojure for a large class of problems.

I think it was this one https://www.youtube.com/watch?v=WxyyJyB_Ssc

In other words, if you buy into using Clojure, I think you have to accept that for parts of your program, you can't insist on the ideal Clojure approach. (Unless your problem has no perf aspects, of course.)

@mfikes about the input, I checked if I wasn’t just lucky with my input so I took yours: https://github.com/borkdude/aoc2017/blob/master/src/day7.clj#L111

Yeah, for tentamen you can see that part of the code has a comment showing that the root is where the unbalanced node is. Then the remainder of the code leverages that fact. Fair.

@mfikes I even find that Clojure can be a more elegant solution to some problems in the high-performance space, what with macros and the runtime compiler as zero-cost abstractions

yeah, or take Om vs React being faster due to immutable state

Definitely: Here is another effect I've seen. Since it is so damned easy to change Clojure code to do something in a different way, it is often feasible to explore different approaches and end up with a faster solution than if you were working in Java.

If you were in Java, you get calcified in an approach quickly.

Time is money. If you can't explore alternatives you often have to accept the perf you have.

@mfikes Funnily, you could say that Clojure programmers are to Java Programmers what JITs interpreters are to AOT compilers: the first start very quickly and spend a little time optimizing the critical parts based on experience, the other ones start slowly and spend a lot of time speculating on what is going to be critical (and being pessimistic about it)

Think about the extreme of programming in machine code. Once you've solved a problem, you are pretty challenged to try a different approach, no matter how fasts your machine code runs.

This has led to a philosophy: Develop in the highest-level programming paradigm you can find that also affords you the opportunity to delve lower when needed.

Breadth first

Also, when correctness isn’t an issue (you want to research solutions first, handling all edge cases is not a problem) then types can get in the way a bit, where you have to be explicit when you don’t want to be

@val_waeselynck I like your JIT to AOT analogy

Also, the REPL helps a lot in this

Exactly. The fact that ClojureScript can be thought of as a compiler is the wrong way of thinking of it, IMHO. The best way to think of ClojureScript is just as a Lisp, but with a mode that can be AOT'd to produce a small artifact when you really need it.

@borkdude totally. Being able to use Criterium and Tufte on the fly helps a lot when optimizing stuff

tufte… hmm, never used it before. @mfikes I see it’s crossplatform…

@mikelis.vindavs I use walk for today's problem: https://github.com/thegeez/clj-advent-of-code-2017/blob/master/src/advent/day7.clj#L81

That was like slogging through mud. I posted it, only because I want to be able to look back in the future and say "Oh, my! I have improved!"

I don't even want to look at the other solutions yet. I feel like I need to keep pounding on it.

And speaking of datomic and databases, Vik Fearing has been solving them using postgres: https://github.com/xocolatl/advent-of-code-2017

I’m surprised.. for few (3) elements, maps seem faster than vectors

that is, mapping to

{:id     name
     :weight   (parse-int weight)
     :children (some-> top (str/split #", "))}))

Any different when using (get x 0)?

I’m using destructuring for both, didn’t try get or nth

@grzm how are you profiling?

I'm not, for the most part.

I'm trying to focus on habit at a time. And in this case it's been transducers and cljc. It's too easy for me to yak shave.

@grzm I’d be happy to throw it against criterium if you have the full snippet

Is this in reference to my "mud" comment? Or perhaps you mean @mikelis.vindavs? The performance of mine was pretty good: 78ms iirc.

Ah sorry. I meant @mikelis.vindavs 🙂 about the 3-tuples

just (time (dotimes [_ 1000] (solve)))

That may not render realistic results

And when I did a bit of refactoring, the mud cleaned up a bit. I don't like throwing to get a result, but that's what I ended up doing.

@grzm Me too. I don’t see that as a problem. Could easily refactor it, but I find it a creative way of solving the problem 🙂

Try with criterium and then quick-bench

https://github.com/borkdude/aoc2017/blob/master/src/day7.clj#L111

https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day7.clj

an application of creative destruction 😉 shows my bias with respect to throwing: I'm inclined to view it as something negative, rather than the tool it actually is.

I’ll try your suggestions , thanks

Detecting an error is fine with throw/catch and that was what the puzzle was about 😉

True!

Also think I applied destructuring as deeply as I ever have: https://github.com/grzm/advent-of-cljc/blob/master/src/main/com/grzm/advent_of_code/advent_2017/day_07/part_2.cljc#L17

Three levels deep. Once you're there it's revealing a pretty specific solution, but it's cool that destructuring works so robustly.

How do you know the common-weight is in the first spot there?

I'm grouping by the tree weight, so the keys are the weights. Given the constraints of the problem, I know there's only going to be one that's an odd tree weight, so everything else is going to have the same tree weight. Then the sort-by transforms the map into a sequence of two vectors, odd-tree-weight first.

@mikelis.vindavs I was a little surprised as well when I changed my solution for yesterday to represent banks of memory as integer-indexed maps instead of vectors, and it ran slightly faster. I did not make this change for perf reasons, but so that the code would be correct when using (merge-with + ,,,) Here is the revision I'm talking about if curious : https://github.com/mfikes/advent-of-code/commit/9a178036eeb2c39b168712fed3388007217933ea

It's kind of obscured by the destructuring, but that let only has a single binding in it.

ah, missed that, I thought it was the argument to the function… getting tired 😉

Where are you at?

benchmarked with criterium, same thing — the difference is small, but still there

I'm in the US midwest.

Europe, Netherlands

but what’s even more interesting that maps vs vectors is the fact that for the 1st part of the problem

a set difference approach is slower than an iterative pruning one

that is, https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day7.clj#L25-L48 is faster than https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day7.clj#L77-L82

I've been staying up and starting AoC at 11PM my time. Not the best to start working on a puzzle, especially ones like this one. Lots of little mistakes getting in the way of getting to the solution.

I can’t wrap my head around why that would be true. Is set/difference slow?

Anyway, thanks for your evangelism wrt AoC! It's made it more enjoyable for me.

We may actually be seeing completely different effects, since mine is in ClojureScript. (I don't know JavaScript that well, but it seems like arrays are integer-indexed maps in a sense anyway, at least until the optimizer does something about them.)

🙂

I've never heard anyone suggesting that set/difference should be avoided for perf reasons.

the difference is pretty small, but in the other approach, I’m iteratively - removing nodes that have no children (`filter + into {}`) - removing references to those nodes (`map + filter + into {}`) until there’s only 1 entry left which seems like a ton more work than 2 map + set difference

is there a way to load a leiningen project in cljs? i have planck installed but am not very familiar with it

also I suppose io/resource isn’t implemented in cljs

@mikelis.vindavs You can run lein classpath to spit out a classpath, and Planck -c to take a classpath

Planck has a <http://planck.io|planck.io> namespace that defines resource. I've been using it: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_05.cljc#L7

To be honest lein classpath dumps out a lot of stuff you may not need, so I often manually specify the classpath, and there is -D sugar that Planck and Lumo have to expand to existing deps in your local Maven repo: http://planck-repl.org/dependencies.html

thanks, I’ll try that

Yeah, just take a peek at my repo https://github.com/mfikes/advent-of-code to see how I have it set up to run both Planck and Clojure with one source tree.

PureScript solution: https://github.com/krisajenkins/AdventOfCode/blob/master/src/Year2017/Day7.purs

Wow. Hefty import list. Wonder if that is normal in PureScript.

Most of my Clojure solution namespaces are about the same size as that import list

_total = _Newtype <<< prop (SProxy :: SProxy "total")
 let childrensTotals = split.right ^.. traversed <<< _total

I Like how Kris came to the same spot where the last bit of code wasn't necessary (you could do the last bit by hand faster than writing the code for it)

Yeah, but I want my part-2 function to always give the answer.. it’s part of my implicit contract

Maybe I have to write a protocol for it 😉

What’s a better way for this:

(defn find-by-val
  [m v]
  (ffirst
   (filter (fn [[k v’]]
             (= v v’))
           m)))

Could have used map-invert, but you’re never sure if the map has duplicate values

@borkdude If you want early termination and nil is not a concern, this seems to read nicely

(defn find-by-val
  [m v]
  (some (fn [[k v']]
          (when (= v v')
            k))
    m))

I’m using

(defn find-where [pred coll]
  (some #(when (pred %) %) coll))

Hmm. Maybe they both produce the same result, even with nil in the map as key or value

ahh but that’s sequences not maps

first + filter is also early termination, but yeah, some is also nice

it’s unfortunate this isn’t in core

I tried .indexOf but this time it didn’t work 😜

Nope, lein findfn "{:a 1}" 1 :a, nothing 😉

Ahh, right yeah ffirst / filter is indeed lazy

@mfikes I was there, too (with you and Kris). I had a prn stuck in my recursive search function which printed out the unbalanced nodes. Did that by hand, then went back and finished the code.

Makes me think there's something getting in the way of me using the machine to explore the problem space. Either practice, or tooling.

Or technique (which is coupled with practice)

busy day finally got my pushed: https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day07.clj

now to read the chat log and see whats up ...

@bhauman Creative, rand-nth, just start at some random node in the tree: https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day07.clj#L30

(time (part-2 data)) 1864, is that milliseconds — or probably the solution 🙂

yeah the solution

@borkdude our data setup is spooky similar

ok, enough yak shaving for today: https://github.com/ChrisBlom/advent-of-code/blob/master/src/adventofcode/2017/day07.clj#L54-L84

@chrisblom Ahh, you got away with calling set/difference with a non-set smaller 2nd argument. For example this works (set/difference #{:a :b :c} [:a :b]) while this doesn't (set/difference #{:a :b :c} [:a :b :c :d :e])

ow, thats nasty

pretend you did not see that

Hah. I can't unsee it.

i forgot how wonky clojure.set functions are for a moment

@bhauman indeed, great minds alike 😜

that’s a beautiful solution!

but does it assume that the weight will always need to be adjusted up?

hmm, yeah, thought that was ok, but on second thought its probably not

just got lucky with my input

I found that getting the “odd one out” was surprisingly complicated

Yeah. This is mine, but I’m sure there are other solutions:

(defn unbalanced-balanced
  [vals]
  (->> (frequencies vals)
       (group-by val)
       sort
       (map #(second %))
       (map #(ffirst %))))

I went with a construct like

((set/map-invert (frequencies [2 2 17 2])) 1)

I wanted both numbers in fixed order

Yeah, I needed both as well, went with (.indexOf [2 2 17 2] 17) for the second bit

.indexOf is something I don't often reach for. I take it it's available in cljs?

fixed it: https://github.com/ChrisBlom/advent-of-code/commit/88bfa7a17e674ddeb3eeeeec84889c3a0c8b30b0

@grzm Yes, but attempting to formally address that with this proposed page https://github.com/mfikes/clojurescript-site/blob/c552daa145ce7005446fa315f042d82ddc4d51f8/content/reference/javascript-api.adoc

Actually this works too:

(defn unbalanced-balanced
  [[a b c]]
  (if (= a b)
        [c a]
        [a b]))

much simpler 🙂

That is nice

But what if you call it like (unbalanced-balanced [2 2 2 2 17 2])

ah crap

I think we do know there are at least 3 items, because if there were 2 it would violate the constraint that "exactly one program is the wrong weight."

yeah, that was my thought too

Maybe something like the triplet comparison can yield an answer though.

Maybe a recursive version of that somehow?

Maybe partition and then moving over those

This might be correct

(let [[a b :as all] (sort [2 2 17 2])]
  (if (= a b)
    (last all)
    a))

^ Inspired by @borkdude’s comparison

Somewhat ugly but fast:

(defn unbalanced-balanced
  [[a b c & nums]]
  (let [[balanced maybe-unbalanced]
        (cond (= a b) [a c]
              (= a c) [a b]
              (= b c) [b a])]
    [(some #(when (not= balanced %) %)
           (cons maybe-unbalanced nums))
     balanced]))

Nice

In fact, in the third condition, we know for sure that a is the unbalanced one, but I didn’t want to write a special case for that

The computational complexity of this game https://www.youtube.com/watch?v=Sm-zWDaoCtI

Another version, more optimized:

(defn unbalanced-balanced
  [[a b c & nums]]
  (let [find-other (fn [v nums]
                     (some #(when (not= v %) %)
                           nums))]
    (cond (= a b) [a (find-other a (cons c nums))]
          (= a c) [a (find-other a (cons b nums))]
          (= b c) [b a])))

Something is wrong maybe, because I don’t get the right output

oh yes, wrong order of returned numbers, but apart from that it should work

anyway, in theory this should be faster, but in reality, I get 7 ms instead of 6 ms… this is BS 🙂

moving the function to its own defn works

Final call for “the odd one out”:

(defn unbalanced-balanced
  [[a b c & nums]]
  (cond (= a b) [(some
                  #(when (not= a %) %)
                  (conj nums c))
                 a]
        (= a c) [b a]
        :else   [a b]))