Created
December 27, 2016 21:15
-
-
Save jeresig/dd6bcb65e879bf1aae7a484d04e74ab7 to your computer and use it in GitHub Desktop.
Super-hacky solver for the "Gopher Holes" puzzle: http://amzn.to/2hqLO2V
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
/** | |
* 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); |
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
$ 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