BOXit solver

boxit-solver.js

// This file is made available under the GPLv3 LICENSE
// For more info, see https://www.gnu.org/licenses/gpl-3.0.html
// Based on ideas presented in https://hatnix.itch.io/boxit

function main() {

    // HGrid format:
    // All whitespace is ignored.
    // Other characters represent tuples of color and symbol
    // Colors are [w]hite/[r]ed, [b]lue, [g]reen, [o]range/[y]ellow, [p]urple/pink

    // Grid format:
    // There is no whitespace; the whole grid is represented as a string of 25 lowercase a-z letters.
    // The letters correspond to numbers and colors based on the following table:
    // 12345
    // .....
    // abcde: White/red
    // fghij: Blue
    // klmno: Green
    // pqrst: Orange/yellow
    // uvwxy: Purple/pink
    // z is empty space.
    
    var input = readlineSync && readlineSync('Enter grid data [Grid/HGrid, empty for random]: ')
    var grid
    
    if (!input) {
        grid = createGrid()
    } else if (input.length == gridSize) {
        grid = input.toLowerCase() // udjvgeywxblapmcnqostrhfki
    } else {
        while (input.replace(/\s|_/g, '').length < gridSize * 2)
            input += readlineSync('Enter additional HGrid data: ') || '*'.repeat(gridSize * 2);
        grid = parseHGrid(input)
        /*
        p1 w4 b5 p2 b2
        w5 p5 p3 p4 w2
        g2 w1 o1 g3 w3
        g4 o2 g5 o4 o5
        o3 b3 b1 g1 b4
        */
    }
    console.log(`--- ${grid}`)

    for (let s of getSolutions(grid)) {
        console.log(`--- ${grid}\n${prettyGrid(grid)}`)
        for (let [f, t, g] of s) {
            console.log(`--- ${g} ${prettyPos(f)} ${prettyPos(t)}\n${prettyGrid(g, {[f]: true, [t]: true})}`)
        }
        break
    }
}

// Constants

var clc = undefined
if (typeof require != 'undefined' && !(typeof process != 'undefined' && process.argv.indexOf('--raw') != -1)) {
    try {
        clc = require('cli-color')
    } catch (e) {
        // pass
    }
}

var readlineSync = undefined
if (typeof prompt != 'undefined') {
    readlineSync = prompt
}
if (typeof require != 'undefined' && !(typeof process != 'undefined' && process.argv.indexOf('--debug') != -1)) {
    try {
        readlineSync = require('readline-sync').question
    } catch (e) {
        // pass
    }
}

const assert = (x) => {if(!x()) throw 'Failed:', x.toString()}

const tokenSymbols = 5
const tokenColors = 5
const gridRows = tokenColors
const gridSize = tokenSymbols * tokenColors
const tokenEmpty = 'z'
const tokenOffset = 'a'.charCodeAt()
const emptyGrid = tokenEmpty.repeat(gridSize)

// Printing utilities

const colorFunctions = clc ? [clc.bgWhite.black, clc.bgBlue.black, clc.bgGreen.black, clc.bgYellow.black, clc.bgMagentaBright.black] : 'wbgop'.split('').map(c => x => ` ${c}${x} `)
const colorHighlightedFunctions = clc ? [clc.bgWhite.red, clc.bgBlue.red, clc.bgGreen.red, clc.bgYellow.red, clc.bgMagentaBright.red]  : 'wbgop'.split('').map(c => x => `_${c}${x}_`)
const symbolsStrings = clc ? ['   ', '[1]', '[2]', '[3]', '[4]', '[5]'] : ['    ', '1', '2', '3', '4', '5']
const symbolsHighlightedStrings = clc ? [' * ', '{1}', '{2}', '{3}', '{4}', '{5}'] : [' ** ', '1', '2', '3', '4', '5']

assert(() => colorFunctions.every(x => typeof x == 'function'))
assert(() => symbolsStrings.every(x => typeof x == 'string'))
assert(() => symbolsHighlightedStrings.every(x => typeof x == 'string'))

function prettyToken(token, h) {
    if (token == tokenEmpty) return (h ? symbolsHighlightedStrings : symbolsStrings)[0]
    let n = token.charCodeAt() - tokenOffset
    return (h ? colorHighlightedFunctions : colorFunctions)[(n / tokenColors) | 0]((h ? symbolsHighlightedStrings : symbolsStrings)[(n % tokenColors) + 1])
}

function prettyPos(n) {
    return '(' + (((n / gridRows) | 0) + 1) + '-' + (n % gridRows + 1) + ')';
}

function prettyGrid(grid, h = {}) {
    let result = ''
    for (let i = 0; i < gridSize; i += gridRows) {
        for (let j = i; j < Math.ceil(i / gridRows + 1) * gridRows; j ++) {
            result += prettyToken(grid[j], h[j]);
        }
        result += '\n'
    }
    return result.slice(0, -1)
}

// Board Generation / Parsing

function shuffle(array) { // https://bost.ocks.org/mike/shuffle/
    var m = array.length, t, i;
    while (m) {
        i = Math.floor(Math.random() * m);
        m -= 1;
        t = array[m];
        array[m] = array[i];
        array[i] = t;
    }

    return array;
}

function createGrid() { // Based on simplified pico code in https://hatnix.itch.io/boxit
    return shuffle(Array(gridSize).fill().map((_, i) => i)).map(x => String.fromCharCode(x + tokenOffset)).join('')
}

function parseHGrid(hgrid) {
    hgrid = hgrid.replace(/\s|_/g, '').toLowerCase()
    let c = 'wbgop'
    let m = {'r': 'w', 'y': 'o'}
    let s = '12345'
    let r = ''
    for (let i = 0; i < gridSize * 2; i += 2) {
        r += String.fromCharCode(c.indexOf(m[hgrid[i]] || hgrid[i]) * tokenSymbols + s.indexOf(hgrid[i + 1]) + tokenOffset)
    }
    return r
}

// Game logic

function tokensMatch(tokenA, tokenB) {
    let a = tokenA.charCodeAt() - tokenOffset
    let b = tokenB.charCodeAt() - tokenOffset
    return ((a / tokenColors) | 0) == ((b / tokenColors) | 0) || (a % tokenColors) == (b % tokenColors)
}

assert(() => tokensMatch(String.fromCharCode(0 + tokenOffset), String.fromCharCode(1 + tokenOffset)))
assert(() => tokensMatch(String.fromCharCode(0 + tokenOffset), String.fromCharCode(0 + tokenSymbols + tokenOffset)))
assert(() => !tokensMatch(String.fromCharCode(0 + tokenOffset), String.fromCharCode(1 + tokenSymbols + tokenOffset)))

function* getPossibleMoves(grid) {
    for (let i = 0; i < gridSize; i ++) if (grid[i] != tokenEmpty) {
        for (let j = i + 1; j < Math.ceil((i + 1) / gridRows) * gridRows; j ++) if (grid[j] != tokenEmpty) {
            if (tokensMatch(grid[i], grid[j])) {
                yield [i, j, grid.replace(grid[i], tokenEmpty).replace(grid[j], grid[i])]
                yield [j, i, grid.replace(grid[j], tokenEmpty).replace(grid[i], grid[j])]
            }
        }
        for (let j = i + gridRows; j < gridSize; j += gridRows) if (grid[j] != tokenEmpty) {
            if (tokensMatch(grid[i], grid[j])) {
                yield [i, j, grid.replace(grid[i], tokenEmpty).replace(grid[j], grid[i])]
                yield [j, i, grid.replace(grid[j], tokenEmpty).replace(grid[i], grid[j])]
            }
        }
    }
}

function isCompleted(grid) {
    let t = 0
    for (let i = 0; i < gridSize; i ++) if (grid[i] != tokenEmpty) {
        t++        
    }
            
    return t == 1
}

// Simple DFS solver, with an explicit stack

function* getSolutions(initialGrid) {
    var previous = {}
    var grids = [initialGrid]
    
    while (grids.length > 0) {
        let grid = grids.pop()
            
        for (let [f, t, g] of getPossibleMoves(grid)) {
            if (!previous[g]) {
                previous[g] = [grid, f, t]
                if (isCompleted(g)) { // Win!!!
                    let path = []
                    let r = g
                    while (previous[r]) {
                        let [nr, pf, pt] = previous[r]
                        path.push([pf, pt, r])
                        r = nr
                    }
                    path.reverse()
                    yield path
                } else {
                    grids.push(g)
                }
            }
        }
    }
}

main()