Skip to content

Instantly share code, notes, and snippets.

@dpchamps
Last active January 27, 2023 06:40
Show Gist options
  • Save dpchamps/58f3da6ec2e827c52b89875317e19b47 to your computer and use it in GitHub Desktop.
Save dpchamps/58f3da6ec2e827c52b89875317e19b47 to your computer and use it in GitHub Desktop.
const getNextMoves = (x, y) => ([
[x+3, y, '⇒'],
[x, y-3, '⇑'],
[x-3, y, '⇐'],
[x, y+3, '⇓'],
[x+2, y+2, '⇘'],
[x-2, y-2, '⇖'],
[x-2, y+2, '⇙'],
[x+2, y-2, '⇗']
]);
const isValidMove = (previousMoves, x, y) => {
if(previousMoves.includes(`${x},${y}`)) return false;
return (x >= 0 && x <= 9) && (y >= 0 && y <= 9)
};
const solve = (x, y, previousMoves, directions = []) => {
if(previousMoves.length === 100) return [previousMoves, directions];
for(const [nextX, nextY, direction] of getNextMoves(x, y)) {
if(!isValidMove(previousMoves, nextX, nextY)) {
continue;
}
previousMoves.push(`${nextX},${nextY}`);
directions.push(direction)
let result = solve(nextX, nextY, previousMoves, directions);
if(result) return result;
previousMoves.pop();
directions.pop()
}
return false;
}
const [movelist ,directions] = solve(0, 0, [`0,0`]);
console.log(directions.map((x, i) => `${i+1}:${x}`).join("\n"))
console.log({movelist})
const list = [
'0,0', '3,0', '6,0', '9,0', '9,3', '6,3', '3,3', '0,3',
'0,6', '3,6', '6,6', '9,6', '9,9', '6,9', '3,9', '0,9',
'2,7', '5,7', '8,7', '8,4', '8,1', '5,1', '2,1', '2,4',
'5,4', '7,6', '7,3', '7,0', '4,0', '1,0', '1,3', '4,3',
'4,6', '1,6', '1,9', '4,9', '7,9', '9,7', '9,4', '9,1',
'6,1', '3,1', '0,1', '0,4', '3,4', '6,4', '6,7', '3,7',
'0,7', '2,9', '5,9', '8,9', '8,6', '8,3', '8,0', '5,0',
'2,0', '2,3', '5,3', '3,5', '6,5', '9,5', '9,8', '6,8',
'3,8', '0,8', '0,5', '0,2', '3,2', '6,2', '9,2', '7,4',
'7,1', '4,1', '1,1', '1,4', '1,7', '4,7', '7,7', '5,5',
'5,2', '8,2', '8,5', '8,8', '5,8', '2,8', '2,5', '2,2',
'4,4', '2,6', '5,6', '7,8', '7,5', '7,2', '4,2', '1,2',
'1,5', '4,5', '4,8', '1,8'
]
const sleep = (ms) => new Promise((res) => setTimeout(res, ms));
const drive = async (movelist) => {
for(const move of movelist){
const [x,y] = move.split(",")
document.getElementById(`${y}_${x}`).click();
await sleep(150);
}
}
drive(list).catch(console.error)
const GAME_BOARD_SIZE = process.env['BOARD_SIZE'] || 10;
const getNextMoves = (x, y) => ([
[x+3, y],
[x, y-3],
[x-3, y],
[x, y+3],
[x+2, y+2],
[x-2, y-2],
[x-2, y+2],
[x+2, y-2]
]);
const randomBetween = (min = 0, max = 0) => {
return Math.floor(Math.random() * (max+1 - min) + min);
}
const randomXY = () => [randomBetween(0, GAME_BOARD_SIZE-1), randomBetween(0, GAME_BOARD_SIZE-1)];
const isValidMove = (x, y, board) => {
if(board[y*GAME_BOARD_SIZE+x]) return false;
return (x >= 0 && x <= GAME_BOARD_SIZE-1) && (y >= 0 && y <= GAME_BOARD_SIZE-1)
};
const getDegree = (x, y, board) => {
let count = 0;
for(const[nextX, nextY] of getNextMoves(x, y)){
if(isValidMove(nextX, nextY, board)){
count += 1;
}
}
return count;
}
const solve = (x, y, previousMoves, board) => {
previousMoves.push(`${x},${y}`);
board[y*GAME_BOARD_SIZE+x] = 1;
if(previousMoves.length === GAME_BOARD_SIZE*GAME_BOARD_SIZE){
return previousMoves
}
const nextPositions = getNextMoves(x, y).filter(([nextX, nextY]) => isValidMove(nextX, nextY, board));
const [minimumDegree] = nextPositions.sort(([xA, yA], [xB, yB]) => getDegree(xA, yA, board) - getDegree(xB, yB, board));
const [nextX, nextY] = minimumDegree;
return solve(nextX, nextY, previousMoves, board);
}
const [x, y] = randomXY();
const result = solve(x, y, [], Array(GAME_BOARD_SIZE*GAME_BOARD_SIZE).fill(0));
console.log(result)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment