Fork me on GitHub
#adventofcode
<
2017-12-20
>
minikomi01:12:45

I never knew you could use case with a list! That’s useful for sure

minikomi03:12:03

adjusted mine to use my new knowledge.. list-condition case and trying out cond->

Miķelis Vindavs04:12:53

Wow, that’s interesting behavior with get-in and cljs. I wonder if that’s “undefined behavior” territory or a bug

dyankowsky05:12:58

I'm not sure how I feel about my solution to tonight's problem

dyankowsky05:12:37

I though about it and came up with two probablistically correct answers, and got the right answer in both cases, but I don't feel like I "solved" the problem

dyankowsky05:12:24

but hey, I finally got points on the global leaderboard, so I guess I'll take that 🙂

minikomi05:12:15

congrats! bit stumped on this one

dpsutton05:12:34

for day 13 did anyone do a sieve of eratosthenes type solution?

dpsutton06:12:36

ah cool. i've been slacking and catching up. it's quite elegant

dpsutton06:12:43

and fast. 1 sec versus 10 for me

dpsutton06:12:06

(comment
  (time (solve2))
  ;; "Elapsed time: 10507.820736 msecs"
  ;; 3870382
  (dotimes [_ 20] (time (sieve-method data/data)))
  ;; "Elapsed time: 1293.195798 msecs"
  ;; 3870382
  )

dpsutton06:12:03

i've ripped off your style of multi arity (solve1) and the data/data namespaces. thanks for that

minikomi06:12:15

man i have no capacity for visualizing this problem 😆

grzm06:12:18

@mfikes I'm not sure I'll be satisfied with your solution unless you also provide a 3D hologram displaying the collisions.

grzm06:12:28

Help me, Mike Fikes Kenobi. You're our only hope! 😉

grzm06:12:33

@minikomi Have you gotten part-1?

minikomi06:12:44

nope, maybe i'm overthinking it

minikomi06:12:55

trying to weed out the particles moving & accelerating away from the origin..

mfikes06:12:46

I’m not satisfied with my day 20 solution either @grzm — I had to fall back on what the AoC game allows 😞

grzm06:12:34

I hope it's clear that's a friendly jab 😉 Your solutions have really inspired me.

mfikes06:12:37

This problem definitely has a tradeoff of overthinking vs. pragmatism.

minikomi06:12:28

wayyyy overthought it hahaha

minikomi07:12:49

well, it's done. but.. what a squiggy way to solve it

minikomi07:12:52

I wonder if there's a way to fine-tune cider output .. or have it print to a terminal. Sometimes it gets reaaaaly slow.

Miķelis Vindavs07:12:11

today marks my biggest facepalm moment so far.. Took me almost 3 hours and writing a quadratic equation solver to realize that the velocities need to be updated before the positions

erwin09:12:07

I have a solution for today, but I am not sure if it is valid for all possible inputs ...

ihabunek10:12:45

i have a nice solution for part 1

ihabunek10:12:09

particles with the greatest accelleration will end up furthest away

ihabunek10:12:19

if they have the same accelleration, then those with greatest speed

ihabunek10:12:31

if they have the same speed, then those which are initially furthers away

ihabunek10:12:49

so if you sort all particles by absolute accelleration, then speed, then position from center

ihabunek10:12:02

and take the first one, that's the solution

ihabunek11:12:12

heh, just saw that @erwin does the same

mfikes12:12:27

Very nice. I was worried that this kind of solution might be susceptible to them setting up a slow moving constant-velocity particle that is far away but would cross near the origin. But I suppose, by the problem definition, even though that one might be close temporarily at some point far out in the future, over the long run, it doesn’t meet the definition. Analogy: That extra-solar body that just passed by, but was, for a short while closer than most of our planets.

mfikes12:12:14

I think your approach is fairly rigorous though.

mfikes12:12:38

Perhaps there is a similar argument to be made for collisions if you somehow compare the inter-particle accelerations, velocities, and positions to know you are done detecting collisions. Quadratic cost.

dyankowsky14:12:42

My reading of the problem was, in the limit, which particle ends up closest to the origin

dyankowsky15:12:23

I also cheated even more; I looked at my dataset and saw that there were no ties for smallest acceleration

dyankowsky15:12:47

for the collisions, I think you could do something like iterate until enough acceleration has accumulated into velocity that the initial velocity is negligible, and until enough velocity has accumulated into position that the initial position is negligible

dyankowsky15:12:01

that is, in the limit, the acceleration is all that matters - it will completely dominate the other two

dyankowsky15:12:03

I think there has to be some way that you could look at each particle in isolation and determine whether this has happened (within some tolerance) and, when that has happened, you know that any collisions that would happen would have already happened

dyankowsky15:12:18

maybe a better way to put it is that, while your particles all start out at various positions around the origin, going in different arcs, eventually those arcs become nearly straight lines as the accumulated acceleration dominates the velocity. And as time ticks on and everything gets further from the origin, you can increasingly approximate your system as "a bunch of lines all shooting out from the origin". Sure, they didn't all start at the origin, but once they get far enough away, it's sufficient to assume that they all started in the same place.

bhauman13:12:43

what format is the answer supposed to be in?

bhauman13:12:12

for part 1

Miķelis Vindavs14:12:13

index of the particle

bhauman14:12:31

oh gosh did they make that clear at all?

Miķelis Vindavs14:12:51

usually the expected answers are monospaced with a background

bhauman14:12:52

i thought that was a temp label

Miķelis Vindavs14:12:29

Picking 0 as the sample answer was perhaps not the best choice simple_smile

mfikes14:12:17

IMHO, they could have improved that aspect of the problem definition. (I say "they" assuming that Eric Wastl has play testers. Who knows?)

mfikes14:12:06

By the way, if my solutions tend to look inexplicably transducer heavy (without justification), it is because I'm working on keeping memory usage down when solving the AoC problems in ClojureScript. Background: ClojureScript doesn't have locals clearing. See http://blog.fikesfarm.com/posts/2016-01-15-clojurescript-head-holding.html With transducers you can sometimes work around this limitation. I'm working on https://dev.clojure.org/jira/browse/CLJS-2445, and for many of these problems (which involve reducing over the results of iterate) they become solvable in ClojureScript with a few MB whereas previously you can easily consume several GB.

mfikes14:12:13

A great example is this line, which is solved in an updated version of Planck in 155 MB (running CLJS-2445 changes), while the unchanged Planck can't effectively solve it unless it is tediously converted to a loop / recur: https://github.com/mfikes/advent-of-code/blob/a440f0ea8326f7ed2eea71270fbc7d4e6d0df1c1/src/advent_2017/day_17.cljc#L24

mfikes15:12:22

Actually, the unrevised Planck can run that code, but it takes 14 GB and about 2 minutes, as opposed to 155 MB and 7 seconds. A loop / recur is still faster for that arithmetic-centric problem, running in about 1 s in Planck, but I'd like to be able to work at the higher level of abstraction if it leads to reasonable results.

mfikes15:12:57

Wow, is physics / calculus sufficient for this problem?

mfikes15:12:58

I suppose it is a good enough approximation, given you have to approximate anyways.

mfikes15:12:37

And, using the distance formula leads to a very fast solution. Nice @bhauman

bhauman15:12:23

its only good enough for the first part

mfikes15:12:31

Ahh... good point

bhauman15:12:07

the second part relies on their slot based interpretation of time

mfikes15:12:08

The second part seems to converge more quickly for me

mfikes15:12:08

I still think a lot of participants are going to end up feeling unsatisfied by this problem, even though, logically, all you need to do to solve it is type in an answer that it accepts.

mfikes15:12:59

In other words, logically, anything you can do that leads you to the right guess is perfectly fine.

dyankowsky15:12:21

that's perhaps one of the more interesting things about AoC - it's not about code per se, but all the problems are problems where machine assistance is extremely useful

mfikes15:12:40

And, if you go down that path, I like @bhauman’s transformation to continuous math as opposed to discrete

bhauman15:12:44

I spent some time "remembering" (i.e googling) that math

mfikes15:12:43

Yeah, @bytecrafter part 2 of day 7 seemed to be initially solved by many participants half via code with the "last mile" by hand, then backfilling with the correct code

mfikes15:12:16

That one was strange in that it was actually easier to do it by hand than to write the code to do the needed calculations.

dyankowsky15:12:32

yep, I was one of those on day7

mfikes15:12:00

If you factor in that part of the game is to beat the clock, these kinds of problems are appropriate.

dyankowsky15:12:28

that's also one of the things I like about doing these in Clojure - even though it's not my most comfortable language, doing stuff in the REPL is great

mfikes15:12:03

Speaking of that, I liked the 4Clojure aspect where part of the problem was to find a solution that was sufficiently efficient for it to be solved before the 4Clojure timeout kicked in.

dyankowsky15:12:12

it kills off your process if it runs too long?

dyankowsky15:12:23

(or request or thread or whatever)

mfikes15:12:32

Yes. Oftentimes you will have some code that actually solves it, but it takes, say 45 seconds.

mfikes15:12:00

I don't recall the timeouts, but it may have required your code to run on their server within, say 30 seconds

mfikes15:12:12

If you get really frustrated, you can "cheat" by writing functions that produce the correct answers instantly, once you know what they are.

mfikes15:12:31

But, then you defeat the learning process 🙂

Miķelis Vindavs15:12:13

Part2 can be solved in a non-iterative way using quadratic equations too

Miķelis Vindavs15:12:58

two particles collide if 1/2*a1^2 + v1*t + s1 == 1/2*a2^2 + v2*t + s2

Miķelis Vindavs15:12:56

^that’s for one dimension, where a is acceleration, v is velocity and s is the inital position solve for t and get the time when it happens

Miķelis Vindavs15:12:15

do that for all 3 dimensions, and if the ts match, the particles collide at that time

dyankowsky15:12:51

to match the iterative approach, t must also be an integer

Miķelis Vindavs15:12:55

that’s still O(n^2) though, where n = number of particles

dyankowsky15:12:27

the iterative approach allows particles to "pass through" each other as long as they do so in the middle of a timestep

Miķelis Vindavs15:12:01

yep, and also need to account for the fact that velocity is “updated” before position

Miķelis Vindavs15:12:25

I guess by doing v1*(t+1) instead of v1*t?

Miķelis Vindavs15:12:42

I have an unfinished and not cleaned up approach to it at https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day20.clj#L63-L89 It doesn’t work because it doesn’t account for the velocity thing

borkdude16:12:14

hmm, day 20, stuck at 1000 particles after 10^3,4,5 iterations..

borkdude16:12:05

can someone give me a hint after how many iterations you should expect collisions? 1? 10? 1000?

Miķelis Vindavs16:12:35

well, the first one start at 10-15 for me

borkdude16:12:45

ok, then I’m having something wrong then

borkdude16:12:05

Definitely…. still got part 1 right though… thanks!

borkdude16:12:53

ah, now they are colliding… phew..

borkdude16:12:40

aaaaand solved…. 😅

bhauman16:12:31

@mikelis.vindavs I don't think the equation solution for part 2 will work, I'm pretty sure we'd need a different position equation as

Miķelis Vindavs16:12:00

Now I’m intrigued simple_smile

ihabunek16:12:43

a friend of mine did part 2 quadratic equation solution in elixir, so it's possible https://gist.github.com/sasa1977/a35e87540669f32c28e3bd2b7698ca7e

borkdude17:12:41

I’m looking at @bhauman’s solution and instantly I remember my high school physics 🙂

mfikes17:12:57

Hah, I happened to have this lying around from a couple of months back when I was trying to explain some stuff to my son

bhauman17:12:17

the position function will work if you do (Math/ceil (* 0.5 t t))

bhauman17:12:14

this is for part 2

borkdude17:12:26

So for part two you could use some algorithm which checks if functions will collide for some interval maybe?

borkdude17:12:16

Not sure which one 🙂

borkdude17:12:34

You could solve equations for every pair

borkdude17:12:45

and if there is no solution, it won’t collide

mfikes17:12:31

If you get a closed-form solution (like what Bruce said), then take the difference between every pair, set it to 0 and see if beyond a certain t it can no longer be solved?

mfikes17:12:27

If you can find such a t that works for all pairs...

borkdude17:12:30

I didn’t read the whole thread. Will do so tonight. Have to make dinner now.

kaffein18:12:08

hey guys... I have had some trouble figuring out what was wrong with my day 5 implementation! can someone tell me if I'm missing something from the following code snippet 😉 P.S : Clojure newbie here ...your eyes may hurt but I have to start with something I guess 🙂

kaffein18:12:24

thanks in advance

erwin18:12:40

@kaffein I think you should end with a (inc steps) on line 14

erwin18:12:13

the last step is also a step I would say

kaffein18:12:59

Thanks @erwin I will try that out ...though the unit test that I've run using the problem example seems to be okay

mfikes21:12:58

It make me feel better that it says "Both of these queries have shameful, arbitrary stopping points"

mfikes21:12:28

All developers hang their heads in shame for some reason for this problem. 🙂

fellshard22:12:05

It edges too close into math we're told we should know and don't really want to explore? 😛

fellshard22:12:24

We'd rather take the approach of 'make the numbers big enough we remove reasonable doubt'

borkdude22:12:58

When I encountered part 1 for a moment I thought, should I solve this more cleverly using Newton or …. meh, no, in part 2 they are going to ask for something ridiculous anyway, like how many times the sum of the coordinates were prime numbers in the first million runs