Fancade Fixel Solver

fancade-fixel.ts

// Solver for fancade "Fixel" game in which you position pixel puzzle pieces on a grid without rotation.
// There is one particularly difficult puzzle on World 17: "21. Orange"

type Grid = number[];
type Puzzle = { board: Grid, pieces: Grid[] };

// calculates width of grid
function width(grid:Grid): number {
    return Math.max.apply(null, grid.map(row => Math.floor(1 + Math.log(row) / Math.log(2))));
}

// returns a new, moved piece
function move(piece:Grid, dx:number, dy:number): Grid {
    return Array(dy).fill(0).concat(piece.map(row => row << dx));
}

// checks if a piece fits on the board
function fits(board:Grid, piece:Grid): boolean {
    return board.length >= piece.length
        && piece.every((row, y) => (board[y] & row) == row);
}

// gets all possible placements of piece on board
function* placements(board: Grid, piece: Grid): IterableIterator<Grid> {
    let boardWidth = width(board);
    for (let x = 0; x < boardWidth; x++) {
        for (let y = 0; y < board.length; y++) {
            let placement = move(piece, x, y);
            if (fits(board, placement))
                yield placement;
        }
    }
}

// puts piece on grid and returns new grid
function put(board:Grid, piece:Grid): Grid {
    return board.map((row, y) => y < piece.length ? piece[y] ^ row : row);
}

// returns list of solutions, which are arrays of piece placements
function* generateSolutions(board: Grid, used: Grid[], unused: Grid[]): IterableIterator<Grid[]> {
    if (unused.length == 0 && board.every(row => row == 0))
        yield used;
    let [piece, ...others] = unused;
    for (let placement of placements(board, piece))
    {
        yield* generateSolutions(put(board, placement), [...used, placement], others);
    }
}

// generates binary string for visualizing a grid
function gridToBinaryString(grid:Grid): string {
    let w = width(grid);
    return grid.map(row => (1 << 30 | row).toString(2).substring(31-w)).join('\n');
}

// generates binary string for visualizing a solution
function solutionToBinaryString(solution: Grid[]): string {
    return solution.map(gridToBinaryString).join('\n\n');
}

// generates letter grid for pretty-printing a solution
function solutionToLetterGrid(solution: Grid[]): string {
    let boardWidth = Math.max.apply(null, solution.map(width));
    let boardHeight = Math.max.apply(null, solution.map(part => part.length));
    let charCode = "A".charCodeAt(0);
    let output = Array(boardHeight).fill(0).map(row => Array(boardWidth).fill(' '));
    for (let part of solution) {
        let partWidth = width(part);
        for (let y = 0; y < part.length; y++)
            for (let x = 0; x < partWidth; x++)
                if (part[y] & (1 << x))
                    output[y][boardWidth - 1 - x] = String.fromCharCode(charCode);
        charCode++;
    }
    return output.map(a => a.join('')).join('\n');
}

// solves puzzle and prints solution(s)
function solvePuzzle(puzzle: Puzzle, printAll: boolean) {
    let solutions = generateSolutions(puzzle.board, [], puzzle.pieces);
    if (printAll) {
        console.log(Array.from(solutions).map(solutionToLetterGrid).join('\n\n'));
    }
    else {
        console.log(solutionToLetterGrid(solutions.next().value));
    }
}

let orangePuzzle = {
    board: [
        0b0111110,
        0b1111111,
        0b1111111,
        0b1111111,
        0b1111111,
        0b0111110
    ],
    pieces: [
        [0b10, 0b11, 0b10],
        [0b1, 0b1, 0b1],
        [0b11, 0b01],
        [0b111, 0b001],
        [0b11, 0b01, 0b01],
        [0b10, 0b11, 0b01],
        [0b01, 0b11, 0b01],
        [0b011, 0b110],
        [0b1, 0b1, 0b1, 0b1],
        [0b001, 0b111]
    ]
};

solvePuzzle(orangePuzzle, false);

/*
Output:

 HHDDD 
HHJCCDG
JJJICGG
FEEIBAG
FFEIBAA
 FEIBA 
*/