This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2017-12-17
Channels
- # adventofcode (96)
- # beginners (49)
- # boot (3)
- # cider (3)
- # cljs-dev (3)
- # clojure (112)
- # clojure-austin (2)
- # clojure-greece (35)
- # clojure-india (2)
- # clojure-sanfrancisco (1)
- # clojure-spec (1)
- # clojure-sweden (1)
- # clojurescript (27)
- # cursive (4)
- # data-science (1)
- # datomic (33)
- # defnpodcast (1)
- # duct (2)
- # editors (1)
- # emacs (4)
- # events (2)
- # figwheel (4)
- # fulcro (4)
- # hoplon (29)
- # instaparse (1)
- # jobs (1)
- # keechma (4)
- # lein-figwheel (2)
- # om (1)
- # parinfer (4)
- # perun (23)
- # reitit (11)
- # shadow-cljs (8)
- # specter (23)
- # uncomplicate (16)
@val_waeselynck I did some quick research before solving it and read about the coordinate systems at https://www.redblobgames.com/grids/hexagons/ and found one that seemed to have a simple distance formula. I’m pretty sure that without having done this research it would have taken a lot of thinking to sort through this one. I went with cube coordinates, which seemed to be pretty popular. The solution for me ended up being fairly clean: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_11.cljc
@mfikes Cool blog! I did not have the option of doing that kind of research as I was on a plane, so I ended up working out some math that are a similar but slightly inferior approach to cube coordinates. I did have to sleep over the problem to come up with this, so definitely not a viable approach if I wanted to be competitive on AoC
I have a solution to day11 without using coordinates https://github.com/thegeez/clj-advent-of-code-2017/blob/master/src/advent/day11.clj (in the alternative for part 2 and 1)
Day 17: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_17.cljc
Hmm, after the state
[[0 2 3 1] 3] ;; s1
I expect it to be
[[0 4 2 3 1] 4] ;; s2
but the example gives
0 2 (4) 3 1
3 is the current position of s1. going 3 steps means going to position 0 whereafter 4 will be inserted.
My solutions for day 17: https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2017/day17.clj
I hang my head in shame; I had a limited time to solve this, explored some time looking for patterns, then in the end copied @val_waeselynck algorithm.
I was looking for some mathematical properties, cycles and so on; but I found too many 🙂
Here’s my exploration, warts and all if anyone is interested: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day17.clj
In my case, I found that 0 is always at the end; therefore the value I care about is always going to be first.
I’m not sure if this is what the requirements say; i.e. do they care for the first element after the value 0 or the element at the 0 position? Is it the same for all the inputs?
BTW, some eval’ed comments there are stale; I was tweaking things in the editor a lot.
looked for patterns but just couldn't swing it, so I optimized the heck out of the data structure and the transitions
https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day17.clj
well that would have been easier, nice work @val_waeselynck
@bhauman Still, it is remarkable that you were able to come up with an imperative version that could solve it by brute force.
In part 1 I lost time because I thought you should run back and forth in the buffer instead of cyclic. Doh…
@bhauman how does yours even work? is this work parallelizable at all? (well yeah, supposedly, but I have to think about it)
I used a cyclical datastructure {a -> b, b->c} i.e. a circular linked list which allowed for fast insertion and lookups
can anyone do me a favor? I'm behind, only on day 7. My friend is taking a flight from SF and wants to do days 10 and 11. Can anyone print those pages with both parts and the answers so he can work on them on the flight and email them to me?
One twist I really liked was Nathan Armstrong's approach of keeping the insertion point at the end of the actual collection representing the circular buffer, thus allowing conj
to be used to insert.
Nathan's approach also means you need not keep track of the current position, if I'm reading his code correctly.
Nathan's code, for reference: https://github.com/armstnp/advent-of-code-2017/blob/master/src/advent_of_code_2017/day-17.clj
The main idea is to rotate the representation so that the current position is always at the end of that representation.
I'm curious: Is there a technique that behaves like iterate
, but produces something that can reduce itself? The reason I ask is that when running the solutions in ClojureScript, the lack of locals clearing can be worked around by carefully using transducers. By way of an example, you can count this way without blowing out memory:
(transduce (comp (map inc) (filter odd?))
(completing (fn [c _] (inc c)))
0
(range 1e8))
@dpsutton if you want an input: https://github.com/borkdude/aoc2017/blob/master/resources/day13.txt
@mfikes something like this for reducible iterate:
(deftype Iter [f init]
clojure.lang.IReduceInit
(reduce [this xf xf-init]
(loop [state (xf xf-init init)
i init]
(if (reduced? state)
@state
(let [i (f i)
ret (xf state i)]
(recur ret i))))))
(comment
(into []
(take 10)
(Iter. inc 0))
)
@dpsutton Why am I sending a PDF if this page is public btw? https://adventofcode.com/2017/day/13
and he's on a flight so he could only see the first half. yeah. he's gonna get the answer himself he just wanted something to work on
@mfikes aren’t iterate results already reducible? https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Iterate.java#L15
Oh, cool @borkdude. Perhaps a patch could land in ClojureScript to make it behave like Clojure 🙂
OK I have explored the sources and I've got my head on straight now, range
does know how to reduce itself and this behavior is obvious from how fast it is
@erwin @orestis @nooga @fellshard Still having fun with Permutations Algebra, I reimplemented day 16 ("Permutation Promenade") without leveraging the cyclic nature of the dance at all, using exponentiation instead: https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2017/day16.clj#L320
I also added a more "literate style" guide explaining how it all works: https://github.com/vvvvalvalval/advent-of-code-2017/blob/master/src/aoc2017/day16.clj#L146
I do realize I'm totally over-engineering this btw 😄
@val_waeselynck am I correct in thinking that this day17 part 2 solution only works in the first position? I don't think it will work other positions as their positions are more easily disturbed?
@bhauman that is correct, I'm relying on the fact that in my representation of the cyclic data structure, 0 has a stable position
@val_waeselynck nice, looks like I came up with something similar https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day16.clj#L63-L78 Although I unfortunately don’t fully grok the math beneath it, I just experimented around until I confirmed my intuition
@U89SBUQ4T AFAICT the main difference is that in your solution, compilation consists of composing functions to avoid the cost of navigating data structures, whereas in mine it consists of compacting the steps into a concrete data structure - which is what enables exponentiation
Hmm it’s function composition only in the sense that mapping a vector of indices over a vector of indices is composition. I’m compiling the dance down to 2 actions - spin+exchange and partner. They could each be passed to exponentiate to get the nth result
Actually I should probably try that :)
Ah right, I guess I misunderstood the code then
the optimized log n exponentation part is nice, probably saves even more time if you know which index you need
yeah, mine still relies on finding the cycle period, with log n application that wouldn’t be needed.. very nice solution & explanation!
for example, I haven’t really gotten my mind around why the order of applying the spin+exchange and partner moves matters
(that is, (spins (partners state))
is not the same as (partners (spins state))
except at the cycle period