This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

## 2018-12-06

## Channels

- # adventofcode (112)
- # announcements (6)
- # beginners (197)
- # boot (3)
- # calva (52)
- # cider (25)
- # clara (14)
- # cljdoc (6)
- # clojure (147)
- # clojure-austin (6)
- # clojure-berlin (7)
- # clojure-brasil (2)
- # clojure-europe (3)
- # clojure-india (4)
- # clojure-italy (8)
- # clojure-new-zealand (2)
- # clojure-nl (7)
- # clojure-russia (7)
- # clojure-spec (29)
- # clojure-uk (63)
- # clojurescript (103)
- # core-async (5)
- # cursive (11)
- # datomic (16)
- # devcards (1)
- # emacs (28)
- # figwheel-main (3)
- # fulcro (97)
- # graphql (4)
- # hyperfiddle (1)
- # jobs (1)
- # kaocha (3)
- # lumo (9)
- # nrepl (4)
- # off-topic (29)
- # onyx (1)
- # pathom (4)
- # pedestal (8)
- # re-frame (24)
- # reagent (1)
- # reitit (13)
- # ring-swagger (6)
- # rum (11)
- # shadow-cljs (79)
- # sql (46)
- # tools-deps (67)
- # yada (8)

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

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??

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

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.

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

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

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
```

Did anyone get a really efficient solution for day6?

This is what I did, but I'm not very content with it: https://github.com/Average-user/adventofcode-clj-2018/blob/master/src/adventofcode_clj_2018/day06.clj

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.

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

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

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

@clashthebunny specifically this line: https://github.com/borkdude/advent-of-cljc/blob/master/test/aoc/new.clj#L69

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…

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

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

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

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

@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
```

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

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… 🙂

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! 😄

After work 😉

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.

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

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

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.

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

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

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

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.

...continued...

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.

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.

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

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

proved*

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

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

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

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

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

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

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

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”

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

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

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

day 6 w/Quil viz code https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/6.clj

@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.

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

I'll check that out then

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

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

@me1740 try to use `(set! *unboxed-math* :warn-on-boxed)`

, this sped up my solution significantly

1500ms/500ms [MrOerni/advent-of-code-2018/day06.clj](https://github.com/MrOerni/advent-of-code-2018/blob/master/src/advent_of_code_2018/day06.clj)

@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.

I'm now at 8s/1s

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

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 🙂

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

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

Had the same problem in day 5

Day 6: https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle06.clj#L82

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?

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

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

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!

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

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

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