Fork me on GitHub
#adventofcode
<
2018-12-06
>
rymndhng00:12:16

from looking at a few other folks do it in other languages, my gut tells me the clojure solutions have been the most concise

fingertoe00:12:14

I am having fun at failing at this 😉 Got mine done with about 4 or 5 approaches, all of them mighty slow… I suspect the liberal memoizing must be a pretty good skill to adopt??

mfikes00:12:24

For this particular problem, it is probably fair to say that the overall algorithm used can dramatically affect perf.

adammiller00:12:59

yes, I actually got my answers with a regex/replace solution that was quite slow (but worked) but then refactored to a simple reduce that is quite fast.

fingertoe00:12:25

Pretty good learning experience — Thanks everyone!

ClashTheBunny02:12:25

@borkdude is there a reason title-cased usernames aren't allowed? Failed to validate "-u ClashTheBunny": Username must start with letter

ClashTheBunny02:12:51

Anybody know how to get a cljs repl in the advent-of-cljc repo?

ClashTheBunny03:12:35

Holy moly! Switching from last and butlast to peek and pop went from

CLJ: Testing aoc.y2018.d05.clashthebunny
part-2 took 222732.26 msecs
part-1 took 8448.07 msecs
to
CLJ: Testing aoc.y2018.d05.clashthebunny
part-2 took 405.82 msecs
part-1 took 9.60 msecs

CLJS: Testing aoc.y2018.d05.clashthebunny
part-1 took 154.00 msecs
part-2 took 905.00 msecs

potetm03:12:21

ah yeah, that makes sense

potetm03:12:53

last & butlast say linear on the tin iirc

Average-user06:12:06

Did anyone get a really efficient solution for day6?

fellshard07:12:29

Still plugging away, I did an off-by-one error at my boundary checks 😓

Ben Grabow07:12:43

Haven't started yet, just brainstorming. I am expecting to need to use something like a convex hull algorithm to filter out the "infinite" regions. I might be overthinking it though.

taylor07:12:53

I optimized for time-to-leaderboard 🙂 https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/6.clj part 1 takes 9s and part 2 takes 1s

taylor07:12:19

the infinite region exclusion is incomplete I think, but it didn’t matter for my inputs

borkdude07:12:45

@clashthebunny That’s a bug in the validation probably 🙂 Welcome to fix it

rymndhng08:12:21

#6 was good -- what really helped me speedup was typehinting lol

🍿 4
fingertoe08:12:56

So, I think my lesson from day 5 just clicked… I am using the same recursion and such as the fast solutions.. I think the crux of the slowness is that I am asking (26*2)^2 possible questions “am I a reactive combination?” instead of asking the (2*26) questions “are you a reactive combination?” Haven’t tested it yet, but woke up thinking…

erwin08:12:10

Messed up the infinite check today (but I really had no clue what to do at first...) https://repl.it/@ekroon/AOC2018-day06

fellshard10:12:36

Hmmm. Now that I've done it the ugly brute-force way, I wonder if there's something simpler...

fellshard10:12:27

This is technically a discrete voronoi fill in part 1, and could probably be accomplished by a variant of Dijkstra's

borkdude10:12:51

I was confused by the description in part 2. I thought I had to calculate also if the region was connected

borkdude10:12:05

but that wasn’t a requirement per se

borkdude10:12:27

Testing aoc.y2018.d06.borkdude
part-2 took 389.71 msecs
part-1 took 5011.38 msecs

borkdude10:12:31

@mfikes there’s a warning in the build logs:

WARNING: /home/circleci/repo/cljs-test-runner-out/cljs_test_runner/gen.js:319: WARNING - incomplete alias created for namespace aoc.y2017.d07.mfikes

borkdude11:12:59

not sure what that is about

borkdude11:12:22

reproducable with script/test-one 2017 7 mfikes

borkdude11:12:56

@erwinrooijakkers did you see my comment on your open PR..?

erwinrooijakkers11:12:19

Yes thanks, the code is different though. The guard->sleep-mask holds a data structure in the :sleep-mask key like [1 2 0 …] (length 60 vector where every index holds the total minutes). In solve-1 the sorted map is sorted by (apply +) (to find the total minutes) and in solve-2 it’s sorted by (apply max) to find the maximum. Thinking about this, maybe it sorts on another key… 🙂

borkdude11:12:04

ah indeed, I see the difference is + vs max

erwinrooijakkers11:12:31

Maybe it also sorts on guard number, and for your input the guard number is lower than the + and in mine it is higher. I’ll look into it! 😄

ihabunek11:12:42

user=> (> (priority aoc) (priority paid-work))
true

ihabunek11:12:07

i solved in elixir today so no clojure solution from me 🙂

norman14:12:46

I haven’t had time to think about it, but I drew a boundary box around the points and assumed that anything that reaches the edge of that box would continue forever. This is probably easy to prove correct/incorrect, but I didn’ worry much about that last night.

genmeblog14:12:32

boundary box coudn't be enough

norman14:12:00

Do you have a counter example?

taylor14:12:35

visualization spoiler in reply…

borkdude14:12:41

is this about part 1 btw?

borkdude14:12:01

I wondered about part 2, if the regions should be connected. I first assumed that, but I got the wrong answer

Björn Ebbinghaus14:12:11

@borkdude Since you have to consider the distance to all points, it has to be a connected area.

taylor15:12:05

Yes this is part 1

fellshard16:12:02

My 'intuition check' for it is that I believe the convex hull of all points will pass through only the infinite regions. (With a caveat that that may not quite work for manhattan distance thanks to the square corners) If you have a square canvas around those points, which by definition encompasses the convex hull of those points, then that square should also pass through only the infinite regions, and so you can sniff around at the edges of the square to find them.

borkdude16:12:58

My check is to verify if at least one of the coordinates in an area touches the edge.

taylor16:12:57

I should note the black regions in the image are the points that are equidistant to two or more coordinates

borkdude16:12:26

sorry, I meant the check if an area is infinite

Average-user14:12:16

I think is enough, but I'm looking for a prove. But i think is because of manhattan distance. With euclidean distance wouldn't work

Ben Grabow17:12:55

With euclidian distance, let's take points A (0,0), B (100,0), and C (50, -1). (Assume more points below the x-axis that prevent C from having an infinite region in the +x, -x, or -y directions.) The minimum bounding box will have its upper edge on the x-axis. C will have many points in its region along the x-axis in the vicinity of x=50. To determine if C's region is infinite we need to consider whether it still has points on the edge of the bounding box as we extend the bounding box infinitely in the +y direction. As we do that, the hypotenuse distance from the box edge to the nearest point in the set of input points becomes dominated by the y distance, and the x distance becomes irrelevant. Consider a point directly above C, such that distance to C (dC) is defined as (dx, dy) and dB is (dx+50, dy-1). At small values of dy (i.e. close to the minimum bounding box), dB is larger than dC (meaning C has points on the box edge. However as dy approaches infinity, the hypotenuse distance (dx^2 + dy^2) becomes larger than ((dx+50)^2 + (dy-1)^2). So C's region is not infinite. However, if we translate this reasoning to manhattan distance, dx never becomes irrelevant as you expand the bounding box.

Ben Grabow17:12:18

...continued...

Ben Grabow17:12:43

In the manhattan case, as dy approaches infinity, since the manhattan distance is the linear sum of dx + dy instead of the squared sum, dC will never get larger than dB. The same reasoning applies on the dA side, and by symmetry on all other edges of the bounding box.

Ben Grabow17:12:29

This isn't a proof that minimum bounding box (MBB) is sufficient in the manhattan case, but it shows that the reasoning I was using for the euclidian case is not applicable to the manhattan case. Someone good at proofs could probably turn this into a proof that MBB is sufficient for manhattan though.

Ben Grabow17:12:48

Would appreciate some eyes on my reasoning for using the minimum bounding box approach.

Average-user18:12:24

I prove that the minimum rectangle that enclose all points is enough

norman14:12:33

I spent all of 30 seconds thinking about whether it was correct or not, but it seemed like a reasonable starting poiint.

taylor14:12:38

a pretty naive approach worked for me w/r/t infinite regions, but I’m guessing there’s an input that would break it

borkdude14:12:32

Living on the edge…

genmeblog14:12:01

@norman I'm probably wrong... boundary box could be enough with manhattan distance

👍 4
norman14:12:26

My intuition is there would always be a bounding box and the real question was how big that box would need to be. It surely shouldn’t have to be any larger than the distance between two points and may just be 1

norman14:12:19

It would be interesting to have be able to move points around in one of those visualizations to try and make a counter example

norman14:12:19

I’ll think about it today at work.

Average-user14:12:05

the box should be the smallest rectangle that encloses all given points

taylor14:12:46

another spoiler visualization and how I detected infinite regions in thread

taylor14:12:21

here I made the infinite region coordinates darker dots than their region, and the non-infinite coords are lighter dots

taylor14:12:30

and used lighter colors for the infinite regions

taylor14:12:21

my approach to identifying infinite regions at first was simply finding the coordinates that were nearest the four corners of the bounding rect, which worked but isn’t “correct”

taylor14:12:33

my second approach was to find the set of coords nearest each pixel around the edge of the bounding rect, and I think this is probably correct — at least it looks correct when visualized as opposed to my first approach

borkdude14:12:29

I just figured if an area has at least one coordinate with [0 y], [x 0], [max-x y], or [x max-y], then it’s infinite

borkdude14:12:52

so at least one coordinate at the edge

taylor14:12:57

Yeah that’s simpler and seems just as trustworthy

borkdude14:12:04

is this a vis of part 2 btw?

taylor15:12:56

Just part 1. Not sure if I’ll have time to do part 2

taylor21:12:54

@borkdude you've inspired me to try my hand at rendering a heat map for part 2, but maybe not until this weekend

👍 4
Average-user15:12:59

@taylor I sow In the code you published that you only check for closest points to corners. I think that will not always work, you should check points closest to every point in the frame that encloses all points.

taylor15:12:05

Are you looking at the latest commit?

taylor15:12:53

That sounds like my first approach which worked well enough to solve the problem, but my latest commit uses a different strategy

Average-user15:12:14

I'll check that out then

Average-user15:12:59

Ohh I see, so you did go for the frame approach. Very similar to what I did

benoit16:12:39

My super slow solution 🙂 (~ 20s for each part). Just doing the naive thing of walking through all points. https://github.com/benfle/advent-of-code-2018/blob/master/day6.clj

borkdude16:12:02

@me1740 try to use (set! *unboxed-math* :warn-on-boxed), this sped up my solution significantly

💡 4
benoit16:12:16

@borkdude Thanks, assuming you mean (set! *unchecked-math* :warn-on-boxed). I'm now at ~2.2s for part one and 317ms for part two.

borkdude16:12:37

sorry, yeah

Average-user16:12:12

I'm now at 8s/1s

Ben Grabow17:12:48

Would appreciate some eyes on my reasoning for using the minimum bounding box approach.

benoit18:12:26

I did a visual proof to convince me that the points on the bounding box belong to infinite areas. If you take a point and a line going through it. All the areas defined by the perpendicular bisectors with the points on one side will create areas that are infinite on the other side of this line. So if you want to close the area that includes this point you will need at least one point on the other side of this line. Now if you take a point on the bounding box and the side of the bounding box as the line, by definition the points on the bounding box have only points on one side of this line so they will all belong to areas that are infinite outside of the bounding box. That was good enough to convince me 🙂

☑️ 4
Average-user18:12:17

Ok: If we have a set R of points that form the perimeter of the smallest rectangle that encloses all points. Then if some element (r) of R has minimum distance with some point (p) of given points set (P), then one of the neighbors of r will also have minimum distance with p. Inductively, if r has a point p as minimum distance, then there are infinite points that have p as minimum distance. If we have a point outside R, then every point between that and the closest point of R, will have the same minimum distance. Therefore it cant exist a point outside R that has minimum distance with some point in P. Without a point r that has minimum distance with the same point in P. Hope is understandable

lilactown18:12:01

I've been stuck on yesterday's part 1 for ~24 hrs. turns out I forgot to trim whitespace :face_with_symbols_on_mouth:

☝️ 4
😡 4
Average-user18:12:46

Had the same problem in day 5

fellshard22:12:43

Mine ran horrendously slowly compared to the times some others are getting. How do y'all usually get detailed profiling on execution beyond bench runtimes?

taylor22:12:29

I've used https://github.com/ptaoussanis/tufte long ago, might be useful for AoC

taylor22:12:01

(and of course there's Criterium)

borkdude22:12:35

yeah, except that it doesn’t work on ClojureScript right now

lilactown22:12:02

so many of these later challenges make mutability feel like a real feature. funny how it in no way reflects my day job 😛

potetm02:12:29

So I thought this as well (esp on Day 4). I was wrong. The correct impl was a change of algorithm to use a linked list! The OG immutable structure!

borkdude22:12:15

@lilactown yeah, it’s very different from my daily coding as well

adammiller22:12:36

definitely great practice for both problem solving and writing code....makes me realize I need to be doing this more often!

mattly22:12:18

same, and yet, these are similar to actual problems I've hit in my real jobs at some point

mattly22:12:49

on the flip side, I don't think anyone would play "advent of Scrum"

lol 4
potetm02:12:29

So I thought this as well (esp on Day 4). I was wrong. The correct impl was a change of algorithm to use a linked list! The OG immutable structure!