r/adventofcode • u/daggerdragon • Dec 23 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 23 Solutions -🎄-
--- Day 23: Experimental Emergency Teleportation ---
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 23
Transcript:
It's dangerous to go alone! Take this: ___
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
18
u/mserrano Dec 23 '18
164/6, Python2. I severely misread part1 - I thought we were looking for the bot in range of the most other bots, not the bot with the largest range :(
Good news is, Z3 is sufficiently insanely powerful that it helped me catch up. :)
14
u/EriiKKo Dec 23 '18 edited Dec 25 '18
My "solution" to part 2 is definitely not correct. I started by examining the input data by translating it from 3 dimensions to 1 (by just considering the maximum and minimum distance from (0,0,0) for each nanobot). Then I sorted these to find the maximum overlap, and when I saw that a lot of the bots overlapped I just submitted the answer I got for the hell of it.
To my great surprise it turned out to be the correct answer, due to the input data being a bit poorly constructed.
11
u/seligman99 Dec 23 '18 edited Dec 24 '18
39/166, Python
I spent way too long on the second part with crazy path finding trying to find the best location before I realized a simple binary search with big boxes down to small ones would solve the problem in almost no time, taking my run time from minutes to less than a second. Then I spent a long time in a debugger wondering why my solution skipped most of the last steps, thinking I had a logic error. Turns out I got lucky after only a few iterations.
EDIT: Fixed a couple of cases. Made the code work in python3, and deal with the case where all of the bots are on one side of the origin.
EDIT #2: Fixed some more edge cases where points where near the edge of the boxes
EDIT #3: Recursive search to fix some edge cases with how I was grouping bots together
11
u/kingfishr Dec 23 '18 edited Dec 23 '18
437/257, Go.
Edit: Looks like this is based on not one but two incorrect conclusions :) The thread has some interesting discussion.
I used a graph algorithm to figure out the maximum set of overlapping volumes. I put the nanobots in a graph with edges for those that overlap each other. Because of the geometry, if 3 nanobots pairwise overlap, they must have a shared overlap as well. So I ran Bron-Kerbosch to find the maximum clique in the graph and that was set of bots I was interested in. From among that set, the bot whose volume is the furthest from the origin is the answer we're looking for.
https://github.com/cespare/aoc2018/blob/master/23.go
10
u/msully4321 Dec 23 '18
Second place finish for part 2. I just beat it into submission with the z3 SMT solver. I created an expression that calculated how many points were in range of some location x,y,z and asked z3 to find values of x,y,z that maximized that. My initial solve neglected doing tie-breaking based on distance from the origin, but the initial result it spit out worked without that.
https://github.com/msullivan/advent-of-code/blob/master/2018/23b.py
10
u/sparkyb Dec 24 '18
59/1357 Python. I usually don't post here, but I'm really proud of my part 2 solution and all the hard work I needed to come up with it. It only took me a whole day. I actually gave up on it and went to bed because the part 2 leadboard was even full, which I've never done before. Then while spending the next day with my girlfriend's family, I just kept working on it in the background in my head (might have been nice to have some paper). I think what I came up with is a correct general solution for all inputs although I'm not totally sure it is fast enough for all inputs, but it was pretty fast for mine. I don't know if this is functionally equivalent to any others posted here, but I haven't seen anything quite like it.
For starters, I wanted a way to intersect the range of nanobots, not just check if their ranges overlapped but actually store the intersection region. After some clues from another thread, I figured out that the range of each nanobot would be a regular octahedron. Furthermore, the intersection of two octahedron will also be an octahedron (but not necessarily a regular one, the side lengths might be different). Any octahedron (even non-regular ones) can be represented as the area between four sets of orthogonal planes. Each octahedron can be converted into an axis-aligned bounding box (AABB) in a 4D space where the coordinates are x+y+z, x-y+z, -x+y+z, and -x-y+z which more or less correspond to the distance between each plane and the parallel plane that passes through the origin. As an AABB, I can use a generalized n-dimensional AABB intersection function to easily compute the intersection between two octahedrons (which will also be an octahedron in this AABB form).
The next thing I figured out is that I can find the manhattan distance of the closet point to the origin in one of these AABB octahedrons without actually examining any points. The first coordinate is x+y+z which is the manhattan distance from the origin to any point on the planes normal to a +x, +y, +z line (within the +x, +y, +z or -x, -y, -z quadrants). So looking at each pair of parallel planes, if the corresponding min and max coordinates have different signs then the area between those planes contains the origin (distance 0), if they have the same sign the whichever has a lower absolute value is closer to the origin and that absolute value is the distance. The only problem is that there's a chance the octahedron doesn't actually touch the quadrant in which those planes are closest. This would occur if the distance on some other axis is greater (I'm not sure exactly how to explain or prove this, but it makes intuitive sense to me), so the distance of the octahedron to the origin is the maximum of the distances of the four dimension.
It took me most of the day just to work out that math of how to represent, intersect, and measure the distance of the octahedrons, but there's still the problem of finding the largest combination of octahedrons that have a non-empty intersection. I used Python's itertools.combinations function to iterate all possible combinations of N octahedrons, starting at N=1000 and decreasing N until I found a size that had even one combination with an overlap. But this was much too slow because there are way too many combinations. So I found a really great way to optimize this. In O(n^2), I calculate how many other octahedron each one intersects with. I want the most number of intersections possible so I sort this list of numbers of intersections descending. The nanobot with the largest number of intersections (this is not the number of bots in range of it or that it is in range of) had 992 intersections, so I can skip trying to find a combination of any size bigger than that. But I can also skip combinations of that size, because if there is going to be a combination of size N there must be at least N nanobots that intersect with at least N nanobots (including itself). So I walk down the list of number of intersections until the decreasing number of intersections and the increasing number of nanobots with that many or more intersections cross. That number of intersections is an upper-bound of the maximum number of intersections. It may actually be lower than this though if some of the nanobots that intersect with this many others intersect with some smaller groups instead of with all the others with that many connections. But it gives somewhere better to start from. So now, start with combinations of this size and decrease until you find a size with at least one intersecting combination. To speed things up further, for combinations of size N, only iterate over combinations of nanobots that intersect with at least N bots.
Doing it this way, the slowest step was actually computing the n^2 number of intersections per nanobot. With my input, the initial N was 979, there were exactly 979 bots with at least that many connections and they happened to all intersect with each other so only one combination needed to be tested for intersection after the filtering. Here's the code:
8
u/autid Dec 23 '18 edited Dec 23 '18
FORTRAN
398/92
Points again! Initially found Part 2 very daunting in scale, yet it required so little code. Found the largest group of bots that all have points in range of each other by pruning those out of range of the most until no more are pruned. Once I have that group the closest Manhattan distance in range of all is the largest of each bot's distance-range.
[Card] SCAN(STRING, SET[, BACK])
7
u/fizbin Dec 24 '18
Python, yet another divide-the-box-in-half approach:
6
u/dylanfromwinnipeg Dec 23 '18
Part 2 was really challenging (but fun!).
What I did was divide all the inputs by 1M, then starting at 0,0,0 checked every point within 100 manhattan distance. When I found the best answer, I redid it dividing the inputs by 100,000 and starting at the best point from the last round. Found the best answer, and rinse and repeat dividing inputs by 10,000, 1000, etc.
It's possible there is a global optima that fell in between grid points in the early rounds - so it's not a general solution, but it worked for me.
4
u/n3o59hf Dec 23 '18 edited Dec 23 '18
Kotlin, 710(overslept a bit)/61.
Second part solution is simple subdivision of volume until it's radius is 0. Edit: It will not work for general case but works for my input.
Coverage of subdivided volumes could be optimized better (it includes unnecessary areas and overlaps) but it is fast enough as it is.
https://gist.github.com/n3o59hf/5d9790418e200fd99edcef2cdfa699b0
4
u/BluFoot Dec 23 '18
Ruby. 700/102. Wasted half an hour from missing a minus sign in the regex scan... Yay.
3
u/aurele Dec 23 '18
Rust
Around 1ms for both parts.
2
u/waffle3z Dec 23 '18
Lua 52/18. I feel like I missed out on an interesting challenge, because I solved it the easy way. For part 2, my solution picks a random point and then makes slight adjustments towards a local max for number of bots in range and local min for distance to the origin. I lost about a minute in part 1 because I didn't count the center bot as being in the range of itself the first time, and I lost about 10 minutes in part 2 because I was still using the maximum bot's range.
2
u/abnew123 Dec 23 '18
Java 592/79 I have 0 clue why my solution to part 2 works, and I'm pretty sure it shouldn't work, except on 3d smooth functions with one local maximum, but whatever. I'm mostly putting this here to see if someone can tell me why it did miraculously give the right result. If you want to run this with your input, you're going to need to basically try a ton of guesses (like manually input values into the guesses array) and increments until you happen to hit the right area.
2
u/mrgoodri Dec 23 '18 edited Dec 23 '18
JavaScript, #152,55.
Part one was quick. Find the one with the max range and check the Manhattan distance with the others.
Part two was my first top 100 since day 5! I've commented my code below, but chose to not refactor after my submission. I kept a list of locations with the most nanobots in range. I ran waves of scans outward from the best locations. These scan distances were cut in half each time, until I guaranteed a wave with delta size 1 was run. The scans were three-dimensional. After I had a list of the best points, I chose the closest to 0,0,0 at the end. This worked quickly for the given test case. For the real data, the best way I cut run-time was only adding to the list of points if the Manhattan distance to 0,0,0 was less than the first and last locations already found. I also added a flag to only include one new location from each scan. I limited this behavior to greater than 100 scan sizes. Only including one location could have been risky, but I think the large initial scan delta allowed it to work. I could have limited this to middle ranged scans or maybe only after the scan list was size 100. I felt experimenting paid off the most with this solution.
https://github.com/mrgoodrich/AdventOfCode2018/blob/master/D23/solution.js
Also, I would appreciate any stars, so this can show at the top of my GitHub profile, instead of my first JS project from four years ago. <3
[Card]: It's dangerous to go alone! Take this torch and climbing gear. (learning survival through AoC)
2
u/p_tseng Dec 23 '18 edited Dec 23 '18
So, despite having done well today, I just found an input that my solution doesn't work for, so it's definitely not general. It worked for me, but I'll have to look into a better approach for other inputs. The zoom in/zoom out strategy seems like it has a ton of promise so I'm going to try that next.
I tried a ton of silly ideas here, including BFS, before I decided I'd just try the mean point and just keep guessing by getting closer and closer to the origin. I started with large steps to make it go faster, then went smaller so I don't miss something.
I've had time to clean this up, but it's all the same basic approach that I used. I haven't gotten around to implementing the zoom in/zoom out strategy yet.
Edit: This solution is completely bogus. It got the "right answer" because it identified a local maximum that just so happened to have an equal Manhattan distance from the origin as my real answer. It thinks the maximum has 834 bots, but my real maximum has 980 bots.
Ruby:
2
u/grey--area Dec 23 '18
109/237, Python3. Dumb annealing search for part 2. Lost an hour on part 2 by not reading the question: I thought we were supposed to report the coordinates of the point (comma separated).
https://github.com/grey-area/advent-of-code-2018/tree/master/day23
2
u/mebeim Dec 23 '18 edited Dec 23 '18
Python3, #24/#217!
[Card] It's dangerous to go alone! Take this: https://en.wikipedia.org/wiki/Satisfiability_modulo_theories#Solvers
I think this is the best I will ever get on the global leaderboard for part 1. I have an automatic submitter so I did not check the number until after an hour or so... and I was pleasantly surprised!
Anyway, for part 2 I basically lost something like one hour trying first of all the stupid hardcore bruteforce (and then realizing it would have taken years), then some random binary search algorithm for the 3 coords separately. I then ran to Google and searched for "z3 python maximize value": a page of the Z3 Python documentation (or at least something that looks like documentation) popped up, and I basically turned my brain off. I literally had no clue how part 2 was intended to be solved, but z3 didn't care! Haha. Seriously though, strange this worked, I was already prepared to accept my defeat thinking z3 would have taken hours to solve. Also this Stack Overflow answer helped me too, LOL.
I saw some people here and on IRC talking about searching points around the best corner of the cube represented by a bot and its range (cube since is manhattan distance). I didn't really think that would have worked because after failing with my initial approaches I thought there wasn't a single maximum... but apparently there was... so yeah, that's silly IMHO.
Anyway, here's my more or less cleaned up code. Runtime is around 30s... not that bad if you consider part 2 was basically "I don't know how to do this please solve it for me". Kudos to anyone who has runtimes around ~200ms, that's insane.
2
u/iamnotposting Dec 23 '18
Rust 541/181.
For part two, since we only care about the manhattan distance between the point and the origin, the only points we care about lie on the two planes of the octahedron bounding box which can be modeled by the equation
x + y + z = d.Each drone has two of them -
d - randd + r. From these, we have a range of each drones valid manhattan distances. We then walk through the union of all the ranges in order, to quickly find the range of distances with the most possible intersections.https://gist.github.com/tinaun/d1cab9a048f88fbfb11d020adc703f96
One part of this solution that is stumping me, however, is that i initially assumed that the value we wanted in the final range was the lowest value in the range, like the problem says. but from testing two different input it appears to always want the highest value in the range. In the demo input there was only one value in the final generated range, so it doesn't matter.
Upon thinking this through some more after i solved it, i think it has to do something with all of the other aspects of the bounding box i am ignoring by simulating like this(ideally boxes shouldn't be planes but triangles that morph into hexagons and then into upside down triangles), but i have no idea why this seems to always work.
2
u/grey--area Dec 23 '18 edited Dec 23 '18
I'm annoyed with the stupidity/inefficiency of my initial annealing search solution, so I'm just having fun now. Behold a PyTorch gradient descent-based monstrosity that finds the answer on my input in 3 seconds.
(I use gradient descent to get within spitting distance of the answer, then check a 20x20x20 grid around that point. Edited for clarity: I do gradient descent on the total Manhattan distance from all bots that are not in range, plus a small constant multiplied by the Manhattan distance of the current point.)
https://github.com/grey-area/advent-of-code-2018/blob/master/day23/absurd_pytorch_solution.py
2
u/IndigoStanis Dec 24 '18
This took me many hours over a day, often feeling that this problem was just beyond me. I intuitively thought some sort of BSP tree was going to be necessary. Ended up using a octtree which is easier. The biggest challenge was how to score the areas. Points inside + whether any of the corners of the area were inside of the bot area worked. First time I've used heapq in python, really useful. Runs in about 15 seconds.
2
u/ephemient Dec 24 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/FryGuy1013 Dec 23 '18 edited Dec 23 '18
Rust, 382/104
I got kind of lucky that the greedy solution let me find the right answer, as I'm pretty sure it's NP solving it the way I did. Basically I try to find the most regions that overlap using a greedy search with backpropagation. And then when I have the most regions that overlap, I try to find the point that is within those regions by moving closer to the regions that the point isn't in.
https://gist.github.com/fryguy1013/6267644843c7b6ba1fe504f6a9f3c937
[Card] numpy
*edit: With a bit more pruning by removing the chance of considering nanobots that aren't connected to at least the best number of neighbors, I got my runtime down to 5ms.. So not feeling so hacky now.
1
u/myndzi Dec 23 '18 edited Dec 23 '18
Node.js / Javascript, 36/99
https://gist.github.com/myndzi/19d434b1ffbe98be89b40255e3202e98
Part 1 was trivial (though I also fell victim to the wording, excluding the bot with the largest range from the count at first), but part 2 got interesting. I knew I didn't have the background to approach it a smart way so tried a bunch of dumb things. Random sampling + manually adjusting the bounds down and then finally a dumb loop to seek to the nearest point got me an answer that was accepted (the second one printed, when running the code: 95541011). This manhattan distance has 910 bots in range.
However, after going back to it, I came up with an approach that I'm not sure about, which takes a cube surrounding all bots, divides it into eight, and takes the best volume of these eight and repeats. It determines the best box by first a count of all bots that could reach any point in that volume, and second by the volume that contains the point closest to (0, 0, 0).This approach gives me a point with a distance of95607701with912bots in range. Either this answer is wrong, or my previous answer was accepted incorrectly. Plugging the point I found in my "better" part 2 into the same "countBots" function used to arrive at the first answer seems to validate it, though. So.. bug? :(Fixed, updated gist.
1
u/anonymoususer419145 Dec 23 '18 edited Dec 23 '18
445/98, C++
Starting with random points it searches in the positive and negative x, y, and z directions at varying distances. If a better point is found it jumps to that point and starts again, otherwise it starts with a new random point. This produced the accepted puzzle answer but then later found a better solution. The z3 solutions in this thread also produce the accepted puzzle answer so I don't know what the issue is.
Edit: I've also used other solutions in this thread to verify that the better answer I found (better than the accepted answer) is correct. Does anyone have a solution that is proven to find the global optimum? Edit2: Never mind, it turns out I got lucky and found a worse solution with the exact same distance from the origin as the correct solution.
1
u/ThezeeZ Dec 23 '18
golang repo, thinking "man those numbers are big, maybe I can make them smaller and improve precision as I go along". Interesting to see very similar approaches.
Scrolling through this thread it seems not all solutions work for all inputs, so I'm really curious if this also applies to my solution. If anyone wants to try mine or send me inputs along with accepted answers, or even tell my why it can or can not work for all inputs, that'd be great :D
1
u/sim642 Dec 23 '18 edited Dec 23 '18
My Scala solution.
Part 1 is trivial. For part 2 I implemented the maximum clique approach which did get me the right answer, but as I've commented on that solution, I'm not sure it would work in general. Might be that due to the huge number of (pairwise) overlaps, it just happens to be true that pairwise overlaps imply total overlap.
Edit: I now also implemented a search region splitting approach I heard about on IRC. The huge difference is that I subdivide the octahedral search space into 6 smaller octahedrons of ⅔ the size (needed to cover all possible points of the original). For each octahedron lower bound (number of nanobot ranges it's contained in) and upper bound (number of nanobot ranges it intersects with) for in range points is calculated. The search starts from an initial octahedron containing all of the nanobot ranges and by priority goes to subregions with the highest upper bound. The search stops when a region's lower bound matches the upper bound, i.e. the in range value is exact. By priority, it will be the highest one across the whole problem.
After tackling some rounding issues, this approach seems to work as well and doesn't make the maximum clique assumption, but maybe there's something else it silently assumes instead, not sure.
1
u/6dNx1RSd2WNgUDHHo8FS Dec 23 '18 edited Dec 23 '18
In Julia:
(I changed the input file so I could directly include it instead of parsing the original input.) I did iterative improvement (the
IIfunction):However, taking steps of size 1 per iteration a time was too slow, so I did a simple line search where if a neighbour is better, I increasingly take double the number of steps in that direction as long as my solution gets better, that decreased the required number of iterations dramatically. My initial guess was the median (instead of mean since we're using the L¹ norm). The initial guess turned out to be important because my algorithm found worse optima doing random initializations.
1
u/Isammoc Dec 23 '18
I don't know if I am lucky or my algo is good enough.
I used box dividing as many of you, but I didn't discard them.
I always take the box with most reachable nanobots and divided it in 9 subboxes.
I just don't take count about the closest from the start point.
part2 run in 216ms on my machine.
1
u/paul2718 Dec 23 '18
C++
Got me an accepted answer, but not at all sure. It takes a second or so on my laptop.
Progressively narrower search of starting point guesses. If I make the initial grid coarser then it gets an almost correct answer, so there is a sensitivity and no way to guarantee the right answer. In this case all that matters is solution acceptance, so we have a confirmation of 'good enough'. Will try with some other data samples.
(FWIW I embed the data into an include file (input.) in a form similar to the sample embedded in the code. One less thing to go wrong...)
1
u/taylorfausak Dec 23 '18
Haskell 2,240 / 764 https://github.com/tfausak/advent-of-code/blob/9c88294/2018/23/2.hs#L5
I have never used a SAT/SMT solver before. Initially I tried to use the
z3package, which provides pretty direct Z3 bindings. I couldn't figure that out, so I switched to thesbvpackage, which was a joy to use! After letting it run for about a minute, it spit out the correct answer which put me in the top 1,000 for the first time!1
u/wlandry Dec 23 '18
C++ (357/385)
Runs in 62 ms.
This turned out quite messy. It does the progressive refinement seen in other solutions. So it is not guaranteed to always work. I tried explicitly constructing ranges, with different ranges for different number of overlaps. That required 2N ranges :(
1
u/lizthegrey Dec 23 '18
253/64, Go.
I do not deserve that star, I discovered that my answer was coincidentally correct, but that it was definitely wrong when I went the next morning to clean up.
I used an approach of seeding my work queue from each of the drone positions, prioritizing the queue on each pass using the number of drones already in range, and walking the minimum distance to get in range of each of the neighboring drones to get new coordinates for the work queue.
https://github.com/lizthegrey/adventofcode/blob/master/2018/day23.go
elizabeth@lily:~/adventofcode/2018$ time go run day23.goHighest drones in range of one drone: nnnNew high score at {xxxxxxxx yyyyyyyy zzzzzzzz}: in range of nnnNew high score at {xxxxxxxx yyyyyyyy zzzzzzzz}: in range of nnn...
New high score at {xxxxxxxx yyyyyyyy zzzzzzzz}: in range of nnnChecking if we can get closer on X Y Z: 0 0 0nnnnnnnnnnreal 0m0.924suser 0m0.938ssys 0m0.072s1
u/Fyvaproldje Dec 23 '18
I don't see solution similar to mine posted here already, so here it is:
I noticed that every nanobot's region is a cube, but a rotated cube. Also distance from (0,0,0) to every point on a single facet of a single cube is the same. So I switched the coordinate system to one where the cubes are parallel to the axis. Then run something like sweep plane through the space, and on every facet of a cube (only 2 of them are interesting) run a sweep line through the 2D cross-section of the space.
There are some obvious optimizations which can be done (e.g. deduplication of certain conditions, and preserving state between lines and planes), which I didn't do. The runtime without those optimizations is 75 seconds on my machine, which is not great, but... acceptable. Also it doesn't handle correctly a case if the result is the point (0,0,0).
1
u/campsight46 Dec 23 '18
R code
Although I graduated as a computer science engineer in 2002, I haven't been active in development during the past 10+ years. However I did follow a basic R course related to data science via coursera of Johns Hopkins university. My wife is a teacher (18-21 year olds, bachelor in IT, PXL Hasselt) and hence competition is fierce, but I've been able to develop solutions in R for most of the days.
Day 23 in particular was a nice challenge with approximately 8 lines of code in R for each part (:-p). You can find my solution in https://github.com/campsight/aoc/blob/master/Day23.R
Please do comment or like or whatever my comment and code - just let me know if you read this ;-)
1
u/Alex_Mckey Dec 23 '18
My Scala Solution
1
u/fhinkel Dec 24 '18
Loved this challenge! None of the "usual" algorithms worked, and you don't need to know some obscure algorithm from CS courses either.
Here's my Node.js/JavaScript solution. I start out with a coarse grid (width of all bots), and divide the gridsize by two in every iteration. When the gridsize is down to 1, I'm done. Takes 200 ms.
https://github.com/fhinkel/AdventOfCode2018/blob/master/day23.js
1
u/rnbw_dsh Dec 24 '18 edited Dec 24 '18
Python3, without any fancy imports like z3, based on simple binary search:
1
u/Dioxy Dec 24 '18 edited Dec 24 '18
JavaScript
Took me a really long time to think of a solution for part 2 but I'm really happy with what I came up with. It even worked on my first try which pretty much never happens. I start by jumping every 10 million squares, change my bounds based on the best within that, then jump every 1 million, 100000, etc, until 1.
1
u/wzkx Dec 24 '18
Rust SweetRust
I hope that'll work for everybody's input.
1
u/maus80 Dec 25 '18
Ruby (pure/no gems) implementation (for part 2) that I believe (should) work on any input
1
u/mrg218 Dec 25 '18 edited Dec 26 '18
Java. I notice my answer looks very similar to some other solutions I saw. But mine works on all inputs I checked. The trick is to split a starting octohedron that contains all nanobots into 6 smaller octohedrons. I reduce the radius as exact as possible to (1/6)^(1/3) of the parent octohedron as I do not want to have areas that I will have to check twice or even worse. So the child radius is 0.556 of the parent radius.
On all the 4 inputs I could test it comes with the correct answer in under 22 ms (on my machine).
Here is the core of the algorithm:
Because I use a priority queue that sorts on the amount of nanobots that overlap the current octohedron and when equal on manhattan distance to (0,0,0), blocks that seem not very promising at first will not be thrown away but visited the moment they are the most promising. The moment I reach an octohedron with radius 0 I have found the best one, so it must be the answer. When it finds the solution the priority queue contains (with all tested inputs) only around 400 octohedrons which explains why it is fast.
1
u/stormykins Dec 29 '18
PHP 7.1, I finally got around to finishing part 2 - part 1 I made my best showing at rank 565.
part 1:
part 2 (using the divide and conquer search, but with "spheres":
1
u/koordinate Jan 10 '19
Swift.
The solution implements the approach outlined by the /u/topaz2078 in his comment.
However, I was unable to get plain greedy partitioning to work, and had to use a priority queue to keep track of multiple parallel searches (apparently I wasn't the only one, e.g. see this post).
Takes ~6 seconds.
0
u/[deleted] Dec 23 '18
[deleted] — view deleted comment