Skip to content

Instantly share code, notes, and snippets.

@likev
Last active October 26, 2023 15:23
Show Gist options
  • Save likev/34d9b434de9420ff118b04f99fe9bed3 to your computer and use it in GitHub Desktop.
Save likev/34d9b434de9420ff118b04f99fe9bed3 to your computer and use it in GitHub Desktop.
https://matrix67.itch.io/this-is-math Color one of the circles in each row red, so that when the nemesis starts from the top circle and moves downwards, he can never pass through four or more red circles. While moving downwards, he can only take one step to the left or one step to the right at a time.
{
"is_find": true,
"red_path": [
0,
0,
2,
0,
2,
4,
6
]
}
function generate_paths(height) {
let path = new Array(height).fill(0); //init
const paths = [path];
let level = height - 1,
pos = 0; //start from bottom
while (true) {
pos++; //check right point
if (pos <= path[level - 1] + 1) {
path = JSON.parse(JSON.stringify(path)); //create new path
for (; level < height; level++) { //go to bottom
path[level] = pos;
}
level = height - 1;
//console.log(`level:${level} ${path}`);
paths.push(path);
} else {
level--; //go back
pos = path[level];
}
if (pos + 1 === height) break;
}
return paths;
}
function random_red(height) {
let path = [];
for (let i = 0; i < height; i++) {
const d = Math.floor(Math.random() * (i + 1));
path.push(d)
}
//console.log(path)
return path;
}
function generate_red_paths(height) {
let path = new Array(height).fill(0); //init
const paths = [path];
let level = height - 1,
pos = 0; //start from bottom
while (true) {
pos++; //check right point
if (pos <= level) {
path = JSON.parse(JSON.stringify(path)); //create new path
path[level] = pos;
for (level = level + 1; level < height; level++) { //go to bottom
path[level] = 0;
}
level = height - 1;
//console.log(`level:${level} ${path}`);
paths.push(path);
} else {
if (level === 0) break;
level--; //go back
pos = path[level];
}
}
return paths;
}
function check_pass_through(path, red) {
let pass_through = 0;
for (let i = 0; i < path.length; i++) {
if (path[i] === red[i]) pass_through++;
}
//console.log(pass_through);
return pass_through;
}
function find_red_path(height, max_pass_through) {
const paths = generate_paths(height);
let try_count = 0;
let is_find = false;
let red_paths = generate_red_paths(height);
for (let red_path of red_paths) {
is_find = true;
for (let path of paths) {
let pass_through = check_pass_through(path, red_path);
if (pass_through > max_pass_through) {
is_find = false;
break;
}
}
if (is_find) return {
is_find,
red_path
};
}
return {
is_find
};
}
function find_red_path_random(height, max_pass_through, max_try_count = 1e6) {
const paths = generate_paths(height);
let try_count = 0;
let is_find = false;
let red_paths = generate_red_paths(height);
while (++try_count < max_try_count) {
let red_path = random_red(height);
//console.log(red_path)
is_find = true;
for (let path of paths) {
let pass_through = check_pass_through(path, red_path);
if (pass_through > max_pass_through) {
is_find = false;
break;
}
}
if (is_find) return {
is_find,
red_path
};
}
return {
is_find
};
}
find_red_path_random(7, 3)
//or
find_red_path(7, 3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment