Skip to content

Instantly share code, notes, and snippets.

@jeresig
Created December 27, 2016 21:15
Show Gist options
  • Save jeresig/dd6bcb65e879bf1aae7a484d04e74ab7 to your computer and use it in GitHub Desktop.
Save jeresig/dd6bcb65e879bf1aae7a484d04e74ab7 to your computer and use it in GitHub Desktop.
Super-hacky solver for the "Gopher Holes" puzzle: http://amzn.to/2hqLO2V
/**
* Super-hacky solver for the "Gopher Holes" puzzle:
* http://amzn.to/2hqLO2V
*
* Note: I assumed that the blocks would be going vertically in one direction
* and horizontally in another.
*
* Also: I wrote this for fun over the holidays - I'm sure this code is
* terrible and could be improved. It was good enough for my needs!
*
* By John Resig <[email protected]>
* License: Public Domain
*/
const blocks = [
// Duplicates
{
top: [-1, 1, 0],
bottom: [-1, 0, 1],
},
{
top: [-1, 1, 0],
bottom: [-1, 0, 1],
},
// Others
{
top: [1, -1, 0],
bottom: [0, -1, 1],
},
{
top: [1, 0, 0],
bottom: [0, 1, 1],
},
{
top: [1, -1, -1],
bottom: [0, -1, -1],
},
{
top: [1, 0, 1],
bottom: [0, 1, 0],
},
];
const numBlocks = blocks.length;
const numOptions = 4;
const options = [];
const initialArray = [];
const allOptions = [];
const optionNames = ["top", "bottom", "top reversed", "bottom reversed"];
let count = 1;
for (const block of blocks) {
options.push([
block.top,
block.bottom,
block.top.slice(0).reverse(),
block.bottom.slice(0).reverse(),
]);
}
// From: https://stackoverflow.com/questions/9960908/permutations-in-javascript/37580979#37580979
function* permute(permutation) {
const length = permutation.length;
const c = Array(length).fill(0);
let i = 1;
yield permutation;
while (i < length) {
if (c[i] < i) {
const k = (i % 2) ? c[i] : 0;
const p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
yield permutation;
} else {
c[i] = 0;
++i;
}
}
}
function* genOptions() {
const max = Math.pow(numOptions, numBlocks);
for (let i = 0; i < max; i++) {
yield ("000000" + (i).toString(4)).slice(-6).split("");
}
}
function check(posA, posB) {
return (posA !== 1 && posB !== 1 || posA === -1 && posB === 1 ||
posA === 1 && posB === -1);
}
for (let num = 0; num < numBlocks; num++) {
initialArray.push(num);
}
for (const option of genOptions()) {
allOptions.push(option);
}
// Go through all of the possible block options
for (const permutation of permute(initialArray)) {
for (const option of allOptions) {
count += 1;
const bottom = [
options[permutation[0]][option[0]],
options[permutation[1]][option[1]],
options[permutation[2]][option[2]],
];
const top = [
options[permutation[3]][option[3]],
options[permutation[4]][option[4]],
options[permutation[5]][option[5]],
];
if (check(bottom[0][0], top[0][0]) &&
check(bottom[1][0], top[0][1]) &&
check(bottom[2][0], top[0][2]) &&
check(bottom[0][1], top[1][0]) &&
check(bottom[1][1], top[1][1]) &&
check(bottom[2][1], top[1][2]) &&
check(bottom[0][2], top[2][0]) &&
check(bottom[1][2], top[2][1]) &&
check(bottom[2][2], top[2][2])) {
console.log("MATCH");
console.log("BOTTOM:",
permutation[0], optionNames[option[0]],
permutation[1], optionNames[option[1]],
permutation[2], optionNames[option[2]]);
console.log(bottom[0][0], bottom[1][0], bottom[2][0]);
console.log(bottom[0][1], bottom[1][1], bottom[2][1]);
console.log(bottom[0][2], bottom[1][2], bottom[2][2]);
console.log("TOP:",
permutation[3], optionNames[option[3]],
permutation[4], optionNames[option[4]],
permutation[5], optionNames[option[5]]);
console.log(top[0][0], top[0][1], top[0][2]);
console.log(top[1][0], top[1][1], top[1][2]);
console.log(top[2][0], top[2][1], top[2][2]);
}
}
}
console.log("Checked:", count);
$ time node block-puzzle.js
...
MATCH
BOTTOM: 3 top reversed 2 bottom reversed 1 bottom reversed
0 1 1
0 -1 0
1 0 -1
TOP: 4 bottom 5 bottom reversed 0 bottom
0 -1 -1
0 1 0
-1 0 1
Checked: 2949121
real 0m0.547s
user 0m0.515s
sys 0m0.034s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment