Clojurians Log v2

single pass is a very elegant solution 😉 definitely the right choice of data structure influences a good solution

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.

Pretty good learning experience — Thanks everyone!

I was interested in how you did lower-case before the set, so I benchmarked it a bit and it seems like it is significant to set twice with a lower-case inbetween:

advent-of-code-2018.day05=> (cr/with-progress-reporting (cr/bench (into #{} (map s/lower-case (into #{} (parse input)))) :verbose))
Warming up for JIT optimisations 10000000000 ...
  compilation occurred before 1 iterations
  compilation occurred before 390 iterations
  compilation occurred before 779 iterations
  compilation occurred before 1168 iterations
  compilation occurred before 1557 iterations
  compilation occurred before 1946 iterations
  compilation occurred before 2335 iterations
  compilation occurred before 2724 iterations
  compilation occurred before 4669 iterations
  compilation occurred before 5447 iterations
  compilation occurred before 5836 iterations
Estimating execution count ...
Sampling ...
Final GC...
Checking GC...
Finding outliers ...
Bootstrapping ...
Checking outlier significance
x86_64 Mac OS X 10.13.6 8 cpu(s)
Java HotSpot(TM) 64-Bit Server VM 25.192-b12
Runtime arguments: -Dfile.encoding=UTF-8 -Xmx8g -Dclojure.compile.path=/Users/ranmason/code/advent-of-code-2017/target/classes -Dadvent-of-code.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 29640 in 60 samples of 494 calls.
      Execution time sample mean : 2.123692 ms
             Execution time mean : 2.124454 ms
Execution time sample std-deviation : 96.420077 µs
    Execution time std-deviation : 96.989667 µs
   Execution time lower quantile : 1.940056 ms ( 2.5%)
   Execution time upper quantile : 2.234693 ms (97.5%)
                   Overhead used : 2.083859 ns
nil
advent-of-code-2018.day05=> (cr/with-progress-reporting (cr/bench (into #{} (map s/lower-case (parse input))) :verbose))
Warming up for JIT optimisations 10000000000 ...
  compilation occurred before 154 iterations
  compilation occurred before 307 iterations
  compilation occurred before 460 iterations
  compilation occurred before 1072 iterations
Estimating execution count ...
Sampling ...
Final GC...
Checking GC...
Finding outliers ...
Bootstrapping ...
Checking outlier significance
x86_64 Mac OS X 10.13.6 8 cpu(s)
Java HotSpot(TM) 64-Bit Server VM 25.192-b12
Runtime arguments: -Dfile.encoding=UTF-8 -Xmx8g -Dclojure.compile.path=/Users/ranmason/code/advent-of-code-2017/target/classes -Dadvent-of-code.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 5040 in 60 samples of 84 calls.
      Execution time sample mean : 12.258769 ms
             Execution time mean : 12.263469 ms
Execution time sample std-deviation : 437.470024 µs
    Execution time std-deviation : 443.078234 µs
   Execution time lower quantile : 11.783289 ms ( 2.5%)
   Execution time upper quantile : 13.224535 ms (97.5%)
                   Overhead used : 2.083859 ns

Found 3 outliers in 60 samples (5.0000 %)
	low-severe	 3 (5.0000 %)
 Variance from outliers : 22.2472 % Variance is moderately inflated by outliers
nil

@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

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

ah yeah, that makes sense

last & butlast say linear on the tin iirc

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

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

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.

https://en.wikipedia.org/wiki/Convex_hull_algorithms

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

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

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

but that wasn’t a requirement per se

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

@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

not sure what that is about

reproducable with script/test-one 2017 7 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… 🙂

ah indeed, I see the difference is + vs max

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 😉

😄

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

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

spoilers!!!

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.

boundary box coudn't be enough

Do you have a counter example?

visualization spoiler in reply…

https://i.imgur.com/ASYGGIG.png

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

beautiful

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

Living on the edge…

@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

We

I’ll think about it today at work.

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

rectangle?

is this about part 1 btw?

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

yes

another spoiler visualization and how I detected infinite regions in thread

https://i.imgur.com/IkKGgyP.png

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

and used lighter colors for the infinite regions

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

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

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

so at least one coordinate at the edge

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

Yeah that’s simpler and seems just as trustworthy

is this a vis of part 2 btw?

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

Are you looking at the latest commit?

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

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

Yes this is part 1

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.

sorry, yeah

I'm now at 8s/1s

https://github.com/Average-user/adventofcode-clj-2018/blob/master/src/adventofcode_clj_2018/day06.clj

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

sorry, I meant the check if an area is infinite

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.

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 🙂

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

proved*

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

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

(and of course there's Criterium)

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

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

@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

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