const input = require("fs").readFileSync(0).toString();
const mazeSize = 71;
const bytesReadPartOne = 1024;

/**
 * @param {string} input
 * @param {number} size
 * @param {number} simulateFirstXBytes
 * @returns {string[][]}
 */
const simulateMapState = (input, size, simulateFirstXBytes) => {
    const grid = [...new Array(size).keys()].map(() => [...new Array(size).keys()].map(() => '.'));
    /** @type {Coords[]} */
    const inputPredictions = input.split("\n").map((c) => ({ x: parseInt(c.split(',')[0]), y: parseInt(c.split(',')[1]) }));
    for (let i = 0; i < simulateFirstXBytes; i += 1) {
        grid[inputPredictions[i].y][inputPredictions[i].x] = '#';
    }
    return grid;
}

/**
 * @typedef {object} Coords
 * @property {number} x
 * @property {number} y
 */

class Escapee {
    static DIRECTIONS = {
        '<': { x: -1, y: 0, },
        '^': { x: 0, y: -1, },
        '>': { x: 1, y: 0, },
        'v': { x: 0, y: 1, },
    };

    /** @type {string[][]} */
    map = [];

    /** @type {Coords} */
    pos = {
        x: 0,
        y: 0,
    };

    /** @type {Coords} */
    end = {
        x: 0,
        y: 0,
    }

    /** @type {keyof Escapee.DIRECTIONS} */
    direction;

    /** @type {string[]} */
    path = [];

    /** @type {number} */
    score;

    /**
     * @param {string[][]} maze
     * @param {Coords} position
     * @param {Coords} end
     * @param {keyof Escapee.DIRECTIONS} direction
     * @param {string[]} path
     */
    constructor(maze, x, y, endX, endY, direction = '>', path = [], score = 0) {
        this.map = maze;
        this.pos.x = x;
        this.pos.y = y;
        this.end.x = endX;
        this.end.y = endY;
        this.direction = direction;
        this.path = path;
        this.score = score;
    }

    /** @returns {Escapee} */
    clone() {
        return new Escapee(
            this.map,
            this.pos.x,
            this.pos.y,
            this.end.x,
            this.end.y,
            this.direction,
            [...this.path],
            this.score,
        );
    }

    /**
     * @param {boolean} ccw Counter-clockwise
     * @returns {Escapee}
     */
    rotate(ccw = false) {
        const keys = Object.keys(Escapee.DIRECTIONS);
        let index = keys.indexOf(this.direction);
        index += !ccw ? 1 : -1;
        if (index >= keys.length) {
            index = 0;
        }
        if (index < 0) {
            index = keys.length - 1;
        }
        this.direction = keys[index];
        return this;
    }

    /**
     * Move in the current facing direction.
     * @returns {boolean|Escapee} True if reached end, false if impossible move or existing move, itself otherwise.
     */
    move() {
        let newX = this.pos.x + Escapee.DIRECTIONS[this.direction].x;
        let newY = this.pos.y + Escapee.DIRECTIONS[this.direction].y;

        if (newX < 0 || newX >= this.map.length || newY < 0 || newY >= this.map.length || this.map[newY][newX] === '#') {
            return false;
        }

        if (this.path.some(r => r.startsWith(`${newX},${newY},`))) {
            return false;
        }

        const key = `${newX},${newY},${this.direction}`;

        this.path.push(key);

        this.score += 1;
        if (newX === this.end.x && newY === this.end.y) {
            this.path.pop();
            return true;
        }
        this.pos.x = newX;
        this.pos.y = newY;
        return this;
    }

    visualize() {
        const maze = this.map.map(y => [...y]);
        for (const path of this.path) {
            const [x, y, dir] = path.split(",");
            maze[y][x] = dir;
        }
        return maze.map(y => y.join("")).join("\n");
    }
}

const map = simulateMapState(
    input,
    mazeSize,
    bytesReadPartOne,
);

const ourEscapee = new Escapee(map, 0, 0, map.length-1, map.length-1);

const logger = new class {
    successes = 0;
    failures = 0;
    queued = 1;
    last = 0;
    ops = 0;
    bytes = bytesReadPartOne;
    lOps = 0;
    /** @param {Escapee} input */
    write(input) {
        const curTs = new Date().getTime();
        if (curTs - this.last > 1000) {
            process.stdout.clearLine(0);
            process.stdout.cursorTo(0);
            const parts = [];
            parts.push(`queued=${this.queued}`);
            parts.push(`successes=${this.successes}`);
            parts.push(`failures=${this.failures}`);
            parts.push(`current_escapee_steps=${input.score}`);
            parts.push(`bytes=${this.bytes}`);
            parts.push(`ops/s=${this.ops - this.lOps}`);
            this.lOps = this.ops;
            process.stdout.write(parts.join(' '));
            this.last = curTs;
        }
    }
}

const queue = new class {
    /** @type {{element: Escapee, priority: number}[]} */
    elements = [];

    /**
     * @param {Escapee} element
     * @param {number} priority
     */
    enqueue(element, priority) {
        this.elements.push({ element, priority });
        this.elements.sort((a, b) => a.priority - b.priority);
    }

    /** @returns {Escapee} */
    dequeue() {
        return this.elements.shift().element;
    }

    /** @returns {boolean} */
    isEmpty() {
        return this.elements.length === 0;
    }
}

/**
 * @param {boolean} stopOnFirst
 * @returns {Escapee[]}
 */
const solveMaze = (stopOnFirst = false) => {
    /** @type {Escapee[]} */
    const successful = [];

    queue.enqueue(ourEscapee, 0);
    /** @type {Map<`${number},${number}.${keyof Escapee.DIRECTIONS}`, number>} */
    const minScores = new Map();

    while (!queue.isEmpty()) {
        const Escapee = queue.dequeue();
        logger.queued = queue.elements.length;
        logger.ops += 1;
        logger.write(Escapee);

        const stateKey = `${Escapee.pos.x},${Escapee.pos.y},${Escapee.direction}`;
        if (minScores.has(stateKey) && minScores.get(stateKey) <= Escapee.score) {
            continue;
        }
        minScores.set(stateKey, Escapee.score);

        const newEscapees = [
            Escapee.clone(),
            Escapee.clone().rotate(),
            Escapee.clone().rotate(true),
        ];

        for (const splitEscapee of newEscapees) {
            const result = splitEscapee.move();
            if (result === true) {
                logger.successes += 1;
                successful.push(splitEscapee);
                if (stopOnFirst) {
                    return successful;
                }
                continue;
            }

            if (result === false) {
                logger.failures += 1;
                continue;
            }

            queue.enqueue(splitEscapee, splitEscapee.score);
        }
    }

    return successful;
}

const successfulEscapees = solveMaze();
const answerOne = Math.min(...successfulEscapees.map(r => r.score));

process.stdout.clearLine(0);
process.stdout.cursorTo(0);
console.log(
    `Part One: ${answerOne}`
);

for (let i = bytesReadPartOne; i <= input.split("\n").length; i += 1) {
    logger.bytes = i;
    const mapAtTime = simulateMapState(
        input,
        mazeSize,
        i,
    );
    ourEscapee.map = mapAtTime;
    queue.enqueue(ourEscapee, 0);
    const result = solveMaze(true);
    if (result.length === 0) {
        process.stdout.clearLine(0);
        process.stdout.cursorTo(0);
        console.log(`Part Two: ${input.split("\n")[i-1]}`);
        break;
    }
}