This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2017-12-20
Channels
- # adventofcode (140)
- # beginners (107)
- # boot (120)
- # boot-dev (1)
- # clara (13)
- # cljs-dev (9)
- # clojure (107)
- # clojure-argentina (5)
- # clojure-art (16)
- # clojure-dev (23)
- # clojure-greece (19)
- # clojure-italy (5)
- # clojure-russia (2)
- # clojure-serbia (3)
- # clojure-spec (27)
- # clojure-sweden (1)
- # clojure-uk (15)
- # clojurescript (134)
- # cursive (5)
- # data-science (10)
- # datomic (23)
- # duct (28)
- # fulcro (48)
- # garden (5)
- # hoplon (2)
- # instaparse (1)
- # klipse (7)
- # leiningen (8)
- # lumo (36)
- # off-topic (72)
- # om (4)
- # onyx (37)
- # perun (4)
- # re-frame (64)
- # reagent (86)
- # remote-jobs (1)
- # shadow-cljs (59)
- # spacemacs (16)
- # sql (1)
- # uncomplicate (6)
- # unrepl (90)
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 🙂
@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
(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
@mfikes I'm not sure I'll be satisfied with your solution unless you also provide a 3D hologram displaying the collisions.
I’m not satisfied with my day 20 solution either @grzm — I had to fall back on what the AoC game allows 😞
get 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 ...
so if you sort all particles by absolute accelleration, then speed, then position from center
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.
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.
My reading of the problem was, in the limit, which particle ends up closest to the origin
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
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
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.
index of the particle
I felt like they did https://www.dropbox.com/s/2uza02wl3jl469v/Screenshot%202017-12-20%2016.03.54.png?dl=0
usually the expected answers are monospaced with a background
Picking 0
as the sample answer was perhaps not the best choice
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
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.
https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day20.clj
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
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.
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 t
s 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
can someone give me a hint after how many iterations you should expect collisions? 1? 10? 1000?
well, the first one start at 10-15 for me
Could it be this? 😅 https://clojurians.slack.com/archives/C0GLTDB2T/p1513756271000087
@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
Now I’m intrigued
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
So for part two you could use some algorithm which checks if functions will collide for some interval maybe?
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?
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 🙂
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"
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'