### re: AoC Day 6: Chronal Coordinates VIEW POST

Here is a quick and dirty (and slow!) Python solution. I will later translate it to Golang, but I doubt it will become any faster since it already uses dictionaries (hashmaps). What slows it down is probably iterating through each coordinate individually.

``````with open('input') as f:

def calculate_distance(p1, p2):
x1, y1 = p1
x2, y2 = p2
return abs(x1 - x2) + abs(y1 - y2)

# Find the outer border:
P = set()  # Contains the points
outer_top, outer_bottom = -1, 1000
outer_left, outer_right = 1000, -1
for d in data:
y, x = map(int, d[:-1].split(','))
outer_top = max(outer_top, y)
outer_bottom = min(outer_bottom, y)
outer_left = min(outer_left, x)
outer_right = max(outer_right, x)

# Map coordinates to closest points and count:
count_P = {}  # Counts for each point number of assigned unique closest coordinates
canvas = {}  # Contains total distance to all points for coordinates
for y in range(outer_bottom, outer_top+1):
for x in range(outer_left, outer_right+1):
canvas[(x, y)] = 0
min_dist = float('inf')
for p in P:
dist = calculate_distance((x, y), p)
canvas[(x, y)] += dist
if dist == min_dist:
min_p = None
elif dist < min_dist:
min_p = p
min_dist = dist
if min_p:
count_P[min_p] = count_P.get(min_p, 0) + 1
if y in (outer_top, outer_bottom) \
or x in (outer_left, outer_right):
# Mark point as having infinite area to not count
count_P[min_p] = float('-inf')

# Part 1:
print('Part 1:')
print('Point with largest area: {}'.format(max(count_P, key=count_P.get)))
print('The area is: {}\n'.format(max(count_P.values())))

# Part 2:
region = []
for p, d in canvas.items():
if d < 10000:
region.append(p)
print('Part 2:')
print('Size of region: {}'.format(len(region)))
``````

Python using a kd-tree.

``````from collections import defaultdict
from collections import Counter
from itertools import product
import numpy as np
from scipy.spatial import KDTree

with open("input.txt") as f:
coords = [(int(x.split(",")[0]), int(x.split(",")[1])) for x in f]

xs, ys = [x for x, y in coords], [y for x, y in coords]

# Part 1

t = KDTree(coords)
d = defaultdict(int)
edge = set()
for i, j in product(range(max(xs)), range(max(ys))):
points, dists = t.query((i, j), k=2, p=1)
if i == 0 or j == 0 or i == max(xs)-1 or j == max(ys)-1:
if points[0] != points[1]:
d[(i,j)] = dists[0]

for p, area in Counter(d.values()).most_common():
if p not in edge:
print(area)
break

# Part 2
def dist(x, y):
return sum(abs(x-a)+abs(y-b) for a, b in coords)

print(sum(1 for i, j in product(range(max(xs)), range(max(ys))) if dist(i, j) < 10000))
``````

Here is the Golang code. Even though it uses the exact same algorithm, it runs surprisingly faster!

``````package main

import (
"bufio"
"fmt"
"math"
"os"
"strconv"
"strings"
)

type coord struct {
x int
y int
}

// and returns a slice of its lines.
func readLines(path string) ([]string, error) {
file, err := os.Open(path)
if err != nil {
return nil, err
}
defer file.Close()

var lines []string
scanner := bufio.NewScanner(file)
for scanner.Scan() {
lines = append(lines, scanner.Text())
}
return lines, scanner.Err()
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}

func max(a, b int) int {
if a < b {
return b
}
return a
}

func min(a, b int) int {
return max(-a, -b)
}

func calculateDistance(p1, p2 coord) int {
return abs(p1.x-p2.x) + abs(p1.y-p2.y)
}

func makeCoord(d string) coord {
c := strings.Split(d, ", ")
x, _ := strconv.Atoi(c[1])
y, _ := strconv.Atoi(c[0])
return coord{x: x, y: y}
}

func main() {
if err != nil {
panic(err)
}

// Find the outer border:
var outerTop, outerBottom, outerLeft, outerRight int
outerBottom = math.MaxInt32
outerLeft = math.MaxInt32
P := []coord{}
for _, d := range data {
c := makeCoord(d)
P = append(P, c)
outerTop = max(outerTop, c.y)
outerBottom = min(outerBottom, c.y)
outerLeft = min(outerLeft, c.x)
outerRight = max(outerRight, c.x)
}

// Map coordinates to closest points and count:
countP := map[coord]int{}
canvas := map[coord]int{}
for y := outerBottom; y <= outerTop; y++ {
for x := outerLeft; x <= outerRight; x++ {
c := coord{x: x, y: y}
canvas[c] = 0
minDist := math.MaxInt32
var minP coord
for _, p := range P {
dist := calculateDistance(c, p)
canvas[c] += dist
if dist == minDist {
minP = coord{x: math.MinInt32, y: math.MinInt32}
} else if dist < minDist {
minP = p
minDist = dist
}
}

if minP.x != math.MinInt32 && minP.y != math.MinInt32 {
if countP[minP] != math.MinInt32 {
countP[minP] = countP[minP] + 1
}
if y == outerTop || y == outerBottom || x == outerLeft || x == outerRight {
countP[minP] = math.MinInt32
}
}
}
}

// Part 1:
fmt.Println("Part 1:")
maxi := math.MinInt32
var maxiP coord
for k, v := range countP {
if v > maxi {
maxi = v
maxiP = k
}
}
fmt.Printf("Point with largest area: %v\n", maxiP)
fmt.Printf("The area is: %v\n", maxi)

// Part 2:
fmt.Println("\nPart 2:")
var region []coord
for p, d := range canvas {
if d < 10000 {
region = append(region, p)
}
}
fmt.Printf("Size of region: %v\n", len(region))
}
``````
code of conduct - report abuse