Created
June 18, 2020 00:37
-
-
Save bojidar-bg/1142c341be5bdd1a9117fcd6e6f85ae9 to your computer and use it in GitHub Desktop.
BOXit solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment