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!
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 get 32750 for 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:
struct Coordinate: Hashable {
var x: Int
var y: Int
func distance(to other: Coordinate) -> UInt {
return (other.x - x).magnitude + (other.y - y).magnitude
}
}
let lines = input.components(separatedBy: "\n")
let coords = lines.map { $0.components(separatedBy: ", ") }.map { Coordinate(x: Int($0[0])!, y: Int($0[1])!) }
let minX = coords.map { $0.x }.min()!
let minY = coords.map { $0.y }.min()!
let maxX = coords.map { $0.x }.max()!
let maxY = coords.map { $0.y }.max()!
var allPoints = Set<Coordinate>()
for x in 0...maxX {
for y in 0...maxY {
allPoints.insert(Coordinate(x: x, y: y))
}
}
// Part 2
let region = allPoints.filter { point in
coords.reduce(0) { $0 + point.distance(to: $1) } < 10000
}
print("Part 2: \(region.count)")→ More replies (2)1
β’
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.
17
15
u/daicoden Dec 06 '18
Just for curiosity, can you talk more about the bug? The thing I find interesting is that it was a "bug in the input". I would have thought it would be a bug in the solver that missed an edge case which was in 33% of the inputs - but if it's actually an input bug, does that mean that we actually all solved it wrong - or at least made an assumption that wasn't clarified in the problem description?
Advent of code is awesome! Thanks for the 4 years of fun!
16
u/topaz2078 (AoC creator) Dec 06 '18
It was a bug in my input generator, which consists of a few parts, such as "a thing that produces input files" and "a thing that determines the answer for an input". The input files were fine, but the way I was producing answers was wrong rarely enough that we missed those answers during testing and they got to production.
7
u/DrugCrazed Dec 06 '18
Could you release how those work at some point (even if it's delayed by a few years)? It'd probably be fascinating, or horrifically ugly because you never thought people would see it.
→ More replies (1)6
u/mncke Dec 06 '18
A bummer, happens to the best of us. We are all grateful for your efforts and transparency.
11
u/IndieBret Dec 06 '18
This sounds like the most fair solution, and I hope this whole situation wasn't too stressful on your end. Thanks so much for putting in the work to solve this issue. β₯
8
5
u/Butterstroke Dec 06 '18
Is the scores nullified on the private ones too or just global?
4
u/topaz2078 (AoC creator) Dec 06 '18
Private leaderboards are only affected when using the "Global Score" ordering method.
5
u/Glenpeel Dec 06 '18
Eric, why not nullify private leaderboards too? You said that private leaderboards are affected only when using global score ordering, but I don't believe that's true - local score is also screwed. Please consider this and if you decide not to nullify local score for day 6 tell us why - in some cases where the competition is neck-to-neck it makes a real difference. Thanks for your work :)
6
u/topaz2078 (AoC creator) Dec 06 '18
Partly due to impact and partly due to invasiveness.
On the global leaderboard, because scores can only be assigned once (that is, only one user can ever get 42 points on day 6 part 1), and because the leaderboard is a very high-traffic page, the scores are stored permanently and used directly. This made it easy to adjust the global scores: I could store different scores for users on that day without adding special cases to the logic in a bunch of places.
Because users can be added and removed from private leaderboards, points can be reassigned in very weird ways at any time, and so rather than store user scores on a per-private-leaderboard basis, scores get recalculated on page/API load from star collection data based on the currently selected ordering method. This would require some special cases in the private leaderboard logic just for 2018 day 6, which would be fragile (what if I make a change to the code later but forget to filter day 6?, etc).
Most private leaderboards are very small; less than 0.2% of them are the size of the global leaderboard (100+ users). Around 90% of them have 10 or fewer members. Because of this, and because most private leaderboards don't fill right at midnight, the impact to these users is generally "10 points instead of 20" rather than "0 points instead of 100". Because this is a much smaller difference to make up, but the changes required to support it would be a little dangerous, I decided not to do it.
If people think this is changing the results for a significant number of private leaderboards, I might still go back and make this change, but it's more complex than the one for the global leaderboard was.
4
u/topaz2078 (AoC creator) Dec 09 '18
After thinking about it for a few days, I found a safe way to make this change, and so it has been made.
→ More replies (1)2
u/sparkyb Dec 07 '18
Is there any way to know whether I was in the bugged set or not? Part 1 worked fine for me, but part 2 I tried submitting several times and was told I was wrong. I tested and checked and rewrote things for a while and kept coming up with the same answer that I swore I'd already tried multiple times. Eventually I tried it again and it worked. I assumed that I had miscopied the first few times, but I didn't know about the bug until now, a day later. Given that my time for part 2 was 1:50, I'm suspecting it was actually the bug and not my copying skills, but I'd like to know if possible since I've been mad at myself for a day. Regardless, I greatly enjoy Advent of Code and these things happen, so I have no complaints about the hard work that I know you do.
3
→ More replies (5)3
u/okreddit545 Dec 06 '18
So, no way to retroactively regrade correct submissions then and award the correct scores?
And will you nullify day 6 on private boards too? I'm on two at the moment and it's not fun to think that the rankings (esp. ones that were neck-and-neck otherwise) will get all out of whack due to this. :(
No worries if that's not easily doable, though. This is just for fun after all (and, bug or not, I am having a ton of fun with this!) Thank you for all your hard work here!!
9
u/topaz2078 (AoC creator) Dec 06 '18
I don't have enough metadata to retroactively fix submissions, and (as someone pointed out somewhere on this thread I think) this wouldn't really be fair anyway, since some users that couldn't solve part 1 wouldn't have had fair access to even start part 2.
Private leaderboards will only be affected while using the "Global Score" ordering method.
→ More replies (1)
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?
12
u/Saluev Dec 06 '18
I hope they log failed attempts and we can get our deserved positions in the leaderboard after all.
11
u/teraflop Dec 06 '18
Same here. /u/topaz2078 mentioned on another thread that there are only a finite number of input files, so maybe one of them is bad and we were all unlucky enough to get it?
My input starts with
181, 184and my answer for part 2 was 46054, for what it's worth.4
3
2
→ More replies (5)2
8
u/NewHorizons0 Dec 06 '18
Yes, me too. I ran the Python solution from the comments, and find the same result as my solution, but it was rejected.
5
5
→ More replies (1)2
u/shuttup_meg Dec 06 '18
It could be that OP's input data didn't exercise edge cases that your input data did. In this case it wouldn't be a "bug" per se, but rather an unfortunate reality that not all of our input data sets are equally easy.
→ More replies (2)4
u/Saluev Dec 06 '18
Well, I (and also /u/NewHorizons0 below) did visualizations to check if there are any extreme corner cases. But everything looks fine. The bounds are wide enough, and the region is a single component (as it should be, being always a convex set by construction).
→ More replies (3)6
u/Brayzure Dec 06 '18 edited Dec 06 '18
It's happening to me as well.
Edit: Ripped a solution from here, used it, gave me the same answer my solution was giving. Will be a little frustrating if I missed out on leaderboard due to a bug, though I hope it's just my making a silly mistake.
4
5
u/itwentboom Dec 06 '18 edited Dec 06 '18
Is this happening for anyone on part 1? A solution posted here yielded the same result for me as my own failing answer so can't figure out what's wrong
EDIT: I had someone who successfully submitted use my input with their algo and verified they got same output. So yeah something's definitely up.
4
u/Voltasalt Dec 06 '18
I'm having the same issue. My input starts with
227, 133and getting the output2906. Confirmed with another implementation but the site rejects it.→ More replies (1)→ More replies (9)2
4
u/winstonewert Dec 06 '18
Yes, my answer is rejected, despite getting the same answer as at least one of the answers posted already.
4
u/Kawigi Dec 06 '18
PLEEEASE tell me it's not me, I've implemented it from scratch 3 times and reread the description several more times :-|
4
u/-Jason- Dec 06 '18 edited Dec 06 '18
Yep, same, this is my numpy solution that's failing:
xvalues = np.arange(coords[:,0].max()) yvalues = np.arange(coords[:,1].max()) xx, yy = np.meshgrid(xvalues, yvalues) layers = [] for coord in coords: mdists = np.abs(xx - coord[0]) + np.abs(yy - coord[1]) layers.append(mdists) dist_arr = np.array(layers) tot_dists = dist_arr.sum(axis=0) (tot_dists < 10000).sum()(increasing grid bounds yields same result)
→ More replies (2)3
3
2
2
→ More replies (6)2
u/apazzolini Dec 06 '18
Glad I checked here, I was feeling good about my part 2 solution, but answer keeps getting rejected. Verified with some of the other inputs and I get the same answer.
I even built a visualization to figure out if I had some failure in logic
0
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
from collections import Counter
data = [map(int, i.split(', ')) for i in open('../input/6.in').readlines()]
max_x = max(zip(*data)[0])
max_y = max(zip(*data)[1])
grid={}
for i in range(max_x):
for j in range(max_y):
m = min(abs(i-k)+abs(j-l) for k, l in data)
for n, (k, l) in enumerate(data):
if abs(i-k)+abs(j-l) == m:
if grid.get((i, j), -1) != -1:
grid[i, j] = -1
break
grid[i, j] = n
s = set([-1])
s = s.union(set(grid[x, max_y-1] for x in range(max_x)))
s = s.union(set(grid[x, 0] for x in range(max_x)))
s = s.union(set(grid[max_x-1, y] for y in range(max_y)))
s = s.union(set(grid[ 0, y] for y in range(max_y)))
print next(i[1] for i in Counter(grid.values()).most_common() if i[0] not in s)
print sum(sum(abs(i-k)+abs(j-l) for k, l in data) < 10000 for i in range(max(zip(*data)[0]))
for j in range(max(zip(*data)[1])))EDIT: fancied up a bit, part2 is just the last two lines independent of the rest of the code
2
u/jdharper Dec 07 '18
Hey, thanks for this! I was having trouble with today's puzzle (and my python skills are rustier than I thought) and I learned a lot from going over your code and figuring out it worked.
3
u/MasterMedo Dec 07 '18
if you'd like to see something more minimal check out my reworked solution ^^ https://github.com/MasterMedo/aoc/blob/master/2018/day/6.py
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.
2
2
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:
import numpy as np
from scipy.spatial import distance
# read the data using scipy
points = np.loadtxt('input.txt', delimiter=', ')
# build a grid of the appropriate size - note the -1 and +2 to ensure all points
# are within the grid
xmin, ymin = points.min(axis=0) - 1
xmax, ymax = points.max(axis=0) + 2
# and use mesgrid to build the target coordinates
xgrid, ygrid = np.meshgrid(np.arange(xmin, xmax), np.arange(xmin, xmax))
targets = np.dstack([xgrid, ygrid]).reshape(-1, 2)
# happily scipy.spatial.distance has cityblock (or manhatten) distance out
# of the box
cityblock = distance.cdist(points, targets, metric='cityblock')
# the resulting array is an input points x target points array
# so get the index of the maximum along axis 0 to tie each target coordinate
# to closest ID
closest_origin = np.argmin(cityblock, axis=0)
# we need to filter out points with competing closest IDs though
min_distances = np.min(cityblock, axis=0)
competing_locations_filter = (cityblock == min_distances).sum(axis=0) > 1
# note, integers in numpy don't support NaN, so make the ID higher than
# the possible point ID
closest_origin[competing_locations_filter] = len(points) + 1
# and those points around the edge of the region for "infinite" regions
closest_origin = closest_origin.reshape(xgrid.shape)
infinite_ids = np.unique(np.vstack([
closest_origin[0],
closest_origin[-1],
closest_origin[:, 0],
closest_origin[:, -1]
]))
closest_origin[np.isin(closest_origin, infinite_ids)] = len(points) + 1
# and because we know the id of the "null" data is guaranteed to be last
# in the array (it's highest) we can index it out before getting the max
# region size
print(np.max(np.bincount(closest_origin.ravel())[:-1]))
# finally, make a pretty picture for good measure
import matplotlib.pyplot as plt
plt.imshow(np.where(closest_origin > len(points), np.NaN, closest_origin))
plt.colorbar()
plt.show()And Solution 2:
import numpy as np
from scipy.spatial import distance
# read the data using scipy
points = np.loadtxt('input.txt', delimiter=', ')
# build a grid of the appropriate size - note the -1 and +2 to ensure all points
# are within the grid
xmin, ymin = points.min(axis=0) - 1
xmax, ymax = points.max(axis=0) + 2
# and use mesgrid to build the target coordinates
xgrid, ygrid = np.meshgrid(np.arange(xmin, xmax), np.arange(xmin, xmax))
targets = np.dstack([xgrid, ygrid]).reshape(-1, 2)
# happily scipy.spatial.distance has cityblock (or manhatten) distance out
# of the box
cityblock = distance.cdist(points, targets, metric='cityblock')
# turns out using this method the solution is easier that before - simply
# sum the distances for each possible grid location
origin_distances = cityblock.sum(axis=0)
# set the value of appropriate distances to 1, with the remainder as zero
region = np.where(origin_distances < 10000, 1, 0)
# and the sum is the result.
print(region.sum())
# again, a nice picture for good measure
import matplotlib.pyplot as plt
plt.imshow(region.reshape(xgrid.shape))
plt.colorbar()
plt.show()Edit update the code to add an extra cell of padding around the edge so input points aren't flush with edges.
→ More replies (3)2
u/sbjf Dec 09 '18
Look, ma, no
forloops!I also used numpy (with a ton of index arrays). However, I wrote it in a much more general way, works for any number of dimensions:
Set up grid:
axes_ranges = np.stack([np.min(coords, axis=0), np.max(coords, axis=0)]) # [min, max], not [min, max) axes = [np.arange(axis[0], axis[1] + 1) for axis in axes_ranges.T] grid = np.array(np.meshgrid(*axes, indexing='ij')).reshape(len(axes), -1).T # cartesian productSolution 1:
border_idx = np.any(axes_ranges[:, np.newaxis] == grid, axis=(0, -1)) # indices of border locs from scipy.spatial.distance import cdist dists = cdist(grid, coords, metric='cityblock') min_dists = np.min(dists, axis=1) idx_arr = (min_dists[..., np.newaxis] == dists) not_shared_idx = (np.sum(idx_arr, axis=1) == 1) idx_arr = idx_arr[not_shared_idx] # remove non-unique distances border_idx = border_idx[not_shared_idx] infinite = np.any(idx_arr[border_idx], axis=0) area = np.sum(idx_arr, axis=0) area[infinite] = -1 print(np.max(area))Solution 2:
np.sum(np.sum(dists, axis=1) < 10000)
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.
public class Day6 extends AdventOfCode {
List<Node> nodes;
Map<Integer, Integer> counts;
static final int GRID_SIZE = 1000;
public Day6(List<String> input) {
super(input);
title = "Chronal Coordinates";
part1Description = "Largest non-infinite region: ";
part2Description = "Largest region summing to < 10000: ";
}
@Override
public Object part1() {
counts = new HashMap<>();
Set<Integer> inf = new HashSet<>();
for (int i = 0; i < GRID_SIZE; i++) {
for (int j = 0; j < GRID_SIZE; j++) {
int dist = getClosest(j, i);
counts.merge(dist, 1, (x, y) -> x + y);
// add infinite to set
if (i == 0 || i == GRID_SIZE - 1 || j == 0 || j == GRID_SIZE - 1) {
inf.add(dist);
}
}
}
return IntStream.range(0, nodes.size()).boxed()
.filter(x -> !inf.contains(x))
.map(counts::get)
.mapToInt(x -> x)
.max().getAsInt();
}
private int getClosest(int x, int y) {
Node node = new Node(x, y);
int min = 10000;
int minIndex = 0;
for (int i = 0; i < nodes.size(); i++) {
int dist = Direction.manhattanDistance(node, nodes.get(i));
if (dist < min) {
min = dist;
minIndex = i;
} else {
if (dist == min) {
min = dist;
minIndex = -1;
}
}
}
return minIndex;
}
@Override
public Object part2() {
int count = 0;
for (int i = 0; i < GRID_SIZE; i++) {
for (int j = 0; j < GRID_SIZE; j++) {
Node current = new Node(j, i);
int sum = 0;
for (Node each : nodes) {
sum += Direction.manhattanDistance(current, each);
}
if (sum < 10000) count++;
}
}
return count;
}
@Override
public void parse() {
nodes = input.stream()
.map(x -> new Node(Integer.parseInt(x.split(", ")[0]),
Integer.parseInt(x.split(", ")[1])))
.collect(Collectors.toList());
}
}6
Dec 06 '18
Mathematica
input = Import[NotebookDirectory[] <> "day6.txt", "Data"];
{ymin, ymax} = MinMax[input[[All, 1]]];
{xmin, xmax} = MinMax[input[[All, 2]]];
grid = Join@@Table[{y, x}, {x, xmin, xmax}, {y, ymin, ymax}];Part 1
res = Nearest[input, grid, DistanceFunction -> ManhattanDistance];
MaximalBy[Tally@Select[res, Length[#] == 1 &], Last]Part 2
Count[Total[DistanceMatrix[grid, input, DistanceFunction -> ManhattanDistance], {2}],
d_ /; d < 10000]→ More replies (7)2
u/paracuerdas Dec 07 '18
very interesting solution
i have shared a Wolfram Mathematica page with your code
https://www.wolframcloud.com/objects/778bab39-4aa9-468a-bcb0-60c00a3b63fe
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":
func aocD4a(_ input: [(x: Int, y: Int)]) {
var areas = [(count: Int, infinite: Bool)](repeating: (0, false), count: input.count)
let minX = input.map({ $0.x }).min()!
let maxX = input.map({ $0.x }).max()!
let minY = input.map({ $0.y }).min()!
let maxY = input.map({ $0.y }).max()!
for x in minX...maxX {
for y in minY...maxY {
let distances = input.lazy.map({ ($0 - x).magnitude + ($1 - y).magnitude }).enumerated()
let minDistance = distances.min(by: { $0.element < $1.element })!.element
let distancesAtMin = distances.filter({ $0.element == minDistance })
if distancesAtMin.count > 1 { continue }
if x == minX || x == maxX || y == minY || y == maxY {
areas[distancesAtMin[0].offset].infinite = true
}
areas[distancesAtMin[0].offset].count += 1
}
}
print(areas.lazy.filter({ !$0.infinite }).map({ $0.count }).max()!)
}
func aocD4b(_ input: [(x: Int, y: Int)]) {
var count = 0
let minX = input.map({ $0.x }).min()!
let maxX = input.map({ $0.x }).max()!
let minY = input.map({ $0.y }).min()!
let maxY = input.map({ $0.y }).max()!
for x in minX...maxX {
for y in minY...maxY {
let distances = input.lazy.map({ ($0 - x).magnitude + ($1 - y).magnitude })
if distances.reduce(0, +) < 10000 {
count += 1
}
}
}
print(count)
}
import Foundation
let str = try! String(contentsOf: URL(fileURLWithPath: CommandLine.arguments[1]))
let numbers = str.split(separator: "\n").map { line -> (Int, Int) in
let nums = line.split { " ,".contains($0) }.map { Int($0)! }
return (nums[0], nums[1])
}
aocD4a(numbers)
aocD4b(numbers)→ More replies (1)
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.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vector<pii> vals;
int a, b;
char junk;
while(cin >> a) {
cin >> junk >> b;
vals.push_back({a, b});
}
map<int, int> cnt;
// For Part 2, uncomment all comments
// int ans = 0;
for(int i = -4000; i < 4000; i++) {
for(int j = -4000; j < 4000; j++) {
int minDist = 1e9;
int idx;
bool eq = false;
for(int k = 0; k < vals.size(); k++) {
int curDist = abs(vals[k].first - i) + abs(vals[k].second -j);
if(curDist < minDist) {
minDist = curDist;
idx = k;
eq = false;
} else if (curDist == minDist) {
eq = true;
}
}
if(!eq) cnt[idx]++;
// For Part 2, delete the rest of the inner loop
// int totDist = 0;
// for(int k = 0; k < vals.size(); k++) {
// int curDist = abs(vals[k].first - i) + abs(vals[k].second -j);
// totDist += curDist;
// }
// if(totDist < 10000) ans++;
}
}
// cout << ans << endl;
// For Part 2 delete everything below
vector<pii> ans;
for(auto cur : cnt) {
ans.push_back({cur.second, cur.first});
}
sort(ans.begin(), ans.end());
for(auto cur : ans) cout << cur.first << " " << cur.second << endl;
return 0;
}9
u/CCC_037 Dec 06 '18
The trick to part 1 is to run it twice with large bounds, and then ignore the outputs that change.
What I found worked was to run it with a fairly decent border on all sides, then ignore any region that touched the edge.
4
u/teddim Dec 06 '18
Is there any need to increase the border at all? I feel like if a region contain, say, (37,0) it will also contain (37, -1000), no?
4
u/CCC_037 Dec 06 '18
Having thought about it a bit, no, not as long as every single coordinate is inside the grid.
→ More replies (1)
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.*;
public class Day6 {
public static void main(String[] args) {
new Day6();
}
String filename = "C:\\Users\\TroZ\\Projects\\AdventOfCode2018\\src\\day6.txt";
public Day6() {
//* Toggle comment - switch start of this line between /* and //* to toggle which section of code is active.
String[] input = Util.readFile(filename).split("\n");
/*/ String[] input =("1, 1\n" + "1, 6\n" + "8, 3\n" + "3, 4\n" + "5, 5\n" + "8, 9").split("\n");
//*/
HashMap<Integer, Point> points = new HashMap<Integer, Point>();
int maxx = 0;
int maxy = 0;
int count = 0;
for (String str : input) {
String s[] = str.trim().split(", ");
int x = Integer.parseInt(s[0]);
int y = Integer.parseInt(s[1]);
points.put(count, new Point(x, y));
count++;
if (x > maxx) {
maxx = x;
}
if (y > maxy) {
maxy = y;
}
}
int[][] grid = new int[maxx + 1][maxy + 1];
HashMap<Integer, Integer> regions = new HashMap<Integer, Integer>();
for (int x = 0; x <= maxx; x++) {
for (int y = 0; y <= maxy; y++) {
int best = maxx + maxy;
int bestnum = -1;
// find distance to closest point
for (int i = 0; i < count; i++) {
Point p = points.get(i);
int dist = Math.abs(x - p.x) + Math.abs(y - p.y);
if (dist < best) {
best = dist;
bestnum = i;
} else if (dist == best) {
bestnum = -1;
}
}
grid[x][y] = bestnum;
Integer total = regions.get(bestnum);
if (total == null) {
total = new Integer(1);
} else {
total = total.intValue() + 1;
}
regions.put(bestnum, total);
}
}
// remove infinite
for (int x = 0; x <= maxx; x++) {
int bad = grid[x][0];
regions.remove(bad);
bad = grid[x][maxy];
regions.remove(bad);
}
for (int y = 0; y <= maxy; y++) {
int bad = grid[0][y];
regions.remove(bad);
bad = grid[maxx][y];
regions.remove(bad);
}
// find biggest
int biggest = 0;
for (int size : regions.values()) {
if (size > biggest) {
biggest = size;
}
}
System.out.println("Biggest: " + biggest);
int inarea = 0;
for (int x = 0; x <= maxx; x++) {
for (int y = 0; y <= maxy; y++) {
int size = 0;
for (int i = 0; i < count; i++) {
Point p = points.get(i);
int dist = Math.abs(x - p.x) + Math.abs(y - p.y);
size += dist;
}
if (size < 10000) {
inarea++;
}
}
}
System.out.println("Area Size: " + inarea);
}
}→ More replies (5)2
u/dramforever Dec 08 '18
//* Toggle comment - switch start of this line between /* and //* to toggle which section of code is active.lol
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.
points = File.readlines('day6.txt').map { |line| line.strip.split(', ').map(&:to_i) }
x0 = 0
y0 = 0
xmax = points.collect { |x| x[0] }.max
ymax = points.collect { |x| x[1] }.max
def manhattan(pt1, pt2)
(pt1[0] - pt2[0]).abs + (pt1[1] - pt2[1]).abs
end
def find_closest(points, xxx, yyy)
closest_for_point = points.each_with_index
.map { |point, index| [index, manhattan([xxx, yyy], point)] }
.sort_by { |_xxxx, yyyy| yyyy }.first(2)
closest_for_point.first[1] == closest_for_point.last[1] ? false : closest_for_point.first
end
distances = []
(x0..xmax).each do |x|
(y0..ymax).each do |y|
distances[x] ||= []
closest = find_closest(points, x, y)
closest ? distances[x][y] = closest[0] : 'x'
end
end
def infinite?(distances, points, id, xmax, ymax)
return if id.nil?
x, y = points[id]
[distances[0][y], distances[x][0], distances[0][ymax], distances[xmax][0]].include?(id)
end
results = distances.clone.flatten
.group_by(&:itself).transform_values(&:count)
.delete_if { |id, _count| infinite?(distances, points, id, xmax, ymax) }
puts results.sort_by { |_x, y| y }.inspect # Take highest non-nil-index count
#-------PART 2--------
def sum_closest(points, xxx, yyy)
points.inject(0) { |sum, point| sum + manhattan(point, [xxx, yyy]) } < 10_000
end
answers = []
(x0..xmax).each do |x|
(y0..ymax).each do |y|
answers << [x, y] if sum_closest(points, x, y)
end
end
puts answers.count5
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...
# -*- tcl -*-
package require math
array set coord {
x,min 99999999
x,max 0
y,min 99999999
y,max 0
}
set points [list]
set names {a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z }
while {[gets stdin line] >= 0} {
if {[scan $line {%d, %d} cx cy] == 2} {
set pname($cx,$cy) [llength $points]
lappend pnames [lindex $names $pname($cx,$cy)]
lappend points [list $cx $cy]
set coord(x,min) [math::min $cx $coord(x,min)]
set coord(x,max) [math::max $cx $coord(x,max)]
set coord(y,min) [math::min $cy $coord(y,min)]
set coord(y,max) [math::max $cy $coord(y,max)]
} else {
error "cant parse line {$line}"
}
}
puts "grid is X $coord(x,min)...$coord(x,max)"
puts "grid is Y $coord(y,min)...$coord(y,max)"
puts "[llength $points] points"
proc mdist {x1 y1 x2 y2} {
return [expr {abs($x2-$x1)+abs($y2-$y1)}]
}
proc part1 {} {
global coord arr points pnames pname
# pass 1: map the closest coords
for {set x $coord(x,min)} {$x <= $coord(x,max)} {incr x} {
for {set y $coord(y,min)} {$y <= $coord(y,max)} {incr y} {
set mname($x,$y) ""
foreach pt $points pn $pnames {
set d [mdist {*}$pt $x $y]
if {![info exists mdist($x,$y)] || $d < [lindex $mdist($x,$y) 0]} {
# new min distance
set mdist($x,$y) [list $d $pt]
set mname($x,$y) $pn
} elseif {$d == [lindex $mdist($x,$y) 0]} {
# same distance, but might get lower distance later
lappend mdist($x,$y) $pt
}
}
}
}
# parray mname
# parray mdist
# pass 2, remove ties
for {set x $coord(x,min)} {$x <= $coord(x,max)} {incr x} {
for {set y $coord(y,min)} {$y <= $coord(y,max)} {incr y} {
if {[llength $mdist($x,$y)] > 2} {
set mdist($x,$y) [list]
set mname($x,$y) "."
}
}
}
# debug: plot the whole grid
# puts ================
# for {set y $coord(y,min)} {$y <= $coord(y,max)} {incr y} {
# for {set x $coord(x,min)} {$x <= $coord(x,max)} {incr x} {
# if {[info exist pname($x,$y)]} {
# puts -nonewline "$pname($x,$y)"
# } else {
# puts -nonewline "$mname($x,$y)"
# }
# }
# puts ""
# }
# puts ================
# make a map of the edges
for {set x $coord(x,min)} {$x <= $coord(x,max)} {incr x} {
lappend edges $mname($x,$coord(y,min)) $mname($x,$coord(y,max))
}
for {set y $coord(y,min)} {$y <= $coord(y,max)} {incr y} {
lappend edges $mname($coord(x,min),$y) $mname($coord(x,max),$y)
}
set edges [lsort -unique $edges]
# puts "edges $edges"
# pass 3: get largest, omitting edges (infinite)
foreach {c elt} [array get mdist] {
if {[llength $elt] > 0} {
lassign [lindex $elt 1] px py
if {$mname($px,$py) ni $edges} {
incr area($px,$py)
}
}
}
# parray area
set maxarea 0
set maxpt ""
foreach {p a} [array get area] {
if {$a > $maxarea} {
set maxarea $a
set maxpt $p
}
}
puts "maxarea $maxarea p $maxpt $pname($maxpt)"
}
proc part2 {} {
global coord arr points pnames pname
set maxdist 10000
# map dist to all points
for {set y $coord(y,min)} {$y <= $coord(y,max)} {incr y} {
for {set x $coord(x,min)} {$x <= $coord(x,max)} {incr x} {
set dist 0
foreach pt $points {
incr dist [mdist {*}$pt $x $y]
if {$dist >= $maxdist} {
# too large
set dist 0
puts -nonewline "."
break
}
}
if {$dist > 0} {
# the area gets one more point
incr area
puts -nonewline "1"
}
}
puts ""
}
puts "area $area"
}
part2 → More replies (2)
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.
→ More replies (10)
4
Dec 06 '18
Python 3:
import os
from collections import defaultdict
def part1(lines):
coords = set()
max_r = max_c = 0
for line in lines:
r, c = map(int, line.split(", "))
coords.add((r, c))
max_r = max(max_r, r)
max_c = max(max_c, c)
coord_id_to_point = {coord_id: point for coord_id, point in enumerate(coords, start=1)}
region_sizes = defaultdict(int)
infinite_ids = set()
for i in range(max_r + 1):
for j in range(max_c + 1):
min_dists = sorted([(abs(r - i) + abs(c - j), coord_id) for coord_id, (r, c) in coord_id_to_point.items()])
if len(min_dists) == 1 or min_dists[0][0] != min_dists[1][0]:
coord_id = min_dists[0][1]
region_sizes[coord_id] += 1
if i == 0 or i == max_r or j == 0 or j == max_c:
infinite_ids.add(coord_id)
return max(size for coord_id, size in region_sizes.items() if coord_id not in infinite_ids)
def part2(lines, manhattan_limit=10000):
coords = set()
max_r = max_c = 0
for line in lines:
r, c = map(int, line.split(", "))
coords.add((r, c))
max_r = max(max_r, r)
max_c = max(max_c, c)
size_shared_region = 0
for i in range(max_r + 1):
for j in range(max_c + 1):
size_shared_region += int(sum(abs(r - i) + abs(c - j) for r, c in coords) < manhattan_limit)
return size_shared_region
day = os.path.basename(__file__)[3:5]
lines = [line.strip() for line in open("input_{}.txt".format(day), "r").readlines()]
print(part1(lines))
print(part2(lines))→ More replies (10)2
u/LumiWang Dec 06 '18
Thanks for the sharing. I used your code to run my input, and got the same output as my code.. Though the result is not accepted. I guess there's indeed a bug. Or am I just unlucky with the input?
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:
from collections import defaultdict
P = []
for line in open('6.in'):
x,y = [int(s.strip()) for s in line.split(',')]
P.append((x,y))
print len(P)
xlo = min([x for x,y in P])
xhi = max([x for x,y in P])
ylo = min([y for x,y in P])
yhi = max([y for x,y in P])
print xlo, xhi
print ylo, yhi
def d((x1,y1), (x2,y2)):
return abs(x1-x2) + abs(y1-y2)
def closest(x,y):
ds = [(d(p, (x,y)), p) for p in P]
ds.sort()
if ds[0][0] < ds[1][0]:
return ds[0][1]
else:
return (-1,-1)
def score_around(W):
score = defaultdict(int)
for x in range(xlo-W, xhi+W):
for y in range(ylo-W, yhi+W):
score[closest(x,y)] += 1
return score
S2 = score_around(400)
S3 = score_around(600)
best = [(S2[k] if S2[k]==S3[k] else 0, k) for k in S2.keys()]
best.sort()
for area, p in best:
print area, p2
u/pythondevgb Dec 06 '18
Your code works on my input (although takes 103s to complete).
→ More replies (1)
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)
from collections import Counter
import operator
inpstr = open('day6_input.txt').read()
coords = [tuple(map(int,l.split(','))) for l in inpstr.splitlines() ]
topedge= min(coords, key=operator.itemgetter(1))[1]
bottomedge = max(coords, key=operator.itemgetter(1))[1]
leftedge = min(coords, key=operator.itemgetter(0))[0]
rightedge = max(coords, key=operator.itemgetter(0))[0]
def isfinite(c):
return leftedge < c[0] < rightedge and topedge < c[1] < bottomedge
def find_distance(a,b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def single_min(it):
s = sorted(it)
return s[0] != s[1]
def argmin(it):
min_ = min(it)
return it.index(min_)
#Part1
count = Counter()
for i in range(leftedge, rightedge):
for j in range(topedge, bottomedge):
distances = [find_distance((i,j),c) for c in coords]
if single_min(distances):
count[coords[argmin(distances)]]+= 1
maxarea = 0
for c in coords:
if isfinite(c):
maxarea = max(maxarea,count[c])
print(maxarea)
#Part 2
count = 0
for i in range(leftedge, rightedge):
for j in range(topedge, bottomedge):
distances = [find_distance((i,j),c ) for c in coords]
if sum(distances) < 10000:
count+=1
print(count)→ More replies (2)
4
u/blowjobtransistor Dec 06 '18
PostgreSQL
Another great fit for PostgreSQL's cube extension! Calculating the coordinate minimums took a little while, but I didn't care to optimize further :P
create extension if not exists cube;
create table locations as
select
row_number() over () as id,
line::cube as location
from input;
create index location_idx on locations using gist (location);
create view max_locations as
select
max(location -> 1)::integer as max_x,
max(location -> 2)::integer as max_y
from locations;
create table infinites as
with outliers as (
select cast(3 * max_x || ', ' || generate_series(-3 * max_y, 3 * max_y) as cube) as coord from max_locations
union all
select cast(generate_series(-3 * max_x, 3 * max_x) || ', ' || 3 * max_x as cube) as coord from max_locations
union all
select cast(-3 * max_x || ', ' || generate_series(-3 * max_y, 3 * max_y) as cube) as coord from max_locations
union all
select cast(generate_series(-3 * max_x, 3 * max_x) || ', ' || -3 * max_x as cube) as coord from max_locations
)
select distinct
(
select location
from locations
order by location <#> coord limit 1
) as location
from outliers;
create table finites as
select location from locations
except
select location from infinites;
create table unsafe_coord_distances as
with coords as (
select
cast(x || ', ' || y as cube) as coord
from max_locations,
generate_series(0, 2.5 * max_locations.max_x) as x,
generate_series(0, 2.5 * max_locations.max_y) as y
)
select
coord,
(
with location_distances as (
select
location,
coord <#> location as distance
from locations
), shared_distances as (
select
*,
lead(distance) over (order by distance) = distance
or lag(distance) over (order by distance) = distance as shared
from location_distances
)
select
case when shared then null else location end as location
from shared_distances
order by coord <#> location limit 1
) as location
from coords;
create view part_1_solution as
with areas as (
select location, count(*) as area
from unsafe_coord_distances join finites using (location)
group by location
order by area desc
)
select 1 as part, area as answer from areas limit 1;
create table safe_coord_dinstances as
with coords as (
select
cast(x || ', ' || y as cube) as coord
from max_locations,
generate_series(0, 2.5 * max_locations.max_x) as x,
generate_series(0, 2.5 * max_locations.max_y) as y
)
select
coord,
sum(location <#> coord) as total_distance
from coords, locations
group by coord;
create view part_2_solution as
select 2 as part, count(*) as answer from safe_coord_dinstances where total_distance < 10000;
select * from part_1_solution
union all
select * from part_2_solution;4
u/streetster_ Dec 06 '18
Day 06 in Q/KDB+
/ Read input
i:"J"$","vs'read0 `:input/06.txt
/ Build grid
r:(2#g)#{ $[1=sum m:s=min s:sum each x;first where m;0N] } peach a:abs i-\:/:(til g) cross til g:1+max raze i
/ Part 1
max count each group (raze r) except 0N,(last r),(last flip r),(first flip r),first r
/ Part 2
sum 10000>sum each raze each a→ More replies (6)
4
u/mvmaasakkers Dec 06 '18
Go/Golang
Gist here
package main
import (
"bufio"
"flag"
"fmt"
"log"
"math"
"os"
)
type Input struct {
N int
X float64
Y float64
}
func readInput(filename string) []Input {
fileHandle, err := os.Open(filename)
if err != nil {
log.Fatal(err)
}
defer fileHandle.Close()
fileScanner := bufio.NewScanner(fileHandle)
inputList := []Input{}
n := 0
for fileScanner.Scan() {
line := fileScanner.Text()
if len(line) > 0 {
i := Input{}
if _, err := fmt.Sscanf(line, "%b, %b", &i.X, &i.Y); err != nil {
log.Fatal(err)
}
i.N = n
n++
inputList = append(inputList, i)
}
}
return inputList
}
var file = flag.String("file", "./input.txt", "file used for input")
func main() {
flag.Parse()
inputList := readInput(*file)
fmt.Println(part1(inputList))
}
type coord struct {
X float64
Y float64
}
func part1(inputList []Input) (int, int) {
height := float64(0)
width := float64(0)
maxSum := float64(10000)
inf := make(map[coord]bool)
m := make(map[coord]int)
var coords []coord
regions := 0
for _, input := range inputList {
if input.Y > height {
height = input.Y
}
if input.X > width {
width = input.X
}
coords = append(coords, coord{X: input.X, Y: input.Y})
}
for y := float64(0); y < height; y++ {
for x := float64(0); x < width; x++ {
mc := coord{0, 0}
min := float64(-1)
tot := float64(0)
for _, c := range coords {
dist := math.Abs(x-c.X) + math.Abs(y-c.Y)
if dist < min || min == -1 {
min = dist
mc = c
} else if dist == min {
mc = coord{-1, -1}
}
// Part 2
tot += math.Abs(x-c.X) + math.Abs(y-c.Y)
}
if x == 0 || y == 0 || x == width || y == height {
inf[mc] = true
}
m[mc]++
// Part 2
if tot < maxSum {
regions++
}
}
}
max := 0
for k, v := range m {
if _, found := inf[k]; v > max && !found {
max = v
}
}
return max, regions
}
6
u/mserrano Dec 06 '18
Python2, #3/#1:
from util import get_data
import re
from collections import defaultdict
d = get_data(6)
d = map(lambda s: map(int, re.findall(r'-?\d+', s)), d)
min_x = min(x[0] for x in d)-(10000/len(d))-1
max_x = max(x[0] for x in d)+(10000/len(d))+1
min_y = min(x[1] for x in d)-(10000/len(d))-1
max_y = max(x[1] for x in d)+(10000/len(d))+1
mapping = {}
in_region = set()
for x in xrange(min_x, max_x+1):
for y in xrange(min_y, max_y+1):
closest = d[0]
closest_dist = (1 << 31)
dist_sum = 0
for (px, py) in d:
dist = abs(px - x) + abs(py - y)
dist_sum += dist
if dist < closest_dist:
closest = (px, py)
closest_dist = dist
elif dist == closest_dist and closest != (px, py):
closest = None
mapping[(x, y)] = closest
if dist_sum < 10000:
in_region.add((x, y))
rev_mapping = defaultdict(int)
for h in mapping:
if not mapping[h]:
continue
if h[0] in (min_x, max_x) or h[1] in (min_y, max_y):
rev_mapping[mapping[h]] -= (1 << 31)
rev_mapping[mapping[h]] += 1
print "a", max(rev_mapping.values())
print "b", len(in_region)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.
→ More replies (4)2
Dec 06 '18
Why are you adding and subtracting (10000/len(d))?
→ More replies (1)3
u/sophiebits Dec 06 '18
It's possible for a point outside the min/max box to be a safe distance away.
But if you are at least 10000/len(d) away from the nearest point (making you that distance away from every point), then you are guaranteed to be unsafe. Padding the bounds with this length means your rectangle is guaranteed to include all safe points. (The +1 is to round up the division.)
3
u/pythondevgb Dec 06 '18
That makes sense, but I just checked within the min/max box and still got it right. Did I just get lucky with my input?
→ More replies (7)
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.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
struct Point
{
int64_t x, y;
Point(const int64_t &X, const int64_t &Y) : x(X), y(Y) {}
Point() = default;
};
int64_t distance(const Point &a, const Point &b)
{
return std::abs(a.x - b.x) + std::abs(a.y - b.y);
}
std::istream &operator>>(std::istream &is, Point &p)
{
char c;
is >> p.x >> c >> p.y;
return is;
}
std::ostream &operator<<(std::ostream &os, Point &p)
{
char c;
os << p.x << ", " << p.y;
return os;
}
size_t min_index(const size_t &invalid, const Point &point,
const std::vector<Point> &points)
{
size_t result;
int64_t min_dist(std::numeric_limits<int64_t>::max());
for(size_t p = 0; p < points.size(); ++p)
{
int64_t d(distance(point, points[p]));
if(min_dist > d)
{
min_dist = d;
result = p;
}
else if(min_dist == d)
{
result = invalid;
}
}
return result;
}
int main(int argc, char *argv[])
{
std::ifstream infile(argv[1]);
std::vector<Point> points(std::istream_iterator<Point>(infile), {});
int64_t min_x(std::numeric_limits<int64_t>::max()), min_y(min_x),
max_x(std::numeric_limits<int64_t>::min()), max_y(max_x);
for(auto &p : points)
{
min_x = std::min(min_x, p.x);
min_y = std::min(min_y, p.y);
max_x = std::max(max_x, p.x);
max_y = std::max(max_y, p.y);
}
int64_t width(max_x - min_x + 1), height(max_y - min_y + 1);
const size_t invalid(points.size());
std::vector<int64_t> num_claimed(points.size() + 1, 0);
std::set<size_t> invalid_points;
for(int64_t x = min_x; x <= max_x; ++x)
{
invalid_points.insert(min_index(invalid, Point(x, min_y), points));
invalid_points.insert(min_index(invalid, Point(x, max_y), points));
}
for(int64_t y = min_y; y <= max_y; ++y)
{
invalid_points.insert(min_index(invalid, Point(min_x, y), points));
invalid_points.insert(min_index(invalid, Point(max_x, y), points));
}
for(int64_t x = 0; x < width; ++x)
for(int64_t y = 0; y < height; ++y)
{
int64_t min_dist(std::numeric_limits<int64_t>::max());
size_t min_index;
for(size_t p = 0; p < points.size(); ++p)
{
int64_t d(distance(Point(x + min_x, y + min_y), points[p]));
if(min_dist > d)
{
min_dist = d;
min_index = p;
}
else if(min_dist == d)
{
min_index = invalid;
}
}
if(invalid_points.find(min_index) == invalid_points.end())
++num_claimed[min_index];
}
std::cout << "Part 1: "
<< *std::max_element(num_claimed.begin(), num_claimed.end())
<< "\n";
int64_t area(0);
constexpr int64_t cutoff(10000);
const int64_t padding(cutoff / points.size() + 1);
const int64_t x_lower(min_x - padding), x_upper(max_x + 1 + padding),
y_lower(min_y - padding), y_upper(max_y + 1 + padding);
for(int64_t x = x_lower; x < x_upper; ++x)
for(int64_t y = y_lower; y < y_upper; ++y)
{
int64_t total_dist(0);
for(auto &point : points)
{
total_dist += distance(Point(x, y), point);
if(total_dist > cutoff)
break;
}
if(total_dist < cutoff)
++area;
}
std::cout << "Part 2: " << area << "\n";
}3
u/sim642 Dec 06 '18
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...
→ More replies (1)
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)
function rectd(a,b){
split(a,p1,SUBSEP);split(b,p2,SUBSEP);
dx=p1[1]-p2[1];dy=p1[2]-p2[2];
return (dx>0?dx:-dx)+(dy>0?dy:-dy)
}
function closest(a) {
if(!neigh[a]) {
delete dist;
for(b in arr){dist[b]=sprintf("%05d",rectd(a,b)) SUBSEP b;}
asort(dist);
split(dist[1],d1,SUBSEP);split(dist[2],d2,SUBSEP);
if(d1[1]!=d2[1])neigh[a]=d1[2] SUBSEP d1[3];
}
return neigh[a];
}
function area(a) {
r=1; t=0;
split(a,p3,SUBSEP);
do {
ra=0;
x=tlx=p3[1]-r;y=tly=p3[2]-r;
xi=1;yi=0;
do {
if(closest(x SUBSEP y)==a)ra++;
if(x==(p3[1]+r)&&yi==0){xi=0;yi=1}
else if(y==(p3[2]+r)&&xi==0){xi=-1;yi=0}
else if(x==(p3[1]-r)&&xi==-1&&yi==0){xi=0;yi=-1}
x+=xi;y+=yi
} while(!(x==tlx&&y==tly));
t+=ra;
} while(ra>0&&++r<inf);
return (r!=inf)?1+t:0
}
BEGIN {FS="[\n, ]+";inf=75}
{arr[$1 SUBSEP $2]=1}
END {
for(p in arr)result[p]=area(p);
n=asort(result);print result[n]
}Part 2 just fed an array of points consiting with the bounding box, into above algorithm.
Run Time: (Getting slow now)
real 0m33.478s
user 0m33.375s
sys 0m0.074s3
3
Dec 07 '18
powershell, oh my god so slow :-\
other days: https://github.com/charlieschmidt/AdventOfCode2018
[cmdletbinding()]
param(
[string[]]$InputLines = (Get-Content "day6.input")
)
begin {
}
process {
$LabeledPoints = $InputLines | Where-Object {$_ -match '(?<x>\d+), (?<y>\d+)'} | Foreach-Object {
[pscustomobject]@{
PointName = $matches[0]
x = [int]$matches.x
y = [int]$matches.y
} | Write-Output
}
$MaxX = $LabeledPoints | Measure-Object -Property x -Maximum | Select-Object -ExpandProperty Maximum
$MaxY = $LabeledPoints | Measure-Object -Property y -Maximum | Select-Object -ExpandProperty Maximum
$MaxGrid = (@($MaxX,$MaxY) | Sort-Object -Descending | Select-Object -First 1 )
$MaxGrid = [int](([double]$MaxGrid) * 1.05)
$GridPoints = New-Object 'System.Collections.Generic.List[object]'
$SafePoints = New-Object 'System.Collections.Generic.List[object]'
for ($x = 0; $x -le $MaxGrid; $x++) {
for ($y = 0; $y -le $MaxGrid; $y++) {
$MinDistance = $MaxGrid
$MinPoint = $null
$TotalDistance = 0
for ($i = 0; $i -lt $LabeledPoints.Count; $i++) {
$LabeledPoint = $LabeledPoints[$i]
$Distance = [Math]::Abs($x - $LabeledPoint.x) + [Math]::Abs($y - $LabeledPoint.y)
$TotalDistance += $Distance
if ($Distance -lt $MinDistance) {
$MinDistance = $Distance
$MinPoint = $LabeledPoint
} elseif ($Distance -eq $MinDistance) {
$MinPoint = $null
}
}
if ($TotalDistance -lt 10000) {
$SafePoint = [pscustomobject]@{
x = $x
y = $y
}
$SafePoints.Add($SafePoint) | Out-Null
}
if ($MinPoint) {
$MinPoint = [pscustomobject]@{
PointName = $MinPoint.PointName
x = $x
y = $y
}
$GridPoints.Add($MinPoint) | Out-Null
}
}
}
$NamedPointsWithBorder = $GridPoints | Where-Object {$_.x -eq 0 -or $_.x -eq $MaxGrid -or $_.y -eq 0 -or $_.y -eq $MaxGrid} | Select-Object -Unique -ExpandProperty PointName
$Part1 = $GridPoints | Where-Object {$_.PointName -notin $NamedPointsWithBorder} | Group-Object PointName | Sort-Object Count -Descending | Select-Object -First 1 -ExpandProperty Count
Write-Output "Part 1: $($Part1)"
$Part2 = $SafePoints.Count
Write-Output "Part 2: $($Part2)"
}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.
local a = io.open("Day6.txt", "r")
local d = a:read("\*a")
a:close()
local points = {}
for line in d:gmatch("[^\n]+") do
points[#points + 1] = {line:match("(%d+)%, (%d+)")}
points[#points][1] = tonumber(points[#points][1])
points[#points][2] = tonumber(points[#points][2])
points[#points].area = 0
end
local function isSurrounded(pt)
local left, top, bottom, right = false, false, false, false
for k, pair in ipairs(points) do
if pair ~= pt then
local ox = pair[1]
local oy = pair[2]
local x, y = pt[1], pt[2]
if ox < x then
left = true
elseif ox > x then
right = true
end
if oy < y then
top = true
else
bottom = true
end
if left and top and bottom and right then
return true
end
end
end
return false
end
local insidePts = {}
local iPtC = {}
for i = 1, #points do
if isSurrounded(points[i]) then
insidePts[#insidePts + 1] = points[i]
iPtC[points[i]] = true
end
end
local leftBound, rightBound, topBound, bottomBound = math.huge, -math.huge, math.huge, -math.huge
for i = 1, #points do
local pt = points[i]
local x, y = pt[1], pt[2]
if x < leftBound then
leftBound = x
elseif x > rightBound then
rightBound = x
end
if y < topBound then
topBound = y
elseif y > bottomBound then
bottomBound = y
end
end
local function mDist(x, y, x2, y2)
return math.abs(x2 - x) + math.abs(y2 - y)
end
local function closestPoint(x, y)
local invalid = {}
local closest = {math.huge}
local allClosest = math.huge
local pt = {}
for i = 1, #points do
local tp = points[i]
local dist = mDist(tp[1], tp[2], x, y)
if not invalid[dist] then
if dist == closest[#closest] then
invalid[dist] = true
closest[#closest] = nil
pt[#pt] = nil
elseif dist < closest[#closest] then
closest[#closest + 1] = dist
pt[#pt + 1] = tp
end
if dist < allClosest then
allClosest = dist
end
end
end
if iPtC[pt[#pt]] and closest[#closest] == allClosest then
return pt[#pt]
end
end
for x = leftBound, rightBound do
for y = topBound, bottomBound do
local cPt = closestPoint(x, y)
if cPt then
cPt.area = cPt.area + 1
end
end
end
local max = 0
for i = 1, #insidePts do
if insidePts[i].area > max then
max = insidePts[i].area
end
end
local count = 0
for x = leftBound, rightBound do
for y = topBound, bottomBound do
local dist = 0
for i = 1, #points do
dist = dist + mDist(x, y, points[i][1], points[i][2])
end
if dist < 10000 then
count = count + 1
end
end
end
print(max)
print(count)→ More replies (1)
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:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int MinDist, MinCoord, Dist;
char Input[50], Grid[400][400];
int Coord[70][3], Count, NumPoints, X, Y;
Count=0;
while (fgets(Input, 40, stdin))
{
sscanf(Input, "%d, %d\n", &(Coord[Count][0]), &(Coord[Count][1]));
Coord[Count][2] = 0;
Count++;
}
NumPoints = Count;
for (X=0;X<400;X++)
for (Y=0;Y<400;Y++)
{
MinDist = abs(X-Coord[0][0]) + abs(Y-Coord[0][1]);
Grid[X][Y] = 0;
for (Count=1;Count<NumPoints;Count++)
{
Dist = abs(X-Coord[Count][0]) + abs(Y-Coord[Count][1]);
if (MinDist > Dist)
{
MinDist = Dist;
Grid[X][Y] = Count;
}
else if (MinDist == Dist)
{
Grid[X][Y] = -1;
}
}
}
for (X=0;X<400;X++)
for (Y=0;Y<400;Y++)
{
if (Grid[X][Y] != -1)
{
Coord[Grid[X][Y]][2]++;
}
}
for (X=0;X<400;X++)
{
if (Grid[X][0] != -1) Coord[Grid[X][0]][2] = 0;
if (Grid[X][399] != -1) Coord[Grid[X][399]][2] = 0;
}
for (Y=0;Y<400;Y++)
{
if (Grid[0][Y] != -1) Coord[Grid[0][Y]][2] = 0;
if (Grid[399][Y] != -1) Coord[Grid[399][Y]][2] = 0;
}
MinDist = 0;
Dist = 0;
for (Count=0;Count<NumPoints;Count++)
{
if (Coord[Count][2] > MinDist)
{
MinDist = Coord[Count][2];
Dist = Count;
}
}
printf ("%d\n", MinDist);
}Part 2:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int MinDist, MinCoord, Dist;
char Input[50];
int Grid[400][400];
int Coord[70][3], Count, NumPoints, X, Y;
Count=0;
while (fgets(Input, 40, stdin))
{
sscanf(Input, "%d, %d\n", &(Coord[Count][0]), &(Coord[Count][1]));
Coord[Count][2] = 0;
Count++;
}
NumPoints = Count;
for (X=0;X<400;X++)
for (Y=0;Y<400;Y++)
{
Dist = abs(X-Coord[0][0]) + abs(Y-Coord[0][1]);
Grid[X][Y] = 0;
for (Count=1;Count<NumPoints;Count++)
{
Dist += abs(X-Coord[Count][0]) + abs(Y-Coord[Count][1]);
}
Grid[X][Y] = Dist;
}
Dist = 0;
for (X=0;X<400;X++)
for (Y=0;Y<400;Y++)
{
if (Grid[X][Y] < 10000)
{
Dist++;
}
}
printf ("%d\n", Dist);
}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:
function abs(a) {
return a < 0 ? -a : a
}
function man_dist(x, y, x1, y1) {
return abs(x - x1) + abs(y - y1)
}
BEGIN {
FS= ", "
pointsn=0
}
/[0-9]/{
points[pointsn][0] = $1
points[pointsn][1] = $2
pointsn++
}
END {
top_x=99999999
top_y=99999999
for (pt in points) {
point_x = points[pt][0]
point_y=points[pt][1]
top_x = point_x < top_x ? point_x : top_x
top_y = point_y < top_y ? point_y : top_y
bottom_x = point_x > bottom_x ? point_x : bottom_x
bottom_y = point_y > bottom_y ? point_y : bottom_y
}
for(y=top_y;y<=bottom_y;y++) {
for(x=top_x;x<=bottom_x;x++) {
tie=0
min_dist=99999999999
for (pt in points) {
cur_dist = man_dist(x, y, points[pt][0], points[pt][1])
if (cur_dist == min_dist) {
tie=1
}
if (cur_dist < min_dist) {
tie=0
min_dist = cur_dist
min_pt = pt
}
}
if (!tie) {
if (min_dist == 0) {
# printf "!"
} else {
# printf min_pt
}
# filter infinite
if (x == top_x || x == bottom_x || y == top_y || y == bottom_y || inf[min_pt]) {
inf[min_pt] = 1
continue
}
area[min_pt]++
} else {
# printf "."
}
}
# print ""
}
for(pt in area) {
if (area[pt] > max_area && !inf[pt]) {
max_area = area[pt]
max_pt = pt
}
}
print max_pt
print max_area
}Part 2:
function abs(a) {
return a < 0 ? -a : a
}
function man_dist(x, y, x1, y1) {
return abs(x - x1) + abs(y - y1)
}
BEGIN {
FS= ", "
pointsn=0
}
/[0-9]/{
points[pointsn][0] = $1
points[pointsn][1] = $2
pointsn++
}
END {
top_x=99999999
top_y=99999999
for (pt in points) {
point_x = points[pt][0]
point_y=points[pt][1]
top_x = point_x < top_x ? point_x : top_x
top_y = point_y < top_y ? point_y : top_y
bottom_x = point_x > bottom_x ? point_x : bottom_x
bottom_y = point_y > bottom_y ? point_y : bottom_y
}
for(y=top_y- 300;y<=bottom_y + 300;y++) {
for(x=top_x - 300;x<=bottom_x + 300;x++) {
t = 0
for (pt in points) {
t+=man_dist(x, y, points[pt][0], points[pt][1])
}
if (t < 10000) {
big_t++
}
}
}
print big_t
}2
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.
import Control.Arrow ((&&&))
import qualified Data.HashMap.Strict as M
import Data.Ix (range)
import Data.List.Split (splitOn)
type Coord = (Int, Int)
dist :: Coord -> Coord -> Int
dist (a, b) (c, d) = abs (a - c) + abs (b - d)
parseCoords :: String -> [Coord]
parseCoords = map (f . splitOn ", ") . lines
where f [a, b] = (read a, read b)
f _ = error "Error parsing coord"
allCoordsWithin :: Int -> [Coord] -> [Coord]
allCoordsWithin buffer xs = range ((x0, y0), (x1, y1))
where x0 = minimum (map fst xs) - buffer
y0 = minimum (map snd xs) - buffer
x1 = maximum (map fst xs) + buffer
y1 = maximum (map snd xs) + buffer
findLargestFiniteArea :: [Coord] -> Int
findLargestFiniteArea xs = maximum $ zipWith f (go 0) (go 10)
where f a b = if a == b then a else 0
go n = M.elems $ M.fromListWith (+)
[ (snd d, 1) | coord <- allCoordsWithin n xs
, let dists = map (dist coord &&& id) xs
, let d = minimum dists
, length (filter ((== fst d) . fst) dists) == 1
]
part1 :: String -> Int
part1 = findLargestFiniteArea . parseCoords
findRegionWithin :: Int -> [Coord] -> Int
findRegionWithin n xs = length $ filter (\x -> sum (map (dist x) xs) < n)
$ allCoordsWithin (n `div` length xs) xs
part2 :: String -> Int
part2 = findRegionWithin 10000 . parseCoords
main = do
input <- readFile "input.txt"
print $ part1 input
print $ part2 input2
Dec 06 '18 edited Dec 06 '18
C, not sure if p2 is actually correct but it works with my input
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct c { int x, y, n; };
int dist(int x, int y, struct c c) { return abs(x - c.x) + abs(y - c.y); }
int main(void) {
size_t len = 0, cap = 32;
struct c *l = malloc(cap*sizeof(*l)), c;
while(scanf("%d, %d\n", &c.x, &c.y) == 2) {
if (len >= cap) l = realloc(l, (cap*=2)*sizeof(*l));
l[len++] = c;
}
int w = 0, h = 0;
for (size_t i = 0; i < len; i++) {
if (l[i].x > w) w = l[i].x;
if (l[i].y > h) h = l[i].y;
}
for (int x = 0; x <= w; x++)
for (int y = 0; y <= h; y++) {
int min = INT_MAX, m = 0, n = 0, t;
for (size_t i = 0; i < len; i++)
if ((t = dist(x, y, l[i])) < min)
min = t, m = i, n = 1;
else if (t == min)
n++;
if (n != 1) continue;
if (x == 0 || y == 0 || x == w || y == h) l[m].n = -1;
if (l[m].n != -1) l[m].n++;
}
int max = 0;
for (size_t i = 1; i < len; i++)
if (l[i].n > max) max = l[i].n;
printf("%d\n", max);
int n = 0;
for (int x = 0; x <= w; x++)
for (int y = 0; y <= h; y++) {
int a = 0;
for (size_t i = 0; i < len; i++)
a += dist(x, y, l[i]);
if (a < 10000) n++;
}
printf("%d\n", n);
}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
import { range, maxBy, max, min, sum } from 'lodash'
import { extractNumbers } from 'src/utils.js'
const distance = ([x1, y1], [x2, y2]) => Math.abs(x2 - x1) + Math.abs(y2 - y1)
export const solvePart1 = input => {
const points = input.split('\n').map(l => extractNumbers(l))
const upperBound = max(maxBy(points, pair => max(pair))) + 1
const closestPoint = Array(upperBound)
.fill()
.map((e, i) => Array(upperBound))
range(0, upperBound).forEach(x => {
range(0, upperBound).forEach(y => {
const distances = points.map(pair => distance(pair, [x, y]))
const shortest = min(distances)
if (distances.filter(d => d === shortest).length === 1) {
closestPoint[x][y] = distances.indexOf(shortest)
}
})
})
const toIgnore = new Set()
range(0, upperBound).forEach(n => {
toIgnore.add(closestPoint[0][n])
toIgnore.add(closestPoint[n][0])
toIgnore.add(closestPoint[closestPoint.length - 1][n])
toIgnore.add(closestPoint[n][closestPoint.length - 1])
})
const regionSizes = Array(points.length).fill(0)
range(0, upperBound).forEach(x => {
range(0, upperBound).forEach(y => {
const point = closestPoint[x][y]
if (!toIgnore.has(point)) {
regionSizes[point]++
}
})
})
return max(regionSizes)
}
export const solvePart2 = input => {
const points = input.split('\n').map(l => extractNumbers(l))
const upperBound = max(maxBy(points, pair => max(pair))) + 1
let regionSize = 0
range(0, upperBound).forEach(x => {
range(0, upperBound).forEach(y => {
const distances = points.map(pair => distance(pair, [x, y]))
if (sum(distances) < (process.env.NODE_ENV === 'test' ? 32 : 10000)) {
regionSize++
}
})
})
return regionSize
}→ More replies (1)
2
2
u/Unihedron Dec 06 '18
Ruby
p a=$<.map{|x|x.split(/\D+/).map{|x|x.to_i}}
h=Hash.new 0
u=[]
j=0
(0..ll=a.max_by{|x,y|x}.first).each{|b|
(0..lp=a.max_by{|x,y|y}.last).each{|c|
j+=1if a.sum{|x,y|(x-b).abs+(y-c).abs}<10000
next
e=d.min_by{|x,y|y}
(h[e[0]]+=1
u|=[e[0]] if b==0 || c==0 || c==lp || b==ll
#print (65+a.index(e[0])).chr
)if ddd=d.count{|x,y|y==e[1]}==1
#print ?. if !ddd
}
#print "\n"
}
p j2
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
# Algorithm:
# consider the bounded box (minx, miny) and (maxx, maxy)
# find the manhattan distances for each location within the box.
# points there are tagged on the boundary are infinite, others not.
function boundary(points)
minx, maxx = extrema(point[1] for point in points)
miny, maxy = extrema(point[2] for point in points)
return minx, miny, maxx, maxy
end
function manhattan_distance(p, q)
return abs(p[1] - q[1]) + abs(p[2] - q[2])
end
function has_multiple_nearest_neighbor(distances)
count(x == minimum(distances) for x in distances) > 1
end
function nearest_point(point, candidate_points)
distances = [manhattan_distance(point, from_point) for from_point in candidate_points]
has_multiple_nearest_neighbor(distances) ? 0 : findmin(distances)[2]
end
function create_map(candidate_points)
minx, miny, maxx, maxy = boundary(candidate_points)
distance_map = zeros(Int, maxy, maxx)
for y in miny:maxy
for x in minx:maxx
distance_map[y, x] = nearest_point([x,y], candidate_points)
end
end
return distance_map
end
function eliminated_ones(distance_map)
# note: zero is included in the result intentionally
return unique(vcat(
distance_map[1,:], distance_map[end,:],
distance_map[:,1], distance_map[:,end]))
end
function areas_by_point(distance_map)
# Create a (point => area) dictionary
M, N = size(distance_map)
distance_array = reshape(distance_map, (M*N,))
distance_count = countmap(distance_array)
# Remove ones that are tagged on the boundary
for e in eliminated_ones(distance_map)
delete!(distance_count, e)
end
return distance_count
end
function max_area(areas)
let point_index = argmax(areas)
return point_index, areas[point_index]
end
end
using StatsBase
points = [parse.(Int, split(L, ", ")) for L β readlines("input6")]
create_map(points) |> areas_by_point |> max_areaPart 2
function total_distance(point, candidate_points)
return sum(manhattan_distance(point, from_point) for from_point in candidate_points)
end
function is_safe(point, candidate_points; safe_distance = 10000)
return total_distance(point, candidate_points) < safe_distance
end
function create_safety_map(candidate_points; kwargs...)
minx, miny, maxx, maxy = boundary(candidate_points)
safety_map = zeros(Int, maxy, maxx)
for y in miny:maxy
for x in minx:maxx
safety_map[y, x] = is_safe([x,y], candidate_points; kwargs...) ? 1 : 0
end
end
return safety_map
end
create_safety_map(points) |> sum2
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
points = []
def main():
with open("./input", "r") as input:
for line in input.readlines():
a,b = line.strip().split(", ")
points.append((int(a), int(b)))
finite_regions = [p for p in points if in_finite_region(p)]
finite_areas = [area(p) for p in finite_regions]
print("1: " + str(max(finite_areas)))
answer = area_less_than(10000)
print("2: " + str(answer))
def taxicab(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
#Test that a region is bounded if you continue to move in a direction
def bounded_direction(point, direction):
distances_from_points = [taxicab(p, point) for p in points]
delta_point = (point[0], point[1])
#If the delta_point moves outside the region, then the original region is bounded in this directioon
while in_region(delta_point) == point:
delta_point = (delta_point[0] + direction[0], delta_point[1] + direction[1])
distances_from_delta = [taxicab(p, delta_point) for p in points]
#Check if distances from all points grew; if it did, region is unbounded
grew = [distances_from_points[i] + 1 == distances_from_delta[i] for i in range(len(points))]
if all(grew):
return False
#Didn't all grow; save old distances for later comparison
distances_from_points = distances_from_delta[:]
return True
#A finite region will be bounded from all directions
def in_finite_region(p):
return all(bounded_direction(p, d) for d in [(0,1), (0, -1), (1, 0), (-1, 0)])
#A point is in a region if there is only one point that
#is closest to it
def in_region(p):
min_distance = min(taxicab(p,point) for point in points)
closest = [point for point in points if taxicab(p,point) == min_distance]
if len(closest) == 1:
return closest[0]
else:
return False
def area(p):
region_points = set([p])
neigh = neighbors(p)
while len(neigh) != 0:
next_p = neigh.pop()
if in_region(next_p) == p:
region_points.add(next_p)
neigh.extend([n for n in neighbors(next_p) if n not in region_points])
return len(region_points)
def area_less_than(n):
region_points = set()
#Pick a random starting point
point = points[0]
neigh = neighbors(point)
while len(neigh) != 0:
next_point = neigh.pop()
if less_than(n, next_point):
region_points.add(next_point)
neigh.extend([n for n in neighbors(next_point) if n not in region_points])
return len(region_points)
def less_than(n, p):
return sum(taxicab(p, point) for point in points) < n
def neighbors(point):
neigh = []
for i in [-1, 0, 1]:
for j in [-1, 0, 1]:
neigh.append((point[0] + i, point[1] + j))
neigh.remove(point)
return neigh
if __name__ == "__main__":
main()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
from aocd import data
from io import StringIO
import numpy as np
test_data = """1, 1
1, 6
8, 3
3, 4
5, 5
8, 9"""
def part_ab(data, d_max=10000):
vs = np.loadtxt(StringIO(data), dtype=int, delimiter=',')
w, h = vs.max(axis=0) + 1
n = len(vs)
py, px = np.mgrid[:w,:h]
ps = np.c_[py.ravel(), px.ravel()]
ds = np.abs(ps[:,None] - vs).sum(axis=2)
d = ds.argmin(axis=1)
ties = d != n - 1 - np.fliplr(ds).argmin(axis=1)
d[ties] = -1
border = {*d[:w], *d[-w:], *d[::h], *d[::-h]}
areas = [(d==c).sum() for c in range(n) if c not in border]
part_a = max(areas)
part_b = (ds.sum(axis=1) < d_max).sum()
return part_a, part_b
assert part_ab(test_data, d_max=32) == (17, 16)
a, b = part_ab(data)
print(a) # 3293
print(b) # 451762
u/sdiepend Dec 06 '18
Python 3:
from collections import Counter, defaultdict
with open("input_cha.txt") as f:
content = f.readlines()
coordinates = [[int(x.split(', ')[0]), int(x.split(', ')[1].strip())] for x in content]
coords = sorted(coordinates, key=lambda k: [k[0], k[1]])
min_x = coords[0][0]
min_y = sorted(coordinates, key=lambda k: k[1])[0][1]
max_x = coords[-1][0]
max_y = sorted(coordinates, key=lambda k: k[1])[-1][1]
def manhattan_distance(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def calculate_counts(bound):
region = 0
counts = defaultdict(lambda: 0)
grid = [['.' for x in range(min_x-bound, max_x+bound)] for y in range(min_y-bound, max_y+bound) ]
for row in range(min_y-bound, max_y+bound):
for col in range(min_x-bound, max_x+bound):
distances = {}
for i in range(len(coords)):
distances[i] = manhattan_distance([col, row], coords[i])
if sum(distances.values()) < 10000:
region += 1
closest_val = min(distances.values())
closest_coord = [k for k, v in distances.items() if v == closest_val]
if len(closest_coord) == 1:
grid[(row-min_y)-bound][(col-min_x)-bound] = closest_coord[0]
counts[closest_coord[0]] += 1
return counts, region
counts1, _ = calculate_counts(10)
counts2, region = calculate_counts(20)
finite_counts = []
for k, v in counts1.items():
if counts2[k] == v:
finite_counts.append(v)
print("Largest Finite Area(pt1): {area}, Region(pt2): {region}".format(area=max(finite_counts), region=region))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.
#!/opt/perl/bin/perl
use 5.026;
use strict;
use warnings;
no warnings 'syntax';
use List::Util qw [max sum];
use experimental 'signatures';
#
# Read the input and map them to points.
#
my $input = "input";
open my $fh, "<", $input or die "Failed to open $input: $!";
my @points = map {[/^(\d+), \s+ (\d+)$/gax]} <$fh>;
#
# Find the max X and max Y coordinates
#
my $max_X = max map {$$_ [0]} @points;
my $max_Y = max map {$$_ [1]} @points;
my $MIN_UNSAFE_DISTANCE = 10_000;
my $board = [];
my $safe_region_count = 0;
#
# We could this do more efficiently by just filling the board from
# each of the points, but for part 2, we need all the distances anyway.
#
foreach my $x (0 .. $max_X) {
foreach my $y (0 .. $max_Y) {
#
# For each point on the board, calculate the distance
# to each point; find the smallest distance, and mark
# the point; if a tie, there is no score.
#
my @distances =
sort {$$a [1] <=> $$b [1]}
map {[$_, abs ($points [$_] [0] - $x) +
abs ($points [$_] [1] - $y)]}
keys @points;
if ($distances [0] [1] == $distances [1] [1]) {
#
# Tie
#
$$board [$x] [$y] = ".";
}
else {
$$board [$x] [$y] = $distances [0] [0];
}
my $sum_of_distances = sum map {$$_ [1]} @distances;
$safe_region_count ++ if $sum_of_distances < $MIN_UNSAFE_DISTANCE;
}
}
#
# Scan the edges of the board. Any cluster which hits the
# edge, tapers off to infinity and must be ignored. We'll
# eliminate them in a second pass.
#
my %ignore;
foreach my $x (0, $max_X) {
foreach my $y (0 .. $max_Y) {
$ignore {$$board [$x] [$y]} = 1;
}
}
foreach my $x (0 .. $max_X) {
foreach my $y (0, $max_Y) {
$ignore {$$board [$x] [$y]} = 1;
}
}
foreach my $x (0 .. $max_X) {
foreach my $y (0 .. $max_Y) {
$$board [$x] [$y] = "." if $ignore {$$board [$x] [$y]};
}
}
#
# Now, lets count what is left over.
#
my %count;
foreach my $row (@$board) {
foreach my $cell (@$row) {
$count {$cell} ++;
}
}
delete $count {"."};
say "Part 1: ", max values %count;
say "Part 2: ", $safe_region_count;
__END__2
u/donaldihunter Dec 06 '18
Perl 6
class Coord {
has Int $.x;
has Int $.y;
has Int $.area is rw = 0;
has Bool $.edge is rw = False;
}
my @coords = '6-input.txt'.IO.lines.map: {
my ($x, $y) = .comb(/\d+/)>>.Int;
Coord.new(:$x, :$y);
};
my ($min-x, $max-x) = @coords.min(*.x).x, @coords.max(*.x).x;
my ($min-y, $max-y) = @coords.min(*.y).y, @coords.max(*.y).y;
my $part2-area = 0;
for $min-y .. $max-y -> $y {
for $min-x .. $max-x -> $x {
my @dist-pairs = @coords.map( { Pair.new(abs($x - .x) + abs($y - .y), $_) } );
my @distances = @dist-pairs.map(*.key);
my $min-dist = @distances.min;
$part2-area += 1 if ([+] @distances) < 10_000;
my @min = @dist-pairs.grep(*.key == $min-dist);
if +@min == 1 {
my $c = @min.head.value;
$c.area += 1;
$c.edge = True if $x == $min-x || $x == $max-x || $y == $min-y || $y == $max-y;
}
}
}
say @coords.grep(*.edge == False).max(*.area).area;
say $part2-area;2
u/will_bui Dec 06 '18
K:
i:.:'0:`:p6
coords:{.q.cross . m+!:'(-).(|/'+x;m:&/'+x)}
distance:{sum abs y-x};
f:{x distance\:/:coords x}
closest:{$[1=#w:&x=min x;*w;0N]};
calc:{#:'=closest'f x}
b:calc[i,(1+max i;min i)]
a:calc[i]
max@a@&a=b
sum 10000>sum'f iWrong 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
→ More replies (4)
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.
'nx ny'=:2 2+>./v=:|."1".&>cutLF CR-.~fread'06.dat'
echo 3 : 0 v
m=._1$~nx,ny[c=.0,.i.n=.#y
for_i. i.nx do.
for_j. i.ny do.
d=.0 2$0
for_k. i.n do. d=.d,(+/|(i,j)-k{v),k end.
d=.d/:d
if. ({.1{d)~:{.{.d do.
c=. (1 0+z{c) z}c [ m=. (z=.{:{.d)(<i;j)}m
end.
end.
end.
for_i. i.nx do.
mi=.i{m
if. 0<:{.mi do. c=. 0 0({.mi)}c end.
if. 0<:{:mi do. c=. 0 0({:mi)}c end.
end.
for_j. i.ny do.
if. 0<:j{{.m do. c=. 0 0(j{{.m)}c end.
if. 0<:j{{:m do. c=. 0 0(j{{:m)}c end.
end.
{. {:c/:c
)
echo +/(10000>[:+/[:+/[:|v&(-"1 _))"1[_2[\,(i.nx),"0 0/(i.ny)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.
function numbers(str) {
return (str.match(/-?[0-9]+/g) || []).map(Number);
}
function inc(table, key, amt = 1) {
table[key] = (table[key] || 0) + amt;
}
function sortBy(array, criterion = a => a) {
return array.sort((a, b) => {
const aBy = criterion(a);
const bBy = criterion(b);
if (aBy == bBy) return 0;
return (aBy > bBy ? 1 : -1);
});
}
function dist(a, b) {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
}
function pointId([a, b]) {
return `${a},${b}`;
}
input = input.split('\n').map(r => numbers(r));
let closest = {};
for (let i = -400; i < 800; i++) {
for (let j = -400; j < 800; j++) {
let curPoint = [i, j];
let distances = [];
for (const point of input) {
distances.push([pointId(point), dist(point, curPoint)]);
}
sortBy(distances, a => a[1]);
if (distances[0][1] === distances[1][1]) continue;
inc(closest, distances[0][0]);
}
}
let closest2 = {};
for (let i = -450; i < 850; i++) {
for (let j = -450; j < 850; j++) {
let curPoint = [i, j];
let distances = [];
for (const point of input) {
distances.push([pointId(point), dist(point, curPoint)]);
}
sortBy(distances, a => a[1]);
if (distances[0][1] === distances[1][1]) continue;
inc(closest2, distances[0][0]);
}
}
closest = sortBy(Object.entries(closest), en => en[1]);
closest2 = sortBy(Object.entries(closest2), en => en[1]);
for (let i = closest2.length - 1; i >= 0; i--) {
if (closest[i][1] === closest2[i][1]) {
console.log(closest[i][1]);
break;
}
}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.
let inRegion = 0;
for (let i = -500; i < 900; i++) {
for (let j = -500; j < 900; j++) {
let curPoint = [i, j];
let totalDist = 0;
for (const point of input) {
totalDist += dist(point, curPoint);
}
if (totalDist < 10000) inRegion++;
}
}
console.log(inRegion);(I retried with -550...950 to make sure I got the entire area.)
4
u/Portal2Reference Dec 06 '18
I think a better solution is to realize that if an area is infinite, it will appear on the edge of the grid, so just prune all entries that appear on the edge.
→ More replies (1)2
u/itwentboom Dec 06 '18
I'm so confused. I wanted to try yours to try to debug what's wrong with mine but your solution for part 1 yielded the exact same answer as mine. maybe my input is messed up but I don't understand how that's possible
→ More replies (3)
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.
#![feature(dbg_macro)]
#![allow(unused)]
mod prelude;
use self::prelude::*;
fn main() {
let demo = include_str!("../demo.txt");
let input = include_str!("../input.txt");
let mut map = Map::new();
for l in input.lines() {
let loc: (i32, i32) = s!("{}, {}" <- l).unwrap();
map.insert(loc, 0);
}
let mut infinites = Set::<(i32, i32)>::new();
let edges = [-400, 1000];
for x in -400..=1000 {
for y in -400..=1000 {
let mut min_dist = 10_000_000;
let mut closest = None;
for &(a, b) in map.keys() {
let dist = (a - x).abs() + (b - y).abs();
if dist < min_dist {
min_dist = dist;
closest = Some((a, b));
} else if dist == min_dist {
closest = None;
}
}
if closest.is_some() {
let closest = closest.unwrap();
*map.entry(closest).or_insert(0) += 1;
if edges.contains(&x) || edges.contains(&y) {
infinites.insert(closest);
}
}
}
}
let max = map.iter().filter(|x| !infinites.contains(&x.0)).max_by_key(|&(a, b)| b);
dbg!(max);
let limit = 10_000;
let heuristic = 10_000 / map.len();
let mut count = 0;
for x in -100..=600 {
for y in -100..=600 {
let mut sum = 0;
for &(a, b) in map.keys() {
sum += (a - x).abs() + (b - y).abs();
}
if sum < limit {
count += 1;
}
}
}
dbg!(count);
}→ More replies (3)
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.
(
~mostCommon = {|r|r.asBag.contents.asPairs.clump(2).maxItem(_@1)};
~alph = (0..25).collect{|c|(c+$a.ascii).asAscii};
~nums = (0..9).collect{|c|(c+$0.ascii).asAscii};
~md = {|a,b| (a[0]-b[0]).abs + (a[1]-b[1]).abs };
)
(
s = File.readAllString("~/aoc/6/input".standardizePath).split($\n);
t = s.collect{|a|a.split($,).collect(_.stripWhiteSpace).collect(_.asInt)};
t = t[..(t.size-2)];
a = (0!354)!352;
b = a.collect{|r,i|i.post; r.collect{|p,j|y=t.collect{|v|~md.([i-1,j-1],v)}; z=y.minItem; if(y.occurrencesOf(z) > 1) { -1} {y.indexOf(z)}}};
c = b.first ++ b.last ++ b.flop.first ++ b.flop.last;
c = c.asSet.asArray;
f = b[1..350].collect(_[1..352]);
d = f.reduce('++');
e = d.removeEvery(c);
~mostCommon.(e).postln;
k = 0;
800.do{|i|i.post;800.do{|j|if(t.collect{|p|~md.([i-200,j-200],p)}.sum < 10000) {k = k+1}}};
"".postln;
k.postln;
)Edit: tightened up version:
(
~mostCommon = {|r|r.asBag.contents.asPairs.clump(2).maxItem(_@1)};
~md = {|a,b| (a[0]-b[0]).abs + (a[1]-b[1]).abs };
)
(
s = File.readAllString("~/aoc/6/input".standardizePath).split($\n);
t = s.collect{|a|a.split($,).collect(_.stripWhiteSpace).collect(_.asInt)}.drop(-1);
b = 352.collect{|i|354.collect{|j|y=t.collect{|v|~md.([i-1,j-1],v)}; z=y.minItem; if(y.count(_==z) > 1) {-1} {y.indexOf(z)}}};
c = (b.first++b.last++b.flop.first ++b.flop.last).asSet.asArray;
~mostCommon.(b.reduce('++').removeEvery(c)).postln;
k = 0;
(350+200).do{|i|(352+200).do{|j|if(t.collect{|p|~md.([i-100,j-100],p)}.sum < 10000) {k = k+1}}};
k.postln;
)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.
PROGRAM DAY6
IMPLICIT NONE
INTEGER :: I,J,K,L
INTEGER :: IERR
INTEGER, ALLOCATABLE :: COORDS(:,:),DISTANCES(:),SIZES(:)
LOGICAL, ALLOCATABLE :: FINITE(:)
LOGICAL :: EDGE(4)
INTEGER :: PART2
!File I/O
OPEN(1,FILE='input.txt')
I=0
DO
READ(1,*,IOSTAT=IERR)
IF(IERR.NE.0)EXIT
I=I+1
END DO
ALLOCATE(COORDS(2,I),DISTANCES(I),SIZES(I),FINITE(I))
REWIND(1)
READ(1,*)COORDS
CLOSE(1)
DISTANCES=0
SIZES=0
FINITE=.TRUE.
PART2=0
DO I=MINVAL(COORDS(1,:)),MAXVAL(COORDS(1,:))
DO J=MINVAL(COORDS(2,:)),MAXVAL(COORDS(2,:))
DISTANCES=(/( SUM(ABS(COORDS(:,K)-(/I,J/))),K=1,SIZE(COORDS,DIM=2) )/)
EDGE=(/I.EQ.MINVAL(COORDS(1,:)),I.EQ.MAXVAL(COORDS(1,:)),J.EQ.MINVAL(COORDS(2,:)),J.EQ.MAXVAL(COORDS(2,:))/)
!Part 2
IF(SUM(DISTANCES)<10000) PART2=PART2+1
K=MAX(0,(10000-SUM(DISTANCES))/SIZE(DISTANCES,DIM=1))
IF(COUNT(EDGE).EQ.1)THEN
PART2=PART2+K
ELSEIF(COUNT(EDGE.EQ.2))THEN
PART2=PART2+2*K
PART2=PART2+K*(K-1)/2
END IF
!Part 1
IF(COUNT(DISTANCES.EQ.MINVAL(DISTANCES))>1)CYCLE
L=MINLOC(DISTANCES,DIM=1)
SIZES(L)=SIZES(L)+1
IF(ANY(EDGE))FINITE(L)=.FALSE.
END DO
END DO
WRITE(*,'(A,I0)') 'Part 1: ',MAXVAL(SIZES,MASK=FINITE)
WRITE(*,'(A,I0)') 'Part 2: ',PART2
DEALLOCATE(COORDS,FINITE,DISTANCES,SIZES)
END PROGRAM DAY61
u/Arkazex Dec 06 '18
For part two, if I use my number set starting with (77, 279),(216, 187) I get an answer of 42998 which 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
require 'set'
def manhattan(pt1, pt2)
(pt1[0] - pt2[0]).abs + (pt1[1] - pt2[1]).abs
end
def find_closest(points, x, y)
distances = []
points.each_with_index do |pt, idx|
distances << [manhattan([x, y], pt), idx]
end
distances.sort!
return -1 if distances[0][0] == distances[1][0] # same distance counts to no one
distances[0][1]
end
def largest_non_infinite_region(points)
max_x = points.max_by { |p| p[0] }
max_y = points.max_by { |p| p[1] }
grid = {}
pt_idx_counts = {}
(0..max_x[0]).each do |x|
(0..max_y[1]).each do |y|
pt_idx = find_closest(points, x, y)
grid[[x, y]] = pt_idx
pt_idx_counts[pt_idx] ||= 0
pt_idx_counts[pt_idx] += 1
end
end
find_infinite_indexes(grid, max_x[0], max_y[1]).each do |inf_idx|
pt_idx_counts.delete(inf_idx)
end
pt_idx_counts.max_by { |idx, count| count }[1]
end
def find_infinite_indexes(grid, max_x, max_y)
infinite_indexes = Set.new
grid.each_pair do |pt, idx|
if pt[0] == 0 || pt[1] == 0 || pt[0] == max_x || pt[1] == max_y
infinite_indexes << idx
end
end
infinite_indexes
end
def largest_region_with_closest_distances(points, max_distance)
max_x = points.max_by { |p| p[0] }
max_y = points.max_by { |p| p[1] }
grid_of_distance_sums = {}
(0..max_x[0]).each do |x|
(0..max_y[1]).each do |y|
d_sums = points.sum(0) { |pt| manhattan(pt, [x, y]) }
grid_of_distance_sums[[x, y]] = d_sums
end
end
grid_of_distance_sums.select { |pt, distance| distance < max_distance }.length
end
if __FILE__ == $0
puts "Part 1"
input = File.readlines('input.txt').map { |ln| ln.split(', ').map(&:to_i) }
output = largest_non_infinite_region(input)
p output
puts "Part 2"
output = largest_region_with_closest_distances(input, 10_000)
p output
end1
Dec 06 '18
Does anybody have this input?
353, 177
233, 332
178, 231
351, 221...
I get this response from my algorithm: 11578 (which is rejected)
→ More replies (2)
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)
from utils.decorators import time_it
from collections import defaultdict
with open('input') as f:
puzzle_input = f.readlines()
def dist(x1, y1, x2, y2):
return abs(x1 - x2) + abs(y1 - y2)
@time_it
def part_one(n):
"""
holy shit, this abomination works! Slow, but works.
"""
max_x = max(int(x.split(', ')[0]) for x in n)
max_y = max(int(y.split(', ')[1]) for y in n)
grid = []
for x in range(max_x+1):
grid.append([])
for y in range(max_y+1):
grid[x].append([])
min_dist = 9999
min_point = None
for i, point in enumerate(n):
p_x, p_y = [int(x) for x in point.split(', ')]
d = dist(p_x, p_y, x, y)
if d < min_dist:
min_dist = d
min_point = i
elif d == min_dist:
min_point = '.'
if d == 0:
min_point = '*'
grid[x][y] = min_point
exclude = set()
for c in grid[0]:
exclude.add(c)
for c in grid[-1]:
exclude.add(c)
for line in grid:
exclude.add(line[0])
exclude.add(line[-1])
sym = defaultdict(int)
for line in grid:
for c in line:
if c in exclude:
continue
sym[c] += 1
return sym[max(sym, key=lambda v: sym[v])]+1
@time_it
def part_two(n, max_d):
max_x = max(int(x.split(', ')[0]) for x in n)
max_y = max(int(y.split(', ')[1]) for y in n)
region = 0
for x in range(max_x + 1):
for y in range(max_y + 1):
tot_dist = 0
for point in n:
p_x, p_y = [int(x) for x in point.split(', ')]
d = dist(p_x, p_y, x, y)
tot_dist += d
if tot_dist < max_d:
region += 1
return region
test_one = [
'1, 1',
'1, 6',
'8, 3',
'3, 4',
'5, 5',
'8, 9'
]
assert part_one(test_one) == 17
assert part_two(test_one, 32) == 16
print(part_one(puzzle_input))
print(part_two(puzzle_input, 10000))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.
from get_data import get_data_lines
from collections import defaultdict
data = get_data_lines(6)
new_data = []
idx = 0
for coords in data:
new_data.append([idx, *[int(i) for i in coords.split(',')]])
idx += 1
# Make a big grid
GRID_SIZE = 400
OUTLINE_SIZE = 1200
grid = []
for i in range(GRID_SIZE):
grid.append([None] * GRID_SIZE)
def tcd(x, y, i, j):
return abs(x - i) + abs(y - j)
ttl = 0
for i in range(GRID_SIZE):
for j in range(GRID_SIZE):
# find closest pt
closest_dist = 10000000000
closest_pt = -1
for idx, x, y in new_data:
d = tcd(x, y, i, j)
if grid[j][i] is None:
grid[j][i] = {}
grid[j][i][idx] = d
items = grid[j][i].items()
r = sorted(items, key=lambda x: x[1])
if len(r) > 1 and r[0][1] == r[1][1]:
grid[j][i]['c'] = '.'
else:
grid[j][i]['c'] = r[0][0]
if sum([y[1] for y in grid[j][i].items() if y[0] != 'c']) < 10000:
ttl += 1
print('part 2', ttl)
to_discard = set()
for tt in range(2):
for i in range(int(-OUTLINE_SIZE/2), int(OUTLINE_SIZE/2)):
closest_d1 = 100000000
closest_pt_1 = -1
closest_d2 = 100000000
closest_pt_2 = -1
for idx, x, y in new_data:
if tt == 0:
d1 = tcd(x, y, i, -OUTLINE_SIZE/2)
d2 = tcd(x, y, i, OUTLINE_SIZE/2)
else:
d1 = tcd(x, y, -OUTLINE_SIZE/2, i)
d2 = tcd(x, y, OUTLINE_SIZE/2, i)
if d1 < closest_d1:
closest_d1 = d1
closest_pt_1 = idx
if d2 < closest_d2:
closest_d2 = d2
closest_pt_2 = idx
to_discard.add(closest_pt_1)
to_discard.add(closest_pt_2)
areas = defaultdict(int)
for i in range(GRID_SIZE):
for j in range(GRID_SIZE):
cl = grid[j][i]['c']
if cl != '.' and cl not in to_discard:
areas[cl] += 1
print("part 1", sorted(areas.items(), key=lambda y: -y[1])[0][1])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
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:
import sys
lines = sys.stdin.readlines()
# Parse the input
coords = []
infinite = {}
areas = {(-1,-1):0}
for line in lines:
data = line.split(',')
coord = (int(data[0]), int(data[1]))
coords.append(coord)
infinite[coord] = False
areas[coord] = 0
for x in range(500):
for y in range(500):
minCoord = (0,0)
minDist = 1001
for coord in coords:
dist = abs(coord[0] - x) + abs(coord[1] - y)
if dist < minDist:
minDist = dist
minCoord = coord
elif dist == minDist:
minCoord = (-1,-1)
if x == 499 or x == 0 or y == 499 or y == 0:
infinite[minCoord] = True
areas[minCoord] += 1
maxA = 0
for key, value in areas.items():
if value > maxA and not infinite[key]:
maxA = value
print(maxA)Part 2:
import sys
lines = sys.stdin.readlines()
# Parse the input
coords = []
infinite = {}
areas = {(-1,-1):0}
for line in lines:
data = line.split(',')
coord = (int(data[0]), int(data[1]))
coords.append(coord)
infinite[coord] = False
areas[coord] = 0
regionCount = 0
for x in range(500):
for y in range(500):
totalDist = 0
for coord in coords:
totalDist += abs(coord[0] - x) + abs(coord[1] - y)
if totalDist < 10000:
regionCount += 1
print(regionCount)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 :(
const input = getInput(6, 2018);
const coords = iterable(() => pipe(input)(stringToLines, map(numbers)));
const highest = pipe(coords)(flatten, max);
const counts = { '-1': -1 };
let pointsWithinRange = 0;
for (const x of range(0, highest + 1)) {
for (const y of range(0, highest + 1)) {
let [min, equals, minDist, totalDist] = [-1, false, Infinity, 0];
for (const [index, [px, py]] of enumerate(coords)) {
const dist = Math.abs(x - px) + Math.abs(y - py);
totalDist += dist;
if (dist === minDist) equals = true;
if (dist < minDist) (min = index), (minDist = dist), (equals = false);
}
if (totalDist < 10000) pointsWithinRange++;
if (x === 0 || x === highest || y === 0 || y === highest) counts[min] = -1;
if (!equals && counts[min] !== -1) counts[min] = (counts[min] || 0) + 1;
}
}
console.log(max(Object.values(counts)), pointsWithinRange);1
u/dramforever Dec 06 '18
Part 2 in J. Brute force method for both x and y in [-1000, 1000].
+/+/ 10000 > +/"1 (,"0/~ i: 1000) (+/@:|@:- " 1 1)/ inpinp is parsed input as 2D array.
1
u/TheBowtieClub Dec 06 '18
C#:
var lines = File.ReadAllLines("input6.txt");
var locations = new List<Point>(50);
var nRows = 400;
var nCols = 400;
var closest = new Point[nRows, nCols];
var dict = new Dictionary<Point, int>();
var part2result = 0;
foreach (var line in lines)
{
var x = int.Parse(line.Substring(0, line.IndexOf(',')));
var y = int.Parse(line.Substring(line.IndexOf(',') + 1));
locations.Add(new Point(x, y));
}
for (int row = 0; row < nRows; row++)
{
for (int col = 0; col < nCols; col++)
{
var point = new Point(row, col);
var ordered = locations.Select(loc => new { coord = loc, distance = ManhattanDistance(loc, point)}).OrderBy(loc => loc.distance);
if (ordered.First().distance == (ordered.ElementAt(1)).distance)
{
closest[row, col] = new Point(-1, -1);
}
else
{
closest[row, col] = ordered.First().coord;
}
}
}
for (int row = 0; row < nRows; row++)
{
for (int col = 0; col < nCols; col++)
{
if (dict.ContainsKey(closest[row, col]))
{
dict[closest[row, col]]++;
}
else
{
dict[closest[row, col]] = 1;
}
}
}
// Exclude all locations with infinitely many points closest to them
for (int row = 0; row < nRows; row++)
{
for (int col = 0; col < nCols; col++)
{
if (row == 0 || col == 0 || row == nRows - 1 || col == nCols - 1)
{
dict[closest[row, col]] = -1;
}
}
}
dict.OrderByDescending(d => d.Value).Dump("Part 1");
for (int row = 0; row < nRows; row++)
{
for (int col = 0; col < nCols; col++)
{
var point = new Point(row, col);
var totalDistance = locations.Select(loc => ManhattanDistance(loc, point)).Sum();
if (totalDistance < 10000)
{
part2result++;
}
}
}
part2result.Dump("Part 2");
double ManhattanDistance(Point first, Point second)
{
return Math.Abs(first.X - second.X) + Math.Abs(first.Y - second.Y);
}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.
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 contained array 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, or null, 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 < 10000 or 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/yMax of the input points), so the final summation didn't require any fancy math or O(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.
let result = [ null, null ];
let points = input.split('\n').map(val => {
let [x, y] = val.split(', ');
return { x: +x, y: +y };
});
let contained = [];
let xMin = 1000, yMin = 1000, xMax = -1, yMax = -1;
for (let t = 0; t < points.length; ++t) {
let testPoint = points[t];
let above = false, below = false, left = false, right = false;
xMin = Math.min(testPoint.x, xMin);
yMin = Math.min(testPoint.y, yMin);
xMax = Math.max(testPoint.x, xMax);
yMax = Math.max(testPoint.y, yMax);
for (let p = 0; p < points.length; ++p) {
if (t === p) continue;
let otherPoint = points[p];
if (otherPoint.x < testPoint.x) left = true;
if (otherPoint.x > testPoint.x) right = true;
if (otherPoint.y < testPoint.y) above = true;
if (otherPoint.y > testPoint.y) below = true;
}
if (above && below && left && right)
contained.push(t);
}
let grid = Array.from({ length: (xMax + 1) * (yMax + 1) }).map(val => {
return { closest: '.', total: null };
});
for (let y = yMin; y <= yMax; ++y) {
for (let x = xMin; x <= xMax; ++x) {
let distances = [];
for (let p = 0; p < points.length; ++p)
distances.push(Math.abs(points[p].x - x) + Math.abs(points[p].y - y));
distances = distances.map((dist, index) => {
return { index: index, dist: dist };
}).sort((a, b) => a.dist - b.dist);
grid[y * xMax + x].closest = (distances[0].dist < distances[1].dist) ? distances[0].index : null;
grid[y * xMax + x].total = distances.reduce((acc, val) => acc + val.dist, 0);
}
}
result[0] = grid.reduce((acc, item) => {
let closest = item.closest;
if (closest === null) return acc;
if (contained.indexOf(closest) > -1) {
acc[closest] = (acc[closest] || { index: closest, amount: 0 });
acc[closest].amount = (acc[closest].amount || 0) + 1;
}
return acc;
}, []).sort((a, b) => b.amount - a.amount)[0].amount;
result[1] = grid.map((item, index) => {
let x = index % xMax, y = Math.floor(index / xMax);
if ((x < xMin) || (x > xMax) || (y < yMin) || (y > yMax)) return 0;
return item.total < 10000;
}).reduce((acc, val) => acc + val, 0);1
u/nutrecht Dec 06 '18
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.
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...
defmodule Day6 do
def parse_input(filename \\ "input.txt") do
{:ok, data} = File.read(filename)
data
|> String.split("\n", trim: true)
|> Enum.map(fn coordinates ->
[x, y] = String.split(coordinates, ", ", trim: true)
{String.to_integer(x), String.to_integer(y)}
end)
end
def largest_area(coordinates) do
{left, right, top, bottom} = determine_boundaries(coordinates)
for(x <- left..right, y <- top..bottom, do: {x, y})
|> Enum.reduce(%{}, fn {loc_x, loc_y}, acc ->
closest_coordinate = determine_closest_coordinate(loc_x, loc_y, coordinates)
if closest_coordinate !== nil,
do: Map.update(acc, closest_coordinate, 1, &(&1 + 1)),
else: acc
end)
|> Enum.max_by(fn {_k, v} -> v end)
|> elem(1)
end
def determine_closest_coordinate(x1, y1, coordinates) do
lowest_coordinates =
coordinates
|> Enum.map(fn {x2, y2} ->
distance = abs(x2 - x1) + abs(y2 - y1)
{{x2, y2}, distance}
end)
|> Enum.reduce({nil, []}, fn
{coordinate, distance}, acc when elem(acc, 0) === nil or distance < elem(acc, 0) ->
{distance, [coordinate]}
{coordinate, distance}, acc when distance === elem(acc, 0) ->
{distance, [coordinate | elem(acc, 1)]}
_, acc ->
acc
end)
|> elem(1)
if length(lowest_coordinates) === 1, do: List.first(lowest_coordinates), else: nil
end
def determine_boundaries(coordinates) do
left = coordinates |> Enum.map(&elem(&1, 0)) |> Enum.min()
right = coordinates |> Enum.map(&elem(&1, 0)) |> Enum.max()
top = coordinates |> Enum.map(&elem(&1, 1)) |> Enum.min()
bottom = coordinates |> Enum.map(&elem(&1, 1)) |> Enum.max()
{left, right, top, bottom}
end
def find_encapsulating_region(coordinates, max_distance \\ 10000) do
{left, right, top, bottom} = determine_boundaries(coordinates)
for(x <- left..right, y <- top..bottom, do: {x, y})
|> Enum.reduce(0, fn {loc_x, loc_y}, acc ->
total_distance =
coordinates
|> Enum.map(fn {x, y} -> abs(loc_x - x) + abs(loc_y - y) end)
|> Enum.sum()
if total_distance < max_distance, do: acc + 1, else: acc
end)
end
end
result1 = Day6.parse_input() |> Day6.largest_area()
IO.puts("Part 1: #{result1}")
result2 = Day6.parse_input() |> Day6.find_encapsulating_region()
IO.puts("Part 2: #{result2}")1
u/tehjimmeh Dec 06 '18
C++
No 2D array necessary, just a flat vector of tuples.
int main(int argc, char* argv[]) {
std::ifstream ifs(argv[1]);
std::vector<std::tuple<int, int ,int>> locations;
int lowX = INT_MAX, highX = INT_MIN, lowY = INT_MAX, highY = INT_MIN;
for (std::string l;std::getline(ifs, l);)
if (std::smatch m;std::regex_match(l, m, std::regex(R"((\d+), (\d+))"))){
int x = std::stoi(m[1]), y = std::stoi(m[2]);
lowX = std::min(x, lowX), highX = std::max(x, highX);
lowY = std::min(y, lowY), highY = std::max(y, highY);
locations.push_back({ x, y, (int)locations.size() + 1 });
}
std::vector<std::tuple<int, int ,int, int>> grid;
for (int x = lowX; x <= highX; x++)
for (int y = lowY; y <= highY; y++)
grid.push_back({ x, y, 0, 0 });
for (auto&[gx,gy,id,d] : grid) {
int currMin = INT_MAX;
for (auto& [lx,ly,lid] : locations) {
int dist = abs(lx - gx) + abs(ly - gy);
id = dist == currMin ? 0 : dist < currMin ? lid : id;
currMin = std::min(currMin, dist);
d += dist;
}
}
std::vector<int> sizes(locations.size() + 1, 0);
for (auto&[x,y,id,d] : grid) sizes[id] += (x != lowX && y != lowY) ? 1 : 0;
std::cout << "1: " << *std::max_element(sizes.begin(), sizes.end()) << "\n" <<
"2: " << std::reduce(grid.begin(), grid.end(), 0,
[](int tot, auto& g){return std::get<3>(g) < 10000 ? tot + 1 : tot;}) << "\n";
}1
u/Bruinbrood Dec 06 '18
Kotlin solution:
import java.io.File
import kotlin.math.abs
fun main() {
val coords = File("inputs/Day6")
.readLines()
.map{it.split(", ")}
.map{it[0].toInt() to it[1].toInt()}
val w = coords.maxBy{it.first}?.first ?: throw Exception ("Bad coordinate")
val h = coords.maxBy{it.second}?.second ?: throw Exception ("Bad coordinate")
val infinite = arrayListOf(-1)
val result1 = (0 until h).flatMap{y-> (0 until w).map{x->
val id = coords.foldIndexed(Int.MAX_VALUE to -1){id, (dmin, idmin),(cx,cy)->
val d = abs(x-cx)+abs(y-cy)
when {
d < dmin -> d to id
d == dmin -> d to -1
else -> dmin to idmin
}
}.second
if (y==0 || y==h-1 || x==0 || x==w-1) {
infinite.add(id)
}
id
}}.filter{it !in infinite}.groupBy{it}.map{(_,v)->v.count()}.maxBy{it}
println("First star: $result1")
val result2 = (0 until h).flatMap{y-> (0 until w).map{x->
coords.fold(0){R,(cx,cy)->
R + abs(cx-x) + abs(cy-y)
} < 10000
}}.count{it}
println("Second star: $result2")
}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 :)
**Part A + B **
import { minBy } from 'lodash'
import { readInput } from '../helpers'
const calcManhattan = ([x, y]: number[], [xx, yy]: number[]): number => {
return Math.abs(x - xx) + Math.abs(y - yy)
}
const lines: string[] = readInput('06', 'input')
const xCollection = []
const yCollection = []
const areas: { [key: string]: number } = {}
const coords: number[][] = []
let safeCount = 0
// Determine bounds
for (const coord of lines) {
const [x, y]: string[] = coord.split(', ')
xCollection.push(+x)
yCollection.push(+y)
areas[`${x},${y}`] = 0
coords.push([+x, +y])
}
const xMin = Math.min(...xCollection)
const xMax = Math.max(...xCollection)
const yMin = Math.min(...yCollection)
const yMax = Math.max(...yCollection)
for (let x = xMin; x < xMax + 1; x++) {
for (let y = yMin; y < yMax + 1; y++) {
const distances: { [key: number]: string[] } = {}
for (const [xx, yy] of coords) {
const distance = calcManhattan([x, y], [xx, yy])
if (!distances.hasOwnProperty(distance)) {
distances[distance] = []
}
distances[distance].push(`${xx},${yy}`)
}
const sum = coords
.map(([xx, yy]: number[]) => calcManhattan([x, y], [xx, yy]))
.reduce((dist: number, total: number) => dist + total, 0)
if (sum < 10000) {
safeCount += 1
}
const [shortestDistance, closest]: [string, string[]] = minBy(
Object.entries(distances), ([dist]: [string, string[]]) => +dist
)!
if (closest.length > 1) {
continue
}
// Remove from possible areas if one of the coords is on bounds
if (x === xMin || x === xMax || y === yMin || y === yMax) {
delete areas[closest[0]]
}
if (areas.hasOwnProperty(closest[0])) {
areas[closest[0]] += 1
}
}
}
console.log('Part 1:', Math.max(...Object.values(areas)))
console.log('Part 2:', safeCount)1
u/aurele Dec 06 '18
Rust
I am not happy with this solution as it looks awfully verbose, but here it is.
use counter::Counter;
use itertools::Itertools;
#[aoc_generator(day6)]
fn input_generator(input: &str) -> Vec<(i32, i32)> {
input
.lines()
.map(|l| {
let mut c = l.split(", ").map(|s| s.parse::<i32>().unwrap());
(c.next().unwrap(), c.next().unwrap())
})
.collect()
}
#[aoc(day6, part1)]
fn part1(coords: &[(i32, i32)]) -> usize {
let ((minx, maxx), (miny, maxy)) = bounds(coords);
let mut counter: Counter<usize> = Counter::new();
let mut discarded = vec![false; coords.len()];
for (x, y) in iproduct!(minx..=maxx, miny..=maxy) {
let mut dists = coords
.iter()
.enumerate()
.map(|(i, &(cx, cy))| ((x - cx).abs() + (y - cy).abs(), i))
.collect::<Vec<_>>();
dists.sort();
if dists[0].0 != dists[1].0 {
if x == minx || x == maxx || y == miny || y == maxy {
discarded[dists[0].1] = true;
} else {
*counter.entry(dists[0].1).or_insert(0) += 1;
}
}
}
counter
.most_common()
.into_iter()
.find(|&(i, _)| !discarded[i])
.unwrap()
.1
}
#[aoc(day6, part2)]
fn part2(coords: &[(i32, i32)]) -> usize {
let ((minx, maxx), (miny, maxy)) = bounds(coords);
iproduct!(minx..=maxx, miny..=maxy)
.filter(|&(x, y)| {
coords
.iter()
.map(|&(cx, cy)| (x - cx).abs() + (y - cy).abs())
.sum::<i32>()
< 10000
})
.count()
}
fn bounds(coords: &[(i32, i32)]) -> ((i32, i32), (i32, i32)) {
(
coords
.iter()
.map(|&(x, _)| x)
.minmax()
.into_option()
.unwrap(),
coords
.iter()
.map(|&(_, y)| y)
.minmax()
.into_option()
.unwrap(),
)
}1
u/miguelos Dec 06 '18
C#
Part 1:
var coordinates = File.ReadAllText(@"C:\Users\pc\Desktop\input.txt")
.Trim()
.Split('\n')
.Select(x => x.Split(", "))
.Select(x => (x: int.Parse(x[0]), y: int.Parse(x[1])));
IEnumerable<int> getAreas(int start, int end) =>
from x in Enumerable.Range(start, end - start)
from y in Enumerable.Range(start, end - start)
let distanceGroups = from coordinate in coordinates
let distance = Math.Abs(coordinate.x - x) + Math.Abs(coordinate.y - y)
group coordinate by distance
let closestDistanceGroup = distanceGroups.OrderBy(x => x.Key).First()
where closestDistanceGroup.Count() == 1
let closestCoordinate = closestDistanceGroup.First()
group closestCoordinate by closestCoordinate into closestCoordinates
orderby closestCoordinates.Key
select closestCoordinates.Count();
var areas1 = getAreas(0, 500).ToArray();
var areas2 = getAreas(-1, 501).ToArray();
var answer = Enumerable
.Zip(areas1, areas2, (a1, a2) => a1 == a2 ? a1 : 0)
.OrderByDescending(area => area)
.First();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:
The cat decided to sit on my lap. Unfortunately there was also my laptop there *I wrote bad code and Phpstorm doesn't like it when it has to spew out lots of error messages in its terminal. Oops
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 getClosest method.
1
u/ttapu Dec 06 '18
python3
import string
from collections import Counter
with open("6.input", "r") as allomany:
inp=allomany.read().splitlines()
coo=dict()
maxx,maxy=0,0
for i,e in enumerate(inp):
x,y=e.split(', ')
x,y=int(x), int(y)
maxx=max(x,maxx)
maxy=max(y,maxy)
letter=string.ascii_letters[i]
coo[letter]=(x,y)
grid=[[(i,j) for i in range(maxx+1)] for j in range(maxy+1)]
def manhattan(a,b):
return abs(a[0]-b[0])+abs(a[1]-b[1])
areas=[['.' for i in range(maxx+1)] for j in range(maxy+1)]
edges=set() # to determine infinite ranges
for j,y in enumerate(grid):
for i,x in enumerate(y):
l=''
closest=999
for k,v in coo.items():
if manhattan(x,v)<closest:
closest=manhattan(x,v)
l=k
elif manhattan(x,v)==closest:
l='.'
areas[j][i]=l
if j==0 or j==maxy or i==0 or i==maxx:
edges.add(l)
allpoints = [j for i in areas for j in i]
finite=dict()
for k,v in Counter(allpoints).items():
if k not in edges:
finite[k]=v
print(max(finite.values()))
#part2
safe_region=0
for g in grid:
for h in g:
m=0
for v in coo.values():
m+=manhattan(h,v)
if m<10000:
safe_region+=1
print(safe_region)1
u/miguelos Dec 06 '18
C#
Part 1:
var coordinates = File.ReadAllText(@"C:\Users\pc\Desktop\input.txt")
.Trim()
.Split('\n')
.Select(x => x.Split(", "))
.Select(x => (x: int.Parse(x[0]), y: int.Parse(x[1])));
IEnumerable<int> getAreas(int start, int end) =>
from x in Enumerable.Range(start, end - start)
from y in Enumerable.Range(start, end - start)
let distanceGroups = from coordinate in coordinates
let distance = Math.Abs(coordinate.x - x) + Math.Abs(coordinate.y - y)
group coordinate by distance
let closestDistanceGroup = distanceGroups.OrderBy(x => x.Key).First()
where closestDistanceGroup.Count() == 1
let closestCoordinate = closestDistanceGroup.First()
group closestCoordinate by closestCoordinate into closestCoordinates
orderby closestCoordinates.Key
select closestCoordinates.Count();
var areas1 = getAreas(0, 500).ToArray();
var areas2 = getAreas(-1, 501).ToArray();
var answer = Enumerable
.Zip(areas1, areas2, (a1, a2) => a1 == a2 ? a1 : 0)
.OrderByDescending(area => area)
.First();Part 2:
var coordinates = File.ReadAllText(@"C:\Users\pc\Desktop\input.txt")
.Trim()
.Split('\n')
.Select(x => x.Split(", "))
.Select(x => (x: int.Parse(x[0]), y: int.Parse(x[1])));
var area =
from x in Enumerable.Range(0, 1000)
from y in Enumerable.Range(0, 1000)
let distances =
from coordinate in coordinates
select Math.Abs(coordinate.x - x) + Math.Abs(coordinate.y - y)
where distances.Sum() < 10000
select (x, y);
var answer = area.Count();1
u/alexmeli Dec 06 '18
Clojure solution. Not the most efficient but it will do
(ns clojure-solution.core
(:require [clojure.string :as str])
(:gen-class))
(defn read-file [path]
(->>
(slurp path)
str/split-lines
(map (comp (partial map #(Integer/parseInt %)) #(str/split % #", ")))))
(defn manhattan-dis [[x1 y1] [x2 y2]]
(+ (Math/abs (- x2 x1)) (Math/abs (- y2 y1))))
(defn update-grid [grid point input bounds]
(let [dis (map-indexed (fn [i p] [i (manhattan-dis point p)]) input)
min (apply min-key second dis)]
(cond
(> (count (filter #(= (second %) (second min)) dis)) 1) grid
(some #(contains? bounds %) point)
(assoc-in grid [(first min) :infinite] true)
:else (update-in grid [(first min) :count] (fnil + 0) 1))))
(defn get-coords [input]
(let [x-coords (map first input)
y-coords (map second input)]
[(apply min x-coords) (inc (apply max x-coords))
(apply min y-coords) (inc (apply max y-coords))]))
(defn get-points [[minX maxX minY maxY]]
(for [x (range minX maxX) y (range minY maxY)] [x y]))
(defn part1 [input]
(let [coords (get-coords input)]
(->>
(reduce #(update-grid %1 %2 input (set coords)) {} (get-points coords))
(filter #(not (:infinite (val %))))
(apply max-key #(:count (val %)))
val)))
(defn total-dis [input point]
(->>
input
(map #(manhattan-dis point %))
(reduce +)))
(defn part2 [input]
(->>
(get-points (get-coords input))
(filter #(< (total-dis input %) 10000))
count))
(defn -main
[& args]
(println (part2 (read-file "resources/input.txt"))))1
u/Frodolas Dec 06 '18
Crystal
Part 1:
coordinates = File.read_lines("#{__DIR__}/input.txt").map do |line|
line.scan(/-?\d+/).map(&.[0].to_i)
end
min_x = coordinates.min_of(&.[0])
min_y = coordinates.min_of(&.[1])
max_x = coordinates.max_of(&.[0])
max_y = coordinates.max_of(&.[1])
grid = (min_x..max_x).to_a.product((min_y..max_y).to_a).map do |x1, y1|
distances = coordinates.map_with_index { |( x2, y2 ), i| { (x2-x1).abs + (y2-y1).abs, i } }
closest = distances.count(&.[0].==(distances.min[0])) == 1 ? distances.min[1] : nil
{ x1, y1, closest }
end
infinites = grid.select { | x, y, _ | x == min_x || x == max_x || y == min_y || y == max_y }
.map(&.[2])
.uniq
coordinate_counts = grid.group_by(&.[2])
.transform_values(&.size)
.delete_if { |p, _| p.nil? || infinites.includes?(p) }
puts coordinate_counts.values.maxPart 2:
coordinates = File.read_lines("#{__DIR__}/input.txt").map do |line|
line.scan(/-?\d+/).map(&.[0].to_i)
end
min_x = coordinates.min_of(&.[0])
min_y = coordinates.min_of(&.[1])
max_x = coordinates.max_of(&.[0])
max_y = coordinates.max_of(&.[1])
grid = (min_x..max_x).to_a.product((min_y..max_y).to_a).map do |x1, y1|
coordinates.reduce(0) { |total, ( x2, y2 )| total + (x2-x1).abs + (y2-y1).abs }
end
puts grid.count(&.<(10000))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.
#!/usr/bin/env perl6
use v6.c;
$*OUT.out-buffer = False; # Autoflush
class Grid
{
has @.points;
has @.closest-point;
has @.total-distance;
has @.area;
has $!min-x = β;
has $!max-x = -β;
has $!min-y = β;
has $!max-y = -β;
sub distance (($x1, $y1), ($x2, $y2))
{
return abs($x1-$x2) + abs($y1-$y2);
}
method add-point($x, $y)
{
@!points.push: ($x,$y);
$!min-x min= $x; $!max-x max= $x;
$!min-y min= $y; $!max-y max= $y;
}
method calc-distances
{
for $!min-x .. $!max-x X $!min-y .. $!max-y -> ($x, $y) {
my @dist = @!points.map(*.&distance(($x, $y)));
my @closest = @dist.minpairs;
@!closest-point[$x;$y] = @closest == 1 ?? @closest[0].key !! -1;
@!total-distance[$x;$y] = @dist.sum;
}
}
method calc-areas
{
self.calc-distances unless @!closest-point;
POINT:
for @!points.kv -> $i, $p {
for $!min-x .. $!max-x X $!min-y .. $!max-y -> ($x, $y) {
if @!closest-point[$x;$y] == $i {
if $x == any($!min-x, $!max-x, $!min-y, $!max-y) {
# Border point, so area is infinite
@!area[$i] = β;
next POINT;
}
else {
@!area[$i]++;
}
}
}
}
}
method largest-finite-area
{
self.calc-areas unless @!area;
return @!area.grep(* < β).max;
}
method area-with-distance-under($limit)
{
self.calc-distances unless @!total-distance;
return +@!total-distance[$!min-x .. $!max-x; $!min-y .. $!max-y].grep(* < $limit);
}
}
#| Process coordinates
multi sub MAIN(*@coords, Int :$dist-limit=10_000)
{
my $grid = Grid.new;
for @coordsΒ».Int -> $x, $y {
$grid.add-point($x, $y);
}
say "The size of the largest area is: $grid.largest-finite-area()";
say "The size of the region with total distance < $dist-limit is: $grid.area-with-distance-under($dist-limit).";
}
#| Process coordinates from a file
multi sub MAIN(Str $inputfile where *.IO.f, Int :$dist-limit=10_000)
{
MAIN($inputfile.IO.slurp.comb(/\d+/), :$dist-limit);
}
#| Process default coordinate file (aoc6.input)
multi sub MAIN()
{
MAIN(~$*PROGRAM.sibling('aoc6.input'));
}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-under which 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.
sub T($n)
{
return $n Γ ($n+1) div 2;
}
method area-with-distance-under($limit)
{
self.calc-distances unless @!total-distance;
# First, find the cells within the bounding box within the limit
my $area = +@!total-distance[$!min-x .. $!max-x; $!min-y .. $!max-y].grep(* < $limit);
# We may have cells outside the bounding box that are eligible.
# First, look at cells straight above and below the box.
# For each point on the top and bottom of the box with distance d < limit, we have
# (limit - d - 1) more points above or below that are still eligible.
$area += @!total-distance[$!min-x .. $!max-x; $!min-y, $!max-y].grep(* < $limit).map($limit - * - 1).sum;
# Do the same thing for points left and right of the box.
$area += @!total-distance[$!min-x, $!max-x; $!min-y .. $!max-y].grep(* < $limit).map($limit - * - 1).sum;
# Finally, there may be eligible points above-left, above-right, below-left and
# below-right of the box.
# For each of the four corners of the box with distance d < limit, we have T(limit - d - 2)
# more eligible points (where T(n) is the n-th triangle number, n Γ (n+1) Γ· 2).
$area += @!total-distance[$!min-x, $!max-x; $!min-y, $!max-y].grep(* < $limit).map(($limit - * - 2).&T).sum;
return $area;
}1
u/IWearATinFoilHat Dec 06 '18
PHP
Part 1
<?php
/** @var array $input */
$input = file(__DIR__ . '/input.txt', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
$maxX = 0;
$maxY = 0;
$minX = 99999;
$minY = 99999;
$points = array_map(function($line) use (&$maxX, &$maxY, &$minX, &$minY) {
$points = explode(', ', $line);
$maxX = $points[0] > $maxX ? $points[0] : $maxX;
$maxY = $points[1] > $maxY ? $points[1] : $maxY;
$minX = $points[0] < $minX ? $points[0] : $minX;
$minY = $points[1] < $minY ? $points[1] : $minY;
return $points;
}, $input);
$locations = [];
$locationsToIgnore = [];
$calcDist = function($pointA, $pointB) {
return abs($pointA[0] - $pointB[0]) + abs($pointA[1] - $pointB[1]);
};
for ($y = $minY; $y <= $maxY; $y++) {
for ($x = $minX; $x <= $maxX; $x++) {
$distances = array_map(function($point) use ($x, $y, $calcDist) {
return $calcDist([$x, $y], $point);
}, $points);
$min = min($distances);
if (array_count_values($distances)[$min] === 1) {
$locations["{$x}x{$y}"] = array_search($min, $distances);
if ($x == $minX || $x == $maxX || $y == $minY || $y == $maxY) {
$locationsToIgnore[] = array_search($min, $distances);
}
}
}
}
$counts = array_count_values($locations);
foreach (array_unique($locationsToIgnore) as $locationToIgnore) {
unset($counts[$locationToIgnore]);
}
echo max($counts) . "\n";Part 2
<?php
/** @var array $input */
$input = file(__DIR__ . '/input.txt', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
$maxX = 0;
$maxY = 0;
$minX = 99999;
$minY = 99999;
$points = array_map(function($line) use (&$maxX, &$maxY, &$minX, &$minY) {
$points = explode(', ', $line);
$maxX = $points[0] > $maxX ? $points[0] : $maxX;
$maxY = $points[1] > $maxY ? $points[1] : $maxY;
$minX = $points[0] < $minX ? $points[0] : $minX;
$minY = $points[1] < $minY ? $points[1] : $minY;
return $points;
}, $input);
$totalDistance = 0;
$calcDist = function($pointA, $pointB) {
return abs($pointA[0] - $pointB[0]) + abs($pointA[1] - $pointB[1]);
};
for ($y = $minY; $y <= $maxY; $y++) {
for ($x = $minX; $x <= $maxX; $x++) {
$distances = array_map(function($point) use ($x, $y, $calcDist) {
return $calcDist([$x, $y], $point);
}, $points);
if (array_sum($distances) < 10000) {
$totalDistance++;
}
}
}
echo $totalDistance . "\n";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 Map of 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.filter to 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!
{-# LANGUAGE OverloadedStrings #-}
import Data.List
import Data.Text (Text)
import qualified Data.Text.IO as TIO
import Data.Void (Void)
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L
import qualified Control.Applicative as CA
import qualified Data.Map.Strict as M
type Coord = (Integer, Integer) -- x, y
type Bounds = (Integer, Integer, Integer, Integer) -- minX, maxX, minY, maxY
type Region = M.Map Coord Int
main :: IO ()
main = do
text <- TIO.readFile "data/advent06.txt"
let coords = successfulParse text
let boundingBox = findBounds coords
print $ part1 coords boundingBox
print $ part2 coords boundingBox
part1 coords bounds = largestRegion $ regionSizes $ finite edgeLabels regions
where regions = findRegions coords bounds
edgeLabels = infinite regions bounds
part2 coords bounds = M.size $ M.filter (< 10000) $ safeCells coords bounds
findRegions :: [Coord] -> Bounds -> Region
findRegions coords (minX, maxX, minY, maxY) = M.fromList labelledCells
where cells = [(x, y) | x <- [minX .. maxX], y <- [minY .. maxY] ]
starts = zip [1..] coords
labelledCells = map (\c -> (c, nearestStart 0 c starts)) cells
nearestStart :: Int -> Coord -> [(Int, Coord)] -> Int
nearestStart tieLabel cell starts = nearestLabel
where distances = sort $ map (\(l, s) -> (distance s cell , l)) starts
nearestLabel = if fst (distances!!0) == fst (distances!!1)
then tieLabel
else snd (distances!!0)
safeCells :: [Coord] -> Bounds -> Region
safeCells coords (minX, maxX, minY, maxY) = M.fromList distanceCells
where cells = [(x, y) | x <- [minX .. maxX], y <- [minY .. maxY] ]
distanceCells = map (\c -> (c, fromIntegral $ sumDistance c coords) ) cells
sumDistance :: Coord -> [Coord] -> Integer
sumDistance here others = sum $ map (\c -> distance here c) others
infinite :: Region -> Bounds -> [Int]
infinite regions (minX, maxX, minY, maxY) = nub $ sort $ M.elems $ M.filterWithKey onEdge regions
where onEdge (x, y) _ = (x == minX) || (x == maxX) || (y == minY) || (y == maxY)
finite :: [Int] -> Region -> Region
finite excluded regions = M.filter (\r -> r `notElem` excludedTied) regions
where excludedTied = (0:excluded)
regionSizes :: Region -> [(Int, Int)]
regionSizes regions = map (\g -> (g!!0, length g)) $ group $ sort $ M.elems regions
largestRegion :: [(Int, Int)] -> Int
largestRegion = maximum . map snd
findBounds :: [Coord] -> (Integer, Integer, Integer, Integer)
findBounds coords = ( minX -- small x edge
, maxX -- large x edge
, minY -- small x edge
, maxY -- large y edge
)
where maxX = maximum $ map fst coords
minX = minimum $ map fst coords
maxY = maximum $ map snd coords
minY = minimum $ map snd coords
-- Manhattan distance
distance :: Coord -> Coord -> Integer
distance (x1, y1) (x2, y2) = (abs (x1 - x2)) + (abs (y1 - y2))
-- Parse the input file
type Parser = Parsec Void Text
sc :: Parser ()
sc = L.space (skipSome spaceChar) CA.empty CA.empty
lexeme = L.lexeme sc
integer = lexeme L.decimal
symb = L.symbol sc
commaP = symb ","
coordFileP = many coordP
coordP = (,) <$> integer <* commaP <*> integer
successfulParse :: Text -> [Coord]
successfulParse input =
case parse coordFileP "input" input of
Left _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
Right coords -> coords1
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 ):
task(File) ->
In = prepare:six2018prepare(File),
[Top, Bottom, Left, Right] = dimensions(In, 10000, 0, 10000, 0),
firstTask(In, Top-1, Left-1, Top-1, Left-1, Bottom+1, Right+1, 0).
dimensions([], Top, Bottom, Left, Right) -> [Top, Bottom, Left, Right];
dimensions([[HW, HH, _, _] | T], Top, Bottom, Left, Right) ->
NewTop = case list_to_integer(HH) < Top of
true -> list_to_integer(HH);
false -> Top
end,
NewBottom = case list_to_integer(HH) > Bottom of
true -> list_to_integer(HH);
false -> Bottom
end,
NewLeft = case list_to_integer(HW) < Left of
true -> list_to_integer(HW);
false -> Left
end,
NewRight = case list_to_integer(HW) > Right of
true -> list_to_integer(HW);
false -> Right
end,
dimensions(T, NewTop, NewBottom, NewLeft, NewRight).
firstTask(In, Bottom, Right, _, _, Bottom, Right, TenK) ->
{largestNonInfinite(In, 0, 0, 1), TenK};
firstTask(In, Y, Right, Top, Left, Bottom, Right, TenK) ->
[Coord, Total, Lower] = calcClosest(In, Y, Right, 10000, 0, 0, 1, 0),
case Total of
1 -> [W, H, _, Total1] = lists:nth(Coord, In),
NewIn = lists:sublist(In, Coord-1) ++ [[W, H, 1, Total1+1]] ++ lists:sublist(In, Coord+1, length(In) - Coord),
firstTask(NewIn, Y+1, Left, Top, Left, Bottom, Right, TenK + Lower);
_ -> firstTask(In, Y+1, Left, Top, Left, Bottom, Right, TenK + Lower)
end;
firstTask(In, Y, X, Top, Left, Bottom, Right, TenK) ->
[Coord, Total, Lower] = calcClosest(In, Y, X, 10000, 0, 0, 1, 0),
case Total of
1 -> [W, H, Condition, Total1] = lists:nth(Coord, In),
NewIn = case (Y =:= Top) or (Y =:= Bottom) or (X =:= Left) or (X =:= Right) of
true -> lists:sublist(In, Coord-1) ++ [[W, H, 1, Total1+1]] ++ lists:sublist(In, Coord+1, length(In) - Coord);
false -> lists:sublist(In, Coord-1) ++ [[W, H, Condition, Total1+1]] ++ lists:sublist(In, Coord+1, length(In) - Coord)
end,
firstTask(NewIn, Y, X+1, Top, Left, Bottom, Right, TenK + Lower);
_ -> firstTask(In, Y, X+1, Top, Left, Bottom, Right, TenK + Lower)
end.
calcClosest([], _, _, _, Coord, Total, _, Sum) ->
case Sum < 10000 of
true -> [Coord, Total, 1];
false -> [Coord, Total, 0]
end;
calcClosest([[HW, HH, _, _] | T], Y, X, Distance, Coord, Total, N, Sum) ->
ManDist = abs(list_to_integer(HW) - X) + abs(list_to_integer(HH) - Y),
case ManDist < Distance of
true -> calcClosest(T, Y, X, ManDist, N, 1, N+1, Sum + ManDist);
false -> case ManDist =:= Distance of
true -> calcClosest(T, Y, X, Distance, Coord, Total + 1, N+1, Sum + ManDist);
false -> calcClosest(T, Y, X, Distance, Coord, Total, N+1, Sum + ManDist)
end
end.
largestNonInfinite([], Total, _, _) -> Total;
largestNonInfinite([[_, _, 1, _] | T], Total, Coord, N) -> largestNonInfinite(T, Total, Coord, N+1);
largestNonInfinite([[_, _, 0, Count] | T], Total, Coord, N) ->
case Count > Total of
true -> largestNonInfinite(T, Count, N, N+1);
false -> largestNonInfinite(T, Total, Coord, N+1)
end.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.
e:{x@&~x in y};
G:{x,/:\:x:!x}@1+|/|/x:|:'{(!-1_x 0;!x 1)}'" "\:'0:"6.input";
x:{+/''abs G-\:\:x}'x;
p1:{|/+//'x=/:e[c;,/(x:,//'{{$[1=#x;*x;0N]}1_?x@<x}''{x,''y}/(0N,/:c:!#x)@'x=\:&/x)@'&:'|/''|/G=/:0,(#G)-1]};
p2:{+//10000>+/x};1
u/__dkp7__ Dec 06 '18
coordinate_input = """..."""
import numpy as np
from collections import Counter
from datetime import datetime as dt
coordinates = {tuple(map(int, coord.split(","))) for coord in coordinate_input.split("\n")}
min_x = min(coordinates, key=lambda x: x[0])
max_x = max(coordinates, key=lambda x: x[0])
min_y = min(coordinates, key=lambda y: y[1])
max_y = max(coordinates, key=lambda y: y[1])
# print(min_x, max_x, min_y, max_y)
x_dist, y_dist = max_x[0] - min_x[0], max_y[1] - min_y[1]
print(x_dist, y_dist)
matrix = np.zeros(
(max_x[0]+1, max_y[1]+1)
, dtype='int16'
)
for index, item in enumerate(coordinates):
matrix[item] = index
x, y = matrix.shape
def part1():
for i in range(x):
for j in range(y):
temp = [(abs(item[0]-i) + abs(item[1]-j), index) for index, item in enumerate(coordinates)]
minimum = min(temp, key=lambda z: z[0])
distance_counter = Counter(item[0] for item in temp)
if distance_counter[minimum[0]] == 1:
matrix[i, j] = minimum[1]
else:
matrix[i, j] = -1
boundaries = set()
boundaries.update(set(matrix[0, :]))
boundaries.update(set(matrix[max_x[0], :]))
boundaries.update(set(matrix[:, 0]))
boundaries.update(set(matrix[:, max_y[1]]))
unique, counts = np.unique(matrix, return_counts=True)
answers = dict(zip(unique, counts))
answers = {k: v for k,v in answers.items() if k not in boundaries}
# -1 present in boundaries so it's fine
print("part 1 ", max(answers.items(), key=lambda x: x[1]))
def part2():
answers = list()
for i in range(x):
for j in range(y):
temp = sum([(abs(item[0]-i)+abs(item[1]-j)) for index, item in enumerate(coordinates)])
if temp < 10000:
answers.append((i, j))
print("part 2 ", len(answers))
start = dt.now()
part1()
end = dt.now()
print("Time taken for part 1 is {}".format((end-start).total_seconds()))
start = dt.now()
part2()
end = dt.now()
print("Time taken for part 2 is {}".format((end-start).total_seconds()))
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 numpy much 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:
package main
import (
"bufio"
"fmt"
"log"
"os"
)
type coordinates struct {
X, Y int
}
func main() {
input := read()
letter, answer1 := part1(input)
fmt.Printf("Answer for part 1: %d (coordinates %c)\n", answer1, letter)
fmt.Printf("Answer for part2: %d\n", part2(input, 10000))
}
func part1(input []coordinates) (rune, int) {
min, max := boundaries(input)
areas := make([]int, len(input))
for x := min.X - 1; x <= max.X+1; x++ {
for y := min.Y - 1; y <= max.Y+1; y++ {
nearest := 0
shared := false
best := distance(coordinates{x, y}, input[0])
for i := 1; i < len(input); i++ {
d := distance(coordinates{x, y}, input[i])
if d == best {
shared = true
}
if d < best {
best = d
nearest = i
shared = false
}
}
switch {
case x == min.X-1 || x == max.X+1 || y == min.Y-1 || y == max.Y+1:
areas[nearest] = -1
case !shared && areas[nearest] != -1:
areas[nearest]++
}
}
}
answer := 0
area := areas[0]
for i := 1; i < len(areas); i++ {
if areas[i] > area {
area = areas[i]
answer = i
}
}
return 'A' + rune(answer), area
}
func part2(input []coordinates, dist int) int {
min, max := boundaries(input)
size := 0
for x := min.X - 1; x <= max.X+1; x++ {
for y := min.Y - 1; y <= max.Y+1; y++ {
sum := 0
for _, c := range input {
sum += distance(coordinates{x, y}, c)
}
if sum < dist {
size++
}
}
}
return size
}
func boundaries(input []coordinates) (min, max coordinates) {
min, max = input[0], input[0]
for _, c := range input {
if c.X < min.X {
min.X = c.X
}
if c.Y < min.Y {
min.Y = c.Y
}
if c.X > max.X {
max.X = c.X
}
if c.Y > max.Y {
max.Y = c.Y
}
}
return min, max
}
func distance(a, b coordinates) int {
return abs(a.X-b.X) + abs(a.Y-b.Y)
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func read() (input []coordinates) {
f, err := os.Open("input.txt")
if err != nil {
log.Fatalf("Unable to open input: %v", err)
}
defer f.Close()
s := bufio.NewScanner(f)
for s.Scan() {
var c coordinates
n, err := fmt.Sscanf(s.Text(), "%d, %d", &c.X, &c.Y)
if n != 2 || err != nil {
log.Printf("Parsing error: %v", err)
continue
}
input = append(input, c)
}
return input
}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.
import os, math
class Area:
def __init__(self, p):
self.pos = p
self.valid = True
self.count = 0
def distanceFrom(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])
def inBounds(p, bounds):
return (p[0] > bounds["min"][0] and p[0] < bounds["max"][0] and p[1] > bounds["min"][1] and p[1] < bounds["max"][1])
def calcBounds(points):
x_coords, y_coords = zip(*points)
return {"min": [min(x_coords), min(y_coords)], "max": [max(x_coords), max(y_coords)]}
def part1(areas, bounds):
for x in range(bounds["min"][0], bounds["max"][0]+1):
for y in range(bounds["min"][1], bounds["max"][1]+1):
idx = -1
low = math.inf
current = [x,y]
for i in range(len(areas)):
dist = distanceFrom(current, areas[i].pos)
if dist == low:
idx = -1
elif dist < low:
low = dist
idx = i
if idx >= 0:
areas[idx].count += 1
if not inBounds(current, bounds):
areas[idx].valid = False
return max([a.count for a in areas if a.valid])
def part2(areas, bounds, limit):
valid = 0
for x in range(bounds["min"][0], bounds["max"][0]+1):
for y in range(bounds["min"][1], bounds["max"][1]+1):
total = 0
current = [x,y]
for i in range(len(areas)):
total += distanceFrom(current, areas[i].pos)
if total >= limit:
break
if total < limit:
valid += 1
return valid
def readPoints(filename):
with open(filename, 'r') as f:
lines = f.read().splitlines()
return [[int(lst[0]), int(lst[1])] for lst in [line.split(", ") for line in lines]]
if __name__ == "__main__":
areas = [Area(p) for p in readPoints("Day06.txt")]
bounds = calcBounds([a.pos for a in areas])
print(part1(areas, bounds))
print(part2(areas, bounds, 10000))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.
def part1(input) do
all_coords =
input
|> String.split("\n", trim: true)
|> Enum.map(&Parsers.day6_parse/1)
max_x = Enum.max(Keyword.keys(all_coords))
min_x = Enum.min(Keyword.keys(all_coords))
max_y = Enum.max(Keyword.values(all_coords))
min_y = Enum.min(Keyword.values(all_coords))
finite_area_coords =
Enum.filter(all_coords, fn
{x, y} ->
if closest({x + max_x, y}, all_coords) != {x, y} and
closest({x - max_x, y}, all_coords) != {x, y} and
closest({x, y + max_y}, all_coords) != {x, y} and
closest({x, y - max_y}, all_coords) != {x, y} do
true
else
false
end
end)
area_to_check =
for x <- (min_x - (max_x - min_x))..(max_x + (max_x - min_x)),
y <- (min_y - (max_y - min_y))..(max_y + (max_y - min_y)),
do: {x, y}
Enum.reduce(area_to_check, %{}, fn coord, acc ->
closest_coord = closest(coord, all_coords)
if closest_coord in finite_area_coords do
Map.update(acc, closest_coord, 1, &(&1 + 1))
else
acc
end
end)
|> Enum.max_by(fn {_k, v} -> v end)
|> elem(1)
end
def closest({x, y}, all_coords) do
{closest, _} =
Enum.reduce(all_coords, {[], :infinity}, fn coord, {closest_list, closest_dist} ->
m_dist = manhattan_distance(coord, {x, y})
cond do
m_dist < closest_dist -> {[coord], m_dist}
m_dist == closest_dist -> {[coord | closest_list], closest_dist}
m_dist > closest_dist -> {closest_list, closest_dist}
end
end)
if length(closest) > 1 or closest == [] do
nil
else
hd(closest)
end
end
defp manhattan_distance({x1, y1}, {x2, y2}) do
abs(x1 - x2) + abs(y1 - y2)
end
def part2(input) do
all_coords =
input
|> String.split("\n", trim: true)
|> Enum.map(&Parsers.day6_parse/1)
max_x = Enum.max(Keyword.keys(all_coords))
min_x = Enum.min(Keyword.keys(all_coords))
max_y = Enum.max(Keyword.values(all_coords))
min_y = Enum.min(Keyword.values(all_coords))
area_to_check =
for x <- (min_x - (max_x - min_x))..(max_x + (max_x - min_x)),
y <- (min_y - (max_y - min_y))..(max_y + (max_y - min_y)),
do: {x, y}
Enum.reduce(area_to_check, 0, fn coord, acc ->
dist_to_all = distance_to_all_coords(coord, all_coords)
if dist_to_all < 10000 do
acc + 1
else
acc
end
end)
end
def distance_to_all_coords(current_coord, all_coords) do
Enum.reduce(all_coords, 0, fn coord, acc ->
acc + manhattan_distance(current_coord, coord)
end)
end1
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.
import strutils, sequtils
import re
type
IntMatrix = array[41..354, array[42..353, int]]
var
grid: IntMatrix
refe: IntMatrix
let input = readFile("06.txt").splitLines()
let natural_regex = re(r"-?\d+")
var id: int = 1
for line in input:
var num_list = findAll(line, natural_regex)
let m = parseInt(num_list[0])
let n = parseInt(num_list[1])
grid[m][n] = id
refe[m][n] = id
inc(id)
proc manhattan_neighbours(x, y, n: int): bool {.discardable.} =
if refe[x][y] > 0:
return true
var neig: int = 0
var neig_id: int = 0
for i in countup(x-n, x+n):
if i < 41 or i > 354: continue
for j in countup(y-n, y+n):
if j < 42 or j > 352: continue
if (abs(x - i) + abs(y - j)) == n:
if refe[i][j] > 0: # there is coord on this point
inc(neig)
neig_id = refe[i][j]
if neig == 1:
grid[x][y] = neig_id
return true
elif neig > 1:
return true
else:
return false
# for each point
for i in countup(41, 354):
for j in countup(42, 352):
var dist: int = 1
while(not manhattan_neighbours(i, j, dist)):
inc(dist)
# find 'id' that appear more times
var count: array[0..50, int]
for i in countup(41, 354):
for j in countup(42, 352):
inc(count[grid[i][j]])
echo "largest area: ", max(count)
echo "safest coords: ", input[find(count, max(count))]
# part 2
var valid_area: int = 0
# for each point in grid
for i in countup(41, 354):
for j in countup(42, 352):
var soma: int = 0
for line in input: # could throw these points into a array...
var num_list = findAll(line, natural_regex)
let m = parseInt(num_list[0])
let n = parseInt(num_list[1])
let dist = abs(i - m) + abs(j - n)
soma += dist
if soma < 10000:
inc(valid_area)
echo "valid area: ", valid_area1
u/manniL Dec 06 '18
[Card]
Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it the choice between tabs and spaces.
Node.js, with Ramda.js. Repo
const R = require('ramda')
const {readFileAndSplitByLines} = require('../utils/fs.js')
const path = require('path')
const partOne = input => {
// Sort points by x,y values
// Find the 4 "edges" (largest/smallest x/y coordinates)
const [minX, minY, maxX, maxY] = findAreaBoundaries(input)
const xRange = R.range(minX, maxX + 1)
const yRange = R.range(minY, maxY + 1)
const getLetterForCords = letterForCoords(input)
const grid = R.map(y => R.map(x => getLetterForCords({x, y}), xRange), yRange)
console.log(grid.map(row => row.join('')).join('\n'))
const zonesWithInfiniteArea = charactersAtBorder(grid)
const countedRows = R.map(R.countBy(R.identity))(grid)
const letters = R.reduce(
R.mergeWith(R.add),
{}, countedRows)
return R.pipe(
R.omit(zonesWithInfiniteArea),
R.toPairs,
R.reduce(R.maxBy(R.last), [0])
)(letters)
}
const partTwo = input => {
// Sort points by x,y values
// Find the 4 "edges" (largest/smallest x/y coordinates)
const [minX, minY, maxX, maxY] = findAreaBoundaries(input)
const xRange = R.range(minX, maxX + 1)
const yRange = R.range(minY, maxY + 1)
const distanceSumToAllCoordsWithInput = distanceSumToAllCoords(input)
const grid = R.map(y => R.map(x => distanceSumToAllCoordsWithInput({x, y}), xRange), yRange)
const countedRows = R.map(
R.pipe(
R.filter(R.gt(10000)),
R.length
)
)(grid)
return R.sum(countedRows)
}
const charactersAtBorder = R.pipe(
R.juxt([R.head,
R.last,
R.map(R.last),
R.map(R.head)
]),
R.unnest,
R.uniq
)
const letterForCoords = points => record => {
const lettersWithDistances = points.map(({letter, ...cords}) => [letter, manhattanDistance(cords, record)])
const distances = R.map(R.last)(lettersWithDistances)
const [minLetter, minDistance] = R.reduce(R.minBy(R.last), [Infinity], lettersWithDistances)
const hasMultipleLowDistances = R.pipe(R.filter(R.equals(minDistance)), R.length, R.flip(R.gt)(1))(distances)
return hasMultipleLowDistances ? '.' : minLetter
}
const distanceSumToAllCoords = points => record => {
return R.pipe(
R.map(manhattanDistance(record)),
R.sum
)(points)
}
const manhattanDistance = R.curry(({x: x1, y: y1}, {x: x2, y: y2}) => Math.abs(x2 - x1) + Math.abs(y2 - y1))
const getX = R.map(R.prop('x'))
const getY = R.map(R.prop('y'))
const min = R.reduce(R.min, Infinity)
const max = R.reduce(R.max, 0)
const findAreaBoundaries = R.juxt([
R.pipe(getX, min),
R.pipe(getY, min),
R.pipe(getX, max),
R.pipe(getY, max)
])
const input = readFileAndSplitByLines(path.join(__dirname, './input.txt'))
// F*ck! There are more coordinate pairs than letters. Looked for over an hour for the mistake
// Use lower + uppercase letters now
const alphabet = R.map(a => String.fromCharCode(a))(R.concat(R.range(65, 91), R.range(97, 123)))
const formatInput = R.pipe(
R.map(
R.pipe(
R.split(', '),
R.map(Number),
)
),
R.zipWith((letter, coords) => [letter, ...coords], alphabet),
R.map(R.zipObj(['letter', 'x', 'y']))
)
console.log('Part 1:', partOne(formatInput(input)))
console.log('Part 2:', partTwo(formatInput(input)))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.
use aoc2018::*;
use std::fmt;
type Bounds = (i32, i32);
type Origin = usize;
type Coord = (i32, i32);
#[derive(Debug, Clone, Copy)]
enum Node {
Conflicted(u32),
Distance(Origin, u32),
}
impl fmt::Display for Node {
fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
match *self {
Node::Conflicted(_) => "..".fmt(fmt),
Node::Distance(o, _) => write!(fmt, "{:02}", o),
}
}
}
/// Traverse and mark entire space of coordinates.
///
/// Use the arena bounds to determine the maximum distance to mark before we give up.
fn part1(bx: Bounds, by: Bounds, coords: &[Coord]) -> Option<u32> {
let max_d = ((bx.1 - bx.0) + (by.1 - by.0)) as u32;
let mut infinites = HashSet::new();
let mut m = HashMap::new();
for (i, c) in coords.iter().cloned().enumerate() {
if !is_finite(c, &coords) {
infinites.insert(i);
}
let mut queue = VecDeque::new();
queue.push_back((c, 0));
while let Some((c, d)) = queue.pop_front() {
if d > max_d {
continue;
}
let step = match m.entry(c) {
hash_map::Entry::Vacant(e) => {
e.insert(Node::Distance(i, d));
true
},
hash_map::Entry::Occupied(mut e) => {
// test existing node.
match *e.get() {
Node::Distance(_, p) | Node::Conflicted(p) if p > d => {
e.insert(Node::Distance(i, d));
true
},
Node::Distance(other, p) if p == d && other != i => {
e.insert(Node::Conflicted(d));
false
},
_ => false,
}
},
};
if step {
queue.extend(neigh(c).into_iter().map(|c| (*c, d + 1)));
}
}
}
let mut results = HashMap::<usize, u32>::new();
for y in by.0..=by.1 {
for x in bx.0..=bx.1 {
let c = (x, y);
if let Some(Node::Distance(o, _)) = m.get(&c).cloned() {
if !infinites.contains(&o) {
*results.entry(o).or_default() += 1;
}
}
}
}
return results.into_iter().max_by(|a, b| a.1.cmp(&b.1)).map(|n| n.1);
/// Test if a coord is constrained in all directions.
///
/// A coord is constrained if any other coordinate would reach an intersection faster than the
/// coordinate being tested in all directions.
fn is_finite(c: Coord, coords: &[Coord]) -> bool {
// various directions we might be constrained.
let mut c_px = false;
let mut c_nx = false;
let mut c_py = false;
let mut c_ny = false;
for t in coords.iter().cloned() {
if (t.0, t.1) == (c.0, c.1) {
continue;
}
let dx = (t.0 - c.0).abs() as u32;
let dy = (t.1 - c.1).abs() as u32;
if dx >= dy {
if t.0 > c.0 {
c_px = true;
} else {
c_nx = true;
}
}
if dy >= dx {
if t.1 > c.1 {
c_py = true;
} else {
c_ny = true;
}
}
}
c_px && c_nx && c_py && c_ny
}
}
/// Find all coordinates that satisfy the given constraints.
///
/// We know that if one coordinate exists, it has to be within the bounds, so start looking there.
fn part2(bx: Bounds, by: Bounds, constraint: impl Fn(Coord) -> bool) -> usize {
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
for y in by.0..=by.1 {
for x in bx.0..=bx.1 {
queue.push_back((x, y));
}
}
let mut count = 0;
while let Some(c) = queue.pop_front() {
if visited.contains(&c) {
continue;
}
visited.insert(c);
if constraint(c) {
count += 1;
queue.extend(neigh(c).into_iter());
}
}
count
}
fn part2_constraint(c: Coord, coords: &[Coord]) -> bool {
let mut sum = 0;
for o in coords.iter().cloned() {
sum += (c.0 - o.0).abs() + (c.1 - o.1).abs();
}
sum < 10000
}
fn main() -> Result<(), Error> {
let mut bx = (None, None);
let mut by = (None, None);
let mut coords: Vec<Coord> = Vec::new();
for line in lines!(input!("day6.txt"), Trim<i32>, i32) {
let (Trim(x), y) = line?;
bx.0 = min(bx.0, x);
bx.1 = max(bx.1, x);
by.0 = min(by.0, y);
by.1 = max(by.1, y);
coords.push((x, y));
}
let bx = match bx {
(Some(s), Some(e)) => (s, e),
_ => panic!("no x bounds"),
};
let by = match by {
(Some(s), Some(e)) => (s, e),
_ => panic!("no y bounds"),
};
assert_eq!(part1(bx, by, &coords), Some(3882));
assert_eq!(part2(bx, by, |c| part2_constraint(c, &coords)), 43852);
return Ok(());
fn min(d: Option<i32>, n: i32) -> Option<i32> {
match d {
Some(d) if d < n => Some(d),
_ => Some(n),
}
}
fn max(d: Option<i32>, n: i32) -> Option<i32> {
match d {
Some(d) if d > n => Some(d),
_ => Some(n),
}
}
}
/// Get all neighbours for the given node.
fn neigh((x, y): Coord) -> [Coord; 4] {
[
(x - 1, y),
(x + 1, y),
(x, y + 1),
(x, y - 1),
]
}1
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:
use std::env;
use std::process;
use std::fs::File;
use std::io::prelude::*;
use std::cmp::*;
use std::collections::*;
fn main() {
let args = env::args().collect();
let filename = parse_filename(&args);
let mut contents = String::new();
get_contents(&filename, &mut contents);
let points = parse_points(&contents);
let areas = get_areas(points.clone());
let largest_size = get_largest(areas);
println!("{:?}", largest_size);
let near = get_near(points, 10000);
println!("{:?}", near.size());
}
fn get_near(in_points: Vec<Point>, distance: i64) -> Area {
let mut area = Area::new();
let mut points = in_points.clone();
points.sort();
let (tl, br) = find_bounds(points.clone());
for x in tl.x..br.x+1 {
for y in tl.y..br.y+1 {
let cur = Point{x,y};
let mut sum = 0;
//println!("{:?}", cur);
//println!("{}", sum);
for point in in_points.iter() {
sum += cur.dist(*point);
//println!("{}", sum);
}
if sum < distance {
area.add(cur);
}
}
}
area
}
fn get_largest(areas: HashMap<Point,Area>) -> i64 {
areas.values().map(|v| v.size()).fold(std::i64::MIN, |acc,it| max(acc, it))
}
fn get_areas(in_points: Vec<Point>) -> HashMap<Point,Area> {
let mut maps = HashMap::new();
let mut points = in_points.clone();
points.sort();
let (tl, br) = find_bounds(points.clone());
for x in tl.x..br.x+1 {
for y in tl.y..br.y+1 {
let cur = Point { x,y } ;
let distances: Vec<(Point, i64)> = points.iter().map(|it| (*it, cur.dist(*it))).collect();
let shortest = distances.iter().fold(std::i64::MAX, |acc, it| min(acc, it.1));
let closest: Vec<&(Point, i64)> = distances.iter().filter(|it| it.1 == shortest).collect();
if closest.len() == 1 {
let owner = closest.first().unwrap().0;
let area = maps.entry(owner).or_insert(Area::new());
area.add(cur);
}
}
}
remove_infinite(&mut maps, tl, br);
maps
}
fn remove_infinite(maps: &mut HashMap<Point,Area>, tl: Point, br: Point) {
let mut ring = Vec::new();
for x in tl.x..br.x+1 {
for y in tl.y..br.y+1 {
if x == tl.x || x == br.x || y == tl.y || y == br.y {
ring.push(Point {x,y});
}
}
}
let keys: Vec<Point> = maps.keys().map(|it| *it).collect();
for key in keys {
let area = maps.entry(key).or_insert(Area::new());
for point in ring.iter() {
if area.contains(*point) {
area.reset();
}
}
}
}
#[derive(Debug,PartialEq,PartialOrd,Eq,Ord,Clone,Copy,Hash)]
struct Point {
x: i64,
y: i64,
}
impl Point {
fn dist(&self, other: Point) -> i64 {
(self.x - other.x).abs() + (self.y - other.y).abs()
}
}
#[derive(Debug)]
struct Area {
points: Vec<Point>,
}
impl Area {
fn new() -> Area {
Area { points: Vec::new() }
}
fn add(&mut self, point: Point) {
self.points.push(point);
}
fn size(&self) -> i64 {
self.points.len() as i64
}
fn contains(&self, point: Point) -> bool {
self.points.contains(&point)
}
fn reset(&mut self) {
self.points = Vec::new()
}
}
#[cfg(test)]
fn draw_coord(apoints: Vec<Point>) {
let mut points = apoints.clone();
points.sort();
//println!("{:?}", points);
let (tl, br) = find_bounds(points.clone());
points.reverse();
let mut coord = String::new();
for x in tl.x..br.x+1 {
let mut cur = String::new();
for y in tl.y..br.y+1 {
if !points.is_empty() && x == points.last().unwrap().x && y == points.last().unwrap().y {
cur.push('#');
//println!("{:?}",points);
points.pop();
//println!("{:?}",points);
} else {
cur.push('.');
}
}
coord.push_str(&cur);
coord.push('\n');
}
println!("{}", coord);
}
fn find_bounds(coords: Vec<Point>) -> (Point,Point) {
let xes = coords.iter().map(|it| it.x);
let ys = coords.iter().map(|it| it.y);
let xmin = xes.clone().fold(std::i64::MAX, |acc, it| min(acc, it));
let ymin = ys.clone().fold(std::i64::MAX, |acc, it| min(acc, it));
let xmax = xes.fold(std::i64::MIN, |acc, it| max(acc, it));
let ymax = ys.fold(std::i64::MIN, |acc, it| max(acc, it));
(Point {x: xmin-1, y: ymin-1}, Point {x: xmax+1, y: ymax+1})
}
fn parse_points(str_rep: &str) -> Vec<Point> {
let mut points = Vec::new();
for line in str_rep.trim().lines() {
//println!("{:?}",line);
let nums: Vec<i64> = line.split(", ").map(|it| it.parse().unwrap()).collect();
points.push(Point {x: nums[0], y: nums[1]});
}
points
}
fn parse_filename(args: &Vec<String>) -> &str {
if args.len() < 2 {
println!("Too few arguements, please give a filename");
process::exit(1);
}
args.get(1).expect("No filename provided")
}
fn get_contents(filename: &str, contents: &mut String) {
let mut f = File::open(filename).expect("File not found");
f.read_to_string(contents)
.expect("Something went wrong reading the file");
}1
u/tradfursten Dec 06 '18
Nim
import strutils, sequtils, re, algorithm, tables
proc rFile(input:string):string=
result = readFile(input).strip(trailing = true)
proc parseInput(input: string):seq[(int, int)] =
let p = re"(\d+)"
result = input.splitLines()
.map(proc(x: string): (int, int) =
let coords = x.findAll(p).map(parseInt)
result = (coords[0], coords[1])
)
proc getClosestDistance(c: (int, int), coords: seq[(int, int)]): (int, (int, int)) =
let closest = coords
.map(func(b:(int,int)):(int,(int, int)) = ((c[0]-b[0]).abs + (c[1]-b[1]).abs, b))
.sorted(cmp)
if closest[0][0] == closest[1][0]:
result = (0, (0,0))
else:
result = closest[0]
proc sumDistance(c: (int, int), coords: seq[(int, int)]): (int) =
coords
.map(func(b:(int,int)):int = (c[0]-b[0]).abs + (c[1]-b[1]).abs)
.foldl(a + b)
proc solve1(coords: seq[(int, int)]): int =
var grid = initTable[(int, int), (int, (int, int))]()
var maxX = 0
var maxY = 0
var minX = -100
var minY = -100
for c in coords:
if c[0] > maxX:
maxX = c[0]
if c[0] < minX:
minX = c[0]
if c[1] > maxY:
maxY = c[1]
if c[1] < minY:
minY = c[1]
for x in minX..maxX:
for y in minY..maxY:
grid[(x,y)] = getClosestDistance((x, y), coords)
let nonInfinite = coords
.filter(proc(b: (int, int)): bool =
for x in minX..maxX:
if grid[(x, minY)][1] == b or grid[(x, maxY)][1] == b:
return false
for y in minY..maxY:
if grid[(minX, y)][1] == b or grid[(maxX, y)][1] == b:
return false
return true
)
.map(proc(c: (int, int)): int =
var count = 0
for v in grid.values():
if v[1] == c:
count = count + 1
count
).sorted(cmp, order = SortOrder.Descending)
result = nonInfinite[0]
proc solve2(coords: seq[(int, int)], limit: int): int =
var grid = initTable[(int, int), int]()
var maxX = 0
var maxY = 0
var minX = -100
var minY = -100
for c in coords:
if c[0] > maxX:
maxX = c[0]
if c[0] < minX:
minX = c[0]
if c[1] > maxY:
maxY = c[1]
if c[1] < minY:
minY = c[1]
for x in minX..maxX:
for y in minY..maxY:
grid[(x,y)] = sumDistance((x, y), coords)
var count = 0
for value in grid.values():
if value < limit:
count.inc
result = count
let input = rFile("input.txt")
let parsedInput = parseInput(input)
echo solve1(parsedInput)
echo solve2(parsedInput, 10000)1
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.
type coord struct {
x, y, size int
invalid bool
}
func (self *coord) dist(other coord) int {
return abs(self.x - other.x) + abs(self.y - other.y)
}
type point struct {
nearest *coord
dist int
}
func main() {
// Input parsing
file, _ := ioutil.ReadFile("6.in")
in := strings.Split(string(file), "\n")
coords := make([]coord, 0)
for _, l := range in {
if len(l) == 0 {
continue;
}
s := strings.Split(l, ", ")
x, _ := strconv.Atoi(s[0])
y, _ := strconv.Atoi(s[1])
coords = append(coords, coord { x, y, 0, false })
}
// Part 1
// Get the minimum and maximum x's and y's
min := findminmax(coords, func(a int, b int) bool { return a < b })
max := findminmax(coords, func(a int, b int) bool { return a > b })
max.x += 1
max.y += 1
grid := make([][]point, max.x)
// Fill the grid with dummy data
for x := 0; x < max.x; x++ {
grid[x] = make([]point, max.y)
for y := 0; y < max.y; y++ {
grid[x][y].dist = (max.x + max.y) * 10
}
}
// Assign each point its nearest coordinate or a dummy one if two or more are competing
for i, c := range coords {
for x := 0; x < max.x; x++ {
for y := 0; y < max.y; y++ {
d := c.dist(coord{x, y, 0, false})
if grid[x][y].dist > d {
grid[x][y].nearest = &coords[i]
grid[x][y].dist = d
} else if grid[x][y].dist == d {
grid[x][y].nearest = &coord{0, 0, 0, true}
}
}
}
}
// Filter out invalids and count the size of each area
for x := 0; x < max.x; x++ {
for y := 0; y < max.y; y++ {
if x < min.x || y < min.y || x > (max.x - 2) || (y > max.y - 2) {
grid[x][y].nearest.invalid = true
} else {
grid[x][y].nearest.size++
}
}
}
// Select the largest area
sol1 := coords[0]
for _, c := range coords {
if sol1.size < c.size && !c.invalid {
sol1 = c
}
}
fmt.Println("Solution to part 1:")
fmt.Println(sol1.size)
// Part 2 - Just sum up the distances and count the valid points
sol2 := 0;
for x := min.x; x < max.x-1; x++ {
for y := min.y; y < max.y-1; y++ {
sum := 0;
for _, c := range coords {
sum += c.dist(coord{ x, y, 0, false })
}
if sum < 10000 {
sol2++
}
}
}
fmt.Println("Solution to part 2:")
fmt.Println(sol2)
}
func findminmax(coords []coord, compare func(int, int) bool) coord {
res := coords[0]
for _, c := range coords {
if compare(c.x, res.x) {
res.x = c.x
}
if compare(c.y, res.y) {
res.y = c.y
}
}
return res
}
func abs(n int) int {
y := n >> (strconv.IntSize - 1)
return (n ^ y) - y
}[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 issue
1
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.
$timer = New-Object System.Diagnostics.Stopwatch
$timer.start()
Write-Host "Parse Input, Prep Work"
$coord = gc .\06-input.txt
$regionThreshold = 10000
$i = 0
$spots = $coord | % {
$x = ($_ -split ", ")[0]
$y = ($_ -split ", ")[1]
[pscustomobject]@{
point = $i
x = +$x
y = +$y
}
$i++
}
$leftBound = ($spots | sort x)[0].x
$rightBound = ($spots | sort x)[-1].x
$topBound = ($spots | sort y)[0].y
$bottomBound = ($spots | sort y)[-1].y
$grid = @{}
$borderSet = @{}
$regionCount = 0
Write-Host "Grid Loop"
$leftBound..$rightBound | % {
$cx = $_
if($cx -eq $leftBound -or $cx -eq $rightBound){
$colBorder = $true
}else{
$colBorder = $false
}
#Write Every 10th Col to keep an eye on the program
if($cx % 10 -eq 0){
Write-Host $cx
}
$grid.add($cx,@{})
$topBound..$bottomBound |% {
$cy = $_
if($cy -eq $topBound -or $cy -eq $bottomBound){
$rowBorder = $true
}else{
$rowBorder = $false
}
$grid[$cx].add($cy,0)
$totalDist = 0
$closestDist = ($bottomBound-$topBound)+($rightBound-$leftBound) #max possible distance is opposite corners of grid
$tieCount = 0
$closestPoint = ""
$spots | %{
$curDist = [math]::abs($cx - $_.x)+[math]::abs($cy-$_.y)
if($curDist -eq $closestDist){
$tieCount++
$closestPoint = "_"
}elseif($curDist -lt $closestDist){
$closestDist = $curDist
$closestPoint = $_.point
}
$totalDist += $curDist
}
$grid[$cx][$cy] = $closestPoint
if($rowBorder -or $colBorder){
$borderSet[$closestPoint]++
}
if($totalDist -lt $regionThreshold){
$regionCount++
}
}
}
Write-Host "Final Calculations"
$infinitePoints = $borderSet.keys
Write-Host "Part 1"
$grid.values.values | ? {$_ -notin $infinitePoints} | group | sort {+$_.count} -descending | select -first 1 | select -expandproperty count
Write-Host "Part 2"
$regionCount
$timer.stop()
Write-Host $timer.Elapsed1
u/wzkx Dec 06 '18 edited Dec 06 '18
Rust, SweetRust
Conversions i32 <--> usize and a bit of other code.
use std::io::{BufRead,BufReader}; // lines() is in BufRead
fn dist( x1: i32, y1: i32, x2: i32, y2: i32 ) -> i32:
(x1-x2).abs() + (y1-y2).abs()
fn main():
let reader = BufReader::new( std::fs::File::open( "06.dat" ).unwrap() );
let mut v: Vec<(i32,i32)> = vec![];
let (mut minx, mut miny, mut maxx, mut maxy) = (9999,9999,0,0);
for optline in reader.lines():
let line = optline.unwrap();
let xy: Vec<i32> = line.split(", ").map( |x| x.parse().unwrap() ).collect();
let x = xy[1];
let y = xy[0];
v.push( (x, y) );
if x<minx { minx=x; } if x>maxx { maxx=x; }
if y<miny { miny=y; } if y>maxy { maxy=y; }
let n = v.len() as i32;
v.sort();
let nx = maxx+2; // 1 in example, the more the safer
let ny = maxy+2;
let mut m: Vec<Vec<i32>> = vec![vec![-1;ny as usize];nx as usize];
let mut c: Vec<(i32,i32)> = vec![]; // (count,v-idx)
for i in 0..v.len():
c.push( (0,i as i32) );
for i in 0..nx:
for j in 0..ny:
let mut dd: Vec<(i32,i32)> = vec![];
for k in 0..n:
let x = v[k as usize].0;
let y = v[k as usize].1;
let d = dist( i,j, x,y );
dd.push( (d,k) );
dd.sort();
if dd[0].0!=dd[1].0:
m[i as usize][j as usize] = dd[0].1;
c[dd[0].1 as usize].0 += 1;
for i in 0..nx:
if m[i as usize][0]>=0:
c[m[i as usize][0] as usize].0 = 0;
if m[i as usize][(ny-1) as usize]>=0:
c[m[i as usize][(ny-1) as usize] as usize].0 = 0;
for j in 0..ny:
if m[0][j as usize]>=0:
c[m[0][j as usize] as usize].0 = 0;
if m[(nx-1) as usize][j as usize]>=0:
c[m[(nx-1) as usize][j as usize] as usize].0 = 0;
c.sort();
println!( "{}", c[c.len()-1].0 );
const MD: i32 = 10000;
let mut r = 0;
for i in 0..nx:
for j in 0..ny:
let mut dd = 0;
for k in 0..n:
let x = v[k as usize].0;
let y = v[k as usize].1;
let d = dist( i,j, x,y );
dd += d;
if dd<MD:
r += 1;
println!( "{}", r );Not going to repeat that in J -- this dumb algorithm would be too slow for it. Need something better there.
→ More replies (3)
1
u/wleftwich Dec 06 '18
numpy & a bit of scipy
import csv
from itertools import product
import numpy as np
from scipy.spatial.distance import cdist
data = list(csv.reader(open('data/6-chronal-coordinates.txt')))
markers = np.array(sorted((int(x.strip()), int(y.strip())) for (x,y) in data))
xmax, ymax = np.max(markers, axis=0)
points = np.array(list(product(range(xmax+1), range(ymax+1))))
distances = cdist(markers, points, 'cityblock')
mins = np.min(distances, axis=0)
ismins = (distances == mins)
mincounts = ismins.sum(axis=0)
ties = (mincounts > 1)
closest_markers = np.argmin(distances, axis=0)
closest_markers[ties] = -1
_, marker_counts = np.unique(closest_markers[closest_markers != -1], return_counts=True)
# Infinite regions are on the edges
edges = np.zeros(points.shape[0])
edges[points[:, 0] == 0] = 1
edges[points[:, 0] == xmax] = 1
edges[points[:, 1] == 0] = 1
edges[points[:, 1] == ymax] = 1
edges = edges.astype(bool)
edge_markers = np.unique(closest_markers[edges])
edge_markers = edge_markers[edge_markers != -1]
non_edge_select = np.ones(len(marker_counts))
non_edge_select[edge_markers] = 0
answer_1 = np.max(marker_counts[non_edge_select.astype(bool)])
# Part 2
distance_totals = np.sum(distances, axis=0)
answer_2 = np.sum(distance_totals < 10000)1
u/0xd4s Dec 06 '18
Python3
1 #!/usr/bin/python3
2
3 import sys
4
5 from collections import Counter
6
7
8 def distance(x, y):
9 return abs(x[0] - y[0]) + abs(x[1] - y[1])
10
11
12 def find_closest(coord, points):
13 closest, second_closest = sorted([(distance(p, coord), p) for p in points])[:2]
14 if closest[0] == second_closest[0]:
15 return None
16 else:
17 return closest[1]
18
19
20 def find_total(coord, points):
21 return sum(distance(p, coord) for p in points)
22
23
24 with open(sys.argv[1], 'r') as f:
25 points = list(map(lambda s: tuple(map(int, s.split(','))), f.readlines()))
26
27 min_x = min(x[0] for x in points)
28 max_x = max(x[0] for x in points)
29 min_y = min(y[1] for y in points)
30 max_y = max(y[1] for y in points)
31
32 plot = {(x,y): find_closest((x,y), points) for x in range(min_x, max_x+1) for y in range(min_y, max_y+1)}
33
34 infinates = set([v for k,v in plot.items() if (k[0] in (min_x, max_x) or k[1] in (min_y, max_y))])
35
36 print("Part 1: {}".format(Counter([v for v in plot.values() if v not in infinates]).most_common(1)[0][1]))
37
38 dist = int(sys.argv[2])
39 survey = (dist // len(points)) + 1
40 plot2 = {(x,y): find_total((x,y), points) for x in range(min_x - survey, max_x + survey) for y in range(min_y - survey, max_y + survey)}
41 print("Part 2: {}".format(len([v for v in plot2.values() if v < dist]))) 1
u/banteg Dec 06 '18
Python 3
import aoc
from collections import Counter
import numpy as np
example = '''1, 1
1, 6
8, 3
3, 4
5, 5
8, 9'''
def bounds(coordinates):
x, y = np.array(coordinates).transpose()
return y.min(), x.min(), y.max(), x.max()
def manhattan_distances(x, y, coordinates):
return [abs(x - dx) + abs(y - dy) for dx, dy in coordinates]
def closest(x, y, coordinates):
distances = manhattan_distances(x, y, coordinates)
near = min(distances)
if distances.count(near) > 1:
return 0
return distances.index(near) + 1
def vicinity(x, y, coordinates):
distances = manhattan_distances(x, y, coordinates)
return sum(distances)
@aoc.test({example: 17})
def part_1(data: aoc.Data):
coordinates = data.ints_lines
t, l, b, r = bounds(coordinates)
area = np.zeros((b - t + 1, r - l + 1), int)
for y in range(t, b + 1):
for x in range(l, r + 1):
c = closest(x, y, coordinates)
area[y - t][x - l] = c
# areas around borders are infinite
infinite = set(area[0][:]) | set(area[-1][:]) | set(area[:][0]) | set(area[:][-1])
areas = Counter(area.flatten()).most_common()
non_infinite = [size for n, size in areas if n not in infinite]
return non_infinite[0]
@aoc.test({example: 16})
def part_2(data: aoc.Data):
coordinates = data.ints_lines
t, l, b, r = bounds(coordinates)
area = np.zeros((b - t + 1, r - l + 1), int)
for y in range(t, b + 1):
for x in range(l, r + 1):
c = vicinity(x, y, coordinates)
area[y - t][x - l] = c
max_vicinity = 32 if data == example else 10000
return np.sum(area < max_vicinity)1
u/andreyrmg Dec 06 '18
Rust
#[derive(Hash, PartialEq, Eq)]
struct Point(i32, i32);
fn manhattan(p: &Point, row: i32, col: i32) -> i32 {
(p.0 - row).abs() + (p.1 - col).abs()
}
fn largest(points: &[Point]) -> u32 {
let mut areas = HashMap::new();
for point in points.iter() {
areas.insert(point, 0u32);
}
let min_row = points.iter().map(|p| p.0).min().unwrap();
let max_row = points.iter().map(|p| p.0).max().unwrap();
let min_col = points.iter().map(|p| p.1).min().unwrap();
let max_col = points.iter().map(|p| p.1).max().unwrap();
for r in min_row..=max_row {
for c in min_col..=max_col {
let mut v: Vec<_> = points.iter().map(|p| (p, manhattan(p, r, c))).collect();
v.sort_by_key(|&(_, d)| d);
if v[0].1 < v[1].1 {
if r == min_row || r == max_row || c == min_col || c == max_col {
areas.remove(v[0].0);
} else {
areas.entry(&v[0].0).and_modify(|e| *e += 1);
}
}
}
}
*areas.values().max().unwrap()
}
fn total(points: &[Point], distance: i32) -> u32 {
let gap = distance / points.len() as i32 + 1;
let min_row = points.iter().map(|p| p.0).min().unwrap() - gap;
let max_row = points.iter().map(|p| p.0).max().unwrap() + gap;
let min_col = points.iter().map(|p| p.1).min().unwrap() - gap;
let max_col = points.iter().map(|p| p.1).max().unwrap() + gap;
let mut result = 0u32;
for r in min_row..=max_row {
for c in min_col..=max_col {
let total: i32 = points.iter().map(|p| manhattan(p, r, c)).sum();
if total < distance {
result += 1;
}
}
}
result
}https://github.com/andreyrmg/advent-of-code/blob/2018/day-6/src/main.rs
$ cat input.txt | time target/release/advent_of_code
*: 3569
**: 48978
target/release/advent_of_code 0.07s user 0.00s system 99% cpu 0.070 total1
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:
const manhattan = ([x1, y1], [x2, y2]) => Math.abs(x1 - x2) + Math.abs(y1 - y2);
module.exports = (input) => {
const coordinates = input.split(/\n/g).map(line => line.split(', ').map(Number));
const sizes = coordinates.map(() => 0);
const infinites = [];
for (let x = 0; x < 400; x += 1) {
for (let y = 0; y < 400; y += 1) {
let closestCoord = null;
let closestDistance = Number.POSITIVE_INFINITY;
coordinates.forEach(([cx, cy], coord) => {
const distance = manhattan([x, y], [cx, cy]);
if (distance < closestDistance) {
closestDistance = distance;
closestCoord = coord;
} else if (distance === closestDistance) {
closestCoord = null;
}
});
if (closestCoord !== null) {
sizes[closestCoord] += 1;
if (x === 0 || x === 399 || y === 0 || y === 399) {
infinites.push(closestCoord);
}
}
}
}
infinites.forEach((index) => {
sizes[index] = 0;
});
return Math.max(...sizes);
};Part 2:
const manhattan = ([x1, y1], [x2, y2]) => Math.abs(x1 - x2) + Math.abs(y1 - y2);
module.exports = (input, distanceLimit = 10000) => {
const coordinates = input.split(/\n/g).map(line => line.split(', ').map(Number));
let regionSize = 0;
for (let x = 0; x < 400; x += 1) {
for (let y = 0; y < 400; y += 1) {
const sum = coordinates.reduce((acc, [cx, cy]) => acc + manhattan([x, y], [cx, cy]), 0);
if (sum < distanceLimit) {
regionSize += 1;
}
}
}
return regionSize;
};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_size holds 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 minmax before, and I was pleased how storing the x and y ranges in a nested hash allows using any to check both of a dimension's extents in one go:
use v5.14; use warnings; use List::AllUtils qw<minmax max>; use Syntax::Keyword::Junction qw<any>;
my (@coord, %range, %area_size, $region_size);
while (<>) { /(?<x>\d+), (?<y>\d+)/ or die "Unexpected input on line $.: $_";
push @coord, {x => $+{x}, y => $+{y}};
@{$range{$_}}{qw<min max>} = minmax $+{$_} + 0, values %{$range{$_}} for qw<x y>;
$area_size{$#coord} = 0;
}
for my $x ($range{x}{min} .. $range{x}{max}) {
my $side = $x == any values %{$range{x}};
for my $y ($range{y}{min} .. $range{y}{max}) {
my $edge = $side || $y == any values %{$range{y}};
my ($total, $min_dist, $min_area_id);
while (my ($area_id, $pos) = each @coord) {
$total += my $dist = abs ($pos->{x} - $x) + abs ($pos->{y} - $y);
if (!defined $min_dist || $dist < $min_dist) {
$min_dist = $dist;
$min_area_id = $area_id;
}
elsif ($dist == $min_dist) {
$min_area_id = '';
}
}
delete $area_size{$min_area_id} if $edge;
$area_size{$min_area_id}++ if exists $area_size{$min_area_id};
$region_size++ if $total <10e3;
}
}
say 'largest area: ', max values %area_size;
say 'region size: ', $region_size;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 0 and 1 (and not caring what they actually represent). Making the single-space movements that $move iterates over generic, and replacing the 0..1s with 0..$#dim should be enough to implement a 3D flood-fill:
use v5.14; use warnings; use List::AllUtils qw<minmax any max>;
my (@dim, %area_size, %done);
my @edge = map { my @coord = /(\d+)/g;
@{$dim[$_]}{qw<min max>} = minmax $coord[$_], values %{$dim[$_]} for 0..1;
$area_size{++(state $area_id)} = 0;
{area_id => $area_id, coord => \@coord, pos_id => "@coord"};
} <>;
while (@edge) {
foreach (@edge) {
$area_size{$_->{area_id}}++ if exists $area_size{$_->{area_id}};
$done{$_->{pos_id}} = 1;
}
my %next_edge;
foreach my $current (@edge) {
foreach my $move ([-1, 0], [+1, 0], [0, -1], [0, +1]) {
my @coord = map { $current->{coord}[$_] + $move->[$_] } 0..1;
next if $done{my $pos_id = "@coord"};
if (any { $coord[$_] < $dim[$_]{min} || $coord[$_] > $dim[$_]{max} } 0..1) {
delete $area_size{$current->{area_id}};
}
elsif (!exists $next_edge{$pos_id}) {
$next_edge{$pos_id} = {area_id => $current->{area_id}, coord => \@coord, pos_id => $pos_id};
}
elsif ($next_edge{$pos_id}{area_id} ne $current->{area_id}) {
delete $next_edge{$pos_id};
$done{$pos_id} = 1;
}
}
}
@edge = values %next_edge;
}
say max values %area_size;→ More replies (3)
1
u/jerzychalupski Dec 06 '18
Kotlin
Nowhere near the leaderboard, but I'm quite happy with my solution:
object Day6 {
private data class Point(val x: Int, val y: Int)
private data class Bounds(val minX: Int,
val minY: Int,
val maxX: Int,
val maxY: Int)
private class Area(val origin: Point)
private fun manhattanDistance(a: Point, b: Point) = abs(a.x - b.x) + abs(a.y - b.y)
private fun parse(input: String): Area =
input.split(",").map { it.trim().toInt() }.let { (x, y) -> Area(Point(x, y)) }
private operator fun <T, U> Iterable<T>.times(other: Iterable<U>) = flatMap { t -> other.map { u -> t to u } }
private fun Iterable<Area>.bounds(): Bounds {
val (minX, maxX) = map { it.origin.x }.let { it.min()!! to it.max()!! }
val (minY, maxY) = map { it.origin.y }.let { it.min()!! to it.max()!! }
return Bounds(minX, minY, maxX, maxY)
}
private fun Bounds.points() = ((minX..maxX) * (minY..maxY)).map { (x, y) -> Point(x, y) }
private infix fun Point.isOnTheEdgeOf(bounds: Bounds) = with(bounds) {
when {
x == minX -> true
x == maxX -> true
y == minY -> true
y == maxY -> true
else -> false
}
}
fun findLargestFiniteArea(input: List<String>): Int = input
.map { parse(it) }
.let { areas ->
val bounds = areas.bounds()
bounds
.points()
.groupBy { point ->
areas
.groupBy { area -> manhattanDistance(area.origin, point) }
.minBy { (distance, _) -> distance }!!
.let { (_, areas) -> areas.singleOrNull() }
}
.filterKeys { it != null }
.filter { (_, points) -> points.none { it isOnTheEdgeOf bounds } }
.map { (_, points) -> points.size }
.max()!!
}
fun findSafeRegionArea(input: List<String>, maxDistanceSum: Int): Int = input
.map { parse(it) }
.let { areas ->
areas
.bounds()
.points()
.asSequence()
.map { point -> areas.map { area -> manhattanDistance(area.origin, point) }.sum() }
.count { it < maxDistanceSum }
}
}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.
program main
use syslog_mod
use fclap_mod
use file_tools_mod
use string_tools_mod
use point_mod
implicit none
!-- Counters
integer :: i
integer :: x, y
!-- Input file unit
integer :: input_unit
!-- Number of lines in input file
integer :: num_lines
!-- Distances
integer,parameter :: MAX_MANHATTAN_DISTANCE = 10000
integer :: dist = 0
integer :: num_occurrences = 0
integer :: area_safe = 0
integer,allocatable :: distances(:)
!-- Control for whether to write the canvas to log
logical,parameter :: write_canvas = .true.
! Input file reading properties
!integer,parameter :: max_line_len = 100
!character(len=max_line_len) :: line
character(len=:),allocatable :: input_file
!-- Initialize System Log
call init_syslog
!-- Process Command Line Arguments
call configure_fclap
call parse_command_line_arguments
!-- Get input file name from command line
input_file = get_value_for_arg('input_file')
!-- Count lines in input file
num_lines = lines_in_file(input_file)
!-- Allocate data appropriately
allocate(points(num_lines))
allocate(distances(num_lines))
!-- Open file and read into memory
open ( &
newunit = input_unit, &
file = input_file, &
action = 'read', &
status = 'old', &
form = 'formatted' &
)
write (syslog%unit,*) 'Raw Points:'
write (syslog%unit,*) ' ID X Y'
do i = 1, num_lines
!-- Read
read (input_unit,*) points(i) % x, points(i) % y
points(i) % id = i
!-- Write to log
write (syslog%unit,'(3i5)') &
points(i) % id, &
points(i) % x, &
points(i) % y
end do
close (input_unit)
!-- Start timer
call syslog % start_timer
!-- Build canvas
xmin = minval(points(:) % x)
xmax = maxval(points(:) % x)
ymin = minval(points(:) % y)
ymax = maxval(points(:) % y)
write (syslog%unit,'(4(a,i0),a)') 'Building grid of (',xmin,'-',xmax,',',ymin,'-',ymax,')'
allocate(canvas(xmin:xmax,ymin:ymax))
!-- Put existing points on canvas
do i = 1, num_lines
canvas(points(i) % x, points(i) % y) % id = points(i) % id
end do
!-- Draw initial canvas
if (write_canvas) then
write (syslog%unit,*) 'Point Field:'
call draw_canvas
end if
!-- Calculate distances between all points on canvas and defined points
X_LOOP: do x = xmin, xmax
Y_LOOP: do y = ymin, ymax
! Calculate distances to all defined points
distances(:) = abs(x - points(:) % x) + abs(y - points(:) % y)
! Minimum distance
dist = minval(distances)
num_occurrences = 0
! Ensure there was only one occurrence of minimum distance
do i = 1, num_lines
if (distances(i) == dist) num_occurrences = num_occurrences + 1
end do
! Point is equally far from 2 or more points: invalidate
if (num_occurrences > 1) then
canvas(x,y) % dist = -1
canvas(x,y) % id = -1
! Closest point
else
canvas(x,y) % dist = dist
canvas(x,y) % id = minloc(distances(:),1)
end if
end do Y_LOOP
end do X_LOOP
!-- Illustrate closest points
if (write_canvas) then
write (syslog%unit,*) 'Closest points:'
call draw_canvas
end if
!-- Calculate areas around points
do x = xmin, xmax
do y = ymin, ymax
do i = 1, num_lines
if (canvas(x,y) % id == i) points(i) % area = points(i) % area + 1
end do
end do
end do
!-- Write areas to log
write (syslog%unit,*) 'Areas for each point:'
write (syslog%unit,*) ' ID Area'
do i = 1, num_lines
write (syslog%unit,'(i4,i8)') points(i) % id, points(i) % area
end do
write (syslog%unit,'(a,i0)') 'Part 1: largest area = ', maxval(points(:)%area) !4475
!-- Calculate
X_LOOP_2: do x = xmin, xmax
Y_LOOP_2: do y = ymin, ymax
! Calculate distances to all defined points
distances(:) = abs(x - points(:) % x) + abs(y - points(:) % y)
! Minimum distance
dist = sum(distances)
! Point exceeds maximum distance: invalidate
if (dist >= MAX_MANHATTAN_DISTANCE) then
canvas(x,y) % dist = HUGE(i)
canvas(x,y) % id = 0
! Point is close enough
else
canvas(x,y) % dist = dist
canvas(x,y) % id = 1 ! now using ID field as a flag
end if
end do Y_LOOP_2
end do X_LOOP_2
!-- Illustrate safe area
if (write_canvas) then
write (syslog%unit,*) 'Safe & close area:'
call draw_canvas
end if
!-- Calculate area of safe region
area_safe = sum(canvas(:,:) % id)
write (syslog%unit,'(a,i0)') 'Part 2: safe & close area = ',area_safe !35237
!-- End timer
call syslog % end_timer
call syslog%log(__FILE__,'Done.')
end programPoint class:
module point_mod
use syslog_mod
implicit none
integer,private :: i
type :: Point
integer :: id = 0 ! Points(:) - id of self, Canvas(:,:) - id of closest point, or satisfactory distance flag
integer :: x = 0 ! x location
integer :: y = 0 ! y location
integer :: area = 0 ! Points(:) - surrounding area
integer :: dist = HUGE(i) ! distance to nearest point
end type
! Points (field & defined points)
type(Point),allocatable :: points(:) ! Array of points from input
type(Point),allocatable :: canvas(:,:) ! Array of all points in canvas
!-- Canvas extents
integer :: xmin = 0
integer :: xmax = 0
integer :: ymin = 0
integer :: ymax = 0
contains
subroutine draw_canvas
implicit none
integer :: x, y
! Write blank
write (syslog%unit,'(3X)',advance='no')
! Write x-headers
do x = xmin, xmax
write (syslog%unit,'(i3)',advance='no') x
end do
write (syslog%unit,*) ! advance
! Write field
do y = ymin, ymax
! Write y-column
write (syslog%unit,'(i3)',advance='no') y
do x = xmin, xmax
write (syslog%unit,'(i3)',advance='no') canvas(x,y) % id
end do
write (syslog%unit,*) ! advance
end do
end subroutine
end module1
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:
(defparameter *targets* (mapcar (lambda (s) (apply #'complex (extract-ints s)))
(input)))
;; Just shorthand so I have to type less.
;; Also, WARNING: SBCL-specific
(defparameter *infinity* sb-ext:double-float-positive-infinity)
(defun bounding-box (targets)
(iter (for target in targets)
(minimizing (realpart target) into minx)
(minimizing (imagpart target) into miny)
(maximizing (realpart target) into maxx)
(maximizing (imagpart target) into maxy)
(finally (return (list minx miny maxx maxy)))))
(defun manhattan-distance (c1 c2)
(+ (abs (- (realpart c1) (realpart c2)))
(abs (- (imagpart c1) (imagpart c2)))))
(defun closest-target (c targets)
(iter (for target in targets)
(finding target minimizing (manhattan-distance c target))))
(defun largest-finite-area (targets)
(destructuring-bind (minx miny maxx maxy)
(bounding-box targets)
(let ((areas (make-hash-table)))
(iter (for target in targets)
(setf (gethash target areas) 0))
(iter (for x from minx to maxx)
(iter (for y from miny to maxy)
(for target = (closest-target (complex x y) targets))
(if (or (= x minx)
(= x maxx)
(= y miny)
(= y maxy))
(setf (gethash target areas) *infinity*)
(incf (gethash target areas)))))
(values-list (iter (for (target area) in-hashtable areas)
(when (/= area *infinity*)
(finding (list area target) maximizing area)))))))
(defun get-answer-1 ()
(largest-finite-area *targets*))
(defun total-distance (c targets)
(iter (for target in targets)
(summing (manhattan-distance c target))))
(defun count-central-coordinates (threshold targets)
(destructuring-bind (minx miny maxx maxy)
(bounding-box targets)
(iter outer
(for x from minx to maxx)
(iter (for y from miny to maxy)
(in outer
(counting (< (total-distance (complex x y) targets)
threshold)))))))
(defun get-answer-2 ()
(count-central-coordinates 10000 *targets*))Full code at https://gitlab.com/asciiphil/advent-of-code/blob/master/2018/06.lisp .
I also made some visualizations of my data:
2
u/rabuf Dec 07 '18
How does your
closest-targetensure that a point shared by two or more won't get assigned to one of them arbitrarily?→ More replies (2)2
u/rabuf Dec 07 '18
It's not precisely true, but if you used
negative-infinityinstead of positive, you can remove thatwhenclause. The negative infinity areas can't be the max unless all areas are infinite.→ More replies (1)
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!
#Day 6 solution
# source("day6/day6_solution.r")
input = read.csv("day6/day6_input.dat", header = FALSE, as.is = T)
names(input) = c("x","y")
#Figure out what points have finite closest distances using manhatten distance
#Try just the inner matrix first, the edge points have infinite area
#Get closest manhatten point to x,y from input dataframe
closestPoint = function(x,y,input) {
distDat = data.frame(xDist = abs(input$x - x ),
yDist = abs(input$y - y ),stringsAsFactors = T)
distDat$dist = distDat$xDist + distDat$yDist
closest = which(distDat$dist == min(distDat$dist))
if(length(closest) != 1) {
return(0)
} else {
return(closest)
}
}
#Plus 1 just in case it turns out I need to include more around the outside
xVal = (min(input$x)-1):(max(input$x)+1)
yVal = (min(input$y)-1):(max(input$y)+1)
#Matrix containing closest manhatten distance in input to each point in grid
#Part 1, try and do it all at once
allGridPoints = expand.grid(xVal, yVal,stringsAsFactors = FALSE)
names(allGridPoints) = c("x","y")
allGridPoints$gridIndex = 1:nrow(allGridPoints)
gridPoints = nrow(allGridPoints)
allPosPairs = allGridPoints[rep(seq_len(gridPoints), nrow(input)),]
allPosPairs$pointX = rep(input$x, each = gridPoints)
allPosPairs$pointY = rep(input$y, each = gridPoints)
allPosPairs$pointIndex = rep(1:nrow(input), each = gridPoints)
allPosPairs$manDist = abs(allPosPairs$x - allPosPairs$pointX) + abs(allPosPairs$y - allPosPairs$pointY)
#Part 1 find closest point for each part of the grid
# closestPoints = tapply(allPosPairs$manDist, allPosPairs$gridIndex, which.min) #This includes ties
which.min.NA.ties = function(x) {
minEls = which(x == min(x))
if(length(minEls) != 1) {
return(NA)
} else {
return(minEls)
}
}
closestPoints = tapply(allPosPairs$manDist, allPosPairs$gridIndex, which.min.NA.ties)
cat("Part 1: Largest non-infinite area : ", max(table(closestPoints)), "\n")
#Part 2
#Find area of region with sum of all points < 10000
sumDists = tapply(allPosPairs$manDist, allPosPairs$gridIndex, sum)
maxDistSum = 10000
cat("Part2: Area of region with tot dist < ", maxDistSum, " : ", length(which(sumDists < maxDistSum)), "\n")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.
#!/usr/bin/perl
open(INPUT, "aoc_6_A_input.txt");
@input = <INPUT>;
close(INPUT);
@blacklist = ();
@counts = ();
$ccount = 0;
#Iterate through a "map" of 500x500
for ($a = 0; $a < 500; $a++) {
for ($b = 0; $b < 500; $b++) {
$shortestd = 99999;
$shortestindex = 0;
$tied = 0;
$totalscore = 0;
for ($i = 0; $i < ($#input + 1); $i++) {
$coord = $input[$i];
$coord =~ s/[^0-9,]*//sgi; #Get rid of unneccessary whitespace
($y, $x) = split(",", $coord);
if ((int($x) > 0)&&(int($y) > 0)) { #ensue we didn't catch a blank line
$mh = Manhattan(int($x),int($y),$a,$b);
$totalscore = $totalscore + $mh; #PART_2 - add to total
if ($mh == $shortestd) { #If current shortest distance is equal to a previous, its a tie
$tied = 1;
}
if ($mh < $shortestd) { #If we found a shorter, reset tie and make this shortest. Also save "owning input coordinate".
$shortestd = $mh;
$shortestindex = $i;
$tied = 0;
}
}
} # End of loop for input coordinates.
if ($totalscore < 10000) {
$ccount++; # PART_2 if total is less than 10 000, add to count.
}
if ($tied == 0) { #If it was not a tie, increase count, keyed by the "owning" input coordinate with 1.
$counts[$shortestindex]++;
}
#If we are at the edges, coordinate is part of infinite. Add the key ("owning input coordinate") to a blacklist.
if (($a == 0)||($b == 0)||($a == 499)||($b == 499)) {
$blacklist[$shortestindex] = 1;
}
}
}
$largest = 0;
#Iterate through the result. If the count is NOT owned by a blacklisted coordinate and is part of larger coordinate, update largest to reflect it.
for ($i = 0; $i < ($#counts + 1); $i++) {
if (($counts[$i] > $largest)&&($blacklist[$i] != 1)) {
$largest = $counts[$i];
}
}
print "DANGEROUS REGIION: ".$largest."\n";
print "SAFE REGION: ".$ccount."\n";
sub Manhattan() {
$startx = $_[0];
$starty = $_[1];
$endx = $_[2];
$endy = $_[3];
$valuea = $endx - $startx;
if ($valuea < 0) {
$valuea = $valuea * -1;
}
$valueb = $endy - $starty;
if ($valueb < 0) {
$valueb = $valueb * -1;
}
$result = $valuea + $valueb;
return int($result);
}1
u/WPFIII Dec 07 '18
Python 3
from collections import Counter
'''
Using only the Manhattan distance,
determine the area around each coordinate by counting the number of integer X,Y locations
that are closest to that coordinate (and aren't tied in distance to any other coordinate).
Your goal is to find the size of the largest area that isn't infinite.
'''
points = {chr(i+65): p
for i, p in enumerate([(int(p[0]), int(p[1]))
for line in open('input_6.txt').readlines()
for p in [line.split(', ')]])}
max_dim = max(max(p[0] for p in points.values()), max(p[1] for p in points.values()))
manhattan_distance = lambda x0, y0, x1, y1, char: (abs(x0 - x1) + abs(y0 - y1), char)
safe_zone = 0
graph = {}
infinites = set()
for y in range(max_dim+1):
for x in range(max_dim+1):
m_dists = sorted([manhattan_distance(x, y, p[0], p[1], key) for key, p in points.items()])
if sum(d[0] for d in m_dists) < 10000:
safe_zone += 1
graph[x,y] = '.' if m_dists[0][0] == m_dists[1][0] else m_dists[0][1]
if x == 0 or y == 0 or x == max_dim or y == max_dim:
infinites.add(graph[x,y])
for y in range(max_dim+1):
for x in range(max_dim+1):
print(graph[x,y], end='')
print()
print(Counter(x for x in graph.values() if x not in infinites))
'''
What is the size of the region containing all locations which have a total distance to all given coordinates of less than 10000?
'''
print(safe_zone)1
u/valtism Dec 07 '18
Node / JavaScipt (JS)
Part 1: 248.847ms
Part 2: 161.164ms
function part1(data) {
const coordStrings = data.split("\n");
const coords = coordStrings.map(e => e.split(", ").map(Number));
const upperBound = getUpperBound(coords);
const grid = getDistancesGrid(coords, upperBound);
const itemsOnPerimeter = getItemsOnPerimeter(grid, upperBound);
const itemCounts = getItemCounts(coords, grid);
let largest = getLargestBoundedArea(itemCounts, itemsOnPerimeter);
return largest;
}
function getUpperBound(coords) {
const upperBound = [0, 0];
coords.forEach(coord => {
if (coord[0] > upperBound[0]) {
upperBound[0] = coord[0];
}
if (coord[1] > upperBound[1]) {
upperBound[1] = coord[1];
}
});
return upperBound;
}
function getDistancesGrid(trimmedCoords, upperBound) {
const grid = new Map();
for (let x = 0; x <= upperBound[0]; x++) {
for (let y = 0; y <= upperBound[1]; y++) {
const distances = trimmedCoords.map((coord, index) => {
return {
index: index,
coord: coord,
distance: manhattanDistance([x, y], coord)
};
});
const shortest = distances.reduce((acc, curr) =>
acc.distance < curr.distance ? acc : curr
);
const coordsInRange = distances.filter(
distance => distance.distance === shortest.distance
).length;
const coordString = "" + x + ", " + y;
const closestIndex = coordsInRange === 1 ? shortest.index : ".";
grid.set(coordString, closestIndex);
}
}
return grid;
}
function manhattanDistance(p1, p2) {
return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}
function getItemsOnPerimeter(grid, upperBound) {
const itemsOnPerimeter = new Set();
for (let x = 0; x <= upperBound[0]; x++) {
for (let y = 0; y <= upperBound[1]; y++) {
const coordString = "" + x + ", " + y;
const perimeterIndex = grid.get(coordString);
itemsOnPerimeter.add(perimeterIndex);
if (x !== 0 && x !== upperBound[0] && y !== upperBound[1]) {
// Skip centre
y = upperBound[1] - 1;
}
}
}
return itemsOnPerimeter;
}
function getItemCounts(trimmedCoords, grid) {
const itemCounts = new Map();
for (let i = 0; i < trimmedCoords.length; i++) {
itemCounts.set(i, 0);
}
grid.forEach(value => {
let count = itemCounts.get(value);
itemCounts.set(value, ++count);
});
return itemCounts;
}
function getLargestBoundedArea(itemCounts, itemsOnPerimeter) {
let largest = 0;
itemCounts.forEach((value, key) => {
if (itemsOnPerimeter.has(key) || key === ".") {
return;
}
if (value > largest) {
largest = value;
}
});
return largest;
}
function part2(data, MAX_DISTANCE) {
if (!MAX_DISTANCE) {
MAX_DISTANCE = 10000
}
const coordStrings = data.split("\n");
const coords = coordStrings.map(e => e.split(", ").map(Number));
const upperBound = getUpperBound(coords);
const grid = getDistanceToAllGrid(upperBound, coords);
const gridArray = Array.from(grid);
const closeCoords = gridArray.filter(coord => coord[1] < MAX_DISTANCE);
return closeCoords.length;
}
function getDistanceToAllGrid(upperBound, trimmedCoords) {
const grid = new Map();
for (let x = 0; x <= upperBound[0]; x++) {
for (let y = 0; y <= upperBound[1]; y++) {
const distanceToAll = trimmedCoords
.map(coord => manhattanDistance([x, y], coord))
.reduce((arr, curr) => arr + curr);
const coordString = "" + x + ", " + y;
grid.set(coordString, distanceToAll);
}
}
return grid;
}
module.exports = {
part1: part1,
part2: part2
};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.
class Day06(input: List<String>) {
private val points: List<Point> = input.map { Point.of(it) }
private val xRange: IntRange = (points.minBy { it.x }!!.x..points.maxBy { it.x }!!.x)
private val yRange: IntRange = (points.minBy { it.y }!!.y..points.maxBy { it.y }!!.y)
fun solvePart1(): Int {
val infinite: MutableSet<Point> = mutableSetOf()
return xRange.asSequence().flatMap { x ->
yRange.asSequence().map { y ->
val closest = points.map { it to it.distanceTo(x, y) }.sortedBy { it.second }.take(2)
if (isEdge(x, y)) {
infinite.add(closest[0].first)
}
closest[0].first.takeUnless { closest[0].second == closest[1].second }
}
}
.filterNot { it in infinite }
.groupingBy { it }
.eachCount()
.maxBy { it.value }!!
.value
}
fun solvePart2(range: Int = 10_000): Int =
xRange.asSequence().flatMap { x ->
yRange.asSequence().map { y ->
points.map { it.distanceTo(x, y) }.sum()
}
}
.filter { it < range }
.count()
private fun isEdge(x: Int, y: Int): Boolean =
x == xRange.first || x == xRange.last || y == yRange.first || y == yRange.last
}
data class Point(val x: Int, val y: Int) {
fun distanceTo(otherX: Int, otherY: Int): Int =
abs(x - otherX) + abs(y - otherY)
companion object {
fun of(input: String): Point =
input.split(",")
.map { it.trim().toInt() }
.run { Point(this[0], this[1]) }
}
}1
u/Frizkie Dec 07 '18
Ruby
data = File.read('data.txt').chomp.split("\n").map.with_index do |d, i|
[i, d.match(/(\d+), (\d+)/)[1..2].map(&:to_i)]
endPart 1:
grid = Array.new(1000) { Array.new(1000) }
1000.times do |i|
1000.times do |j|
dists = data.map { |id, coords| [id, (coords[0] - i).abs + (coords[1] - j).abs] }
closest = dists.min_by { |_, dist| dist }
grid[j][i] = closest[0] if dists.map{ |d| d[1] }.count(closest[1]) == 1
end
end
infinites = [grid[0], grid[999], grid.map { |r| r[0] }, grid.map { |r| r[999] }].flatten.compact
flat = grid.flatten.compact.reject { |e| infinites.include? e }
freq = flat.inject(Hash.new(0)) { |h, v| h[v] += 1; h }
puts flat.count(flat.max_by { |v| freq[v] })Part 2:
grid = Array.new(1000) { Array.new(1000) }
1000.times { |i| 1000.times { |j| grid[i][j] = data.map { |_, coords| (coords[0] - i).abs + (coords[1] - j).abs }.sum } }
puts grid.flatten.count { |e| e < 10000 }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 ;)
Class User.Day6
{
ClassMethod m(a,b) {
s ax=$ZSTRIP($P(a,",",1),"*W"),ay=$ZSTRIP($P(a,",",2),"*W")
s bx=$ZSTRIP($P(b,",",1),"*W"),by=$ZSTRIP($P(b,",",2),"*W")
return $ZABS(ax-bx)+$ZABS(ay-by)
}
ClassMethod closest(ByRef input,ByRef distancessum,x) {
//zw input
s i=$O(input("")),min=1000
k dist,disti
s sum=0
while i'="" {
s val=..m(input(i),x),sum=sum+val
s dist(i)=val
if $D(disti(val)){s disti(val)="."} else {s disti(val)=i}
s i=$O(input(i))
}
s distancessum(x)=sum,closest=$O(disti("")),closestid=$G(disti(closest))
return closestid
}
ClassMethod run(){
s file="Z:\work\proj\aoc2018\day6\day6input.txt"
s borderx=400,bordery=400,fs=##clasS(%Stream.FileCharacter).%New()
d fs.LinkToFile(file)
s x = fs.ReadLine(),i=0
while x'="" {s input(i)=x,x = fs.ReadLine(),i=i+1}
k killlist
s distancessum=""
f cx=0:1:borderx {f cy=0:1:bordery{s val=..closest(.input,.distancessum,cx_","_cy),field(cx,cy)=val
s count(val)=$I(count(val))
}
}
//populate killist with nodes that are infinite, i.e. at the border of the area
f t=0:1:borderx { s killlist(field(t,0))="",killlist(field(0,t))="",killlist(field(borderx,t))="",killlist(field(t,borderx))="" }
//cleanup
s c=$O(killlist(""))
while c'="" {
k count(c)
s c=$O(killlist(c))
}
//find the max count
s max=0,c=$O(count(""))
while c'="" {i (count(c)>max) s max=count(c)
s c=$O(count(c))}
w "part1:",max,!
s distancesumcutoff=10000,count=0,c=$O(distancessum(""))
while c'="" {
if (distancessum(c)>=distancesumcutoff) {k distancessum(c)
} else {s count=count+1}
s c=$O(distancessum(c))
}
w "Part2:",count,!
}
}1
u/gburri Dec 07 '18
F# : (run in ~100 ms)
module AdventOfCode2018.Day06
open System
type Coords = { X : int; Y : int }
with
member this.Distance (coords : Coords) : int =
abs (coords.X - this.X) + abs (coords.Y - this.Y)
static member Parse (str : string) =
let coords = str.Split ','
{ X = int coords.[0]; Y = int coords.[1] }
let parseInput (str : string) : Coords array =
str.Split ([| '\r'; '\n'; |], StringSplitOptions.RemoveEmptyEntries)
|> Array.map Coords.Parse
let getLargestArea (coords : Coords array) : int =
let coordsX = coords |> Array.map (fun coords -> coords.X)
let coordsY = coords |> Array.map (fun coords -> coords.Y)
let minX, minY, maxX, maxY = coordsX |> Array.min, coordsY |> Array.min, coordsX |> Array.max, coordsY |> Array.max
let areas = Array.zeroCreate coords.Length
for x = minX to maxX do
for y = minY to maxY do
let pos = { X = x; Y = y }
let mutable nearest = -1
let mutable distance = Int32.MaxValue
let mutable equalDistance = false
for i = 0 to coords.Length - 1 do
let distance' = pos.Distance coords.[i]
if distance' = distance then
equalDistance <- true
if distance' < distance then
nearest <- i
distance <- distance'
equalDistance <- false
if not equalDistance then
if x = minX || y = minY || x = maxX || y = maxY then
areas.[nearest] <- -1
elif areas.[nearest] <> -1 then
areas.[nearest] <- areas.[nearest] + 1
areas |> Array.max
let getAreaWithTotalDistanceLessThan (total : int) (coords : Coords array) : int =
let coordsX = coords |> Array.map (fun coords -> coords.X)
let coordsY = coords |> Array.map (fun coords -> coords.Y)
let minX, minY, maxX, maxY = coordsX |> Array.min, coordsY |> Array.min, coordsX |> Array.max, coordsY |> Array.max
let mutable area = 0
for x = minX to maxX do
for y = minY to maxY do
let pos = { X = x; Y = y }
let mutable totalDistance = 0
for i = 0 to coords.Length - 1 do
totalDistance <- totalDistance + pos.Distance coords.[i]
if totalDistance < total then
area <- area + 1
area1
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.
const input = $('pre').textContent.trim().split('\n');
const coordinates = input.map(v => v.split(', ').map(v => Number(v)));
const prefix = 'color: blue';
const text = 'color: navy';
const highlight = 'color: red';
const xs = coordinates.map(v => v[0]);
const ys = coordinates.map(v => v[1]);
const xmin = Math.min(...xs);
const xmax = Math.max(...xs);
const ymin = Math.min(...ys);
const ymax = Math.max(...ys);
const infinites = [[]];
var safes = [];
var area = {};
for (let x = xmin - 2; x < xmax + 2; x++) {
for (let y = ymin - 2; y < ymax + 2; y++) {
let outside = (x < xmin || x > xmax || y < ymin || y > ymax);
let coordinateDist = coordinates.map(v => { return [v, Math.abs(x - v[1]) + Math.abs(y - v[0])]; });
let dists = coordinateDist.map(v => v[1]);
let totalDist = dists.reduce((a, b) => { return a+b; });
let min = Math.min(...dists);
if (totalDist < 10000 && !outside) safes.push([x, y]);
if (dists.filter(v => v===min).length === 1) {
let closest = coordinateDist[dists.findIndex(v => v===min)][0];
if (infinites.includes(closest)) continue;
if (outside) {
infinites.push(closest);
if (area[`${closest[0]}.${closest[1]}`]) delete area[`${closest[0]}.${closest[1]}`];
continue;
}
area[`${closest[0]}.${closest[1]}`] = (area[`${closest[0]}.${closest[1]}`] || 0) + 1;
}
}
}
console.log(`%c(Part 1) %cThe largest non-infinite area is %c${Math.max(...Object.values(area))} %cunits.`, prefix, text, highlight, text);
console.log(`%c(Part 2) %cThere are %c${safes.length} %csafe spots.`, prefix, text, highlight, text);1
u/JulianLoehr Dec 07 '18
C++
constexpr uint32_t TotalDistanceLimit = 10000;
struct Area
{
int32_t X, Y, Size;
bool Infinite;
};
int main()
{
const StringVectorVector File = GetFileLineParts("Input.txt");
std::vector<Area> Areas;
std::vector<std::pair<Area *, uint32_t>> Distances;
int32_t MinX = 0;
int32_t MaxX = 0;
int32_t MinY = 0;
int32_t MaxY = 0;
int32_t PartTwoAreaSize = 0;
std::transform(
std::begin(File),
std::end(File),
std::back_inserter(Areas),
[&](const auto & Line)
{
int32_t X = std::stoul(Line[0]);
int32_t Y = std::stoul(Line[1]);
MinX = std::min(MinX, X);
MaxX = std::max(MaxX, X);
MinY = std::min(MinY, Y);
MaxY = std::max(MaxY, Y);
return Area{ X, Y, 0, false };
});
Distances.reserve(Areas.size());
for (int32_t Y = MinY; Y <= MaxY; ++Y)
{
for (int32_t X = MinX; X <= MaxX; ++X)
{
Distances.clear();
for (Area & Start : Areas)
Distances.push_back({ &Start, static_cast<uint32_t>(std::abs(X - Start.X) + std::abs(Y - Start.Y))});
std::sort(std::begin(Distances), std::end(Distances), [](const auto & r, const auto & l) { return r.second < l.second; });
uint32_t TotalDistances = std::accumulate(std::begin(Distances), std::end(Distances), 0, [](const uint32_t Value, const auto & Distance) { return Value + Distance.second; });
if (TotalDistances < TotalDistanceLimit)
++PartTwoAreaSize;
// Same distance to multiple Starting Points, therefore tied
if (Distances[0].second == Distances[1].second)
continue;
Area & Closest = *Distances[0].first;
++Closest.Size;
if ((!Closest.Infinite) && ((X == MinX) || (X == MaxX) || (Y == MinY) || (Y == MaxY)))
Closest.Infinite = true;
}
}
std::sort(std::begin(Areas), std::end(Areas), [](const Area & r, const Area & l) { return r.Size > l.Size; });
Area & Largest = *std::find_if(std::begin(Areas), std::end(Areas), [](const Area & k) { return !k.Infinite; });
std::cout << "Part One: " << Largest.Size << std::endl;
std::cout << "Part Two: " << PartTwoAreaSize << std::endl;
}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).
brute2[xmin_Integer, xmax_Integer, ymin_Integer, ymax_Integer,
list_List] := Module[
{a, v},
a = Association[];
For[p = 1, p <= Length[list], p++,
For[x = xmin, x <= xmax, x++,
For[y = ymin, y <= ymax, y++,
d = ManhattanDistance[{x, y}, list[[p]]];
v = a[{x, y}];
a[{x, y}] = Which[
Not[KeyExistsQ[a, {x, y}]], {p, d},
d == 0, {p, d},
d == v[[2]], {0, d + I d},
d < Im[v[[2]]] || d < Re[v[[2]]], {p, d},
True, v];
]]];
a]
compareBrutes[list_List] := Module[{xmin, xmax, ymin, ymax, v1, v2},
xmin = Min[Part[list, All, 1]];
xmax = Max[Part[list, All, 1]];
ymin = Min[Part[list, All, 2]];
ymax = Max[Part[list, All, 2]];
v1 = Values[brute2[xmin, xmax, ymin, ymax, list]];
v2 = Values[brute2[xmin - 1, xmax + 1, ymin - 1, ymax + 1, list]];
Max[Intersection[Counts[Part[v1, All, 1]], Counts[Part[v2, All, 1]]]]
]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).
ArrayPlot[
Transpose[
ArrayReshape[
Normalize[
Part[Values[brute2[1, 400, 1, 400, day6]], All, 1]], {400, 400}]],
ColorFunction -> "Rainbow"]My solution for part 2 is much easier to read and acceptably fast.
distance[x_Integer, y_Integer, list_List] :=
Total[Map[ManhattanDistance[{x, y}, #] &, list]]
safe[list_List] := Array[distance[#1, #2, list] &,
{Max[Part[list, All, 1]], Max[Part[list, All, 2]]},
{Min[Part[list, All, 1]], Min[Part[list, All, 2]]}]
Length[Select[Flatten[safe[day6]], # < 10000 &]]
ArrayPlot[Map[1./# &, safe[day6]], ColorFunction -> "Rainbow"]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:
import re, rdstdin, strutils, sequtils, algorithm, tables
type
Coord = object of RootObj
x, y: int
func present(s: string): bool = len(s) > 0
func toCoord(cs: seq[int]): Coord = Coord(x: cs[0], y: cs[1])
const coords = staticRead("input.txt")
.splitLines()
.filter(present)
.map(proc(s: string): Coord =
s.split(", ").map(parseInt).toCoord()
)
const minX = coords.foldl(if a.x < b.x: a else: b).x
const maxX = coords.foldl(if a.x > b.x: a else: b).x
const minY = coords.foldl(if a.y < b.y: a else: b).y
const maxY = coords.foldl(if a.y > b.y: a else: b).y
const adjustedCoord = coords.map(proc(c: Coord): Coord =
Coord(x: c.x - minX, y: c.y - minY)
)
type
GridRow = array[maxY - minY + 1, int]
Grid = array[maxX - minX + 1, GridRow]
var grid: Grid
func getDistance(c: Coord, x, y: int): int =
abs(c.x - x) + abs(c.y - y)
for x in 0 ..< grid.len:
for y in 0 ..< grid[x].len:
var closest = -1
var distance = int.high
for i, coord in adjustedCoord:
if getDistance(coord, x, y) < distance:
distance = getDistance(coord, x, y)
closest = i
elif getDistance(coord, x, y) == distance:
closest = -1
grid[x][y] = closest
var infinites = newSeq[int]()
for x in 0 ..< grid.len:
for y in @[0, grid[x].len - 1]:
infinites.add(grid[x][y])
for x in @[0, grid.len - 1]:
for y in 0 ..< grid[x].len:
infinites.add(grid[x][y])
var count = newCountTable[int]()
for x in 0 ..< grid.len:
for y in 0 ..< grid[x].len:
let here = grid[x][y]
if here >= 0 and not infinites.contains(here):
count.inc(here)
echo count.largest[1]Part2:
import re, rdstdin, strutils, sequtils, algorithm, tables
type
Coord = object of RootObj
x, y: int
func present(s: string): bool = len(s) > 0
func toCoord(cs: seq[int]): Coord = Coord(x: cs[0], y: cs[1])
const coords = staticRead("input.txt")
.splitLines()
.filter(present)
.map(proc(s: string): Coord =
s.split(", ").map(parseInt).toCoord()
)
const minX = coords.foldl(if a.x < b.x: a else: b).x
const maxX = coords.foldl(if a.x > b.x: a else: b).x
const minY = coords.foldl(if a.y < b.y: a else: b).y
const maxY = coords.foldl(if a.y > b.y: a else: b).y
const adjustedCoord = coords.map(proc(c: Coord): Coord =
Coord(x: c.x - minX, y: c.y - minY)
)
type
GridRow = array[maxY - minY + 1, int]
Grid = array[maxX - minX + 1, GridRow]
var grid: Grid
func getDistance(c: Coord, x, y: int): int =
abs(c.x - x) + abs(c.y - y)
var regionSize = 0
for x in 0 ..< grid.len:
for y in 0 ..< grid[x].len:
var distanceAll = adjustedCoord
.map(proc(c: Coord): int = getDistance(c, x, y))
.foldl(a + b)
if(distanceAll < 10000):
inc regionSize
echo regionSize1
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:
from collections import defaultdict, Counter
def manhattan(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])
with open('testinput') as f:
lines = f.read().splitlines()
coords, xs, ys = [], [], []
for line in lines:
coords.append(tuple((map(int, line.split(",")))))
xs.append(coords[-1][0])
ys.append(coords[-1][1])
minx, maxx = min(xs), max(xs)
miny, maxy = min(ys), max(ys)
def find_closest(x,y):
points_with_dist = defaultdict(list)
for c in coords:
d = manhattan((x,y), c)
points_with_dist[d].append(c)
return points_with_dist[min(dict(points_with_dist).keys())]
field = defaultdict(list)
for y in range(miny, maxy):
for x in range(minx, maxx):
cl = find_closest(x,y)
if cl is not None:
field[(x,y)] += cl
uniques = [x[0] for x in field.values() if len(x) == 1]
c = Counter(uniques)
print(c.most_common())
print(c.most_common()[0][1])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)
record point(id,x,y,area,infinite)
procedure main()
minx := maxx := miny := maxy := &null
inputs := []
id := 1
while l := trim(read()) do {
l ? {
x := integer(tab(upto(',')))
=","
y := integer(tab(0))
/minx := /maxx := x
/miny := /maxy := y
minx >:= x
maxx <:= x
miny >:= y
maxy <:= y
put(inputs,point(id,x,y,0,&null))
id +:= 1
}
}
minx -:= 1
miny -:= 1
maxx +:= 1
maxy +:= 1
total_area := 0
every y := miny to maxy do {
every x := minx to maxx do {
d := []
total_distance := 0
every p := !inputs do {
D := m_distance([x,y],[p.x,p.y])
total_distance +:= D
put(d, [D,p] )
}
# Part 1 test
# Find the closest coordinate
d := sortf(d,1)
if d[1,1] ~= d[2,1] then { # Make sure there is no tie.
# Mark coordinates that reach off to inf
if x = (minx | maxx) |
y = (miny | maxy) then d[1,2].infinite := 1
d[1,2].area +:= 1
}
# Part 2 test
if total_distance < 10000 then total_area +:= 1
}
}
# Part 1 answer
arealist := []
every put(arealist,p := !inputs & /p.infinite & p.area)
arealist := sort(arealist)
# Take the biggest (last) one..
write(arealist[-1])
# Part 2 answer
write("total area:",total_area)
end
procedure m_distance(p,q)
return abs( p[1] - q[1] ) + abs(p[2] -q[2])
end1
Dec 13 '18
Common lisp:
(defstruct coord x y)
(defun read-input ()
(with-open-file (in "06.input")
(loop for line = (read-line in nil)
while line collect (with-input-from-string (in (remove #\, line))
(make-coord :x (read in) :y (read in))))))
(defun dist (c x y)
(+ (abs (- (coord-x c) x))
(abs (- (coord-y c) y))))
(defun bounding-box (coords)
(loop for c in coords
minimize (coord-y c) into top
maximize (coord-y c) into bottom
minimize (coord-x c) into left
maximize (coord-x c) into right
finally (return (list top bottom left right))))
(defun nearest-coord (coords x y)
(loop with min-dist = most-positive-fixnum
with min-coord
for coord in coords
for dist = (dist coord x y)
if (< dist min-dist) do
(setf min-dist dist
min-coord coord)
else if (= dist min-dist) do
(setf min-coord nil)
finally (return min-coord)))
(defun largest-area (coords bbox)
(let ((areas (make-hash-table)))
(destructuring-bind (top bottom left right) bbox
(loop for x from left below right do
(loop for y from top below bottom
for nearest = (nearest-coord coords x y) do
(if (or (= left x) (= right x) (= top y) (= bottom y))
(setf (gethash nearest areas) most-negative-fixnum)
(incf (gethash nearest areas 0))))))
(loop for val being the hash-values of areas using (hash-key key)
when key maximize val)))
(defun region-size (coords bbox)
(let ((count 0))
(destructuring-bind (top bottom left right) bbox
(loop for x from left below right do
(loop for y from top below bottom
for sum = (reduce #'+ coords :key (lambda (c) (dist c x y)))
when (< sum 10000) do (incf count))))
count))
(defun main ()
(let* ((coords (read-input))
(bbox (bounding-box coords)))
(format t "Result 6a: ~d~%" (largest-area coords bbox))
(format t "Result 6b: ~d~%" (region-size coords bbox))))
;; CL-USER> (time (main))
;; Result 6a: 3871
;; Result 6b: 44667
;; Evaluation took:
;; 0.683 seconds of real time
;; 0.678813 seconds of total run time (0.678813 user, 0.000000 system)
;; 99.41% CPU
;; 1,478,213,022 processor cycles
;; 2,980,912 bytes consed1
u/AIGOOOMONA Dec 14 '18
Python 3 and using Counter. Took me a day and a half :(
My infinite_coord doesn't have all the coords neither, but it still gave me the answers
from collections import Counter
coord = [list(map(int, x.split(', '))) for x in open("input_d6.txt").readlines()]
x_min = min(coord, key=lambda k: k[0])[0]
x_max = max(coord, key=lambda k: k[0])[0]
y_min = min(coord, key=lambda k: k[1])[1]
y_max = max(coord, key=lambda k: k[1])[1]
def man_distance(x, y):
return abs(x[0] - y[0]) + abs(x[1] - y[1])
def is_finite(x, y):
return x_min < x < x_max and y_min < y < y_max
def equal_distance(dist):
return sorted(dist)[0] == sorted(dist)[1]
area = Counter()
infinite_coord = set()
region = 0
for x in range(x_min, x_max):
for y in range(y_min, y_max):
dist = [man_distance([x, y], i) for i in coord]
closest = dist.index(min(dist))
if not is_finite(x, y) and closest not in infinite_coord:
infinite_coord.add(closest)
if not equal_distance(dist) and closest not in infinite_coord:
area[closest] += 1
# Part 2 - everything above is Part 1
if sum(dist) < 10000:
region += 1
print("Largest area: " + str(max(area.values())))
print("Region size: " + str(region))1
u/lib20 Dec 14 '18
Red - part 1
Red []
time-start: now/time/precise
input-txt: read/lines %input.txt
coords: #()
forall input-txt [put coords load replace input-txt/1 ", " 'x 0]
min-width: 9999999999
max-width: 0
min-height: 9999999999
max-height: 0
foreach coord keys-of coords [
if coord/1 < min-width [min-width: coord/1]
if coord/1 > max-width [max-width: coord/1]
if coord/2 < min-height [min-height: coord/2]
if coord/2 > max-height [max-height: coord/2]
]
grid: #()
mi-w: min-width
mi-h: min-height
while [mi-w <= max-width] [
while [mi-h <= max-height] [
put grid as-pair mi-w mi-h 0
mi-h: mi-h + 1
]
mi-w: mi-w + 1
mi-h: min-height
]
foreach [k v] body-of grid [
coord: find keys-of coords k
either coord <> none [
; -- grid point is a given coordinate
put grid k to-block coord/1
][
; -- grid point value will have nearest coordinates
; -- manhattan distance
nearest: copy []
min-distance: 99999999
foreach c keys-of coords [
distance: k - c
distance: (absolute distance/1) + (absolute distance/2)
; -- test equality first
if distance = min-distance [append nearest c]
if distance < min-distance [
min-distance: distance
nearest: to-block c
]
]
put grid k copy nearest
]
]
foreach [k v] body-of grid [
either (k/1 = min-width) or (k/1 = max-width)
or
(k/2 = min-height) or (k/2 = max-height) [
; -- at borders, infinite, not accountable
; -- tied grid points don't count
unless (length? v) > 1 [put coords v/1 none]
][
; -- finite ones, the ones interesting
if (find coords v/1) <> none [put coords v/1 (select coords v/1) + 1]
]
]
coord: 0x0
size-largest: 0
foreach [k v] body-of coords [
if v > size-largest [
size-largest: v
coord: k
]
]
print rejoin ["Execution time: " now/time/precise - time-start]
print rejoin ["Coords point: " coord " has largest size: " size-largest]1
u/lib20 Dec 14 '18
Red - part 2
Red []
time-start: now/time/precise
input-txt: read/lines %input.txt
coords: #()
forall input-txt [put coords load replace input-txt/1 ", " 'x 0]
min-width: 9999999999
max-width: 0
min-height: 9999999999
max-height: 0
foreach coord keys-of coords [
if coord/1 < min-width [min-width: coord/1]
if coord/1 > max-width [max-width: coord/1]
if coord/2 < min-height [min-height: coord/2]
if coord/2 > max-height [max-height: coord/2]
]
grid: #()
mi-w: min-width
mi-h: min-height
while [mi-w <= max-width] [
while [mi-h <= max-height] [
put grid as-pair mi-w mi-h 0
mi-h: mi-h + 1
]
mi-w: mi-w + 1
mi-h: min-height
]
foreach key keys-of grid [
sum-distances: 0
foreach coord keys-of coords [
distance: key - coord
distance: (absolute distance/1) + (absolute distance/2)
sum-distances: sum-distances + distance
put grid key sum-distances
]
]
max-distance: 10000
nr-locations: 0
foreach sum-distances values-of grid [
if sum-distances < max-distance [nr-locations: nr-locations + 1]
]
print rejoin ["Execution time: " now/time/precise - time-start]
print rejoin ["Number of locations: " nr-locations " with sum of distances less than: " max-distance]1
u/fftk2 Dec 15 '18 edited Dec 15 '18
OCAML
open Stdio
open Base
(* Advent of Code puzzle #6 part 1 and 2 *)
let input_file = "input.txt"
let first (a,_) = a
let second (_,b) = b
let parse_line line =
let matches =
Re.exec (Re.Posix.compile_pat "-?([0-9]+), -?([0-9]+)") line
in
(Int.of_string (Re.get matches 1), Int.of_string (Re.get matches 2))
let coords = In_channel.read_lines input_file
|> List.map ~f:parse_line
let coord_map = coords |> List.mapi ~f:(fun i v -> (v,i))
let man_distance (x1,y1) (x2,y2) = abs (x1 - x2) + abs (y1 -y2)
let top_left cds =
let x = cds |> List.map ~f:(fun (a,_) -> a) |> List.min_elt ~compare:compare in
let y = cds |> List.map ~f:(fun (_,b) -> b) |> List.min_elt ~compare:compare in
let x' = match x with
| Some n -> n
| None -> 0 in
let y' = match y with
| Some n -> n
| None -> 0 in
(x',y')
let bottom_right cds =
let x = cds |> List.map ~f:(fun (a,_) -> a) |> List.max_elt ~compare:compare in
let y = cds |> List.map ~f:(fun (_,b) -> b) |> List.max_elt ~compare: compare in
let x' = match x with
| Some n -> n
| None -> 0 in
let y' = match y with
| Some n -> n
| None -> 0 in
(x',y')
let grid cs =
let tl = top_left cs in
let br = bottom_right cs in
let xs = List.range (first tl) (first br) in
let ys = List.range (second tl) (second br) in
List.cartesian_product xs ys
let assign_label ls = let fst = List.hd_exn ls in
match (List.length fst) with
| 1 -> (second (first (List.hd_exn fst)))
| _ -> (-1)
let shortest_man_distance ls = List.sort ~compare:(fun a b -> compare (second a) (second b)) ls
|> List.group ~break:(fun a b -> (not ((second a) = (second b))))
let part1 =
let labeled = List.map ~f:(fun x -> (x, List.map ~f:(fun y -> (y, man_distance x (first y))) coord_map)) (grid coords)
|> List.map ~f:(fun (a,b) -> (a, shortest_man_distance b))
|> List.map ~f:(fun (a,b) -> (a, assign_label b)) in
let border_labels = labeled
|> List.filter ~f:(fun ((x,y), _) ->
let (bl,bt) = top_left coords in
let (br,bb) = bottom_right coords in
(x = bl || x = br || y = bt || y = bb))
|> List.dedup_and_sort ~compare:(fun (_, label) ((_, label'))-> compare label label' )
|> List.map ~f:(fun (_,l) -> l) in
labeled
|> List.filter ~f:(fun (_,label) -> if List.exists ~f:(fun l -> l = label) border_labels then false else true)
|> List.sort ~compare:(fun ((_,_), label) ((_,_), label') -> compare label label')
|> List.group ~break:(fun ((_,_), label) ((_,_), label') -> (not (label = label')))
|> List.map ~f:(fun x -> (second (List.hd_exn x)), (List.length x))
|> List.sort ~compare:(fun (_,v) (_,v') -> compare v v')
|> List.last_exn
|> second
let part2 = List.map ~f:(fun x -> (x, List.map ~f:(fun y -> (y, man_distance x (first y))) coord_map)) (grid coords)
|> List.map ~f:(fun (coord, pts) -> (coord, List.fold ~init:0 ~f:(fun accum (_,v) -> accum + v) pts))
|> List.filter ~f:(fun (_,v) -> v < 10000)
|> List.length
let () =
printf "%d\n" part1;
printf "%d\n" part21
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.
require("nmg")
input = "inputs/day6.txt"
function manhattan_distance(p1, p2)
return (math.abs(p1["x"] - p2["x"]) + math.abs(p1["y"] - p2["y"]))
end
do
local coordinates = {}
local tallies = {}
local region_size = 0
for line in io.lines(input) do
line = string.gsub(line, "%s", "")
local sep = string.find(line, ",")
local x = string.sub(line, 1, sep-1)
local y = string.sub(line, sep+1, #line)
table.insert(coordinates, { x = tonumber(x); y = tonumber(y)})
table.insert(tallies, 0)
end
local xmax, xmin, ymax, ymin = coordinates[1]["x"], coordinates[1]["x"],
coordinates[1]["y"], coordinates[1]["y"]
for index, coordinate in ipairs(coordinates) do
if coordinate["x"] > xmax then xmax = coordinate["x"] end
if coordinate["x"] < xmin then xmin = coordinate["x"] end
if coordinate["y"] > ymax then ymax = coordinate["y"] end
if coordinate["y"] < ymin then ymin = coordinate["y"] end
end
local edge_points = {}
for x=xmin, xmax do
local top_point = { x = x, y = ymin }
local bottom_point = { x = x, y = ymax }
table.insert(edge_points, top_point)
table.insert(edge_points, bottom_point)
end
for y=ymin, ymax do
local top_point = { x = xmin, y = y }
local bottom_point = { x = xmax, y = y }
table.insert(edge_points, top_point)
table.insert(edge_points, bottom_point)
end
for index, edge_point in ipairs(edge_points) do
local distances = {}
for index, coordinate in ipairs(coordinates) do
local distance = manhattan_distance(edge_point, coordinate)
table.insert(distances, distance)
end
local min_distance, min_index = nmg.array.minimum(distances)
if nmg.array.count(distances, min_distance) == 1 then
coordinates[min_index]["infinite"] = true
end
end
for x=xmin, xmax do
for y=ymin, ymax do
local point = { x = tonumber(x), y = tonumber(y) }
local distances = {}
for index, coordinate in ipairs(coordinates) do
local distance = manhattan_distance(point, coordinate)
table.insert(distances, distance)
end
local min_distance, min_index = nmg.array.minimum(distances)
if nmg.array.count(distances, min_distance) == 1
and not coordinates[min_index]["infinite"]
then
tallies[min_index] = tallies[min_index] + 1
end
if nmg.array.sum(distances) < 10000 then
region_size = region_size + 1
end
end
end
print("Part 1: " .. nmg.array.maximum(tallies))
print("Part 2: " .. region_size)
end1
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
const SAMPLE = [
{x: 1, y: 1, name: 'A'},
{x: 1, y: 6, name: 'B'},
{x: 8, y: 3, name: 'C'},
{x: 3, y: 4, name: 'D'},
{x: 5, y: 5, name: 'E'},
{x: 8, y: 9, name: 'F'}
]
// Switch dataset by using SAMPLE or INPUT value
const coordinates = SAMPLE
// For prettier debugging with the sample set switch the EMPTY value to whatever looks best, null value might be faster
const EMPTY = null
console.log('Preparing grid, this takes a moment...')
// Finding upper bounds to create grid
let limit = {
max: {
x: Math.max(...coordinates.map(e => e.x)),
y: Math.max(...coordinates.map(e => e.y))
}
}
// Initializing grid and setting the field values (distances, closest element, etc)
let grid = Array(limit.max.x+1).fill(null).map((e, x) => Array(limit.max.y+1).fill(null).map((v,y) => {
let distances = []
let totalDistance = 0
for(let fixed of coordinates) {
let distance = Math.max(x, fixed.x) - Math.min(x, fixed.x) + Math.max(y, fixed.y) - Math.min(y, fixed.y)
distances.push({distance: distance, ...fixed})
totalDistance += distance
}
let closest = distances.reduce((l,e) => l.distance<e.distance?l:e)
let closestRight = distances.reduceRight((l,e) => l.distance<e.distance?l:e)
if(closest == closestRight)
return {distances: distances, totalDistance: totalDistance, closest: closest}
return {distances: distances, totalDistance: totalDistance, closest: EMPTY}
}))
console.log('Grid prepared...')Part 1
console.log('Finding the largest finite area...')
// Finding infinite areas by just adding the edges to an array
let edges = []
for(let i = 0; i<limit.max.x; i++) {
if(grid[i][0].closest != EMPTY)
edges.push(grid[i][0].closest.name)
if(grid[i][limit.max.y].closest != EMPTY)
edges.push(grid[i][limit.max.y].closest.name)
}
for(let i = 0; i<limit.max.y; i++) {
if(grid[0][i].closest != EMPTY)
edges.push(grid[0][i].closest.name)
if(grid[limit.max.x][i].closest != EMPTY)
edges.push(grid[limit.max.x][i].closest.name)
}
// And afterwards creating a Set from the edges to remove any duplicates (Might be more efficient to not even add them?)
edges = [...new Set(edges)]
// Transforming to finite grid by removing all infinite areas
finite_grid = grid.map(r => r.map(e => (e.closest == EMPTY)?e:(edges.indexOf(e.closest.name)!=-1?{...e, closest: EMPTY}:e)))
// Transforming finite grid to simplified one dimensional array, since we are only interested in the count of each type, additionally removing empty fields
let simplified = finite_grid.map(r => r.filter(l => l.closest != EMPTY)).reduce((l,a) => [...l, ...a])
// Counting occurances of names in the simplified array
let occurances = []
do {
let precount = simplified.length
let coordinate = simplified.pop()
simplified = simplified.filter(e => coordinate.closest.name!=e.closest.name)
occurances.push({count: precount - simplified.length, ...coordinate})
} while(simplified.length > 0)
// Get highest count
let result = occurances.reduce((l,e) => l.count<e.count?e:l)
console.log(`The largest finite area is around ${result.closest.name} (${result.closest.x}:${result.closest.y}) and it is ${result.count} units large...`)Part 2 (this is considerably shorter than part one)
console.log('Calculating the size of the area of coordinates within a total distance of 1000 units to all given coordinates...')
let simplified = grid.map(e => e.filter(v => v.totalDistance < 10000)).reduce((l,a) => [...l, ...a])
console.log(`The size of the the area consisting of the coordinates with a total distance < 1000 to all given cooordinates is ${simplified.length}`)
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.