Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Recursive search (DFS) solution in Clear category for [old] Graphical Key by Sim0000
"use strict";
function gKey(grid, path) {
function search(x, y, n, v){
if(n == path){
if(x == gx && y == gy && v > max_v) max_v = v;
return;
}
for(let d of [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]){
const [dx, dy] = d;
const nx = x + dx, ny = y + dy;
if(nx < 0 || xsize <= nx || ny < 0 || ysize <= ny || grid[ny][nx] < 0) continue;
if(Math.max(gx - nx, gy - ny) > path - n) continue;
const nv = grid[ny][nx];
grid[ny][nx] = -1;
search(nx, ny, n + 1, v + nv);
grid[ny][nx] = nv;
}
}
const sum = ary => ary.reduce((a, b) => a + b);
const xsize = grid[0].length, ysize = grid.length;
const gx = xsize - 1, gy = ysize - 1;
if(xsize * ysize == path){
return grid.reduce((acc, row) => acc + sum(row), 0);
}
let max_v = grid[0][0];
grid[0][0] = -1;
search(0, 0, 1, max_v);
return max_v;
}
var assert = require('assert');
if (!global.is_checking) {
console.log('Example:')
console.log(gKey([[1, 6, 7, 2, 4],
[0, 4, 9, 5, 3],
[7, 2, 5, 1, 4],
[3, 3, 2, 2, 9],
[2, 6, 1, 4, 0]], 9))
// These "asserts" are used for self-checking and not for an auto-testing
assert.equal(gKey([[1, 6, 7, 2, 4],
[0, 4, 9, 5, 3],
[7, 2, 5, 1, 4],
[3, 3, 2, 2, 9],
[2, 6, 1, 4, 0]], 9), 46)
assert.equal(gKey([[2, 5, 4, 1, 8],
[0, 4, 9, 5, 3],
[7, 2, 5, 1, 4],
[3, 3, 2, 2, 9],
[2, 6, 1, 4, 1]], 6), 27)
assert.equal(gKey([[1, 2, 3, 4, 5],
[2, 3, 4, 5, 1],
[3, 4, 5, 1, 2],
[4, 5, 1, 2, 3],
[5, 1, 2, 3, 4]], 25), 75)
assert.equal(gKey([[1, 6],
[5, 1]], 2), 2)
console.log("Coding complete? Click 'Check' to earn cool rewards!");
}
Oct. 1, 2018