Clojurians Log v2

@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

Do you have any links to where I can read up on this? I understand how the cyclic nature would lead you to the right answer, but I'm not sure I see how we can assume the dance itself is idempotent.

Ohh, wait. Because the possible permutations operations are limited, there are far fewer than 1e13 operations that can be performed?

@fellshard re: your question, see this thread 🙂

@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

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

[[0 4 2 3 1] 4] ;; s2

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

o wait, I don’t have to go back and forth probably

Got it.

Solved.

https://github.com/borkdude/aoc2017/blob/master/src/day17.clj

these puzzles…

I have a solution that works with the example

but doesn’t with 50M

hah, I used wrong input 😂

My solution for part 1 is slow, no way it can scale to 50M…

Bah. Still too slow for my tastes.

It's another one that's asking you to dig into the math of it

Or, at least, to find a simplifying pattern

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.

They're looking for value (get buf 1)

well my second part should finish in 6 minutes

I'm finished with mine but again I'll have to wait for 6 minutes to pass to be sure

looked for patterns but just couldn't swing it, so I optimized the heck out of the data structure and the transitions

well the answer was correct at least

https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day17.clj

oh position zero has a special property that the rest don't have ...

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.

Mine runs in 2s 🙂

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

not really paralizable

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?

ah nevermind. he found them on reddit

sorry for the noise

cool!

no worries

@bhauman r/reduce applies the function in parallel over the sequence right?

nope

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.

@borckdude it can't as it needs the input from the previous iter

Nathan's approach also means you need not keep track of the current position, if I'm reading his code correctly.

@mfikes with a circular buffer you don't need to keep track of the last position

Nathan's code, for reference: https://github.com/armstnp/advent-of-code-2017/blob/master/src/advent_of_code_2017/day-17.clj

@bhauman Exactly. I didn't take that approach.

oh sorry,let me look at nathan's ...

The main idea is to rotate the representation so that the current position is always at the end of that representation.

@bhauman let me try it differently: what did you use reducers for specifically?

speed

actually I didn't need to use a reducer

can you elaborate? if there’s nothing to parallelize, what’s the speed gain?

I thought the reducer would treat the range as an iterable

and not a lazy seq

which it think is the wrong assumption, transduce would have done that for me

on second thought, could anyone email me the full page for day 13?

was trying to find it online for him but no luck

perfect! thanks!

you'll make a flight of his much better.

@borkdude inputs?

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

this is a good question, I'd like to know the answer as well

@dpsutton if you want an input: https://github.com/borkdude/aoc2017/blob/master/resources/day13.txt

ah thanks

@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

because it only shows the first half until you solve it

ah ok. and now he also has my outcomes + input, so that should do it.

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

and usually the second half is the more interesting half

@mfikes aren’t iterate results already reducible? https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Iterate.java#L15

Not in ClojureScript it seems.

Found this link: http://insideclojure.org/2015/01/18/reducible-generators/

Oh, cool @borkdude. Perhaps a patch could land in ClojureScript to make it behave like Clojure 🙂

so if I wanted range to be reducible?

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

got it

@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

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