Skip to content

Latest commit

 

History

History
356 lines (310 loc) · 9.97 KB

10.md

File metadata and controls

356 lines (310 loc) · 9.97 KB
Raw

Day 10: The Stars Align - Code

It's no use; your navigation system simply isn't capable of providing walking directions in the arctic circle, and certainly not in 1018.

The Elves suggest an alternative. In times like these, North Pole rescue operations will arrange points of light in the sky to guide missing Elves back to base. Unfortunately, the message is easy to miss: the points move slowly enough that it takes hours to align them, but have so much momentum that they only stay aligned for a second. If you blink at the wrong time, it might be hours before another message appears.

You can see these points of light floating in the distance, and record their position in the sky and their velocity, the relative change in position per second (your puzzle input). The coordinates are all given from your perspective; given enough time, those positions and velocities will move the points into a cohesive message!

Rather than wait, you decide to fast-forward the process and calculate what the points will eventually spell.

For example, suppose you note the following points:

position=< 9,  1> velocity=< 0,  2>
position=< 7,  0> velocity=<-1,  0>
position=< 3, -2> velocity=<-1,  1>
position=< 6, 10> velocity=<-2, -1>
position=< 2, -4> velocity=< 2,  2>
position=<-6, 10> velocity=< 2, -2>
position=< 1,  8> velocity=< 1, -1>
position=< 1,  7> velocity=< 1,  0>
position=<-3, 11> velocity=< 1, -2>
position=< 7,  6> velocity=<-1, -1>
position=<-2,  3> velocity=< 1,  0>
position=<-4,  3> velocity=< 2,  0>
position=<10, -3> velocity=<-1,  1>
position=< 5, 11> velocity=< 1, -2>
position=< 4,  7> velocity=< 0, -1>
position=< 8, -2> velocity=< 0,  1>
position=<15,  0> velocity=<-2,  0>
position=< 1,  6> velocity=< 1,  0>
position=< 8,  9> velocity=< 0, -1>
position=< 3,  3> velocity=<-1,  1>
position=< 0,  5> velocity=< 0, -1>
position=<-2,  2> velocity=< 2,  0>
position=< 5, -2> velocity=< 1,  2>
position=< 1,  4> velocity=< 2,  1>
position=<-2,  7> velocity=< 2, -2>
position=< 3,  6> velocity=<-1, -1>
position=< 5,  0> velocity=< 1,  0>
position=<-6,  0> velocity=< 2,  0>
position=< 5,  9> velocity=< 1, -2>
position=<14,  7> velocity=<-2,  0>
position=<-3,  6> velocity=< 2, -1>

Each line represents one point. Positions are given as <X, Y> pairs: X represents how far left (negative) or right (positive) the point appears, while Y represents how far up (negative) or down (positive) the point appears.

At 0 seconds, each point has the position given. Each second, each point's velocity is added to its position. So, a point with velocity <1, -2> is moving to the right, but is moving upward twice as quickly. If this point's initial position were <3, 9>, after 3 seconds, its position would become <6, 3>.

Over time, the points listed above would move like this:

Initially:
........#.............
................#.....
.........#.#..#.......
......................
#..........#.#.......#
...............#......
....#.................
..#.#....#............
.......#..............
......#...............
...#...#.#...#........
....#..#..#.........#.
.......#..............
...........#..#.......
#...........#.........
...#.......#..........

After 1 second:
......................
......................
..........#....#......
........#.....#.......
..#.........#......#..
......................
......#...............
....##.........#......
......#.#.............
.....##.##..#.........
........#.#...........
........#...#.....#...
..#...........#.......
....#.....#.#.........
......................
......................

After 2 seconds:
......................
......................
......................
..............#.......
....#..#...####..#....
......................
........#....#........
......#.#.............
.......#...#..........
.......#..#..#.#......
....#....#.#..........
.....#...#...##.#.....
........#.............
......................
......................
......................

After 3 seconds:
......................
......................
......................
......................
......#...#..###......
......#...#...#.......
......#...#...#.......
......#####...#.......
......#...#...#.......
......#...#...#.......
......#...#...#.......
......#...#..###......
......................
......................
......................
......................

After 4 seconds:
......................
......................
......................
............#.........
........##...#.#......
......#.....#..#......
.....#..##.##.#.......
.......##.#....#......
...........#....#.....
..............#.......
....#......#...#......
.....#.....##.........
...............#......
...............#......
......................
......................

After 3 seconds, the message appeared briefly: HI. Of course, your message will be much longer and will take many more seconds to appear.

What message will eventually appear in the sky?

Solution

Consider that we want to show a single letter 'l':

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

The movement of these two #s is linear. Regardless of what the velocity is, the position equation will be x = vx * t + xo, right? The #s are going to move in a specific direction and will indefinitely keep moving in that direction. Basic physics. So the #s are either:

  • Are approaching each other, and will eventually form a letter, and then start moving away from each other, or
  • Are already moving away from one another.

Visually, the first option is

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

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

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

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

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

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

The #s inch closer and closer, and then they reach a minimum closeness, and then start separating.

And the second option is

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

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

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

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

In this option, the #s are going farther and farther apart.

We can measure closeness by calculating the area. How?

  1. Find the top-most y called yMin,
  2. Find the bottom-most y called yMax,
  3. Calculate height by doing yMax - yMin,
  4. Do the same thing for width: xMax - xMin, and finally,
  5. area = height * width.

So in our first example above, the height is always 1, but the width gets smaller and smaller until it reaches a minimum of 0, giving us an area of 0. The area then starts growing again.

Let's do this for a bigger example like the HI example from the problem description, calculating the area in each step:

width = [-4, 13], height = [-2, 9]
area 187 time 1
........#....#
......#.....#
#.........#......#
.
....#
..##.........#
....#.#
...##.##..#
......#.#
......#...#.....#
#...........#
..#.....#.#

width = [-2, 11], height = [-1, 8]
area 117 time 2
..........#
#..#...####..#
.
....#....#
..#.#
...#...#
...#..#..#.#
#....#.#
.#...#...##.#
....#

width = [0, 9], height = [0, 7]
area 63 time 3
#...#..###
#...#...#
#...#...#
#####...#
#...#...#
#...#...#
#...#...#
#...#..###

width = [-2, 10], height = [-1, 9]
area 120 time 4
........#
....##...#.#
..#.....#..#
.#..##.##.#
...##.#....#
.......#....#
..........#
#......#...#
.#.....##
...........#
...........#

Finally, some code:

export const getArea = (snapshots: ISnapshot[]) => {
  const minX = Math.min(...snapshots.map(s => s.start.x));
  const minY = Math.min(...snapshots.map(s => s.start.y));
  const maxX = Math.max(...snapshots.map(s => s.start.x));
  const maxY = Math.max(...snapshots.map(s => s.start.y));

  return (maxX - minX) * (maxY - minY);
};

export const getPosition = (snapshots: ISnapshot[]) => (timeElapsed: number) => {
  return snapshots.map(s => ({
    start: s.start.add(s.velocity.multiply(timeElapsed)),
    velocity: s.velocity
  }));
};

export const getMinAreaTime = (snapshots: ISnapshot[]) => {
  let curr = Infinity;
  let prev = Infinity;
  let time = 0;
  do {
    curr = getArea(getPosition(snapshots)(++time));
    if (curr > prev) {
      break;
    } else {
      prev = curr;
    }
  // eslint-disable-next-line
  } while(true);

  return { minArea: prev, minTime: time - 1 };
};

Finally, the display logic:

export const display = (snapshots: ISnapshot[]) => {
  const minX = Math.min(...snapshots.map(s => s.start.x));
  const minY = Math.min(...snapshots.map(s => s.start.y));
  const grid: boolean[][] = [[]];
  for (const p of snapshots) {
    // this is important because if minY is like -40, we don't want to
    // put data in grid[-40], we want it to be grid[0].
    // Thus, we offset every x and y with the minX and minY
    const x = p.start.x - minX;
    const y = p.start.y - minY;
    if (grid[y] == null) {
      grid[y] = [];
    }
    grid[y][x] = true;
  }

  let printout = '';
  for (let i = 0; i < grid.length; i++) {
    // if no # in this row, still display the row, but just put `.`
    // at the beginning of the row
    if (grid[i] == null) {
      printout += '.';
    }
    else {
      // it's likely that each row in grid will be something like this:
      // [ <39 empty items>, '#', <10 empty items>, '#' ]
      // The length of this array is still 51, even though
      // it only has 2 items. We can't do grid[i].map(f) because f will
      // only be called on the 2 non-empty items--undesireable.
      for (let j = 0; j < grid[i].length; j++) {
        printout += grid[i][j] ? '#' : '.';
      }
    }
    printout += '\n';
  }
  return printout;
};

The answer to my input was:

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