const { readFileSync } = require("fs");

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

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

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

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

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

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

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

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

    /**
     * @param {string[][]} maze
     * @param {Coords} position
     * @param {Coords} end
     * @param {keyof Reindeer.DIRECTIONS} direction
     * @param {string[]} path
     */
    constructor(maze, x, y, endX, endY, direction = ">", path = [], score = 0) {
        this.maze = 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 {Reindeer} */
    clone() {
        return new Reindeer(
            this.maze,
            this.pos.x,
            this.pos.y,
            this.end.x,
            this.end.y,
            this.direction,
            [...this.path],
            this.score
        );
    }

    /**
     * @param {boolean} ccw Counter-clockwise
     * @returns {Reindeer}
     */
    rotate(ccw = false) {
        const keys = Object.keys(Reindeer.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];
        this.score += 1000;
        return this;
    }

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

        if (this.maze[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.maze.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");
    }
}

class Logger {
    successes = 0;
    failures = 0;
    queued = 1;
    ops = 0;
    lOps = 0;

    last = 0;
    start;
    constructor() {
        this.start = new Date().getTime();
        process.stdout.write("\n");
    }
    /** @param {Reindeer} 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_reindeer_score=${input.score}`);
            parts.push(`ops/s=${this.ops - this.lOps}`);
            parts.push(`duration=${Math.round(((curTs - this.start) / 1000) * 100) / 100}s`);
            this.lOps = this.ops;
            process.stdout.write(parts.join(" "));
            this.last = curTs;
        }
    }
}

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

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

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

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

/**
 * @param {typeof queue} queue
 * @param {number|null} lowestScore
 * @returns {Reindeer[]}
 */
const getReindeers = (queue, lowestScore = null) => {
    const logger = new Logger();
    /** @type {Map<`${number},${number}.${keyof Reindeer.DIRECTIONS}`, number>} */
    const visited = new Map();
    /** @type {Reindeer[]} */
    const matches = [];

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

        if (lowestScore !== null && reindeer.score > lowestScore) {
            continue;
        }

        const stateKey = `${reindeer.pos.x},${reindeer.pos.y},${reindeer.direction}`;
        if (visited.has(stateKey)) {
            const visitedScore = visited.get(stateKey);
            if (lowestScore === null && visitedScore <= reindeer.score) {
                continue;
            } else if (lowestScore !== null && visitedScore < reindeer.score) {
                continue;
            }
        }
        visited.set(stateKey, reindeer.score);

        const newDeer = [
            reindeer.clone(),
            reindeer.clone().rotate(),
            reindeer.clone().rotate(true),
        ];

        for (const splitDeer of newDeer) {
            const result = splitDeer.move();
            if (result === true) {
                logger.successes += 1;
                matches.push(splitDeer);
                continue;
            }

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

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

    logger.last = 0;
    logger.write(matches[matches.length - 1]);

    return matches;
};

const main = () => {
    const input = readFileSync(0).toString();
    const maze = input.split("\n").map((y) => y.split(""));

    const theFirstReindeer = new Reindeer(
        maze,
        maze[maze.findIndex((y) => y.includes("S"))].indexOf("S"),
        maze.findIndex((y) => y.includes("S")),
        maze[maze.findIndex((y) => y.includes("E"))].indexOf("E"),
        maze.findIndex((y) => y.includes("E"))
    );

    queue.enqueue(theFirstReindeer, 0);
    const successfulReindeer = getReindeers(queue);
    const answerOne = Math.min(...successfulReindeer.map((r) => r.score));

    // if you want to visualize the maze, uncomment this
    // console.log(
    //     successfulReindeer.find(r => r.score === answer).visualize()
    // );

    process.stdout.write("\n");
    console.log(`Part One: ${answerOne}`);

    queue.enqueue(theFirstReindeer, 0);
    queue.flipped = true;
    /** @type {Reindeer[]} */
    const bestReindeer = getReindeers(queue, answerOne);

    const oMaze = maze.map((y) => [...y].map((s) => (["S", "E"].includes(s) ? "O" : s)));
    for (const reindeer of bestReindeer) {
        for (const path of reindeer.path) {
            const [x, y] = path.split(",");
            oMaze[y][x] = "O";
        }
    }

    // if you want to view the optimized seating map
    // console.log(oMaze.map(y => y.join("")).join("\n"));

    const answerTwo = oMaze.reduce(
        (acc, y) => acc + y.filter((s) => s === "O").length,
        0
    );

    process.stdout.write("\n");
    console.log(`Part Two: ${answerTwo}`);
};

main();