Ryan Palo

Posted on Dec 6, 2018

AoC Day 6: Chronal Coordinates

#adventofcode #discuss

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 days ago, have I got a treat for you! Now we're dealing with blobby, non-uniform shapes with possibly infinite area! Yay us!

I'm definitely not going to be able to complete this one tonight. I'll have to work on it tomorrow after a good night's sleep.

Happy plotting (X-Y plotting, I mean)!

Top comments (19)

Bjarne Magnussen • Dec 6 '18 • Edited

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:
    data = f.readlines()


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(','))
    P.add((x, y))
    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)))

Florian Rohrer • Dec 6 '18

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:
        edge.add(int(dists[0]))
    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))

Bjarne Magnussen • Dec 6 '18

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
}

// readLines reads a whole file into memory
// 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() {
    data, err := readLines("input")
    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))
}

Neil Gall • Dec 6 '18

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

For readable code we'll add some useful operations, using Kotlin's carefully limited operator overloading where appropriate:

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()
        }
    }

    stack.addAll(around(c.pos))
    while (!stack.isEmpty()) {
        val p = stack.first()
        stack.addAll(fill(p))
        stack.remove(p)
    }
}

Things to note:

Recursive functions are often best implemented with a helper and a "starter" method.
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.
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.
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.
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:

If any edge position claims the ID, the area will be infinite
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...

Viktors Jenovs • Dec 6 '18 • Edited

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
$array = require_once 'readFile.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[1], $top);
  $right = (int)max($value[0], $right);
  $bottom = (int)max($value[1], $bottom);
  $left = (int)min($value[0], $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[1], $value[0]);

      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
$array = require_once 'readFile.php';

define("TOTAL_DIST", 10000);

function calcDist($p, $q) {
  return abs($p[0] - $q[0]) + abs($p[1] - $q[1]);
}

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

foreach ($array as $value) {
  $top = (int)min($value[1], $top);
  $right = (int)max($value[0], $right);
  $bottom = (int)max($value[1], $bottom);
  $left = (int)min($value[0], $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[1], (int)$value[0]]);
    }
    if ($dist < TOTAL_DIST) {
      $distances++;
    }
  }
}

echo $distances;
?>

readFile.php

<?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[0], (int)$val[1]);
}, $array));
?>

Jon Bristow • Dec 6 '18 • Edited

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[0].toInt(), found[1].toInt())
}

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

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

fun answer1(input: List<Point>): Int? {
    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()
}

Jon Bristow • Dec 6 '18 • Edited

The promised images!

Sample Data

Part 1 - Answer

Part 2 - Answer

Answers

Part 1 - Answer

Part 2 - Answer

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.

𒎏Wii 🏳️‍⚧️ • Dec 6 '18

You don't have to construct an array; you can just iterate over min(x)..max(x) and min(y)..max(y) and add + to the nearest input point.

E. Choroba • Dec 7 '18

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}[0] - $x) + abs($locations{A}[1] - $y),
                  'A' );
        for my $location (keys %locations) {
            next if 'A' eq $location;

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

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

Ryan Palo • Dec 7 '18

Oh no! That’s a bummer 😐

Shahor • Dec 7 '18 • Edited

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"

const input = Fs.readFileSync(Path.join(__dirname, "input.txt"))
    .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[0].distance === distances[1].distance) {
        return null
    }

    return distances[0].id
}

const canvas: Array<Array<Pixel>> = []
for (let x = boundaries[0].x; x <= boundaries[1].x; x++) {
    for (let y = boundaries[0].y; y <= boundaries[1].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[0].x; x <= boundaries[1].x; x++) {
            for (let y = boundaries[0].y; y <= boundaries[1].y; y++) {
                if (canvas[x][y] === id) {
                    count++
                }
            }
        }
        return count
    })
    .sort((a, b) => b - a)

// 01
console.log(sorted[0])

Part2:

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

const input = Fs.readFileSync(Path.join(__dirname, "input.txt"))
    .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[0].x; x <= boundaries[1].x; x++) {
    for (let y = boundaries[0].y; y <= boundaries[1].y; y++) {
        const beacon = { x, y }
        const sum = coordinates.reduce((total, point) => {
            return total + computeManhattanDistance(beacon, 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}`
)

Ryan Palo • Dec 7 '18

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)
}

Carly Ho 🌈 • Dec 6 '18

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) {
    array_pad($row, 1, -1);
    array_pad($row, -1, -1);
  }
  array_pad($grid, 1, array_fill(0, count($grid[0]), -1));
  array_pad($grid, -1, array_fill(0, count($grid[0]), -1));

  $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[1]);
$coordinates = array_map(function($x) {
  $expl = explode(", ", $x);
  return array(
    'x' => intval($expl[0]),
    'y' => intval($expl[1])
  );
}, 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[0]);
$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) {
    array_pad($row, 1, 0);
    array_pad($row, -1, 0);
  }
  array_pad($grid, 1, array_fill(0, count($grid[0]), 0));
  array_pad($grid, -1, array_fill(0, count($grid[0]), 0));

  $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[1]);
$coordinates = array_map(function($x) {
  $expl = explode(", ", $x);
  return array(
    'x' => intval($expl[0]),
    'y' => intval($expl[1])
  );
}, 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[0]);
  $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);

Ali Spittel • Dec 6 '18 • Edited

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[0] > max_x: max_x = line[0]
        if line[1] > max_y: max_y = line[1]
        coords.append((line[1], line[0],))

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] == 0 or dist < col[1]: 
                matrix[r_idx][c_idx] = (idx+1, dist,)
            elif dist == col[1] and col[0] != idx+1:
                matrix[r_idx][c_idx] = (None, dist,)


matrix = [[i[0] for i in sublist] for sublist in matrix]
flipped_matrix = matrix[::-1]
to_filter = set(matrix[0] + matrix[-1] + flipped_matrix[0] + 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)[0][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[0] > max_x: max_x = line[0]
        if line[1] > max_y: max_y = line[1]
        coords.append((line[1], line[0],))

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)

𒎏Wii 🏳️‍⚧️ • Dec 6 '18

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[1], self[2])
  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[1], point[2]
  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[1]) + math.abs(y-p[2]))
    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

-- Output the answer and be happy about it :)

print(highest)

View full discussion (19 comments)

DEV Community

AoC Day 6: Chronal Coordinates

Top comments (19)

Part 1

Part 2

Kotlin Solution

Part 1

Part 2

Sample Data

Answers

Read next

10 IT traditions and superstitions: from mischievous gremlins to a cactus on the desk

Laravel's $57M Funding is a Step Forward, Not a Sellout

Procrastination

What is your way declare types for objects in TypeScript?