Fork me on GitHub
#adventofcode
<
2017-12-17
>
mfikes00:12:27

@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

val_waeselynck02:12:50

@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

thegeez17:12:22

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)

borkdude08:12:27

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

borkdude08:12:34

3 is the current position of s1. going 3 steps means going to position 0 whereafter 4 will be inserted.

borkdude08:12:27

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

nooga10:12:30

these puzzles…

nooga11:12:12

I have a solution that works with the example

nooga11:12:36

but doesn’t with 50M

nooga11:12:48

hah, I used wrong input 😂

orestis12:12:47

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

orestis12:12:06

Bah. Still too slow for my tastes.

fellshard13:12:15

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

fellshard13:12:42

Or, at least, to find a simplifying pattern

orestis13:12:05

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.

orestis13:12:43

I was looking for some mathematical properties, cycles and so on; but I found too many 🙂

orestis13:12:45

In my case, I found that 0 is always at the end; therefore the value I care about is always going to be first.

orestis13:12:19

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?

orestis14:12:48

BTW, some eval’ed comments there are stale; I was tweaking things in the editor a lot.

grzm15:12:07

They're looking for value (get buf 1)

bhauman16:12:47

well my second part should finish in 6 minutes

bhauman16:12:19

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

bhauman16:12:17

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

bhauman16:12:34

well the answer was correct at least

bhauman16:12:44

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

bhauman16:12:12

well that would have been easier, nice work @val_waeselynck

mfikes16:12:40

@bhauman Still, it is remarkable that you were able to come up with an imperative version that could solve it by brute force.

borkdude17:12:24

Mine runs in 2s 🙂

borkdude17:12:47

In part 1 I lost time because I thought you should run back and forth in the buffer instead of cyclic. Doh…

borkdude17:12:41

@bhauman how does yours even work? is this work parallelizable at all? (well yeah, supposedly, but I have to think about it)

bhauman17:12:27

I used a cyclical datastructure {a -> b, b->c} i.e. a circular linked list which allowed for fast insertion and lookups

bhauman17:12:13

not really paralizable

dpsutton17:12:17

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?

dpsutton17:12:50

ah nevermind. he found them on reddit

dpsutton17:12:59

sorry for the noise

bhauman17:12:02

no worries

borkdude17:12:06

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

mfikes17:12:56

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.

bhauman17:12:58

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

mfikes17:12:41

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

bhauman17:12:27

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

mfikes17:12:48

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

bhauman17:12:09

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

mfikes17:12:42

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

borkdude17:12:51

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

bhauman17:12:57

actually I didn't need to use a reducer

borkdude17:12:13

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

bhauman17:12:32

I thought the reducer would treat the range as an iterable

bhauman17:12:38

and not a lazy seq

bhauman17:12:02

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

dpsutton17:12:48

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

dpsutton17:12:12

was trying to find it online for him but no luck

dpsutton18:12:47

perfect! thanks!

dpsutton18:12:20

you'll make a flight of his much better.

bhauman18:12:21

@borkdude inputs?

mfikes18:12:00

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

bhauman18:12:06

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

thegeez18:12:43

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

borkdude18:12:17

@dpsutton Why am I sending a PDF if this page is public btw? https://adventofcode.com/2017/day/13

dpsutton18:12:53

because it only shows the first half until you solve it

borkdude18:12:08

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

dpsutton18:12:24

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

dpsutton18:12:31

and usually the second half is the more interesting half

borkdude18:12:04

Not in ClojureScript it seems.

mfikes19:12:52

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

bhauman21:12:38

so if I wanted range to be reducible?

bhauman21:12:58

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

val_waeselynck22:12:25

@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

val_waeselynck22:12:02

I do realize I'm totally over-engineering this btw 😄

bhauman22:12:48

@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?

val_waeselynck22:12:02

@bhauman that is correct, I'm relying on the fact that in my representation of the cyclic data structure, 0 has a stable position

mikelis23:12:15

@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

val_waeselynck01:12:41

@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

mikelis09:12:11

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

mikelis09:12:23

Actually I should probably try that :)

val_waeselynck22:12:05

Ah right, I guess I misunderstood the code then

mikelis23:12:58

the optimized log n exponentation part is nice, probably saves even more time if you know which index you need

mikelis23:12:25

yeah, mine still relies on finding the cycle period, with log n application that wouldn’t be needed.. very nice solution & explanation!

mikelis23:12:41

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