Clojurians Log v2

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

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

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

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

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

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

congrats! bit stumped on this one

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

@dpsutton I didn’t see one in Clojure, but Kris Jenkins appeared to do so: https://github.com/krisajenkins/AdventOfCode/blob/master/src/Year2017/Day13.purs#L44

Day 20: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_20.cljc

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

and fast. 1 sec versus 10 for me

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

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

man i have no capacity for visualizing this problem 😆

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

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

@minikomi Have you gotten part-1?

nope, maybe i'm overthinking it

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

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

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

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

wow

wayyyy overthought it hahaha

get it?

heh

lol..

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

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

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

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

https://github.com/ekroon/adventofcode2017/blob/master/src/adventofcode/day20.clj

my solution: https://github.com/ihabunek/aoc2017/blob/master/src/aoc2017/day20.clj

SPOILERS

i have a nice solution for part 1

particles with the greatest accelleration will end up furthest away

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

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

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

and take the first one, that's the solution

heh, just saw that @erwin does the same

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.

I think your approach is fairly rigorous though.

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.

what format is the answer supposed to be in?

for part 1

index of the particle

oh gosh did they make that clear at all?

I felt like they did https://www.dropbox.com/s/2uza02wl3jl469v/Screenshot%202017-12-20%2016.03.54.png?dl=0

@mikelis.vindavs shared a file: https://clojurians.slack.com/files/U89SBUQ4T/F8HD2895Y/screenshot_2017-12-20_16.03.54.png

usually the expected answers are monospaced with a background

i thought that was a temp label

gotcha

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

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

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.

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

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

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.

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

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

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

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

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

Wow, is physics / calculus sufficient for this problem?

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

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

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.

its only good enough for the first part

Ahh... good point

the second part relies on their slot based interpretation of time

The second part seems to converge more quickly for me

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.

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

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

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

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

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

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.

yep, I was one of those on day7

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

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

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.

it kills off your process if it runs too long?

(or request or thread or whatever)

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

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

interesting

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

But, then you defeat the learning process 🙂

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

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

^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

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

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

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

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

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

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

not sure

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

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

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

100

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

ok, then I’m having something wrong then

Could it be this? 😅 https://clojurians.slack.com/archives/C0GLTDB2T/p1513756271000087

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

ah, now they are colliding… phew..

aaaaand solved…. 😅

@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

oh shoot

Now I’m intrigued :simple_smile:

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

FWIW, my day 20, no fancy math involved: https://github.com/borkdude/aoc2017/blob/master/src/day20.clj

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

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

@mfikes uploaded a file: https://clojurians.slack.com/files/U04VDQDDY/F8JCEAZ4N/pasted_image_at_2017_12_20_12_07_pm.png

HINT

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

this is for part 2

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

Not sure which one 🙂

You could solve equations for every pair

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

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?

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

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

I did a numerical approach on day 20 as well: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day20.clj

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 🙂

@kaffein uploaded a file: https://clojurians.slack.com/files/U0DTAJS3Y/F8JDU6JF8/day5.txt

@kaffein uploaded a file: https://clojurians.slack.com/files/U0DTAJS3Y/F8H2PEBMF/day5.clj

thanks in advance

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

the last step is also a step I would say

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

In Postgres: https://github.com/xocolatl/advent-of-code/blob/master/Day20/script.sql

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

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

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

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

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

Wow: https://www.reddit.com/r/adventofcode/comments/7l42yy/day_20_with_calculus/