Advent of Code: Day 3

For Day 3, the challenge is to calculate the Manhattan Distance for a given number given a formula for calculating a spiral of numbers. My initial brute force solution, in Javascript, is shown below:

const UP = [0, -1];
const DOWN = [0, 1];
const LEFT = [-1, 0];
const RIGHT = [1, 0];

const X = 0;
const Y = 1;

function get_position(n) {
    let pos = [0, 0];
    let x_range = [-1, 1];
    let y_range = [-1, 1];
    let direction = RIGHT;
    let number = 1;

    while (number < n) {
        number += 1
        pos[X] += direction[X]
        pos[Y] += direction[Y]

        if (direction == RIGHT && pos[X] == x_range[1]) {
            direction = UP;
            x_range[1] += 1;
        } else if (direction == LEFT && pos[X] == x_range[0]) {
            direction = DOWN;
            x_range[0] -= 1;
        } else if (direction == UP && pos[Y] == y_range[0]) {
            direction = LEFT;
            y_range[0] -= 1;
        } else if (direction == DOWN && pos[Y] == y_range[1]) {
            direction = RIGHT;
            y_range[1] += 1;
        }
    }

    return pos;
}

const position = get_position(289326);
console.log(Math.abs(position[0]) + Math.abs(position[1]));

And for Part 2:

const HashMap = require("HashMap");
const UP = [0, -1];
const DOWN = [0, 1];
const LEFT = [-1, 0];
const RIGHT = [1, 0];

const X = 0;
const Y = 1;

function get_value_greater_than(n) {
    const values = new HashMap();
    values.set([0, 0], 1);

    let pos =  [0, 0];
    let x_range = [-1, 1];
    let y_range = [-1, 1];
    let direction = RIGHT;

    function sum_adjacent(pos) {
        adjacent = [
            [pos[X] - 1, pos[Y] - 1],
            [pos[X], pos[Y] - 1],
            [pos[X] + 1, pos[Y] - 1],
            [pos[X] - 1, pos[Y]],
            [pos[X] + 1, pos[Y]],
            [pos[X] - 1, pos[Y] + 1],
            [pos[X], pos[Y] + 1],
            [pos[X] + 1, pos[Y] + 1],
        ];

        return adjacent.map(x => values.get(x) || 0).reduce((acc, cur) => acc + cur);
    }

    while (values.get(pos) < n) {
        pos = [pos[X] + direction[X], pos[Y] + direction[Y]];
        values.set(pos, sum_adjacent(pos));

        if (direction == RIGHT && pos[X] == x_range[1]) {
            direction = UP
            x_range[1] += 1
        } else if (direction == LEFT && pos[X] == x_range[0]) {
            direction = DOWN
            x_range[0] -= 1
        } else if (direction == UP && pos[Y] == y_range[0]) {
            direction = LEFT
            y_range[0] -= 1
        } else if (direction == DOWN && pos[Y] == y_range[1]) {
            direction = RIGHT
            y_range[1] += 1
        }
    }

    return values.get(pos);
}

console.log(get_value_greater_than(289326));

This uses the hashmap package, as Javascript lacks a native hashmap implementation.

Looking at it, I can't immediately see a better way to do Part 2 than just looping over every value until finding one that works.

For part one though, it looks like there should be a closed-form way of calculating the X and Y coordinates for a given value. I don't immediately have time to figure that out though so I'll return to it if I have time later.

Advent of Code runs every day up to Christmas, you should join in!.

Show Comments

Get the latest posts delivered right to your inbox.