Fork me on GitHub
<
2021-02-18
>
Jeff Evans00:02:19

Is that significantly faster than using a transient vector with `assoc!` ?

Phil Shapiro00:02:07

No idea about using assoc! I did try a few things on the way to aset/aget but they were too slow. If you want to try it out, my code is here: https://github.com/pshapiro4broad/advent2020/blob/main/src/day23.clj

Max Deineko15:02:54

My solution for day 23 runs in abount 9s with int-arrays, 13s with transient vectors, 18s with vanilla vectors here. fwiw & hth: https://github.com/next-mad-hatter/adventofcode/blob/master/src/aoc_2020/day_23.clj (transients) & https://github.com/next-mad-hatter/adventofcode/blob/master/src/aoc_2020/day_23_inplace.clj (int-arrays)

Jeff Evans16:02:24

fascinating. thanks for sharing!

pavlosmelissinos17:02:00

I really struggled with day 7. I tried to solve it without recursion. Modeling the data into a structure that made sense to me was kinda hard but was nothing compared to coming up with the ugly, imperative code that did the actual computation 😛(inspired by the topological sorting algorithm; I used 2, or maybe 3, atoms). It's not public yet but I'll probably put it on gihub as soon as I get a little bit further. 1. Any of you come up with a pretty non-recursive solution? 2. The recursive solution feels much more natural to me, so I've also been wondering: why is recursion so frowned upon and more or less considered "inferior" to an iterative approach? I understand that in some cases it's hard to understand but in this case I really don't see any reason to avoid it.

Max Deineko20:02:05

One should take advice from people who consider recursion inferior with massive grain of salt afaiac 😉 Fwiw, or mayby luckily, this (it being frowned upon) had never been my experience. Which isn't to say recursion is equally useful in every programming language -- not every language supports tco, and even less support unlimited recursion in general. But if one wants to avoid mutable state there's no way around it.

Jeff Evans17:02:44

AFAIK, the only non-recursive approach to topo sorting is to use a stack and do DFS, right? I have no clue how that would work in idiomatic Clojure. This is one of the top hits on Google, and it’s using recursion: http://hueypetersen.com/posts/2013/06/25/graph-traversal-with-clojure/ The examples here are also using recursion: https://github.com/life0fun/clojure-idiom/blob/master/graph.clj

👍 3
pavlosmelissinos18:02:34

Indeed, stack + dfs is how I did it and it's probably the most unidiomatic thing ever written 😂 thanks for the response and the links 🙂

Max Deineko19:02:41

If you have some priority queue implementation then topological sort can be written as rather simple "loop" (whether it is expressed recursively or not is another matter somewhat)

Jeff Evans20:02:31

true, the pseudeocode on the Wikipedia article does just that

Max Deineko20:02:51

From what I've heard, this year's aoc was a bit easier than some previous entries. I think I spent most time on (and had most fun with) day 11, seeing how far I could speed it up. Second would probably be day 23, trying out and comparing different vector types. The part I enjoyed the least was probably the last part of day 20, was a bit too long for me. And day 15 I cheesed, didn't feel like doing it at all 🙂

Phil Shapiro21:02:06

Was that day 15 or 13? Because day 13 was a really hard one for me. And I agree day 20 part 2 was a lot of work. Most of the other days weren’t that bad. Overall it seemed easier to me than 2019, which I got about 1/2 way through, or 2018, which I also didn’t finish.

Max Deineko21:02:27

I skipped implementing day 15. For day 13 I had to dust off and look up some long forgotten math, but coding it wasn't that bad.

Max Deineko21:02:42

2020 is the first aoc year I took time to solve all problems (but not in december :)), only did a couple from 2018 before that, so cannot myself comment on difficulty compared to previous ones, only hearsay

Max Deineko21:02:01

of course, the difficulty is somewhat subject to variation depending on which building blocks of the solutions one is willing to take from libraries -- 2020's days 18 and 19 would have definitely been more work without instaparse 🙂

Phil Shapiro21:02:39

I don’t really know clojure, doing advent2020 was my first use of it so I didn’t know about instaparse, although I did look at it for day 18. I ended up doing something cheesy with regular expressions. I’m sure using a proper parser would’ve been cleaner.

Max Deineko22:02:07

Ah, similar story here :) Took aoc as opportunity to practice clojure, whenever people mentioned libraries here, put them on my to-check-out list..

Max Deineko22:02:24

I guess some would only consider implementing a complete parser to be proper solution.. But that's the nice thing about aoc, only you get to set your goals and constraints :)