Fork me on GitHub
#adventofcode
<
2019-12-12
>
fellshard00:12:52

Lotta folks don't dig the cpu simulators; they've always been my favs, and it's much more interesting to me now that he's using it to drive other systems. The integration aspect is its own set of neat challenges that he wouldn't have been able to put in a single day previously. The downside I can see is that it makes catching up very linear; skipping days isn't as simple this year as it was in prior.

rjray00:12:39

Yeah, I'd agree with you on the fun-aspect of integrating the sim with other systems. I only finally today got around to extracting the intcode "machine" into its own namespace and refactored my day 11 code to use the imported machine. Figure we've got at least 6 more days that'll use the machine, maybe more.

misha06:12:53

nothing wrong with cpu simulator except too convoluted and verbose description of one, spread across 3 or 4 days, and like total of 15 pages of text. Even changes in requirements are not that bad comparing to this.

misha06:12:22

any part 2 ideas?

rjray07:12:35

Definitely can't brute-force it. I ran out of memory on the second test data set (and I have 16Gb of physical memory). Gonna sleep on it and see if I can think of something in the morning.

mpcjanssen07:12:22

my velocities keep blowing up for part 1

Roman Liutikov08:12:02

Guess the name of the task itself is known problem with existing solutions

misha08:12:20

I just read reddit for hints today opieop

misha08:12:14

slow though:

p1 input   "Elapsed time: 35.301894 msecs"
p2 sample1 "Elapsed time: 2.732321 msecs"
p2 sample2 "Elapsed time: 293.312654 msecs"
p2 input   "Elapsed time: 11600.599702 msecs"

misha08:12:48

spoiler inside

misha08:12:40

total cycle can be predicted from cycles of each of the axes, which are much shorter. Think frequency of a wave which is a summary of sine waves with different frequencies

mpcjanssen08:12:29

ah was almost there, needed to split by axis too

mpcjanssen09:12:12

now some primw factor voodoo

mpcjanssen10:12:28

am stuck example 1 works with my code exampen2 and my puzzle give way too high answers

misha11:12:40

another spoiler: it is not (* x y z)

mpcjanssen11:12:30

you need to check when the whole x axis and vx isnrhe same for all moons

mpcjanssen11:12:47

and you need some prime factor work indeed

mpcjanssen11:12:49

main observation. The equations of motion in each axis are completely independent

mpcjanssen08:12:18

not for me 🙂

mpcjanssen14:12:27

interesting. Changing the moons from maps to records reduces the part 2 runtime from 40 to 30 seconds

mpcjanssen14:12:34

Any other performance tips?

yuhan15:12:01

You don't actually have to find the prime factorizations of each axis, just their lowest common multiple

yuhan15:12:37

which you can use Euclid's algorithm for - LCM(a,b) = a*b / GCD(a,b)

yuhan15:12:36

although I don't think that's the bottleneck - my solution for part2 runs in 680ms

mpcjanssen15:12:57

Thats indeed not thw borrlenexk

mpcjanssen15:12:19

It was a fun exercise though

mpcjanssen15:12:56

how do check if you reached the initial state?

yuhan15:12:28

I just use = on a seq of [p, v] tuples

yuhan15:12:28

looking at your notebook, it's hard to read because of all the funky indentation

yuhan15:12:54

I've only played around with Clojure notebooks for a while before, but the Parinfer plugin was essential for keeping some grasp on the parens: https://github.com/jelmerderonde/jupyter-lab-parinfer

yuhan15:12:27

your dv-ax function is simply compare

mpcjanssen15:12:50

my step is slow

mpcjanssen15:12:15

i am doing this on my phone so indentation is not the best

yuhan15:12:28

ah, that explains it

yuhan15:12:23

your addp is (mapv + p1 p2)

yuhan15:12:56

30s on a phone with Clojurescript might not be that bad after all?

mpcjanssen15:12:45

count on a lazy seq is slow?

yuhan15:12:48

count forces the elements of the seq to be realised

mpcjanssen15:12:10

if I remove the xount

mpcjanssen15:12:28

and add a doall, its much faster

mpcjanssen15:12:00

did you use recur or iterate?

mpcjanssen15:12:36

how do you know the number of steps?

yuhan15:12:09

iterate generates an infinite seq, I reduce over it and break using reduced when it cycles back around

yuhan15:12:06

Here's some of the relevant bits

(def input
  (parse "<x=14, y=9, z=14>
<x=9, y=11, z=6>
<x=-6, y=14, z=-4>
<x=4, y=-4, z=-3>"))
;; => ((14 9 14) (9 11 6) (-6 14 -4) (4 -4 -3))

(def test-input
  (parse "<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>"))
;; => ((-1 0 2) (2 -10 -7) (4 -8 8(3 5 -1))


;; * Part 2
(defn axis-step
  [pvs]
  (map (fn [[p v]]
         (let [nv (+ v (reduce (fn [acc [p']]
                                 (+ acc (compare p' p)))
                         0 pvs))]
           [(+ p nv) nv]))
    pvs))

(defn axis-period
  [ps]
  (let [vs (repeat 0)
        pvs (map vector ps vs)]
    (reduce (fn [cnt x]
              (if (= pvs x)
                (reduced cnt)
                (inc cnt)))
      1 (next (iterate axis-step pvs)))))

(for [ps (apply map vector test-input)]
  (axis-period ps))
;; => (18 28 44)

(util/lcm 18 28 44)
;; => 2772


(apply util/lcm
  (for [ps (apply map vector input)]
    (axis-period ps)))
;; => 282399002133976

mpcjanssen15:12:07

oww addp is just +

mpcjanssen15:12:35

ah and reduce for the count

mpcjanssen16:12:31

my phone is quite fast I am not much slower than the really fast solutions

misha16:12:45

oh yeah, I did not think to completely split the computation from for-all-axes-in-a-single-step into 1-axis-per-step

Average-user02:12:53

@UCPS050BV But why do you assume that the cycle will include the first configuration?

yuhan04:12:22

ah, I interpreted the puzzle that way and it worked out - wonder if I just got lucky?

yuhan04:12:10

Also I strongly suspect the equations of motion are time-reversible, which would mean that for any configuration to repeat, all the previous steps leading up to it would also have to be repeated

dmarjenburgh17:12:03

Finally one that required some puzzling 😃. I drew a graph of one of the moon coordinates that hinted towards a solution. https://gitlab.com/dmarjenburgh/adventofcode/blob/master/src/adventofcode/year_2019.clj#L277-314

Average-user17:12:25

adventofcode-clj-2019.day12> (time (part-2))
"Elapsed time: 2809.105945 msecs"
324618307124784

Mario C.23:12:42

I am working on Day 11 part 2 and I keep getting a weird drawing. Looks like a rabbit. I already set the first panel to white as per the instructions but still no actual word.

fellshard23:12:38

Hmm. I'd ask if there's something wrong with your turning implementation, but Part 1 should have rooted that out.

Mario C.23:12:46

This would be my turning function

(defn move-bot
  [[face [x y]] outputs]
  (let [[_ turn] outputs]
    (if (empty? outputs)
      (do (println "OUTPUTS EMPTY standing still")
          [face [x y]])
      (case face
        :north (if (= turn 0)
                 [:west [(dec x) y]]
                 [:east [(inc x) y]])
        :south (if (= turn 0)
                 [:east [(inc x) y]]
                 [:west [(dec x) y]])
        :west (if (= turn 0)
                [:south [x (dec y)]]
                [:north [x (inc y)]])
        :east (if (= turn 0)
                [:north [x (inc y)]]
                [:south [x (dec y)]])))))

misha07:12:49

you can leverage maps and vectors:

{:north [[:west  [dec identity]] [:east  [inc identity]]]
 :south [[:east  [inc identity]] [:west  [dec identity]]]
 :west  [[:south [identity dec]] [:north [identity inc]]]
 :east  [[:north [identity inc]] [:south [identity dec]]]}

misha07:12:47

and then (get-in m [face turn])

Mario C.16:12:39

Thats funny because I actually did this exact thing for another function

(defn get-input
  [[_ pos] grid]
  (let [color (get grid pos :black)]
    (get {:black 0 :white 1} color)))
Didn't think of using it for this! Good catch! :thumbsup:

misha16:12:21

you'll get diff-functions though, instead of calculated values, so there will be extra apply step