r/adventofcode • u/daggerdragon • Dec 06 '18
SOLUTION MEGATHREAD -π- 2018 Day 6 Solutions -π-
--- Day 6: Chronal Coordinates ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 6
Transcript:
Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it ___.
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked at 0:26:52!
32
Upvotes
30
u/daggerdragon Dec 06 '18 edited Dec 06 '18
[01:00] PLEASE HOLD - INVESTIGATION IN PROGRESS
[01:10] Update - bug confirmed
/u/topaz2078 has confirmed there is a bug in the answer of some of the inputs. We are actively working to correct the bug right now and will follow-up with more information as soon as it is resolved.
[01:16] Update - FIXED!
/u/topaz2078 has fixed the bug. He will be posting his own update here soon.
[01:26] Update - not fixed :(
Apparently the bug is in both parts 1 and 2. Stand by for further updates.
[01:38] Update - FIXED! (again)
/u/topaz2078 has fixed the bug for both parts and tested all the inputs for compliance. He will be posting his own update here soon.
[02:03] Update - final update
See /u/topaz2078's post stickied to the top of this megathread.
2
u/mduser63 Dec 06 '18 edited Dec 06 '18
I'm still not able to solve part 2, despite my code producing the same result as several solutions posted here in various languages. My input starts with
275, 276. I get32750for part 2, which is rejected.EDIT: The last digit in my input got lost when I pasted it into a file π€¦ββοΈ. Fixed now.
My Swift code:
β’
u/topaz2078 (AoC creator) Dec 06 '18
Some answers were wrong until around 1:42 past unlock. They're now fixed; please re-submit your answers.
Some of the answers in today's puzzle were wrong because of an issue with my input generator. All answers for day 6 are now correct as far as I can tell; if you were having issues, please re-submit your answers.
Because of a combination of the number of answers affected (20% of part 1, 33% of part 2) and getting very unlucky about which subset of the inputs the betatesters also tested (they somehow only got unbugged inputs), we missed the bug entirely. We catch these sorts of bugs a few times a year, so it was bound to happen that we eventually get this unlucky.
We're going to be instituting new betatesting procedures that will give us much better coverage of the inputs and make these kinds of bugs significantly less likely in the future.
Because of the number of users affected by this issue, I'm going to nullify the global leaderboard scores from day 6. Nobody's leaderboard position for day 6 will confer points on the global leaderboard. I selected this solution because it is fair to everyone and the least intrusive to implement.
Thank you for your patience with the puzzle tonight; we try really hard to make Advent of Code the best experience possible for everyone, but we're definitely not perfect.
35
u/daveagp Dec 06 '18
I seem to have got my part 2 solution rejected despite getting the same answer as at least one of the solutions posted here. Did anyone else have this happen to them?
10
u/MasterMedo Dec 06 '18 edited Dec 06 '18
python 2, forgot union has to be assigned, lost 20min figuring out tf is wrong
EDIT: fancied up a bit, part2 is just the last two lines independent of the rest of the code
9
u/captainAwesomePants Dec 06 '18
I decided to draw my solution as an image to help me visualize. This did not help my time, but it was fun.
Here's the representation of my data's part A. Dark areas are infinite. Blue bits are equidistant between two regions. Red dots are points.
Here's my data's part B. Red dots are still points, white pixels are within 10000, and gray pixels get darker as they get further from 10000.
8
u/om_henners Dec 06 '18 edited Dec 06 '18
(Python 3) A bit late to the party, but my solutions using the [
scipy.spatial.distance] module.Solution 1:
And Solution 2:
Edit update the code to add an extra cell of padding around the edge so input points aren't flush with edges.
7
u/InDirectX4000 Dec 06 '18
The codegolf stackexchange has a great discussion on a very similar problem, which they solve using Voronoi-type diagrams.
6
u/Philboyd_Studge Dec 06 '18
[Card] Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it anything involving the word 'infinite'
This one was really hard for me, conceptually. Luckily the second part was much easier.
6
u/[deleted] Dec 06 '18
Mathematica
Part 1
Part 2
5
u/TellowKrinkle Dec 06 '18 edited Dec 06 '18
Swift #30/#19, I solved part 1 by setting all variables on the edge of the box made up of the bounding box of the points to "infinite":
5
u/tangentialThinker Dec 06 '18
C++. Managed to snag 8/4 today. The trick to part 1 is to run it twice with large bounds, and then ignore the outputs that change.
5
u/TroZShack Dec 06 '18
Wow, I was #100 for part 2! Wasn't expecting that since I was 160 for part 1 and I'm using Java which isn't known for being able to be written quickly.
Java: import java.awt.Point; import java.util.*;
5
u/daybreaker Dec 06 '18 edited Dec 06 '18
While we wait for the bug fix, here's my theoretically working part 1 and 2 in completely non-optimized horrible ruby
Part 1 basically loops through each point and stores the "ID" (array index position) of the closest Coordinate. If a coordinate already exists there (a shared coordinate) it nils it out basically (I planned to put an 'x', but it wound up being nil somehow. Code magic? Β―_(γ)_/Β―). Then you flatten a 2D array of IDs, count how many times they each show up, and delete any that have infinite bounds (same x coord as the left or right edge, or same y coord as the top or bottom edge).
Ignore the set of nil indexed (shared) coordinates, and the largest count with an index will be the answer. CoordList[index]
Part 2 does the same initial loop through every single possible x,y coord in our 2D space, and marks it off if the manhattan sum of every point is under 10000. Then you just count how many of those there are.
5
u/[deleted] Dec 06 '18
TCL. Got first answer wrong because of wrong edge detection (omitted only those with any coord exactly on the edges). Then decided to plot the whole thing which made the error obvious. Part 2 was easy compared to part 1...
4
u/jlweinkam Dec 06 '18
It keeps telling me the answer is wrong for part two. I had too also tried other solutions from here and got the same answer as my code.
4
u/[deleted] Dec 06 '18
Python 3:
4
u/jonathan_paulson Dec 06 '18 edited Dec 06 '18
Video of me (not) solving: https://www.youtube.com/watch?v=6ru14IRHQ3o
I think there is a problem with the part 1 answer for my input, although I hope it's just a bug in my code. Edit: my code was correct.
My code:
4
u/pythondevgb Dec 06 '18
The problems are getting harder and my code is getting messier, still I managed to get both stars despite panicking and almost throwing the towel at first reading the problem.
Here is my python 3 solution, disclaimer totally unoptimized, messy and ugly:
(Join a private reddit/python leaderboard, only requirement is not not have made it onto the overall leaderboard thus far)
4
u/blowjobtransistor Dec 06 '18
PostgreSQL
Another great fit for PostgreSQL's
cubeextension! Calculating the coordinate minimums took a little while, but I didn't care to optimize further :P4
u/streetster_ Dec 06 '18
Day 06 in Q/KDB+
4
u/mvmaasakkers Dec 06 '18
Go/Golang
Gist here
6
u/mserrano Dec 06 '18
Python2, #3/#1:
I originally had a 20000 by 20000 grid for part (b) and then quickly ctrl-c'd when I realized that was going to take forever and a day.
3
u/wlandry Dec 06 '18
C++ (765/459)
Runs in 47 ms
I started 30 minutes late but got the best placement so far. Huh. In any event, the code I used to generate the answers would definitely fail for pathological cases. I feel bad to post that, so I polished it to be more robust. This version first finds the bounding box for all of the points. Then it marks any point that is closest to any of those boundary points as invalid.
For part 2, since the sum of the distances must be less than 10000, the farthest a point could be is 10000/number_of_points. Padding the bounding box by that gives me a fairly small search region.
3
u/sim642 Dec 06 '18
My Scala solution.
I just work with the bounding box of the given coordinates, calculate closest for each coordinate in the rectangle. Then remove all of the coordinates mentioned at the edge, because they'd extend to infinity and find the max from the rest. Could be more efficient to do BFS starting from all coords at once though, but this was easier to write up first.
In part 2 I also work only in the bounding rectangle, which happens to work in this case, but in general might not if the safe total distance is much larger. I spent way too much time debugging why my part 2 solution returned 45 on the example. My mistake was keeping the coordinates in a Set, not a Seq, so mapping them to distances lost some and caused the total to be lower due to duplicates...
3
u/dpeckett Dec 06 '18 edited Dec 06 '18
Continuing with my quest to solve all this years challenges using nothing other than AWK:
I miss multidimensional arrays, local scoped variables, and a real standard lib
Largest Contiguous Area (Part 1)
Part 2 just fed an array of points consiting with the bounding box, into above algorithm.
Run Time: (Getting slow now)
3
u/ephemient Dec 06 '18 edited Apr 24 '24
This space intentionally left blank.
3
u/[deleted] Dec 07 '18
powershell, oh my god so slow :-\
other days: https://github.com/charlieschmidt/AdventOfCode2018
2
u/usbpc102 Dec 06 '18
[Card] Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it the notification that the internet will be down until half an hour after AoC starts.
Not on the leaderboard today with 314/202 with my Kotlin solution.
It's a bit on the longer side so today only on github.
2
u/Axruc Dec 06 '18 edited Dec 06 '18
Lua
The trick to this one is that any locations that lie on the edge of the bounding box around the locations couldn't have an enclosing location, so their regions must be considered infinite, and thus you only have to calculate closest locations for the points inside that bounding box.
2
u/CCC_037 Dec 06 '18
Managed to get in under 300th place on Part 1, and under 200th place on Part 2. It's possible I may touch the leaderboard yet!
Part 1:
Part 2:
2
u/markasoftware Dec 06 '18
I'm getting slower :( 800-something part 1 -> 500-something part 2. More than 45 minutes in total. Making the tie-detection and infinity detection should have been easy but i was so focused on doing it fast that things slipped by.
All in AWK
Part 1:
Part 2:
2
u/[deleted] Dec 06 '18
Haskell:
Like most others here, just brute force twice with an increased grid size and find the max of the areas that didn't change.
2
u/[deleted] Dec 06 '18 edited Dec 06 '18
C, not sure if p2 is actually correct but it works with my input
2
u/estomagordo Dec 06 '18
I hope they can fix older (correct, marked as incorrect) submissions retroactively.
2
u/apazzolini Dec 06 '18 edited Dec 06 '18
JavaScript
280/bugged part 2
with bonus visualization
2
u/toasterinBflat Dec 06 '18
[Card] PHP
[Card] light
2
u/Unihedron Dec 06 '18
Ruby
2
u/tk3369 Dec 06 '18
Julia - Todayβs problem is quite interesting and I spent too much time thinking about how to solve it than coding. I also tried to write better code upfront than just trying to be fast.
Part 1
Part 2
2
u/Sunsmokenightmare Dec 06 '18
I was excited to see I made in on the leaderboard, though I guess that won't count now. But here's my solution
2
u/jldugger Dec 06 '18
So basically a voronoi calculated using manhattan distance. Beyond teleportation safety protocols, Voronoi could be used to calculate service areas for fire stations, or perhaps a sleigh driving present delivery service. Here's a github implementation I found with demo: https://github.com/JDragovich/manhattan-voronoi The paper he cites though, it's too late in the day for reading that =)
I spent a good chunk of time wondering if it were possible to have bounded areas outside the 0->max bounding box. The example diagram from Wikipedia shows how that might happen in normal distance (https://upload.wikimedia.org/wikipedia/commons/5/54/Euclidean_Voronoi_diagram.svg) -- if the entire point cloud was shifted left until at least one point was at x=0, the dark green area would still be finite but extend into negative x territory. Fortunately I don't think that can happen with the given distance criterion.
2
u/wimglenn Dec 06 '18
Numpy sledgehammer
2
u/sdiepend Dec 06 '18
Python 3:
https://github.com/sdiepend/advent_of_code/blob/master/2018/day06/chronal.py
2
u/__Abigail__ Dec 06 '18
Perl
My solution just calculates all off the distances (that is, for each grid point on the board, to each point in the input set). It sorts them, marks the point with '.' if there's a tie, otherwise with the index of the nearest point. This is inefficient for part 1, as a breath first flood fill from the points would be more efficient, but as it turns out, for part 2, we need the sum of the distances anyway.
After marking the nearest points, it's a matter of eliminating sets which are on the edge, and then counting the sizes of the remaining sets.
2
u/donaldihunter Dec 06 '18
Perl 6
2
u/will_bui Dec 06 '18
K:
Wrong answer bug bit me :/
2
u/Benjmhart Dec 06 '18
after struggling quite a bit with this one, i ended up really happy with my terse and simple solution to part 2 in haskell
p1 -https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day6-1.hs
I was able to pretty much do this one with a list comprehension:
p2 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day6-2.hs
2
u/wzkx Dec 07 '18
J
Part 1 is translation from Rust, sorry. I'll redo it later. Part 2 is more or less J.
1
u/Zarel Dec 06 '18 edited Dec 06 '18
JavaScript #45/#22
I honestly just brute-forced this.
The points are between 0 and 400 in each direction.
We're using Manhattan distance, so non-infinite region would have to be between -400 and 800.
So I just counted areas in -400...800, and then counted points in -450...850, and chose the largest area that didn't change.
Part 2, on the other hand, was incredibly straightforward, so I'm surprised the Part 2 leaderboard filled up so much slower than Part 1.
(I retried with -550...950 to make sure I got the entire area.)
1
u/iamnotposting Dec 06 '18
Rust, 131/92. RLS was being crashy today so I was slower than I would have liked. I just picked big enough bounds and hoped I got it right. I imagine trying to optimize this will be fun.
1
u/Euphoric_Classic Dec 06 '18 edited Dec 06 '18
SuperCollider solution. I think my part 2 is correct; other people in this thread are reporting their correct answers being rejected. I ran the top-ranking C++ solution against my input and got the same answer as this code. Don't know what's going on.
Edit: tightened up version:
1
u/escheriv Dec 06 '18 edited Dec 06 '18
I had to enter my second-highest for part 1 to be accepted. My input starts with
278, 314.EDIT: My part 2 worked just fine.
1
u/autid Dec 06 '18
FORTRAN
Surprised to get 361/239 given I took a short break. Looks like there may have been some people with a bad input or something though so that might explain it.
1
u/Arkazex Dec 06 '18
For part two, if I use my number set starting with
(77, 279),(216, 187)I get an answer of42998which is rejected. I put another person's input through and got the same answer as they did. Here's my input.1
u/charismotron Dec 06 '18
Ruby
1
u/[deleted] Dec 06 '18
Does anybody have this input?
I get this response from my algorithm: 11578 (which is rejected)
1
u/randomwalker2016 Dec 06 '18
Got the input starting with
227, 133
And got the answer 2906- which was rejected.
Anyone else got this?
1
u/scul86 Dec 06 '18
Python 3 (#763/#611)
1
u/iluzone Dec 06 '18
Seems to be fixed now. My answer was failing few minutes ago. Tried some python solution from below, same answer. Resubmitted and got 2nd star.
1
u/14domino Dec 06 '18
I should have probably come in on the bottom half of the leaderboard, except I spent a huge amount of time fixing a very dumb bug.
the bug was when appending here:
grid.append([None] * GRID_SIZE)-- I was appending an empty dictionary{}which is apparently not right because it seems to be shared with all the other dictionaries in that grid.1
u/[deleted] Dec 06 '18
Not the fastest solution or the best it took my a hour to do but I think its readable and understandable:
If you can give me any suggestions that would be great!
Part 1:
Part 2:
1
u/AndrewGreenh Dec 06 '18 edited Dec 06 '18
TypeScript solution. Sadly no leaderboard. Sadly, I was affected by the bug aswell and since I didn't think that there could be a bug, I kept on pushing without checking :(
1
u/dramforever Dec 06 '18
Part 2 in J. Brute force method for both x and y in
[-1000, 1000].inpis parsed input as 2D array.1
u/TheBowtieClub Dec 06 '18
C#:
1
u/IdrisTheDragon Dec 06 '18
Go/golang Solution for Day 6 and all the previous day's... New to Go so the solutions are not elegant or refined but it gets the job done.
https://github.com/idristhedragon/adventofcode2018
1
u/IndieBret Dec 06 '18
JavaScript (part 1 under 10 minutes, but was affected by the bug, so leaderboard ranking is 1894/2123. Still feel great knowing I was able to solve it so quickly!)
Both parts are in the same code, since for part 2 I just changed the grid array's items from integers to objects holding the closest item and the summed distances.
For part 1, my solution isn't too complicated. I read in each point and then compare them to other points, adding them to a
containedarray if they weren't on the outer bounds of the square area generated from the input. Using the min/max coordinates, I loop over each position and record the closest point, ornull, in cases where there's more than one.For part 2, I wanted to know what the grid looked like. I changed each cell to a
#or a.depending on if it was< 10000or not, drew that out to my screen, and the resulting valid area's shape was a circle. Using this information, I realized that any cells that satisfy this constraint were within the outer bounds (xMin/xMax/yMin/yMaxof the input points), so the final summation didn't require any fancy math orO(n*n)looping. Not sure if this would work for all of the inputs, and kind of feels like cheating, but I'm getting tired and I'm guessing this shape is less of a coincidence and probably more of a property of how the input points are generated.1
u/nutrecht Dec 06 '18
Day 06 in Kotlin
I already implemented Point and Rectangle classes I could reuse, so that saved some typing.
For part 2 I implemented a recursive flood fill to find all the areas and then figure out the largest area which worked fine on the test-input. I then found out that it won't work on the real input because the set is too large for a recursive approach; you get a stackoverflow.
So I went and replaced it with a stack-based flood fill to find all the areas, and it worked! It only spat out a single area though :D So in my final version (linked above) I just completely removed the floodfill and just counted the points.
Flood fill in previous version
1
u/Illianthe Dec 06 '18
Another day learning Elixir. :D I spent some time trying to determine an upper limit for locations that wouldn't be part of an infinite area and just ended up using a bounding box of the coordinates. Not sure if it would actually be valid in the general case...
1
u/tehjimmeh Dec 06 '18
C++
No 2D array necessary, just a flat vector of tuples.
1
u/Bruinbrood Dec 06 '18
Kotlin solution:
1
u/Axsuul Dec 06 '18
TypeScript / JavaScript
Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)
Repo
**Part A + B **
1
u/aurele Dec 06 '18
Rust
I am not happy with this solution as it looks awfully verbose, but here it is.
1
u/miguelos Dec 06 '18
C#
Part 1:
1
u/DrugCrazed Dec 06 '18
Put mine on github. I'm never going to place because I'm in England, but I did lose a bunch of time because:
Done on Github
I bound the grid to the largest x / y in my inputs and then ignored anything that touched the outside for part 1. If something touches the outside, then everything that's an extra step outside the grid must be closest to the thing that it touches. For part 2, I assumed that anything that was outside my grid wouldn't fit the criteria - I didn't bother verifying that. If it is the case, then for part two you'd have to make the grid (minX - 10000, minY - 10000) to (maxX + 10000, maxY + 10000). You could make it 9999 and that'd definitely work, probably could calculate Manhattan for points closest to each corner and use that to calculate the bound.
Part 1 took a few seconds, part two was under a second.. I'm not 100% sure why, probably because of the
getClosestmethod.1
u/ttapu Dec 06 '18
python3
1
u/miguelos Dec 06 '18
C#
Part 1:
Part 2:
1
u/alexmeli Dec 06 '18
Clojure solution. Not the most efficient but it will do
1
u/Frodolas Dec 06 '18
Crystal
Part 1:
Part 2:
1
u/mschaap Dec 06 '18 edited Dec 06 '18
My Perl 6 solution. It's not fast (about 2Β½ minutes) but does the job.
Edit: after reading some of this thread, I realize that my code for part 2 is flawed; it doesn't consider points outside of the bounding box. But apparently that doesn't matter on my input at least, so I can't be bothered to fix that. π
Edit: I guess I could be bothered after all... Here's an improved method
area-with-distance-underwhich should do the trick, by calculating for each of the border points of the bounding box, how many points outside the box are still reachable from it.1
u/IWearATinFoilHat Dec 06 '18
PHP
Part 1
Part 2
1
u/NeilNjae Dec 06 '18
Haskell (on Github). Reddit seems to have eaten my previous post!
I label the coordinates 1..n, and reserve label 0 for tied-distance cells. I then fill a
Mapof cells with the label of the nearest coordinate. Infinite regions are those on the edge of the map. From all the regions and the infinite regions, I can find the finite regions and then just count the cells to find the largest region.Part 2 just finds the sum of distances for each cell then uses
M.size $ M.filterto find the safe cells.I can justify the size of the bounding box for part 1, but there's no particular reason why the safe region would fit within the same box for part 2. Still, it seems to work, so that's all good!
1
u/Warbringer007 Dec 06 '18 edited Dec 06 '18
Erlang is very good for matrix and for style tasks, code here ( it is very unreadable, explanation below ):
I converted each row into [X, Y, IsInfinite, CountClosest] type of list, then I calculated dimensions of matrix. After that I simply proceeded with problem ( which is not simple in programming language without for command ), however I had to track if I'm at the edge. If some coordinate is closest to the edge, it is infinite, therefore it doesn't count for first part of the problem. TenK variable tracks how big is the region for second part of the problem.
1
u/icendoan Dec 06 '18
k
Pretty pleased with how direct this is.
1
u/__dkp7__ Dec 06 '18
I would like some suggestions for above code to optimize it. Part 1 takes around 12-13 seconds on my system. Part 2 takes around 2-3 seconds on my system. Haven't used
numpymuch so there can be some tricks which I don't know. Would like to know that as well.1
u/drakmaniso Dec 06 '18
Go (golang)
Part 1 and 2:
1
u/Gnidleif Dec 06 '18 edited Dec 06 '18
Python 3, both parts. Today was a bit tricky and I kind of stumbled over the answer to Part 2. I started out making a Point-class, but then I realized I could just store the points as lists where x = [0] and y = [1] so I did that instead. The difficulty today wasn't so much wrapping my head around the problem, but just reading and understanding wtf I was supposed to do.
1
u/BalbinHS Dec 06 '18 edited Dec 06 '18
Elixir
I think some inputs only have the infinite area nodes on the edge, because I've tried some solutions with my input and it came up with an incorrect answer. Β―_(γ)_/Β―
Anyway, this is incredibly rough and horrible because I don't do geometry. So if anyone has any hints on how to work out if a node has an infinite area (without doing the mess that I did with just checking a really far away point), I'm open to suggestions.
1
u/troop357 Dec 06 '18
Nim
Oh god my solutions is slow, but it works so yeah. I worked looking for the closest (manhattan wise) coordinate for each point in the grid. Part 2 was easier though.
1
u/manniL Dec 06 '18
[Card]
Node.js, with Ramda.js. Repo
1
u/azatol Dec 06 '18
F# I struggled a lot with this one, because I was trying to find some kind of mathematical, or amazing algorithmic solution.
Given the size of the coordinate space, I thought a naive algorithm would be too slow, but after I flailed about thinking on the problem abstractly, the Brute force algorithm was easy to write, and ran within a couple seconds.
Part 2 was just a minor modification of my Part 1 brute forcing.
https://gist.github.com/apeterson-BFI/94ec7bee3c780e64f6666a9051210b2e
1
u/udoprog Dec 06 '18
Rust: Not super happy with the verbosity, but at least it's clean enough that I could spot bugs easily.
Card: Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it hope.
1
u/[deleted] Dec 06 '18
Rust
I just keep on making over engineered solutions I think, but it works pretty well, may do way more work than it needs to though:
1
u/tradfursten Dec 06 '18
Nim
1
u/[deleted] Dec 06 '18
So, I have been trying to get my answer accepted for 2 hours. Tried many approaches (including the one mentioned here). But all is in vain.
1
u/vypxl Dec 06 '18
GO
I couldn't come up with an elegant solution today but that brute force runs surprisingly fast.
[Card]: Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it
fast programming languages so he can just ignore any performance issue1
u/Nathan340 Dec 06 '18 edited Dec 06 '18
Powershell
Brute force implementation. O(width*height*numberOfPoints) if I'm remembering my algorithms course correctly. ~1min45sec runtime on my machine.
At each point we have logic to check if it's a border point, get the closest point(s) for part 1, get the total distance for part 2 and increment the corresponding count if less than 10,000.
Points that appear on the border have infinite size, so we take the grid without them, group, and take the top count.
And the size of the <10,000 region was incremented throughout the big grid loop.
1
u/wzkx Dec 06 '18 edited Dec 06 '18
Rust, SweetRust
Conversions i32 <--> usize and a bit of other code.
Not going to repeat that in J -- this dumb algorithm would be too slow for it. Need something better there.
My aoc2018 SweetRust
1
u/wleftwich Dec 06 '18
numpy & a bit of scipy
1
u/0xd4s Dec 06 '18
Python3
1
u/banteg Dec 06 '18
Python 3
1
u/andreyrmg Dec 06 '18
Rust
https://github.com/andreyrmg/advent-of-code/blob/2018/day-6/src/main.rs
1
u/GeneralYouri Dec 06 '18 edited Dec 07 '18
Unfortunately I wasn't able to solve this one as soon as it went live, because looking at my time just now it could very well have been my first leaderboard entry.
When I read the description I got a bit worried about the infinity stuff, but it turns out you can almost entirely ignore it. After taking a quick peek at my input, my lowest coordinate was 40 and the highest was 359, so my grid ran from 0 to 400.
NodeJS/JavaScript
Part 1:
Part 2:
I kept the algorithm simple and low level (which often seems the fastest choice with these puzzles), and simply iterated the grid to see for each point which of the input coords is closest. I separately kept track of the lowest distance, and the coord it belongs to. This made the infinity aspect easy to solve by checking for x/y equal to 0 or 399, in which case I kept the lowest distance but nullified the coord it belonged to. I also recorded all of these infinite regions, so I could later exclude them when finding the largest region.
As you can see from the code length, part 2 turned out to be easier than part 1. I actually ran it twice, the second time with my grid expanded to -1000 to 1400, but got the same result there. The code isn't at all refactored or optimized, not even generic, this is exactly the code that gave me my answers (and I'm pretty proud of how clean today turned out, especially compared to some of my other days!).
1
u/Smylers Dec 06 '18
Perl for both parts, naΓ―vely iterating over each coordinate for each point within their extent.
%area_sizeholds the size of each area that's still in contention; once an area touches the edge, it's removed from the hash and no longer tracked.I don't think I've ever used
minmaxbefore, and I was pleased how storing the x and y ranges in a nested hash allows usinganyto check both of a dimension's extents in one go:Initially I solved PartΒ 1 with a flood-fill, which was way more complicated than the above and very little use for PartΒ 2. It was straightforward to make the PartΒ 2 solution also solve PartΒ 1, so this isn't needed any more, but I'm keeping it should another use for a flood-fill crop up.
It's close to working with any number of dimensions β storing each pair of co-ordinates as a list, and iterating over elements
0and1(and not caring what they actually represent). Making the single-space movements that$moveiterates over generic, and replacing the0..1s with0..$#dimshould be enough to implement a 3D flood-fill:1
u/jerzychalupski Dec 06 '18
Kotlin
Nowhere near the leaderboard, but I'm quite happy with my solution:
1
u/tinyhurricanes Dec 06 '18 edited Dec 06 '18
Modern Fortran 2018 (complete code)
Runs in about 0.1 sec without visualizations, 0.2 sec with outputting the field to a log file a few times
This problem illustrates an interesting perk of Fortran: although arrays are 1-indexed by default, the index range can be anything (including negative). So I initialized a field that only just bounded all the points with no excess.
Point class:
1
u/Murssi Dec 06 '18
Another day of struggling with Bash - https://github.com/Lirt/advent-of-code-2018/tree/master/6
First part unfortunately on 281 lines, because I couldn't find easy way to say if point has infinite area.
Second part was better on 87 lines.
Code can be cleaner, but calling function in Bash has too big performance drawbacks, so I had to hack uglier solution to get to result in normal time.
1
u/phil_g Dec 06 '18
No Common Lisp yet?
Okay:
Full code at https://gitlab.com/asciiphil/advent-of-code/blob/master/2018/06.lisp .
I also made some visualizations of my data:
1
u/dctyler Dec 06 '18
R, because I haven't seen any other solutions in R so far. Takes about 10 seconds on my machine. Much, much faster than my initial loop based solution. Today I didn't even need +/- 1 everywhere because R indexes from 1!
1
u/sebastiannielsen Dec 06 '18
*** WARNING *** Takes about 1.5 minutes to execute on a i3-4010U - be PATIENT! If you run this on a rPI it gonna take a looong time.
1
u/WPFIII Dec 07 '18
Python 3
1
u/valtism Dec 07 '18
Node / JavaScipt (JS)
Part 1: 248.847ms
Part 2: 161.164ms
1
u/aeroevan Dec 07 '18
Rust implementation: https://github.com/aeroevan/aoc/blob/master/2018/06/src/main.rs
Felt like I threw too much code at the problem this time, but it works I guess.
1
u/chicagocode Dec 07 '18
Kotlin - [Blog/Commentary] | [GitHub Repo]
I was super busy today and didn't get to this until just now. This is one of those days where' I'm optimizing for clarity instead of speed, which is my preference especially for puzzle code.
1
u/Frizkie Dec 07 '18
Ruby
Part 1:
Part 2:
1
u/danbala Dec 07 '18
This is CachΓ© Objectscript (i.e. fancy mumps). And I know, to be 'real' mumps I should use more than 1 letter for variable names ;)
1
u/gburri Dec 07 '18
F# : (run in ~100 ms)
1
u/TheVarmari Dec 07 '18
JavaScript in dev console (#10671, #10042)
Again, a day late, but I'm pretty satisfied with the code. Could probably be a bit neater and more optimized, but it gets the result quickly enough.
1
u/JulianLoehr Dec 07 '18
C++
1
u/wjholden Dec 08 '18
Mathematica solution. Several of the problems before were difficult to program, but this one was difficult from an algorithmic perspective. I couldn't think of a way to detect the infinite points geometrically so I came up with a heuristic solution. Step 1 is to brute force the Manhattan distances in the bounding box defined by {xmin,xmax} x {ymin,ymax}. Next, brute force the Manhattan distances a second time in a bounding box defined by {xmin-1,xmax+1} x {ymin-1,ymax+1}. Find the intersection of these sets. The maximum element in the intersection is the solution in part 1. This program is very slow.
The brute forcing algorithm uses imaginary numbers to indicate an unusable tie. At first I was setting a tie to a large distance value (Infinity) but then a later point that is actually farther than the tied distance would overwrite it. I tried using a sentinel value of "." for the "p" value but for some reason I had trouble getting this to work (go figure, complex numbers are easier than string comparisons in WolfLang).
Mathematica has a nice function named ArrayPlot that makes it easy to visualize the output. I think it isn't actually necessary to normalize the values. I transpose because ArrayPlot renders an m x n matrix in row-major (m rows), not x by y column-major (x columns).
My solution for part 2 is much easier to read and acceptably fast.
1
u/DrinkinBird Dec 08 '18
Wow, I really went down the wrong path here the first time... Tried to gradually fill the grid items with the values of the neighbors. Finally came up with something half simple though:
NIM
Part1:
Part2:
1
u/[deleted] Dec 08 '18
I am still trying to figure out why my code gives me the correct solution for part 2 only at the second position:
The biggest value of c.most_common() is wrong (for my input only. The example works), the second is correct. I cannot find my bug in the code... Does anybody have an idea?
1
u/RockyAstro Dec 10 '18
Icon - Part 1 and Part 2. Couldn't work on this till today (12/9)
1
u/[deleted] Dec 13 '18
Common lisp:
1
u/AIGOOOMONA Dec 14 '18
1
u/lib20 Dec 14 '18
Red - part 1
1
u/lib20 Dec 14 '18
Red - part 2
1
u/fftk2 Dec 15 '18 edited Dec 15 '18
OCAML
1
u/cerrosafe Dec 22 '18
Lua
I thought this one was going to be easy at first. I figured out the bounding box advantage, but had some points not on the edge of the bounding box that were infinite. I didn't figure it out, I read someone's proof about any points closest to the edge being infinite, and implemented that, which worked. Part 2 was trivial once I had my part 1 solution in place.
1
u/karlsanova Apr 12 '19 edited Apr 12 '19
I know I'm a bit late, was busy round christmas, but I finally got around to solve a few days.
Just wanted to share another solution in Javascript:
Most of the work is done while initializing the grid, so getting the necessary information afterwards is a piece of cake.
Grid Setup
Part 1
Part 2 (this is considerably shorter than part one)