const fs = require("fs");

const alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

function reps(x, n) {
    return new Array(n).fill(x);
}

class Shift {
    constructor(dir, ind) {
        this.dir = dir;
        this.ind = ind;
    }

    serialize(len) {
        if (this.dir == "l") {
            return reps(alpha[this.ind], 1);
        }
        if (this.dir == "r") {
            return reps(alpha[this.ind], len - 1);
        }
        if (this.dir == "u") {
            return reps(this.ind.toString(), 1);
        }
        if (this.dir == "d") {
            return reps(this.ind.toString(), len - 1);
        }
    }
}

function serializeShifts(arr, len) {
    return arr.flatMap(v => v.serialize(len)).join`,`.replace(new RegExp(String.raw`(\w+),(?:\1,){${len - 1}}`, "g"), "");
}

class Point {
    constructor(r, c) {
        this.r = r;
        this.c = c;
    }

    withRow(r) {
        return new Point(r, this.c);
    }

    withColumn(c) {
        return new Point(this.r, c);
    }

    shiftedHoriz(x) {
        return this.withColumn(this.c + x);
    }

    shiftedVert(x) {
        return this.withRow(this.r + x);
    }

    shiftedHorizMod(x, m) {
        return this.withColumn((this.c + x) % m);
    }

    shiftedVertMod(x, m) {
        return this.withRow((this.r + x) % m);
    }

    equals(p) {
        return this.r == p.r && this.c == p.c;
    }
}

// find an element e in 2d array arr
function find2d(arr, e) {
    for (let i = 0; i < arr.length; i ++) {
        for (let j = 0; j < arr[i].length; j ++) {
            if (arr[i][j] == e) {
                return new Point(i, j);
            }
        }
    }
    return null;
}

let yeet = 0;

class Board {
    constructor(arr) {
        this.nums = arr;
        this.len = arr.length;
        this.ins = [];
        this.last = this.len - 1;
        let i = 0;
        this.final = new Array(this.len).fill(0).map(v => new Array(this.len).fill(0).map(k => i ++));
    }

    // find where the number n should go
    dest(n) {
        return find2d(this.final, n);
    }

    // find what number should be a point p
    desired(p) {
        return this.final[p.r][p.c];
    }

    at(p) {
        return this.nums[p.r][p.c];
    }

    // find the point where n is located
    find(n) {
        return find2d(this.nums, n);
    }

    // find what point should end up at p
    findDesired(p) {
        return this.find(this.desired(p));
    }

    isDesired(p) {
        return p.equals(this.findDesired(p));
    }

    isFinished() {
        for (let i = 0; i < this.len; i ++) {
            for (let j = 0; j < this.len; j ++) {
                if (!this.isDesired(new Point(i, j))) {
                    return false;
                }
            }
        }
        return true;
    }

    clearIns() {
        this.ins = [];
    }

    makeShift(shift) {
        if (shift.dir == "l") {
            return this.shiftLeft(shift.ind);
        }
        if (shift.dir == "r") {
            return this.shiftRight(shift.ind);
        }
        if (shift.dir == "u") {
            return this.shiftUp(shift.ind);
        }
        if (shift.dir == "d") {
            return this.shiftDown(shift.ind);
        }
    }

    shiftLeft(ind) {
        this.ins.push(new Shift("l", ind));
        this.nums[ind].push(this.nums[ind].shift());
        return this;
    }

    shiftRight(ind) {
        this.ins.push(new Shift("r", ind));
        this.nums[ind].unshift(this.nums[ind].pop());
        return this;
    }

    shiftUp(ind) {
        this.ins.push(new Shift("u", ind));
        const top = this.nums[0][ind];
        for (let i = 0; i < this.last; i ++) {
            this.nums[i][ind] = this.nums[i + 1][ind];
        }
        this.nums[this.last][ind] = top;
        return this;
    }

    shiftDown(ind) {
        this.ins.push(new Shift("d", ind));
        const bottom = this.nums[this.last][ind];
        for (let i = this.last; i > 0; i --) {
            this.nums[i][ind] = this.nums[i - 1][ind];
        }
        this.nums[0][ind] = bottom;
        return this;
    }

    pointLeft(p) {
        return this.shiftLeft(p.r);
    }

    pointRight(p) {
        return this.shiftRight(p.r);
    }

    pointUp(p) {
        return this.shiftUp(p.c);
    }

    pointDown(p) {
        return this.shiftDown(p.c);
    }

    // move point p horizontally to column c with only left shifts
    pointHoriz(p, c) {
        const diff = p.c - c;
        let shifts = 0;
        if (diff > 0) {
            shifts = diff;
        }
        if (diff < 0) {
            shifts = p.c + this.len - c;
        }
        for (let i = 0; i < shifts; i ++) {
            this.shiftLeft(p.r);
        }
        return this;
    }

    // move point p vertically to row r with only up shifts
    pointVert(p, r) {
        const diff = p.r - r;
        let shifts = 0;
        if (diff > 0) {
            shifts = diff;
        }
        if (diff < 0) {
            shifts = p.r + this.len - r;
        }
        for (let i = 0; i < shifts; i ++) {
            this.shiftUp(p.c);
        }
        return this;
    }

    // insert point p into row r using the last column
    insertRow(p, r) {
        const val = this.at(p);
        if (p.r == r && p.c != this.last) {
            // annoying case where you first have to get the point out
            const reference = this.at(p.withColumn(this.last));
            // shift to last column then shift down to remove from row
            this.pointHoriz(p, this.last);
            this.pointDown(this.find(val));
            this.pointHoriz(this.find(reference), this.last); // restore reference point
        }
        // load the point into the rightmost tile in the row
        this.pointHoriz(this.find(val), this.last);
        this.pointVert(this.find(val), r);
        // slide it in
        this.pointLeft(this.find(val));
        return this;
    }

    // put every piece in row r in the correct place except for the one in the last column
    solveRow(r) {
        for (let i = 0; i < this.last; i ++) {
            this.insertRow(this.findDesired(new Point(r, i)), r);
        }
        return this;
    }

    // solve the (n - 1)x(n - 1) square starting at the top left
    solveSmallSquare() {
        for (let i = 0; i < this.last; i ++) {
            this.solveRow(i);
        }
        return this;
    }

    // insert point p into the last column using the bottom row
    insertLastColumn(p) {
        const val = this.at(p);
        if (p.c == this.last && p.r != this.last) {
            // annoying case where you first have to get the point out;
            const reference = this.at(p.withRow(this.last));
            // shift to last row then shift left to remove from column
            this.pointVert(p, this.last);
            this.pointLeft(this.find(val));
            this.pointVert(this.find(reference), this.last);
        }
        // load the point into the bottom right corner
        this.pointHoriz(this.find(val), this.last);
        // slide it in
        this.pointUp(this.find(val));
        return this;
    }

    // solve the last column except for the last two rows
    solveLastColumn() {
        for (let i = 0; i < this.len - 2; i ++) {
            this.insertLastColumn(this.findDesired(new Point(i, this.last)));
        }
        this.shiftUp(this.last);
        return this;
    }

    // insert the tile in the lower insertion slot to the correct place (last column, penultimate row)
    lowerInsertion() {
        const p = new Point(this.last - 1, this.last);
        const val = this.at(p);
        let loc;
        if (this.isDesired(p)) {
            // annoying case where you just insert into an out-of-place tile
            let broken = false;
            for (let i = 0; i < this.len; i ++) {
                if (!this.isDesired(new Point(this.last, i))) {
                    loc = new Point(this.last, i);
                    broken = true;
                    break;
                }
            }
            if (!broken) {
                return false;
            }
        } else {
            loc = this.dest(val);
        }
        const refC = (loc.c + 1) % this.len;
        const reference = this.at(new Point(this.last, refC));
        // move tile over and insert down
        this.pointHoriz(loc, this.last);
        this.shiftDown(this.last);
        this.pointHoriz(this.find(reference), refC); // restore reference point
        return true;
    }

    // insert the tile in the upper insertion slot to the correct place (top right corner)
    upperInsertion() {
        const p = new Point(0, this.last);
        const val = this.at(p);
        let loc = this.dest(val);
        if (loc.equals(new Point(this.last - 1, this.last))) {
            // annoying case where you just insert into an out-of-place tile
            let broken = false;
            for (let i = 0; i < this.len; i ++) {
                if (!this.isDesired(new Point(this.last, i))) {
                    loc = new Point(this.last, i);
                    broken = true;
                    break;
                }
            }
            if (!broken) {
                return false;
            }
        }
        const refC = (loc.c + 1) % this.len;
        const reference = this.at(new Point(this.last, refC));
        // move tile over and insert up
        this.pointHoriz(loc, this.last);
        this.shiftUp(this.last);
        this.pointHoriz(this.find(reference), refC); // restore reference point
        return true;
    }

    isParity() {
        if (this.len % 2 == 1) {
            return false;
        }
        let wrong = 0;
        for (let i = 0; i < this.len; i ++) {
            for (let j = 0; j < this.len; j ++) {
                if (!this.isDesired(new Point(i, j))) {
                    wrong ++;
                }
            }
        }
        return wrong == 2;
    }

    // solve the remaining part
    solveOther() {
        let looping = true;
        let upper = false;
        while (!this.isFinished()) {
            if (upper) {
                looping = this.upperInsertion();
            } else {
                looping = this.lowerInsertion();
            }
            // check for parity
            if (upper && !looping) {
                console.log("doing parity");
                for (let i = 0; i < this.len / 2; i ++) {
                    this.shiftLeft(this.last).shiftUp(this.last).shiftLeft(this.last).shiftDown(this.last);
                }
                this.shiftLeft(this.last);
                //this.shiftUp(this.last);
                looping = true;
            }
            upper = !upper;
        }
        return this;
    }

    solve() {
        this.solveSmallSquare();
        this.solveLastColumn();
        this.solveOther();
        return this;
    }

    serializeShifts() {
        return serializeShifts(this.ins, this.len);
    }
}

let board = new Board(fs.readFileSync("board.txt", "utf8").split`\n`.slice(1).map(v => v.match(/\d+/g).map(x => +x)));
//console.log(JSON.stringify(board.solve().ins.map(i => ({dir: i.dir, ind: i.ind}))));
board.solve();
console.log(board.serializeShifts());
const ilen = board.ins.length;
const rev = [];
for (let i = 0; i < ilen; i ++) {
    const ins = board.ins[ilen - i - 1];
    let newdir;
    if (ins.dir == "l") {
        newdir = "r";
    } else if (ins.dir == "r") {
        newdir = "l";
    } else if (ins.dir == "u") {
        newdir = "d";
    } else if (ins.dir == "d") {
        newdir = "u";
    }
    rev.push(new Shift(newdir, ins.ind));
}
const str = board.serializeShifts() + ",\n" + serializeShifts(rev, board.len) + ",";
const rowMappings = permutator([0, 1, 2, 3]);
const columnMappings = permutator([0, 1, 2, 3]);
let tot = "";
rowMappings.map(r => columnMappings.map(c => tot += (str.replace(/[A-Z]/g, m => alpha[r[alpha.indexOf(m)]]).replace(/\d+/g, m => c[+m]))));
fs.writeFileSync("yeet.txt", tot);