dotgame.js

const width = 7;
const height = 7;
let grid = new Array(width * height);

const WALL = 0;
const DOT = 1;
const EMPTY = 2;

for (let x = 0; x < width; x++) {
    for (let y = 0; y < height; y++) {
        grid[x + y * width] = WALL;
    }
}
const inset = 2;

for (let x = inset; x < width - inset; x++) {
    for (let y = 0; y < height; y++) {
        grid[x + y * width] = DOT;
    }
}

for (let x = 0; x < width; x++) {
    for (let y = inset; y < height - inset; y++) {
        grid[x + y * width] = DOT;
    }
}
let centerX = Math.floor(width / 2);
let centerY = Math.floor(height / 2);
grid[centerX + centerY * width] = EMPTY;


function processPath(grid) {
    let initStatus = calcStatus(grid);
    let newStates = [{grid, lastGrid: null, ser: initStatus.ser, score: initStatus.score}];
    let now = +new Date();
    let closedStates = {};
    let tries = 0;
    let lowestScore = width * height;
    let lowestScoreIndex = 0;

    while (newStates.length > 0) {
        let state = newStates[lowestScoreIndex];
        newStates.splice(lowestScoreIndex, 1);
        closedStates[state.ser] = true;
        let grid = state.grid;
        if (tries++ % 10000 === 0) {
            console.log(newStates.length, Object.keys(closedStates).length, state.score, ((+new Date()) - now) / 10000 + " per try");
            now = +new Date();
            // drawUI(grid)
        }
        processNeighbors(grid, state, newStates, closedStates);


        lowestScore = width * height;
        for (let i = 0; i < newStates.length; i++) {
            if (newStates[i].score < lowestScore) {
                lowestScoreIndex = i;
                lowestScore = newStates[i].score;
            }
        }

        if (lowestScore === 1) {
            if (newStates[lowestScoreIndex].grid[centerX + centerY * width] === DOT) {
                break;
            } else {
                console.log('made it to 1');
                let s = newStates[lowestScoreIndex];
                closedStates[s.ser] = true;
                newStates.splice(0, 1);
            }
        }
    }

    let path = [newStates[lowestScoreIndex].grid];
    let state = newStates[lowestScoreIndex];
    while (state.lastState) {
        path.push(state.lastState.grid);
        state = state.lastState;
    }
    console.log(`${path.length} moves, ${tries} tries`);
    path.reverse();
    return path;
}

function processNeighbors(grid, lastState, newStates, closedStates) {
    for (let x = 0; x < width; x++) {
        for (let y = 0; y < height; y++) {
            if (grid[x + y * width] === EMPTY) {
                let neighbors = getDotNeighbors(grid, x, y);
                for (let i = 0; i < 4; i++) {
                    let neighbor = neighbors[i];
                    if (neighbor.inner === -1) break;

                    let newGrid = grid.slice(0);
                    newGrid[x + y * width] = DOT;
                    newGrid[neighbor.inner] = EMPTY;
                    newGrid[neighbor.outer] = EMPTY;
                    let ser = newGrid.join();

                    if (closedStates[ser]) {
                        continue;
                    }
                    newStates.push({grid: newGrid, lastState: lastState, ser: ser, score: lastState.score - 1});
                }
            }
        }
    }
};


function calcStatus(grid) {
    let score = 0;
    let size = width * height;
    for (let i = 0; i < size; i++) {
        if (grid[i] === DOT) {
            score++;
        }
    }
    return {score, ser: grid.join()};
}


const neighborItems = new Array(4);
neighborItems[0] = {inner: -1, outer: -1};
neighborItems[1] = {inner: -1, outer: -1};
neighborItems[2] = {inner: -1, outer: -1};
neighborItems[3] = {inner: -1, outer: -1};

function getDotNeighbors(grid, x, y) {

    neighborItems[0].inner = -1;
    neighborItems[1].inner = -1;
    neighborItems[2].inner = -1;
    neighborItems[3].inner = -1;
    let count = 0;

    if (x > 1 && grid[(x - 2) + y * width] === DOT && grid[(x - 1) + y * width] === DOT) {
        neighborItems[count].inner = (x - 1) + y * width;
        neighborItems[count++].outer = (x - 2) + y * width;
    }
    if (x < width - 2 && grid[(x + 2) + y * width] === DOT && grid[(x + 1) + y * width] === DOT) {
        neighborItems[count].inner = (x + 1) + y * width;
        neighborItems[count++].outer = (x + 2) + y * width;

    }
    if (y > 1 && grid[x + (y - 2) * width] === DOT && grid[x + (y - 1) * width] === DOT) {
        neighborItems[count].inner = x + (y - 1) * width;
        neighborItems[count++].outer = x + (y - 2) * width;

    }
    if (y < width - 2 && grid[x + (y + 2) * width] === DOT && grid[x + (y + 1) * width] === DOT) {
        neighborItems[count].inner = x + (y + 1) * width;
        neighborItems[count].outer = x + (y + 2) * width;
    }
    return neighborItems;
}

function drawUI(grid) {
    let ui = '';
    for (let x = 0; x < width; x++) {
        for (let y = 0; y < height; y++) {
            if (grid[x + y * width] === WALL) {
                ui += "X";
            } else {
                if (grid[x + y * width] === DOT) {
                    ui += ".";
                } else {
                    ui += " ";
                }
            }
        }
        ui += "\r\n";
    }
    console.clear();
    console.log(ui);
}


let path = processPath(grid);

for (let i = 0; i < path.length; i++) {
    let p = path[i];
    drawUI(p);
}


//0.0369
//0.0409
//820001 0.0721 made it to 1
//0.04
//0.0409
//0.0349
//820001 0.0654 made it to 1
//0.0291
//820001 0.0568 made it to 1
//0.0248
//820001 0.0549 made it to 1
//0.0207
//820001 0.0523 made it to 1
//solved at 1390001 0.0755