Advent of Code - Day 6

Note by the Moderators: This topic is to talk about Day 6 of the Advent of Code.

For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.

Anybody do this yet?

I can’t even figure out how they want me to build the areas. The description just leaves me like… :dizzy_face:

A certain square belongs to point X, if there is no other point Y that is closer than X using Manhattan distance.

I struggled with this one more than I’m willing to admit, and ultimately made a brute-force solution which works reasonably fast and is not very ugly. You can find it here.

1 Like

Today was a bit tricky… I scraped my elixir solution and wrote one in javascript (which would be trivial to translate to Elixir now when I know how).

Part 1.
I implemented a “flood fill” algorithm, relying on the fact that it is easy to enumerate all positions with distance N from a given position.

Part 2.
Step 1. Find the center of gravity
Step 2. ´Enumerate all positions with distance N from the center, count positions where the condition is true (sum all manhattan distances to the position). Continue to do this with distance N + 1, stop when the conditions fails for all positions in a level (N).

1 Like

Finally I found the time to sit down and do day 6.

I’m not very happy with the code, as it is brute force.

Part 1 checks every square in a given bounding box for the nearest coordinate from the input, and returns a list of tuples, where the first element is the input coordinate and the second the actual field. Then I group by the input coordinate and reject those that are infinite (an area is classified as infinite if the line to the “owner” is orthogonal to the edge this field is on). Then just map the length of the lists and find the maximum…

Part 2 is even more brute force. It scans all coordinates in the bounding box, calculates the sum of the distances and rejects all fields that have a sum greater than or equal the threshold.


TIL: Enum.group_by has a third argument, that can be used to alter the value inserted in the list. Such that Enum.group_by(input, key_fun, val_fun) is equivalent to input |> Enum.group_by(key_fun) |> Enum.map({k, values} -> {k, Enum.map(values, val_fun) end)}) |> Enum.into(%{}), well roughly. I think you see what I mean…


My code is available at gitlab, as usual:

Today’s challenge is rough. I’ve just completed part 1 after a lot of head scratching before I realised that my issue was in determining what were the infinite coordinates. I too had to resort to a brute-force approach so it will be really interesting to look at some of the other solutions posted as well as José’s code from his stream tomorrow.

I’m going to have a quick look at part 2 but that may become a weekend task. Along with the other ones. This could be where I start to fall behind a bit.

Edit 22 minutes later… Part 2 was way, way easier for me. Fortunately!

My solution is at:

I’m not overly proud of the code but it’s late and I need some sleep!

This one wasn’t pretty. Both solutions were rather brute force, but they completed quickly enough. https://github.com/sorentwo/aoc_2018/blob/master/lib/aoc/day_06.ex

I thought I was doing okay until I went to submit my answer. I can’t figure out what I’m doing wrong, I can get the example/test data to work but not my input. Obviously I’m doing something stupid, but can’t see what.

Can anyone else see what the heck I’m doing wrong?

Looking at your code, it seems you assume that the finite region is a square, when it’s in fact a rectangle. So instead of finding one min-max pair, like you do in line 24, you need two pairs ((xmin, xmax) and (ymin, ymax)), and eliminate coordinates where x == xmin or xmax, or y == ymin or ymax.

1 Like

I was being told by AoC site that my answer for part1 is wrong. So I tried @sasajuric 's code from the repo and the output generated was exactly the same.

Here is my input file content.

118, 274
102, 101
216, 203
208, 251
309, 68
330, 93
91, 179
298, 278
201, 99
280, 272
141, 312
324, 290
41, 65
305, 311
198, 68
231, 237
164, 224
103, 189
216, 207
164, 290
151, 91
166, 250
129, 149
47, 231
249, 100
262, 175
299, 237
62, 288
228, 219
224, 76
310, 173
80, 46
312, 65
183, 158
272, 249
57, 141
331, 191
163, 359
271, 210
142, 137
349, 123
55, 268
160, 82
180, 70
231, 243
133, 353
246, 315
164, 206
229, 97
268, 94

And the output generated by both mine and @sasajuric 's code is 5047. Can someone else, who has completed the part 1 successfully, please try running this input through their code and share the output…

I get the answer 3251 for your input.

Here is my solution.

1 Like

My solver has a much lower result of 3253.

@bjorng @NobbZ Strange… I suppose that the outputs of both of your codes was accepted… and they are giving different outputs for the same input… Anyways, thanks for the quick reply. I will go through your programs and try to find why I am getting a much higher output (and even @sasajuric’s answer is giving the same).

Yes, it generates a solution which is accepted for my own input.

Your input though discovered a bug in my code to find the bounding box, I was missing a clause in the giant case/2 beginning on line #46 of y2018/d6.ex, which actually reminds me that I wanted to rewrite that one anyway.

Will you be rewriting it anytime soon?

Not this year. My wife and my son are in the kitchen, preparing Berliner, I do play a bit with my 2 years old to keep her out of the kitchen for now :slight_smile: and of course, as a side-job we prepare the diner-table for the big “table-grill” tonight.

oh yes right, sorry! Happy New Year !

1 Like

The change was much quicker to do than I expected, and also my wife and kids are in the bath now, as the dough has to rest.

It doesn’t change the result for your input,. nor mine.

Yes, the output of my code was accepted for my input.

Was neither 3251 nor 3253 accepted? Was there any hint whether the answers were too low or too high?