Day 14: Restroom Redoubt

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • JRaccoon@discuss.tchncs.deEnglish
    4·
    9 days ago

    TypeScript

    Part 2 was a major curveball for sure. I was expecting something like the grid size and number of seconds multiplying by a large amount to make iterative solutions unfeasible.

    First I was baffled how we’re supposed to know what shape we’re looking for exactly. I just started printing out cases where many robots were next to each other and checked them by hand and eventually found it. For my input the correct picture looked like this:

    The Christmas tree

    Picture

    Later it turned out that a much simpler way is to just check for the first time none of the robots are overlapping each other. I cannot say for sure if this works for every input, but I suspect the inputs are generated in such a way that this approach always works.

    The code 
    import fs from "fs";

type Coord = {x: number, y: number};
type Robot = {start: Coord, velocity: Coord};

const SIZE: Coord = {x: 101, y: 103};

const input: Robot[] = fs.readFileSync("./14/input.txt", "utf-8")
    .split(/[\r\n]+/)
    .map(row => /p=(-?\d+),(-?\d+)\sv=(-?\d+),(-?\d+)/.exec(row))
    .filter(matcher => matcher != null)
    .map(matcher => {
        return {
            start: {x: parseInt(matcher[1]), y: parseInt(matcher[2])},
            velocity: {x: parseInt(matcher[3]), y: parseInt(matcher[4])}
        };
    });

console.info("Part 1: " + safetyFactor(input.map(robot => calculatePosition(robot, SIZE, 100)), SIZE));

// Part 2
// Turns out the Christmas tree is arranged the first time none of the robots are overlapping
for (let i = 101; true; i++) {
    const positions = input.map(robot => calculatePosition(robot, SIZE, i));
    if (positions.every((position, index, arr) => arr.findIndex(pos => pos.x === position.x && pos.y === position.y) === index)) {
        console.info("Part 2: " + i);
        break;
    }
}

function calculatePosition(robot: Robot, size: Coord, seconds: number): Coord {
    return {
        x: ((robot.start.x + robot.velocity.x * seconds) % size.x + size.x) % size.x,
        y: ((robot.start.y + robot.velocity.y * seconds) % size.y + size.y) % size.y
    };
}

function safetyFactor(positions: Coord[], size: Coord): number {
    const midX = Math.floor(size.x / 2);
    const midY = Math.floor(size.y / 2);

    let quadrant0 = 0; // Top-left
    let quadrant1 = 0; // Top-right
    let quadrant2 = 0; // Bottom-left
    let quadrant3 = 0; // Bottom-right

    for (const {x,y} of positions) {
        if (x === midX || y === midY) { continue; }

        if (x < midX && y < midY) { quadrant0++; }
        else if (x > midX && y < midY) { quadrant1++; }
        else if (x < midX && y > midY) { quadrant2++; }
        else if (x > midX && y > midY) { quadrant3++; }
    }

    return quadrant0 * quadrant1 * quadrant2 * quadrant3;
}
    • lwhjp@lemmy.sdf.org
      2·
      9 days ago

      Checking for no overlaps is an interesting one. Intuitively I’d expect that to happen more often due to the low density, but as you say perhaps it’s deliberate.