### AoC Day 6: Chronal Coordinates

#### Ryan Palo on December 06, 2018

Day 6 already! Around a quarter of the way through Advent of Code! For those of you that didn't like rectangular shapes on 2D grids a couple of... [Read Full] From my github:

I'm starting to see what's going on here. The elves of 1518 have somehow procured a future book of classic programming algorithms. Today there was a little distraction in problem description around infinite spaces and equidistant points, but it boils down to a pixel fill algorithm. If you ever worked on a classic 1980s-90s style paint program you'll recognise it.

First let's make some geometric primitives:

``````data class Pos(val x: Int, val y: Int)

data class Box(val x: IntRange, val y: IntRange)

enum class Dir { UP, DOWN, LEFT, RIGHT }

typealias Manhattan = Int
``````

``````fun Box.contains(p: Pos): Boolean = x.contains(p.x) && y.contains(p.y)

operator fun Pos.minus(other: Pos): Manhattan =
Math.abs(x - other.x) + Math.abs(y - other.y)

operator fun Pos.plus(dir: Dir) = when(dir) {
Dir.UP -> Pos(x, y-1)
Dir.DOWN -> Pos(x, y+1)
Dir.LEFT -> Pos(x-1, y)
Dir.RIGHT -> Pos(x+1, y)
}

fun around(p: Pos): Set<Pos> = enumValues<Dir>().map { dir -> p + dir }.toSet()
``````

We need a data model for our coordinates, and a parser. I know it's just two integers separated by a comma, but I hope by now you see what I mean by the One True Way of parsing text:

``````typealias CoordinateID = Int
data class Coordinate(val id: CoordinateID, val pos: Pos)

fun parse(input: String): List<Coordinate> {
val integer: Parser<Int> = INTEGER.map(String::toInt)
val pos: Parser<Pos> = sequence(integer.followedBy(string(", ")), integer, ::Pos)
val positions: List<Pos> = pos.sepBy(WHITESPACES).parse(input)

val ids: Sequence<Int> = generateSequence(0) { it + 1 }
return positions.asSequence().zip(ids).map { (pos, id) -> Coordinate(id, pos) }.toList()
}
``````

The last two lines make an infinite sequence of integers and zip it with the parsed coordinates so each coordinate gets a "name".

The problem talks about an infinite space, but the insight you need to solve it is that any area which reaches the edge of the "known" space is effectively infinite. The known space is the extent of the input coordinates in every direction, so let's compute that:

``````fun IntRange.extend(i: Int): IntRange = minOf(start, i) .. maxOf(endInclusive, i)

operator fun Box.plus(p: Pos): Box = Box(x.extend(p.x), y.extend(p.y))

fun spaceExtent(coords: Collection<Coordinate>): Box =
coords.map { c -> c.pos }.fold(Box.EMPTY, Box::plus)
``````

Breaking things down into tiny operations makes everything much easier to understand, means you're composing ideas at the same level of abstraction and frankly leaves fewer places for bugs to creep in.

We know the size of the space, now we need the area filling data model. A cell is either unclaimed, has a coordinate on it, is claimed by a single coordinate or is equidistant to two or more coordinates. It's a sum type!

``````sealed class Cell {
object Unclaimed: Cell()
data class Coordinate(val id: CoordinateID): Cell()
data class Claimed(val id: CoordinateID, val distance: Manhattan): Cell()
data class Equidistant(val distance: Manhattan): Cell()
}
``````

And we represent the space with a simple two-dimensional array of these:

``````data class Space(val box: Box) {
val cells: Array<Array<Cell>>

init {
val width = box.x.endInclusive - box.x.start + 1
val height = box.y.endInclusive - box.y.start + 1
cells = Array<Array<Cell>>(height) { Array<Cell>(width) { Cell.Unclaimed } }
}
``````

Now the fill algorithm. I've written this before, so I'm happy to say once it compiled this actually gave the correct result first time. The only change I had to make was to change it from stack-based recursion to a heap-based stack of pending operations to cope with the size of the main input data.

``````fun Space.fill(c: Coordinate) {
val stack = mutableSetOf<Pos>()

fun fill(p: Pos): Set<Pos> {
if (!box.contains(p)) return setOf()

val distance: Manhattan = p - c.pos
val cell = this[p]
val newCell = when (cell) {
is Cell.Unclaimed -> Cell.Claimed(c.id, distance)
is Cell.Claimed -> when {
cell.id == c.id -> cell
distance < cell.distance -> Cell.Claimed(c.id, distance)
distance == cell.distance -> Cell.Equidistant(distance)
else -> cell
}
is Cell.Equidistant -> when {
distance < cell.distance -> Cell.Claimed(c.id, distance)
else -> cell
}
is Cell.Coordinate -> cell
}
return if (newCell != cell) {
this[p] = newCell
around(p)
} else {
setOf()
}
}

while (!stack.isEmpty()) {
val p = stack.first()
stack.remove(p)
}
}
``````

Things to note:

1. Recursive functions are often best implemented with a helper and a "starter" method.
2. In the original version the inner `fill()` helper called itself recursively. Now it returns the next set of cells to fill, and the outer loop processes these.
3. The first check is that we've remained inside the bounding box. You could note here that the affected ID has an infinite area but I feel that's conflating the fill and area check parts of the problem. Merge them later if performance is an issue.
4. The `when` block looks at the current state of the cell and computes what to do. If the cell is unclaimed or closer to the current coordinate, we claim it. If it's the same distant it becomes `Equidistant`. Some of the cases leave it alone.
5. Finally if we've made a change to the cell, update the 2D array and continue to the surrounding set of cells.

## Part 1

The question in part 1 is to determine the largest finite area. We need a sum type!

``````sealed class Area {
object Infinite: Area()
data class Finite(val size: Int): Area()
}
``````

To calculate the area for a coordinate ID I took a very simple approach:

1. If any edge position claims the ID, the area will be infinite
2. Otherwise scan the whole space and count the claimed cells.
``````fun Space.areaForCoordinate(id: CoordinateID): Area {
val claimed: (Cell) -> Boolean = { cell -> cell.claimedBy(id) }

return if (topEdge().any(claimed) || bottomEdge().any(claimed) || leftEdge().any(claimed) || rightEdge().any(claimed))
Area.Infinite
else
Area.Finite(cells.map { row -> row.count(claimed) }.sum())
}
``````

This is not the most efficient form of the algorithm by any means. It will check the same cell many times during a pass. It runs in 1.5 seconds on my Thinkpad though.

## Part 2

Part 2 was a bit disappointing as it didn't really build on the first much. I refactored the `Space` class to be generic in its content, so I could make a space of manhattan distances. Filling it was easy:

``````fun Space<Manhattan>.fillDistances(coords: Collection<Coordinate>) {
box.y.forEach { y ->
box.x.forEach { x ->
val pos = Pos(x, y)
this[pos] = coords.map { c -> c.pos - pos }.sum()
}
}
}
``````

Then the size of the area under the threshold is `space.count { d -> d < max }`

I enjoyed this one a lot, which was pleasing after yesterday. Roll on the next...

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(",")), int(x.split(","))) 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 != points:
d[(i,j)] = dists

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)
y, _ := strconv.Atoi(c)
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))
}
``````

PHP solution

Part 1 took me a while to figure out how to get rid of coordinates that have infinite area. Part 2 was straight forward loop.

Btw using `array_filter` was ~3x slower than `foreach` loop. PHP ¯\(ツ)

Part 1

``````<?php

function calcDist(\$p1, \$p2, \$q1, \$q2) {
return abs(\$p1 - \$q1) + abs(\$p2 - \$q2);
}

\$top = INF;
\$right = 0;
\$bottom = 0;
\$left = INF;

foreach (\$array as \$value) {
\$top = (int)min(\$value, \$top);
\$right = (int)max(\$value, \$right);
\$bottom = (int)max(\$value, \$bottom);
\$left = (int)min(\$value, \$left);
}

\$distances = [];
for (\$i=\$top; \$i <= \$bottom; \$i++) {
for (\$j=\$left; \$j <= \$right; \$j++) {
\$index;
\$minDist = INF;
\$isUnique = true;
foreach (\$array as \$key => \$value) {
\$dist = calcDist(\$i, \$j, \$value, \$value);

if (\$dist == 0) {
\$index = \$key;
} else if (\$dist == \$minDist) {
\$isUnique = false;
\$index = '.';
} else if (\$dist < \$minDist) {
\$isUnique = true;
\$minDist = \$dist;
\$index = \$key;
}
}

\$distances[\$i][\$j] = \$index;
}
}

function getEdges(\$array) {
\$firstRow = array_shift(\$array);
\$lastRow = array_pop(\$array);

\$edges = array_filter(array_merge(\$firstRow, \$lastRow), function(\$val) {
return \$val != '.';
});

foreach (\$array as \$cols) {
\$first = array_shift(\$cols);
\$last = array_pop(\$cols);

\$first != '.' && \$edges[] = \$first;
\$last != '.' && \$edges[] = \$last;
}
return array_unique(\$edges);
}

\$edges = getEdges(\$distances);

\$max = 0;
\$len = count(\$array);
for (\$i=0; \$i < \$len; \$i++) {
if (in_array(\$i, \$edges)) {
continue;
}

\$res = 0;

foreach (\$distances as \$cols) {
foreach (\$cols as \$val) {
if (\$val != '.' && \$i == \$val) {
\$res++;
}
}
}

if (\$res > \$max) {
\$max = \$res;
}
}

echo \$max;
?>
``````

Part2

``````<?php

define("TOTAL_DIST", 10000);

function calcDist(\$p, \$q) {
return abs(\$p - \$q) + abs(\$p - \$q);
}

\$top = INF;
\$right = 0;
\$bottom = 0;
\$left = INF;

foreach (\$array as \$value) {
\$top = (int)min(\$value, \$top);
\$right = (int)max(\$value, \$right);
\$bottom = (int)max(\$value, \$bottom);
\$left = (int)min(\$value, \$left);
}

\$distances = 0;

for (\$i=\$top; \$i <= \$bottom; \$i++) {
for (\$j=\$left; \$j <= \$right; \$j++) {
\$dist = 0;
foreach (\$array as \$key => \$value) {
\$dist += calcDist([\$i, \$j], [(int)\$value, (int)\$value]);
}
if (\$dist < TOTAL_DIST) {
\$distances++;
}
}
}

echo \$distances;
?>
``````

``````<?php
\$file = fopen("input.txt", "r") or exit("Unable to open file");

while(!feof(\$file)) {
\$array[] = explode(", ", fgets(\$file));
}

fclose(\$file);

return array_filter(array_map(function(\$val) {
return array((int)\$val, (int)\$val);
}, \$array));
?>
``````

### Kotlin Solution

#### Part 1

This one wasn't too bad. I had a false start trying to flood-fill with multiple generators, and that got silly really quickly.

Then I realized I could just build a big array, chunk through item by item, remove any symbol on an edge, and then just count the places they reached.

``````fun String.parsePoint() = this.split(""", """).let { found ->
Point(found.toInt(), found.toInt())
}

fun Point.manhattanDistance(b: Point): Int =
(x - b.x).absoluteValue + (y - b.y).absoluteValue

val alpha = ('a'..'z') + ('A'..'Z')

val minX = input.minBy { (x, y) -> x }!!.x
val minY = input.minBy { (x, y) -> y }!!.y
val maxX = input.maxBy { (x, y) -> x }!!.x
val maxY = input.maxBy { (x, y) -> y }!!.y

val map = input.mapIndexed { i, point ->
point to alpha[i].toString()
}.toMap().toMutableMap()

val output =
(minY..maxY).map { y ->
(minX..maxX).map { x ->
map.toList().groupBy { (k, _) ->
(x to y).manhattanDistance(k)
}.minByKey()!!.value.let { closest ->
when {
closest.count() > 1 -> "."
else -> closest.first().second
}
}
}
}

return map.values.filter { v ->
v !in output.first()
&& v !in output.map { it.first() }
&& v !in output.last()
&& v !in output.map { it.last() }
}.map { v ->
output.flatten().count { it == v }
}.max()
}
``````

#### Part 2

This is where I got stuck a bit trying to optimize instead of just letting it finish this code's 30 second cycle.

I'm not happy I couldn't figure out the math, but I'll post some pictures I've generated from my output in penance.

``````fun answer2(input: List<Point>): Int? {
val dist = 10000

val minX = input.minBy { (x, y) -> x }!!.x
val minY = input.minBy { (x, y) -> y }!!.y
val maxX = input.maxBy { (x, y) -> x }!!.x
val maxY = input.maxBy { (x, y) -> y }!!.y

val ptc =
(maxX - dist..minX + dist).map { x ->
println("row \$x")
(maxY - dist..minY + dist).map { y ->
x to y
}
.filter { point -> input.sumBy(point::manhattanDistance) < dist }
}.fold(emptySet<Point>()) { a, b ->
a + b
}

return ptc.count()
}
``````

The promised images!

### Sample Data

Annnnnd, by posting these pictures, I see that the optimization for part 2 is to bound yourself by the points. 10000 is a bit of a red herring.

EDIT: 2018-12-06T11:01:40-08:00
Found some problems with my image processing and fixed them.

The worst for this day was understanding the instructions.
I just couldn't for the life of me understand what was being asked, until a friend helped me and then I was on my way.

Full disclosure: I was feeling pretty dumb, and almost gave up. I'm glad I didn't 🙏

``````import Fs from "fs"
import Path from "path"

.toString()
.trim()
.split("\n")

interface Coordinates {
x: number
y: number
}
type Distance = number
type Boundaries = [Coordinates, Coordinates]
type ID = string
type Pixel = null | ID

function getIdFromCoordinates(coords: Coordinates): ID {
return `\${coords.x}\${coords.y}`
}

function convertToCoordinates(line: string): Coordinates {
const [x, y] = line.split(", ")

return { x: parseInt(x, 10), y: parseInt(y, 10) }
}

function computeManhattanDistance(a: Coordinates, b: Coordinates): Distance {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y)
}

function computeBoardBoundaries(coords: Array<Coordinates>): Boundaries {
return coords.reduce(
(boundaries: Boundaries, coordinate: Coordinates, index: number) => {
let [topLeftBoundary, bottomRightBoundary] = boundaries

if (index === 0) {
return [{ ...coordinate }, { ...coordinate }] as Boundaries
}

if (coordinate.x < topLeftBoundary.x) {
topLeftBoundary.x = coordinate.x
}
if (coordinate.y < topLeftBoundary.y) {
topLeftBoundary.y = coordinate.y
}

if (coordinate.x > bottomRightBoundary.x) {
bottomRightBoundary.x = coordinate.x
}
if (coordinate.y > bottomRightBoundary.y) {
bottomRightBoundary.y = coordinate.y
}

return [topLeftBoundary, bottomRightBoundary] as Boundaries
},
[
// first element is top left boundary
{ x: 0, y: 0 },
// last element is bottom right boundary
{ x: 0, y: 0 },
] as Boundaries
)
}

function doesBeaconHaveFiniteArea(
beacon: Coordinates,
beacons: Array<Coordinates>
): Boolean {
let hasTopLeft = false
let hasTopRight = false
let hasBottomLeft = false
let hasBottomRight = false

for (let i = 0; i < beacons.length; i++) {
const comparedBeacon = beacons[i]

if (
hasTopRight === false &&
comparedBeacon.x >= beacon.x &&
comparedBeacon.y > beacon.y
) {
hasTopRight = true
}

if (
hasBottomRight === false &&
comparedBeacon.x >= beacon.x &&
comparedBeacon.y < beacon.y
) {
hasBottomRight = true
}

if (
hasBottomLeft === false &&
comparedBeacon.x <= beacon.x &&
comparedBeacon.y < beacon.y
) {
hasBottomLeft = true
}

if (
hasTopLeft === false &&
comparedBeacon.x <= beacon.x &&
comparedBeacon.y > beacon.y
) {
hasTopLeft = true
}
}

return hasTopLeft && hasTopRight && hasBottomLeft && hasBottomRight
}

const coordinates = input.map(convertToCoordinates)
const beaconsWithFiniteArea: Array<Coordinates> = coordinates.reduce(
(beacons, beacon) => {
const hasFiniteArea = doesBeaconHaveFiniteArea(
beacon,
coordinates.filter(ref => ref.x !== beacon.x || ref.y !== beacon.y)
)

if (hasFiniteArea) {
return [...beacons, beacon]
}

return beacons
},
[] as Array<Coordinates>
)

const boundaries: Boundaries = computeBoardBoundaries(coordinates)
console.log(JSON.stringify(boundaries))

function computePixelForCoords(
coordinates: Coordinates,
coordinatesList: Array<Coordinates>
): Pixel {
const distances = coordinatesList
.map(beacon => {
return {
id: getIdFromCoordinates(beacon),
distance: computeManhattanDistance(coordinates, beacon),
}
})
.sort((a, b) => a.distance - b.distance)

if (distances.distance === distances.distance) {
return null
}

return distances.id
}

const canvas: Array<Array<Pixel>> = []
for (let x = boundaries.x; x <= boundaries.x; x++) {
for (let y = boundaries.y; y <= boundaries.y; y++) {
if (canvas[x] === undefined) {
canvas[x] = []
}

canvas[x][y] = computePixelForCoords({ x, y }, coordinates)
}
}

const sorted = beaconsWithFiniteArea
.map(beacon => {
let count = 0
let id = getIdFromCoordinates(beacon)

for (let x = boundaries.x; x <= boundaries.x; x++) {
for (let y = boundaries.y; y <= boundaries.y; y++) {
if (canvas[x][y] === id) {
count++
}
}
}
return count
})
.sort((a, b) => b - a)

// 01
console.log(sorted)
``````

Part2:

``````import Fs from "fs"
import Path from "path"

.toString()
.trim()
.split("\n")

interface Coordinates {
x: number
y: number
}
type Distance = number
type Boundaries = [Coordinates, Coordinates]

function convertToCoordinates(line: string): Coordinates {
const [x, y] = line.split(", ")

return { x: parseInt(x, 10), y: parseInt(y, 10) }
}

function computeManhattanDistance(a: Coordinates, b: Coordinates): Distance {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y)
}

function computeBoardBoundaries(coords: Array<Coordinates>): Boundaries {
return coords.reduce(
(boundaries: Boundaries, coordinate: Coordinates, index: number) => {
let [topLeftBoundary, bottomRightBoundary] = boundaries

if (index === 0) {
return [{ ...coordinate }, { ...coordinate }] as Boundaries
}

if (coordinate.x < topLeftBoundary.x) {
topLeftBoundary.x = coordinate.x
}
if (coordinate.y < topLeftBoundary.y) {
topLeftBoundary.y = coordinate.y
}

if (coordinate.x > bottomRightBoundary.x) {
bottomRightBoundary.x = coordinate.x
}
if (coordinate.y > bottomRightBoundary.y) {
bottomRightBoundary.y = coordinate.y
}

return [topLeftBoundary, bottomRightBoundary] as Boundaries
},
[
// first element is top left boundary
{ x: 0, y: 0 },
// last element is bottom right boundary
{ x: 0, y: 0 },
] as Boundaries
)
}

const coordinates = input.map(convertToCoordinates)
const boundaries: Boundaries = computeBoardBoundaries(coordinates)
const MAX_DISTANCE = 10000

let closestSum: number = -Infinity
let position: Coordinates = { x: Infinity, y: Infinity }
let numberOfPixelsForRegion: number = 0
for (let x = boundaries.x; x <= boundaries.x; x++) {
for (let y = boundaries.y; y <= boundaries.y; y++) {
const beacon = { x, y }
const sum = coordinates.reduce((total, point) => {
}, 0)

if (sum < MAX_DISTANCE) {
numberOfPixelsForRegion++

if (sum > closestSum) {
closestSum = sum
position = { x, y }
}
}
}
}

console.log(
`Chosen position \${JSON.stringify(
position
)} with sum \${closestSum} and region size: \${numberOfPixelsForRegion}`
)

``````

Oh no, I've been affected by the bug in Day 6. My solution was correct, but the adventofcode.com didn't recognise it. I tested some of the solutions posted here and they gave the same output as mine. I'm not sure how to progress to Part 2, so only posting Part 1:

``````#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ max };

my %locations;
my \$location = 'A';
my (\$X, \$Y) = (0, 0);
while (<>) {
chomp;
my (\$x, \$y) = split /,\s+/;
\$locations{\$location++} = [ \$x, \$y ];
\$X = \$x if \$x > \$X;
\$Y = \$y if \$y > \$Y;
}

my @nearest;
for my \$x (0 .. \$X + 1) {
for my \$y (0 .. \$Y + 1) {
my @n = ( abs(\$locations{A} - \$x) + abs(\$locations{A} - \$y),
'A' );
for my \$location (keys %locations) {
next if 'A' eq \$location;

my \$distance = abs(\$locations{\$location} - \$x)
+ abs(\$locations{\$location} - \$y);
if (\$distance <= \$n) {
@n = (\$distance) if \$distance < \$n;
push @n, \$location;
}
}
\$nearest[\$x][\$y] = \@n;
}
}

my %freq;
++\$freq{ \$_-> } for grep @\$_ == 2, map @\$_, @nearest;
delete @freq{ map \$_->, grep @\$_ == 2, \$nearest,
\$nearest[-1],
map(\$_->, @nearest),
map(\$_->[-1], @nearest) };
say max(0, values %freq);
``````

Oh no! That’s a bummer 😐

I want to come back to this exercise after Advent is over and refactor, because I think I could make my solution really nice now, but for right now, I'm delirious and need sleep. Here's what I've got. It's not pretty, but it gets stars and that's all that matters.

``````/// Day 6: Chronal Coordinates
///
/// Calculate Manhattan Distances on the X-Y plane

use std::collections::HashMap;
use std::collections::HashSet;

/// A grid of X-Y coordinates and unclaimed points
///
/// coords is a vector of Coordinates.  Their index is their "ID number"
/// points is a vector of unclaimed points.  Their value is the ID of the
///     closest Coordinate
struct Grid {
coords: Vec<Coordinate>,
points: Vec<Option<usize>>,
width: usize,
height: usize,
}

impl Grid {
pub fn new() -> Self {
Self { coords: vec![], points: vec![], width: 0, height: 0 }
}

/// Loads a grid from text, building each coordinate and calculating
/// most of part 1
pub fn from_text(text: &str) -> Self {
let mut grid = Grid::new();
for line in text.lines() {
let mut coord = Coordinate::from_str(line);
coord.id = grid.coords.len();
grid.coords.push(coord);
}
let (height, width) = grid.bounds();
grid.height = height;
grid.width = width;
grid.points.resize(width*height, None);
grid.calculate_closest_coords();
grid
}

/// Calculates the width and height of the grid
fn bounds(&self) -> (usize, usize) {
let max_row = self.coords.iter().map(|coord| coord.y).max().unwrap();
let max_col = self.coords.iter().map(|coord| coord.x).max().unwrap();
(max_row, max_col)
}

/// For each point on the Grid, calculates the closest Coordinate to
/// that point
///
/// Ties count as nothing!
fn calculate_closest_coords(&mut self) {
for y in 0..self.height {
for x in 0..self.width {
let mut min_dist = self.width + self.height;
for coord in self.coords.iter() {
let dist = coord.manhattan_distance_to(x + 1, y + 1);
if dist < min_dist {
min_dist = dist;
self.points[x + y*self.width] = Some(coord.id);
} else if dist == min_dist {
// It's a tie.  No one gets it
self.points[x + y*self.width] = None;
}
}
}
}
}

/// Checks whether or not a coordinate is internal
///
/// Internal coordinates are completely fenced in by other
/// coordinates.  No infinite boundaries (i.e. not touching the edges)
///
/// This could probably be batched in the contructor rather than done in a loop.
fn is_internal(&self, id: usize) -> bool {
let mut external: HashSet<usize> = HashSet::new();
// Left and right side
for y in 0..self.height {
let left = self.points[0 + y*self.width];
let right = self.points[y*self.width + self.width - 1];
if left.is_some() { external.insert(left.unwrap()); }
if right.is_some() { external.insert(right.unwrap()); }
}

// Top and bottom
for x in 0..self.width {
let top = self.points[x];
let bottom = self.points[x + (self.height - 1)*self.width];
if top.is_some() { external.insert(top.unwrap()); }
if bottom.is_some() { external.insert(bottom.unwrap()); }
}

!external.contains(&id)
}

/// Calculates the area of the internal coordinate that claims the most area
pub fn most_claimed_area(&self) -> usize {
let mut counter: HashMap<usize, usize> = HashMap::new();
for point in self.points.iter() {
if point.is_some() {
*counter.entry(point.unwrap()).or_insert(0) += 1;
}
}
*counter.iter()
.filter(|(id, _count)| self.is_internal(**id))
.map(|(_id, count)| count)
.max().unwrap()
}

/// Counts how many points have a total manhattan distance less than
/// a threshold when checked against all Coordinates
pub fn squares_closer_than(&self, dist: usize) -> usize {
let mut distances: Vec<usize> = vec![];
for y in 0..self.height {
for x in 0..self.width {
let total = self.coords.iter()
.fold(0, |acc, coord| acc + coord.manhattan_distance_to(x, y));
if total < dist {
distances.push(total);
}
}
}
distances.iter().count()
}
}

/// An X-Y coordinate on a Grid
struct Coordinate {
id: usize,
x: usize,
y: usize,
}

impl Coordinate {
pub fn new(x: usize, y: usize) -> Self {
Self { id: 0, x, y }
}

/// Loads data from a line of text, essentially a CSV line
pub fn from_str(text: &str) -> Self {
let mut parts = text.split(',');
let x = parts.next().unwrap().trim().parse().unwrap();
let y = parts.next().unwrap().trim().parse().unwrap();
Self { id: 0, x, y }
}

/// Calculate manhattan distance from here to any X-Y pair
pub fn manhattan_distance_to(&self, x: usize, y: usize) -> usize {
let x1 = self.x as i32;
let x2 = x as i32;
let y1 = self.y as i32;
let y2 = y as i32;
((x2 - x1).abs() + (y2 - y1).abs()) as usize
}
}

/// Part 1
pub fn largest_finite_area(text: &str) -> usize {
let grid = Grid::from_text(text);
grid.most_claimed_area()
}

/// Part 2
pub fn squares_closer_than(text: &str, dist: usize) -> usize {
let grid = Grid::from_text(text);
grid.squares_closer_than(dist)
}
``````

``````from collections import defaultdict

from operator import itemgetter

def main():
part_one(coordinates)
part_two(coordinates)

coordinates = []
with open('input.txt', 'r') as input_file:
index = 1
for line in input_file:
cor_pair = [int(cor) for cor in line.strip().split(',')]
cor_pair.append(index)
coordinates.append(cor_pair)
index += 1
return coordinates

def part_one(coordinates):
min_x = min([cor_pair for cor_pair in coordinates])
max_x = max([cor_pair for cor_pair in coordinates]) + 1
min_y = min([cor_pair for cor_pair in coordinates])
max_y = max([cor_pair for cor_pair in coordinates]) + 1

area_dict = defaultdict(int)

for i in range(min_y, max_y):
for j in range(min_x, max_x):
h_distances = [[hamming_distance([i, j], cor_pair), cor_pair] for cor_pair in coordinates]
min_h_distance = min(h_distances, key=itemgetter(0))
count_min_h_distance = sum(1 for item in h_distances if item == min_h_distance)
if count_min_h_distance == 1:
area_dict[min_h_distance] += 1
if i in (min_y, max_y - 1) or j in (min_x, max_x - 1):
area_dict[min_h_distance] = float('-inf')

print max(area_dict.iteritems(), key=itemgetter(1))

def part_two(coordinates):
min_x = min([cor_pair for cor_pair in coordinates])
max_x = max([cor_pair for cor_pair in coordinates]) + 1
min_y = min([cor_pair for cor_pair in coordinates])
max_y = max([cor_pair for cor_pair in coordinates]) + 1

total_distance_dict = defaultdict(int)

for i in range(min_y, max_y):
for j in range(min_x, max_x):
total_distance_dict[(i, j)] = sum([hamming_distance([i, j], cor_pair) for cor_pair in coordinates])

region_size = 0

for _, value in total_distance_dict.iteritems():
if value < 10000:
region_size += 1

print region_size

def hamming_distance(a, b):
return abs(a - b) + abs(a - b)

if __name__ == '__main__':
main()
``````

Better late than never...

Had no time yesterday to write the solution down, but here it is.

Most of the time I struggled to understand how to filter "infinity areas". After I solved this it was a pretty easy.

This is my least favorite code I may have ever written. Need to refactor.

Part 1

``````from collections import Counter

with open('input.txt', 'r') as f:
coords = []
max_x = 0
max_y = 0
for line in f:
line = [int(i) for i in line.strip().split(', ')]
if line > max_x: max_x = line
if line > max_y: max_y = line
coords.append((line, line,))

matrix = [[(0, 0) for i in range(max_x + 2)] for n in range(max_y + 2)]
for idx, (x, y) in enumerate(coords):
matrix[x][y] = (idx+1, 0,)
for r_idx, row in enumerate(matrix):
for c_idx, col in enumerate(row):
dist = abs(x - r_idx) + abs(y - c_idx)
if col == 0 or dist < col:
matrix[r_idx][c_idx] = (idx+1, dist,)
elif dist == col and col != idx+1:
matrix[r_idx][c_idx] = (None, dist,)

matrix = [[i for i in sublist] for sublist in matrix]
flipped_matrix = matrix[::-1]
to_filter = set(matrix + matrix[-1] + flipped_matrix + flipped_matrix[-1])
list_matrix = []

for row in matrix:
for col in row:
if col not in to_filter:
list_matrix.append(col)

print(Counter(list_matrix).most_common(1))
``````

part 2

``````from collections import Counter

with open('input.txt', 'r') as f:
coords = []
max_x = 0
max_y = 0
for line in f:
line = [int(i) for i in line.strip().split(', ')]
if line > max_x: max_x = line
if line > max_y: max_y = line
coords.append((line, line,))

n_regions = 0
matrix = [[(0, 0) for i in range(max_x + 2)] for n in range(max_y + 2)]
for r_idx, row in enumerate(matrix):
for c_idx, col in enumerate(row):
total_dist = 0
for idx, (x, y) in enumerate(coords):
dist = abs(x - r_idx) + abs(y - c_idx)
total_dist += dist
if total_dist < 10000:
n_regions += 1

print(n_regions)
``````

I doubt this is the most performant solution, but it gets the job done for smaller sets of input data.

``````-- Set up some stuff

local inf = math.abs(1/0)

local point = {
__tostring = function(self)
return string.format("(%03i, %03i)", self, self)
end
}

-- First of all, read in all the points.
-- This is just some boring I/O, and integer parsing.
local points = {}
for line in io.stdin:lines() do
local point = setmetatable({}, point)
for coordinate in line:gmatch('%d+') do
table.insert(point, tonumber(coordinate))
end
table.insert(points, point)
end

-- Find smallest axis-aligned rectangle (R) that contains all points

local min_x, max_x, min_y, max_y = inf, 0, inf, 0
for _,point in ipairs(points) do
local x, y = point, point
min_x = math.min(x, min_x)
min_y = math.min(y, min_y)
max_x = math.max(x, max_x)
max_y = math.max(y, max_y)
end

-- Helper function that finds the nearest input point given two coordinates.

local function nearest(x, y)
local dist, point = inf
local mid = false
for _,p in ipairs(points) do
local d = (math.abs(x-p) + math.abs(y-p))
if d == dist then
mid = true
elseif d < dist then
mid = false
dist = d
point = p
end
end
return (not mid) and point
end

-- Mapping points to their respective counts:
-- Iterate all points in R, find the nearest input point and add 1 to its count.

local counts = {}
for y = min_y, max_y do
for x = min_x, max_x do
local nearest = nearest(x, y)
if nearest then
if y==min_y or y==max_y or x==max_x or x==min_x then
counts[nearest] = -inf
else
counts[nearest] = (counts[nearest] or 0) + 1
end
end
end
end

-- Iterate all point-count pairs and remember the highest count; this is our answer.

local highest = 0
for point, count in pairs(counts) do
print(point, count)
highest = math.max(count, highest)
end

print(highest)
``````

Here we go, this is my solution in Elixir.

The idea for part one is to first determine the maximum field, based on the min/max values of the x and y coordinates. Then, for each position in the field, determine the distance to each of the input coordinates, keeping track of the coordinate that is the closest to the position in the field. Once this information is calculated, we can determine the size of the largest area within the field.

Part two largely follows the same logic, but takes the sum of a position in the field to all input coordinates, instead of taking only the closest one.

Common:

``````defmodule AoC.DaySix.Common do
alias AoC.DaySix.{Coordinate, Field}

path
|> File.stream!()
|> Stream.map(&String.trim_trailing/1)
|> Enum.with_index()
|> Enum.map_reduce(%Field{}, fn {line, index}, field -> parse_input(line, index, field) end)
end

defp parse_input(line, index, field) do
coordinate = get_coordinate(line, index)
field = get_field(coordinate, field)
{coordinate, field}
end

defp get_coordinate(line, index) do
[x, y] = String.split(line, ",")
x = get_integer(x)
y = get_integer(y)
%Coordinate{id: index, x: x, y: y}
end

defp get_integer(string) do
string
|> String.trim()
|> String.to_integer()
end

defp get_field(coordinate, field) do
%Field{
min_x: min(coordinate.x, field.min_x),
min_y: min(coordinate.y, field.min_y),
max_x: max(coordinate.x, field.max_x),
max_y: max(coordinate.y, field.max_y)
}
end
end
``````

Part one:

``````defmodule AoC.DaySix.PartOne do
alias AoC.DaySix.{Coordinate, Common}

def main() do
"lib/day6/input.txt"
|> get_distance()
|> Enum.filter(fn {_k, v} -> v != nil end)
|> Enum.reduce(%{}, fn {_, {[c], _}}, acc ->
Map.update(acc, c.id, 1, &(&1 + 1))
end)
|> Enum.reduce(0, fn {_, v}, acc -> max(v, acc) end)
end

defp get_distance({coordinates, field}) do
Enum.reduce(field.min_x..field.max_x, %{}, fn x, acc ->
Enum.reduce(field.min_y..field.max_y, acc, fn y, acc ->
get_field_distances(x, y, coordinates, field, acc)
end)
end)
end

defp get_field_distances(x, y, coordinates, field, acc) do
field_coordinate = %Coordinate{x: x, y: y}
max_distance = get_max_distance(field)

{result, distance} =
Enum.reduce(coordinates, {[], max_distance}, fn input_coordinate, {result, distance} ->
get_distance_to_coordinate(input_coordinate, field_coordinate, result, distance)
end)

result_distance =
case length(result) do
1 -> {result, distance}
_ -> nil
end

Map.put(acc, {x, y}, result_distance)
end

defp get_max_distance(field) do
get_manhattan_distance(%Coordinate{x: field.min_x, y: field.min_y}, %Coordinate{
x: field.max_x,
y: field.max_y
})
end

defp get_distance_to_coordinate(input_coordinate, field_coordinate, result, distance) do
distance_total = get_manhattan_distance(input_coordinate, field_coordinate)

cond do
distance_total == distance -> {[input_coordinate | result], distance}
distance_total < distance -> {[input_coordinate], distance_total}
true -> {result, distance}
end
end

defp get_manhattan_distance(c1, c2) do
abs(c1.x - c2.x) + abs(c1.y - c2.y)
end
end
``````

Part two:

``````defmodule AoC.DaySix.PartTwo do
alias AoC.DaySix.{Common}

@max_region_size 10000

def main() do
"lib/day6/input.txt"
|> get_distance()
|> Enum.filter(fn {_k, v} -> v < @max_region_size end)
|> Enum.count()
end

defp get_distance({coordinates, field}) do
Enum.reduce(field.min_x..field.max_x, %{}, fn x, acc ->
Enum.reduce(field.min_y..field.max_y, acc, fn y, acc ->
result =
Enum.reduce(coordinates, 0, fn coordinate, result ->
get_total_distance(coordinate, x, y, result)
end)

Map.put(acc, {x, y}, result)
end)
end)
end

defp get_total_distance(coordinate, x, y, result) do
result + abs(coordinate.x - x) + abs(coordinate.y - y)
end
end
``````

PHP

Weird fact I learned about PHP in this puzzle: if you try and splice a very large array into an already very large multidimensional array, at a certain point PHP will throw an overflow error, but it doesn't happen with array_pad?

Anyway for the first one, I ended up just manually increasing the value by which I was expanding the grid and seeing at what point the number I was getting stopped changing, since "is this infinite" is hard to check for. The second part, I checked all the edge spaces to see if any of them were part of the central area, and if they weren't then I knew I could stop.

Part 1:

``````<?php
\$grid;
\$coordinates;
\$zonesizes;

function expandgrid() {
global \$grid;
global \$coordinates;
global \$zonesizes;

foreach (\$grid as \$row) {
}

\$coordinates = array_map(function(\$x) {
return array(
'x' => \$x['x']+1,
'y' => \$x['y']+1
);
}, \$coordinates);

for(\$i = 0; \$i < count(\$grid); \$i+=(count(\$grid)-1)) {
for (\$j = 0; \$j < count(\$grid); \$j+=(count(\$grid)-1)) {
\$distances = null;
\$zone = null;
\$distances = array_map(function(\$x) {
global \$j;
global \$i;
return (abs(\$i - \$x['y']) + abs(\$j - \$x['x']));
}, \$coordinates);
\$shortest = min(\$distances);
\$counts = array_count_values(\$distances);
if (\$counts[\$shortest] > 1) {
\$grid[\$i][\$j] = -1;
break;
}
\$zone = array_search(\$shortest, \$distances);
\$grid[\$i][\$j] = \$zone;
\$zonesizes[\$zone] += 1;
}
}
}

\$input = file_get_contents(\$argv);
\$coordinates = array_map(function(\$x) {
\$expl = explode(", ", \$x);
return array(
'x' => intval(\$expl),
'y' => intval(\$expl)
);
}, explode("\n", trim(\$input)));

\$largest = array_reduce(\$coordinates, function(\$c, \$i) {
if (\$c < \$i['x']) {
if (\$i['x'] < \$i['y']) {
return \$i['y'];
}
return \$i['x'];
}
return \$c;
}, 0);

\$grid = array_fill(0, \$largest+1, array_fill(0, \$largest+1, -1));
\$zonesizes = array_fill(0, count(\$coordinates), 0);

for(\$i = 0; \$i < \$largest+1; \$i++) {
for (\$j = 0; \$j < \$largest+1; \$j++) {
\$distances = null;
\$zone = null;
\$distances = array_map(function(\$x) {
global \$j;
global \$i;
return (abs(\$i - \$x['y']) + abs(\$j - \$x['x']));
}, \$coordinates);
\$shortest = min(\$distances);
\$counts = array_count_values(\$distances);
if (\$counts[\$shortest] > 1) {
\$grid[\$i][\$j] = -1;
continue;
}
\$zone = array_search(\$shortest, \$distances);
\$grid[\$i][\$j] = \$zone;
\$zonesizes[\$zone] += 1;
}
}

for (\$k = 0; \$k < 5000; \$k++) {
expandgrid();
}

\$finalzones = \$zonesizes;
\$edge_top = array_unique(\$grid);
\$edge_bottom = array_unique(\$grid[count(\$grid)-1]);
\$edge_left = array_unique(array_column(\$grid, 0));
\$edge_right = array_unique(array_column(\$grid, 0));
\$remove = array_values(array_unique(array_merge(\$edge_top, \$edge_bottom, \$edge_left, \$edge_right)));

\$finalzones = array_filter(\$finalzones, function(\$k) {
global \$remove;
if (in_array(\$k, \$remove)) {
return 0;
}
return 1;
}, ARRAY_FILTER_USE_KEY);

echo max(\$finalzones);

die(1);
``````

Part 2:

``````<?php
\$grid;
\$coordinates;
\$size;

function expandgrid() {
global \$grid;
global \$coordinates;
global \$size;

foreach (\$grid as \$row) {
}

\$coordinates = array_map(function(\$x) {
return array(
'x' => \$x['x']+1,
'y' => \$x['y']+1
);
}, \$coordinates);

for(\$i = 0; \$i < count(\$grid); \$i++) {
for (\$j = 0; \$j < count(\$grid); \$j++) {
if (\$i != 0 && \$i != count(\$grid) && \$j != 0 && \$j != count(\$grid)) {
continue;
}
\$distances = null;
\$zone = null;
\$distances = array_map(function(\$x) {
global \$j;
global \$i;
return (abs(\$i - \$x['y']) + abs(\$j - \$x['x']));
}, \$coordinates);
if (array_sum(\$distances) < 10000) {
\$grid[\$i][\$j] = 1;
\$size += 1;
}
}
}
}

\$input = file_get_contents(\$argv);
\$coordinates = array_map(function(\$x) {
\$expl = explode(", ", \$x);
return array(
'x' => intval(\$expl),
'y' => intval(\$expl)
);
}, explode("\n", trim(\$input)));

\$largest = array_reduce(\$coordinates, function(\$c, \$i) {
if (\$c < \$i['x']) {
if (\$i['x'] < \$i['y']) {
return \$i['y'];
}
return \$i['x'];
}
return \$c;
}, 0);

\$grid = array_fill(0, \$largest+1, array_fill(0, \$largest+1, 0));
\$size = 0;

for(\$i = 0; \$i < \$largest+1; \$i++) {
for (\$j = 0; \$j < \$largest+1; \$j++) {
\$distances = null;
\$zone = null;
\$distances = array_map(function(\$x) {
global \$j;
global \$i;
return (abs(\$i - \$x['y']) + abs(\$j - \$x['x']));
}, \$coordinates);
if (array_sum(\$distances) < 10000) {
\$grid[\$i][\$j] = 1;
\$size += 1;
}
}
}

do {
echo "expanding grid"."\n";
\$edge_top = array_unique(\$grid);
\$edge_bottom = array_unique(\$grid[count(\$grid)-1]);
\$edge_left = array_unique(array_column(\$grid, 0));
\$edge_right = array_unique(array_column(\$grid, 0));
\$edges = array_merge(\$edge_top, \$edge_bottom, \$edge_left, \$edge_right);
expandgrid();
} while(array_sum(\$edges) > 0);

echo \$size;

die(1);
``````

## Javascript solution

I enjoyed doing this one. It somehow felt satisfying. Maybe it's because for this one I was able to realize it's a series of steps and I could develop and test each one of them step-by-step, so I felt confident I was moving into the right direction.

``````const fs = require('fs');

const readLines = (file, onLine) => {
crlfDelay: Infinity
});

return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
const lines = [];
return lines;
}

module.exports = {
};
``````

### 06-common.js

``````class Coordinate {
constructor(x, y, id) {
this.x = x;
this.y = y;
this.id = id;
}
}

const buildCoordinates = lines => {
return lines.map((line, index) => {
const [x, y] = line.split(', ');
return new Coordinate(+x, +y, index);
});
};

const getGridDimension = coordinates => {
let largestX = 0;
let largestY = 0;
for (let coordinate of coordinates) {
const { x, y } = coordinate;
largestX = Math.max(largestX, x);
largestY = Math.max(largestY, y);
}
return Math.max(largestX, largestY) + 1;
}

const plotCoordinates = coordinates => {
const n = getGridDimension(coordinates);

const grid = Array.from({ length: n }, row => Array.from({ length: n }));
for (let coordinate of coordinates) {
const { x, y } = coordinate;
grid[x][y] = coordinate;
}
return grid;
};

const calculateManhattanDistance = (c1, c2) => {
return Math.abs(c1.x - c2.x) + Math.abs(c1.y - c2.y);
};

module.exports = {
Coordinate,
buildCoordinates,
getGridDimension,
plotCoordinates,
calculateManhattanDistance
};
``````

### 06a.js

``````const { readFile } = require('./reader');

const {
Coordinate,
buildCoordinates,
getGridDimension,
plotCoordinates,
calculateManhattanDistance
} = require('./06-common');

const plotLocations = (coordinates, grid) => {
const n = grid.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (!grid[i][j]) {
const location = new Coordinate(i, j);
grid[i][j] = location;

let smallestDistance;
let closestCoordinates;
for (let coordinate of coordinates) {
const distance = calculateManhattanDistance(location, coordinate);

if (!closestCoordinates || distance < smallestDistance) {
smallestDistance = distance;
closestCoordinates = [coordinate];
}
else if (distance === smallestDistance) {
closestCoordinates.push(coordinate);
}
}

if (closestCoordinates.length === 1) {
location.closestCoordinate = closestCoordinates;
}
}
}
}
};

const getFiniteCoordinateIds = (coordinates, grid) => {
const n = grid.length;
const infiniteCoordinateIds = new Set();

// Top and bottom edges
for (let i = 0; i < n; i += n-1) {
for (let j = 0; j < n; j++) {
const closestCoordinate = grid[i][j].closestCoordinate;
if (closestCoordinate) {
}
}
}

// Left and right edges
for (let j = 0; j < n; j += n-1) {
for (let i = 0; i < n; i++) {
const closestCoordinate = grid[i][j].closestCoordinate;
if (closestCoordinate) {
}
}
}

const finiteCoordinateIds = coordinates
.filter(coordinate => !infiniteCoordinateIds.has(coordinate.id))
.map(coordinate => coordinate.id);

return new Set(finiteCoordinateIds);
};

const calculateCoordinateRegions = (finiteCoordinates, grid) => {
const n = grid.length;
const frequencyMap = new Map();
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const closestCoordinate = grid[i][j].closestCoordinate;
if (closestCoordinate && finiteCoordinates.has(closestCoordinate.id)) {
const { id } = closestCoordinate;
const frequency = frequencyMap.get(id) || 1;
frequencyMap.set(id, frequency+1);
}
}
}
return frequencyMap;
};

(async () => {

const coordinates = buildCoordinates(lines);
const grid = plotCoordinates(coordinates);
plotLocations(coordinates, grid);
const finiteCoordinateIds = getFiniteCoordinateIds(coordinates, grid);
const coordinateRegions = calculateCoordinateRegions(finiteCoordinateIds, grid);
const largestRegion = Math.max(...coordinateRegions.values());

console.log(`The largest region is \${largestRegion}`);
})();
``````

### 06b.js

``````const { readFile } = require('./reader');

const {
Coordinate,
buildCoordinates,
getGridDimension,
plotCoordinates,
calculateManhattanDistance
} = require('./06-common');

const MAX_TOTAL_DISTANCE = 10000;

const plotLocations = (coordinates, grid) => {
const n = grid.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
let location = grid[i][j];
if (!grid[i][j]) {
location = new Coordinate(i, j);
grid[i][j] = location;
}

const totalDistance = coordinates.reduce((sum, coordinate) =>{
return sum + calculateManhattanDistance(location, coordinate);
}, 0);

location.inSafeRegion = totalDistance < MAX_TOTAL_DISTANCE;
}
}
};

const getSafeRegionSize = grid => {
const n = grid.length;
let safeRegionSize = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const location = grid[i][j];
safeRegionSize += +location.inSafeRegion;
}
}
return safeRegionSize;
};

(async () => {  