AoC Day 10: The Stars Align

On Day 10, the stars are aligning to send us messages. It's not a proper Advent of Code until we've had a vector problem, and I'll be honest that, as I started reading the prompt, I was thinking, "Oh, no problem! Vector math! I'm a mechanical engineer! I love vector math!"

And then.

......................
......................
......................
......................
......#...#..###......
......#...#...#.......
......#...#...#.......
......#####...#.......
......#...#...#.......
......#...#...#.......
......#...#...#.......
......#...#..###......
......................
......................
......................
......................

Head -> Desk.

OK, back to my consistent state of "not sure how we're going to do this." But that's what makes it fun! Right? Right? I'm excited to see your solutions.

Comments

[Ali Spittel]

This is my fastest one yet! May clean up the solution tomorrow, but:

import re
import time

class CoordinatePlane:
    def __init__(self, values):
        self.values = [Point(*value) for value in values]

    def x_vals(self):
        vals = [val.x for val in self.values]
        return min(vals), max(vals)

    def y_vals(self):
        vals = [val.y for val in self.values]
        return min(vals), max(vals)

    def draw(self):
        min_x, max_x = self.x_vals()
        min_y, max_y = self.y_vals()
        if max_x - min_x > 100 or max_y - min_y > 100: return
        grid = [['.' for _ in range(min_x, max_x+1)] for _ in range(min_y, max_y+1)]
        for value in self.values:
            grid[value.y - min_y][value.x - min_x] = 'X'
        for row in grid:
            print(''.join(row))
        time.sleep(2)
        print('\n\n\n')

    def increment(self):
        for value in self.values:
            value.move()


class Point:
    def __init__(self, x, y, x_speed, y_speed):
        self.x = x
        self.y = y
        self.x_speed = x_speed
        self.y_speed = y_speed

    def move(self):
        self.x += self.x_speed
        self.y += self.y_speed


with open('sample-input.txt', 'r') as f:        
    values = []
    for line in f:
        x, y, x_speed, y_speed = [int(n) for n in re.findall(r'[+-]?\d+', line)]
        values.append((x, y, x_speed, y_speed,))
    plane = CoordinatePlane(values)
    speed = 0
    while True:
        print(speed)
        plane.draw()
        plane.increment()
        speed += 1

[Viktors Jenovs]

This one was quite easy - just do calculations until all the values are closest together (i.e. check for min height) and then print them to the console. Didn't event have to do anything for part 2 ;)

<?php
$input = require_once 'readFile.php';

$array = array_map(function($str) {
  $re = "/position=<\s?(-?\d+),\s+(-?\d+)>\svelocity=<\s?(-?\d+),\s+(-?\d+).+/";
  return preg_split($re, $str, NULL, PREG_SPLIT_NO_EMPTY | PREG_SPLIT_DELIM_CAPTURE);
}, $input);


function caclcMinHeight($array) {
  $min = INF;
  $max = 0;
  foreach ($array as $value) {
    if ($value[1] < $min) {
      $min = $value[1];
    }
    if ($value[1] > $max) {
      $max = $value[1];
    }
  }
  return $max - $min;
}

function calcPosition($array, $seconds) {
  return array_map(function($data) use($seconds) {
    $posX = $data[0] + $data[2] * $seconds;
    $posY = $data[1] + $data[3] * $seconds;
    return [$posX, $posY];
  }, $array);
}

$positions = [];
$height = INF;
$seconds = 1;

while (true) {
  $positions = calcPosition($array, $seconds);
  $newHeight = caclcMinHeight($positions, $height);

  if ($newHeight > $height) {
    $seconds--;
    $positions = calcPosition($array, $seconds);
    break;
  } else {
    $height = $newHeight;
    $seconds++;
  }
}

$pixels = [];
foreach ($positions as $value) {
  $pixels[$value[0]][$value[1]] = true;
}

$minY = INF;
$maxY = 0;
$minX = INF;
$maxX = 0;

foreach ($positions as $value) {
  if ($value[0] > $maxX) {
    $maxX = $value[0];
  }
  if ($value[0] < $minX) {
    $minX = $value[0];
  }
  if ($value[1] > $maxY) {
    $maxY = $value[1];
  }
  if ($value[1] < $minY) {
    $minY = $value[1];
  }
}

for ($y=$minY - 1; $y <= $maxY + 1; $y++) { 
  for ($x=$minX - 1; $x <= $maxX + 1; $x++) { 
    echo !empty($pixels[$x][$y]) ? "#" : " ";
  }
  echo "\n";
}
echo "Done in " . $seconds . " \"seconds\"\n\n";
?>

readFile.php

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

while(!feof($file)) {
  $array[] = fgets($file);
}

fclose($file);

return array_filter($array);
?>

[Joe Zack]

I also stopped when I noticed that the stars started getting further apart. I wish that had been part of the problem description though, since it's possible for to come up with an input that breaks that assumption.

[E. Choroba]

Just waiting for the smallest constellation could be wrong, I can imagine the lights forming even smaller image after (or before) showing the message. So, I printed all the possibilities fitting to an old-school terminal. In my case, there were three, and one of them contained the message. I printed the time along the way, so I solved both the parts in one go.

#!/usr/bin/perl
use warnings;
use strict;

use List::Util qw{ min max };

my @lights;
while (<>) {
    push @lights, [ /(-?\d+)/g ];
}

my $time = 0;
while (1) {
    show() if width() < 80;
    update();
    ++$time;
}

sub width { max(map $_->[0], @lights) - min(map $_->[0], @lights) }

sub show {
    my %grid;
    my ($min_x, $max_x, $min_y, $max_y)
        = ($lights[0][0], $lights[0][0], $lights[0][1], $lights[0][0]);
    for my $light (@lights) {
        $min_x = $light->[0] if $light->[0] < $min_x;
        $min_y = $light->[1] if $light->[1] < $min_y;
        $max_x = $light->[0] if $light->[0] > $max_x;
        $max_y = $light->[1] if $light->[1] > $max_y;
        ++$grid{ $light->[0] }{ $light->[1] };
    }

    for my $y ($min_y .. $max_y) {
        for my $x ($min_x .. $max_x) {
            print $grid{$x}{$y} ? '#' : '.';
        }
        print "\n";
    }
    print "$time\n";
}

sub update {
    for my $light (@lights) {
        $light->[0] += $light->[2];
        $light->[1] += $light->[3];
    }
}

[Neil Gall]

This one was quite interesting. Integrating moving points over time is straightforward enough but how do we detect the moment a message appears? I'm going to assume it's at the point in time when the bounding box of all the points is smallest.

First we'll reuse and extend some of the geometric primitives from day 6:

data class Position(val x: Int, val y: Int)
data class Velocity(val x: Int, val y: Int)
data class Box(val x: IntRange, val y: IntRange)
data class Point(val position: Position, val velocity: Velocity)
typealias Time = Int

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

fun Collection<Position>.boundingBox(): Box = fold(Box.EMPTY, Box::plus)

And we'll add a function to get a point's position at any time t:

fun Point.integrate(t: Time): Position =
    Position(x = position.x + velocity.x * t,
             y = position.y + velocity.y * t)

We'll solve the problem by iterating over a large period of time and computing the bounding box for the points at each time. Then take the smallest of these bounding boxes:

val sizes: List<Pair<Int, Box>> = (1..100000).map { t -> Pair(t, input.map { p -> p.integrate(t) }.boundingBox()) }
val time: Int = sizes.minBy { (_, box) -> box.area }?.first

Then we'll render the points into beautiful ASCII art at that time by building a 2D array of characters and filling in the ones at the right positions:

fun Collection<Position>.render(): String {
    val box: Box = boundingBox()
    var cells = Array<Array<Char>>(box.height) { Array<Char>(box.width) { '.' }}
    forEach { p ->
        cells[p.y - box.y.start][p.x - box.x.start] = '#'
    }
    return cells.map { row -> row.joinToString("") }.joinToString("\n")
}

Part 2 was either disappointing or a relief, depending on your viewpoint, as my part 1 solution already had the answer.

Full code at github.com/neilgall/adventofcode20...

[Tiago Romero]

Javascript solution

I had a really hard time with Stack Overflows (I even tried my company's computer to see if it would be better). I even looked at pixel plotting libraries for Node.js.

It took me 1 hour to realize that I would not need to print the whole matrix - but I could just keep processing it until I got it to the smallest height, and then I print it.

However I would only know I got to the smallest height after I'm no longer on the smallest height and then I need to tick the clock just once backwards to get back to the smallest height and print it.

reader.js

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

const readLines = (file, onLine) => {
    const reader = readline.createInterface({
        input: fs.createReadStream(file),
        crlfDelay: Infinity
    });

    reader.on('line', onLine);

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

const readFile = async file => {
    const lines = [];
    await readLines(file, line => lines.push(line));  
    return lines;
}

module.exports = {
    readLines,
    readFile
};

10.js

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

const regex = /^position=<\s?(?<posX>-?\d+), \s?(?<posY>-?\d+)> velocity=<\s?(?<velX>-?\d+), \s?(?<velY>-?\d+)>$/;

const parseInput = lines => {
    return lines.map(line => {
        const { posX, posY, velX, velY } = line.match(regex).groups;
        return {
            posX: +posX,
            posY: +posY,
            velX: +velX,
            velY: +velY
        };
    });
};

const printPointsUntilMinimum = points => {
    const viewSize = 100;

    let minimumY = getEdges(points).lengthY;
    let hasReachedMinimum = false;
    let secondsForMessage = 0;

    while (!hasReachedMinimum) {
        tick(points);   
        secondsForMessage++;     

        const { lengthY } = getEdges(points);
        if (lengthY < minimumY) {
            minimumY = lengthY;            
        }
        else {
            tick(points, false);
            console.log(`${lengthY} lines`);
            printPoints(points);

            hasReachedMinimum = true;            
        }
    }

    console.log(`The elves had to wait ${secondsForMessage-1} seconds`);
}

const tick = (points, forward = true) => {
    const sign = forward ? 1 : -1;
    for (let point of points) {
        point.posX += point.velX * sign;
        point.posY += point.velY * sign;
    }
};

const getEdges = points => {
    const posX = points.map(p => p.posX);
    const posY = points.map(p => p.posY);

    const minX = Math.min(...posX);
    const maxX = Math.max(...posX);
    const minY = Math.min(...posY);
    const maxY = Math.max(...posY);

    return {
        minX,
        minY,
        lengthX: maxX - minX + 1,
        lengthY: maxY - minY + 1
    };
};

const printPoints = points => {
    const { minX, minY, lengthX, lengthY } = getEdges(points);

    const grid = Array.from({length: lengthY}, row => Array.from({length: lengthX}, col => '.'));

    for (let point of points) {
        const x = point.posX - minX;
        const y = point.posY - minY;
        grid[y][x] = '#';
    }

    for (let row of grid) {
        console.log(row.join(''));
    }
};

(async () => {
    const lines = await readFile('10-input.txt');

    const points = parseInput(lines);

    printPointsUntilMinimum(points);    
})();

[Franco Cedillo]

my solution here 😃 thanks for your suggestions

it's coded in Python. it uses vectorization with numpy ndarrays

positions_nda += velocities_nda * iterations

In order to find the instant for points of light alignment, it uses minimize from scipy.optimize module,

from scipy.optimize import minimize
import numpy as np
from parse import parse


filename = 'input'
filepath = f'data/{filename}.plain'

positions = []
velocities = []

pattern = 'position=<{px},{py}> velocity=<{vx},{vy}>'

for line in open(filepath):
    result = parse(pattern, line)
    position = (int(result['px']), int(result['py']))
    positions.append(position)
    velocity = (int(result['vx']), int(result['vy']))
    velocities.append(velocity)

positions_nda = np.array(positions)
velocities_nda = np.array(velocities)


def gen_area(iterations, initial_positions, velocities):
    positions = initial_positions + velocities * i
    x_min, y_min = positions.min(axis=0)
    x_max, y_max = positions.max(axis=0)
    w = x_max - x_min
    h = y_max - y_min
    area = w * h
    return area


# identify the second that minimizes the dispersion of points
t = minimize(gen_area, 0, (positions_nda, velocities_nda))
second = int(np.round(t.x))

positions_nda += velocities_nda * second


def draw(positions_nda):

    x_min, y_min = positions_nda.min(axis=0)
    x_max, y_max = positions_nda.max(axis=0)

    for y in range(y_min, y_max + 1):
        line = ''
        for x in range(x_min, x_max + 1):
            if [x, y] in positions_nda.tolist():
                line += '#'
            else:
                line += '.'
        print(line)


draw(positions_nda)

[Ryan Palo]

This one wasn't as bad as I thought it was going to be -- albeit I did it significantly more manually than they might have hoped. Basically, I just iterated until the stars were reasonably close together (I guessed 30 rows overall range, and it worked out pretty well), and then printed out the sky at each iteration and scrolled through my terminal until I found one that wasn't nonsense. For the second part, I added one line to print the time above each iteration.

Maybe not the most algorithmically performant (lots of nested for-loops), but it did like 20k ticks in less than a second, so probably OK.

/// Day 10: The Stars Align
/// 
/// Figure out what message appears as 2D vectors line up

use regex::Regex;

/// A star in the sky that has position and velocity in 2 dimensions
struct Star {
    x: isize,
    y: isize,
    vx: isize,
    vy: isize,
}

impl Star {
    pub fn update(&mut self) {
        self.x += self.vx;
        self.y += self.vy;
    }
}

/// A night sky that has kinematic stars in it
pub struct Sky {
    stars: Vec<Star>,
}

impl Sky {
    pub fn new() -> Self {
        Self { stars: vec![] }
    }

    /// Loads stars in the sky from text
    pub fn from_text(text: &str) -> Self {
        let mut sky = Self::new();
        let number_regex = Regex::new(r"-?\d+").unwrap();
        for line in text.lines() {
            let mut numbers = number_regex.find_iter(line);
            let x = numbers.next().unwrap().as_str().parse().unwrap();
            let y = numbers.next().unwrap().as_str().parse().unwrap();
            let vx = numbers.next().unwrap().as_str().parse().unwrap();
            let vy = numbers.next().unwrap().as_str().parse().unwrap();
            sky.stars.push(Star { x, y, vx, vy });
        }
        sky
    }

    /// Updates the position of each star based on its velocity
    pub fn update(&mut self) {
        for star in self.stars.iter_mut() {
            star.update();
        }
    }

    /// Loop over time, updating the Sky and potentially displaying the
    /// current state.  Only displays if the stars are clustered enough
    /// together.  Stars are '#' and empty sky is '.'
    pub fn display(&mut self, frames: isize) {
        for t in 0..frames {
            self.update();

            let xmin = self.stars.iter().map(|star| star.x).min().unwrap();
            let xmax = self.stars.iter().map(|star| star.x).max().unwrap();
            let ymin = self.stars.iter().map(|star| star.y).min().unwrap();
            let ymax = self.stars.iter().map(|star| star.y).max().unwrap();

            // Only display if the bounds are reasonable
            if (ymax - ymin) > 30 {
                continue;
            }
            println!("");
            println!("t = {}", t);
            for y in (ymin - 5)..=(ymax + 5) {
                for x in (xmin - 5)..=(xmax + 5) {
                    if self.stars.iter().any(|star| star.x == x && star.y == y) {
                        print!("#");
                    } else {
                        print!(".");
                    }
                }
                println!("");
            }
        }
    }
}

[Matt Morgis]

A data scientist on my team visualized her solution

[Ryan Palo]

Whoah! That's smart! So cool. Thanks for sharing!