Neggsweeper helper

try to take over the world!
目前为 2021-03-03 提交的版本。查看最新版本。
换行
// ==UserScript==
// @name         Neggsweeper helper
// @namespace    http://tampermonkey.net/
// @version      0.1
// @description  try to take over the world!
// @author       You
// @match        http://www.neopets.com/games/neggsweeper/neggsweeper.phtml
// @grant        none
// ==/UserScript==

(function() {
    'use strict';
    // how's your relationship with God?
    // decisions made from freedom or fear?
    // Community say?
    //
    var htmlGrid = [];
    var grid = [];

    /* UI Components */
    function isUnknown(el) { // tested
        return $(el).find('[src="http://images.neopets.com/x/gn.gif"]').length;
    }

    function isMarked(el) { // tested
        return $(el).find('[src="http://images.neopets.com/games/neggsweeper/old/flagnegg.gif"]').length;
    }

    function getSurroundingNumber(el) { // tested
        return +$(el).find('b').html();
    }

    function parseHtmlGrid() { // tested
        var rows = $($('[name=grid] tbody')[0]).find('tr');

        rows.each(function(r, d) {
            if (r >= 3) {
                var htmlRow = [];
                var row = [];
                $(d).find('td').each(function(i, el) {
                    htmlRow.push(el);
                    if (isUnknown(el) || isMarked(el)) {
                        row.push(null);
                    } else {
                        row.push(getSurroundingNumber(el));
                    }
                });
                htmlGrid.push(htmlRow);
                grid.push(row);
            }
        })
    }

    function markBad(row, col) { // tested
        $(htmlGrid[row][col]).css('border', '3px solid red');
    }

    function markGood(row, col) { // tested
        $(htmlGrid[row][col]).css('border', '3px solid green');
    }

    function markPercentBad(row, col, p) { // tested
        $(htmlGrid[row][col]).append('<font color="red">' + Math.round(100 * p) + '%</font>');
    }

    function markAll() { // tested
        for (var r = 0; r < grid.length; ++r) {
            for (var c = 0; c < grid[0].length; ++c) {
                if (grid[r][c]) {
                    if (grid[r][c] === "x") {
                        markBad(r, c);
                    } else if (grid[r][c] === "o") {
                        markGood(r, c);
                    } else if (grid[r][c] > 0 && grid[r][c] < 1) {
                        markPercentBad(r, c, grid[r][c]);
                    }
                }
            }
        }
    }

    /* Logic components */
    /* Constructor for Coords objects */
    Array.prototype.indexOfCoord = function (c) {
        for (var i = 0; i < this.length; ++i) {
            if (this[i].row === c.row && this[i].col === c.col) {
                return i;
            }
        }
        return -1;
    }

    function Coords(row, col) {
        this.row = row;
        this.col = col;
        this.isMine = false;
        this.mineOdds = 0;
        this.hits = 0; // currently not really used, maybe for isolated cluster solution in the future

        this.equals = function(c) {
            return c.row === this.row && c.col === this.col;
        };
        this.deepCopy = function() {
            var temp = new Coords(this.row, this.col);
            temp.isMine = this.isMine;
            temp.mineOdds = this.mineOdds;
            temp.hits = this.hits;
            return temp;
        }
    }

    /* Constructor for unsolved tree node
     * coords: Coords
     * unsolvedList: [coords<Coords>, ...]
     * numSurround: 1 (number of surrounding mines)
     * possibleConfig: [1, 0, 0, 0] (1 being a mine, 0 not)
     */
    function UnsolvedNode(coords, unsolvedNeighbors, numSurround) {
        this.coords = coords;
        this.unsolvedNeighbors = unsolvedNeighbors; // source of truth
        this.numSurround = numSurround;
        this.fixedIdx = [];

        this.countMines = function() { return this.unsolvedNeighbors && this.unsolvedNeighbors.map(d => +d.isMine).reduce(function(a,b){ return a + b }) };
        this.validate = function() {
            return this.countMines() <= this.numSurround;
        }
        this.generateConfig = function * (config, numMines, idx) { //
            config = [...config];
            if (idx === config.length - 1) {
                var sumMines = config.reduce((a,b) => a + b);
                if (this.fixedIdx.indexOf(idx) === -1) {
                    config[idx] = 0;
                    sumMines = config.reduce((a,b) => a + b);
                    if (sumMines === numMines) {
                        yield config;
                    }

                    if (sumMines < numMines) {
                        config[idx] = 1;
                        sumMines = config.reduce((a,b) => a + b);
                        if (sumMines === numMines) {
                            yield config;
                        }
                    }
                } else {
                    config[idx] = +this.unsolvedNeighbors[idx].isMine;
                    if (sumMines === numMines) {
                        yield config;
                    }
                }
            } else {
                if (this.fixedIdx.indexOf(idx) === -1) {
                    config[idx] = 0;
                    yield * this.generateConfig(config, numMines, idx + 1);

                    if (config.reduce((a,b) => a + b) < numMines) {
                        config[idx] = 1;
                        yield * this.generateConfig(config, numMines, idx + 1);
                    }
                } else {
                    config[idx] = this.unsolvedNeighbors[idx].isMine ? 1 : 0;
                    yield * this.generateConfig(config, numMines, idx + 1);
                }
            }
        }
        this.configGenerator = null;
        this.mapConfigToNodes = function(cfg) {
            var that = this;
            if (cfg) {
                cfg.forEach(function(d, i) {
                    that.unsolvedNeighbors[i].isMine = !!d;
                });
                return this.unsolvedNeighbors;
            }
            return null;
        }
        this.getNextPossibleConfig = function() {
            /* config: [1, 0, 0, 0] (1 being a mine, 0 not) */
            if (numSurround <= this.unsolvedNeighbors.length) {
                if (this.configGenerator === null) {
                    this.configGenerator = this.generateConfig(this.unsolvedNeighbors.map(d => d.isMine? 1: 0), this.numSurround, 0);
                }
                var val = this.configGenerator.next().value;
                if (val === null) {
                    this.configGenerator = null;
                }
                //while (val && numSurround !== val.reduce((a,b) => a + b)) {
                //    this.configGenerator.next().value
                //}
                return this.mapConfigToNodes(val)
            } else {
                console.error("UnsolvedNode > incorrect number of mines to possible squares. Is this really unsolved? call this.validate() first");
            }
        }
        this.reset = function() {
            this.fixedIdx = [];
            this.configGenerator = null;
        };
        /* Return a new mc that takes all marked mines of the rhs and marks them for this object */
        this.merge = function(otherNode) {
            var that = this;
            otherNode.unsolvedNeighbors.forEach(function(d) {
                var idx = that.unsolvedNeighbors.indexOfCoord(d);
                if (idx > -1) {
                    if (that.fixedIdx.indexOf(idx) === -1) {
                        that.fixedIdx.push(idx);
                    }
                }
            });
            return this.validate();
        };
        this.deepCopy = function() {
            var temp = new UnsolvedNode(this.coords.deepCopy(), this.unsolvedNeighbors.map(d => d.deepCopy()), this.numSurround);
            temp.fixedIdx = [...this.fixedIdx];
            return temp;
        }
    }

    function Solution(unsolvedNodes) {
        var that = this;
        this.nodes = []; //[UnsolvedNode, ...]
        unsolvedNodes.forEach(function(d) {
            that.nodes.push(d.deepCopy());
        });
        this.allNeighbors = [];

        this.nodes.forEach(function(d) {
            d.unsolvedNeighbors.forEach(function(n, i, a) {
                var idx = that.allNeighbors.indexOfCoord(n);
                if (idx === -1) {
                    that.allNeighbors.push(n);
                } else {
                    a[i] = that.allNeighbors[idx];
                }
            })
        })
    }

    function getUnsolvedNeighbors(r, c) { // tested
        // Assume bigger than 1x1
        var n = [];
        if (r > 0) {
            if (c > 0) {
                if (grid[r - 1][c - 1] === null) {
                    n.push(new Coords(r - 1, c - 1));
                }
            }
            if (c < grid[0].length - 1) {
                if (grid[r - 1][c + 1] === null) {
                    n.push(new Coords(r - 1, c + 1));
                }
            }
            if (grid[r - 1][c] === null) {
                n.push(new Coords(r - 1, c));
            }
        }
        if (r < grid.length - 1) {
            if (c > 0) {
                if (grid[r + 1][c - 1] === null) {
                    n.push(new Coords(r + 1, c - 1));
                }
            }
            if (c < grid[0].length - 1) {
                if (grid[r + 1][c + 1] === null) {
                    n.push(new Coords(r + 1, c + 1));
                }
            }
            if (grid[r + 1][c] === null) {
                n.push(new Coords(r + 1, c));
            }
        }
        if (c > 0) {
            if (grid[r][c - 1] === null) {
                n.push(new Coords(r, c - 1));
            }
        }
        if (c < grid[0].length - 1) {
            if (grid[r][c + 1] === null) {
                n.push(new Coords(r, c + 1));
            }
        }
        return n;
    }

    function findAllUnsolvedNodes() { // tested
        var result = {};
        var unsolvedNodes = [];
        var allCoords = [];
        grid.forEach(function(r, i) {
            r.forEach(function(c, j) {
                if (c >= 1) {
                    var n = getUnsolvedNeighbors(i, j);
                    if (n && n.length) {
                        unsolvedNodes.push(new UnsolvedNode(new Coords(i, j), n, c));
                    }
                }
            });
        });

        result.unsolvedNodes = unsolvedNodes;
        result.allCoords = allCoords;
        return unsolvedNodes;
    }

    function findAllSolutionsHelper(unsolvedNodes, idx, solutions) {
        if (idx >= unsolvedNodes.nodes.length - 1) {
            unsolvedNodes.nodes[idx].unsolvedNeighbors = unsolvedNodes.nodes[idx].getNextPossibleConfig();
            while (unsolvedNodes.nodes[idx].unsolvedNeighbors !== null) {
                var minesMatch = true;
                for (var i = 0; i < unsolvedNodes.nodes.length; ++i) {
                    var numMines = unsolvedNodes.nodes[i].countMines();

                    if (unsolvedNodes.nodes[i].numSurround !== numMines) {
                        minesMatch = false;
                        break;
                    }
                }
                if (minesMatch) {
                    solutions.push(new Solution(unsolvedNodes.nodes));
                }
                unsolvedNodes.nodes[idx].unsolvedNeighbors = unsolvedNodes.nodes[idx].getNextPossibleConfig();
            }
        } else {
            var isValid = true;
            unsolvedNodes.nodes[idx].unsolvedNeighbors = unsolvedNodes.nodes[idx].getNextPossibleConfig();
            while (unsolvedNodes.nodes[idx].unsolvedNeighbors !== null) {
                for (var j = idx + 1; (j < unsolvedNodes.nodes.length) && isValid; ++j) {
                    isValid = unsolvedNodes.nodes[j].merge(unsolvedNodes.nodes[idx]);
                }

                //if (isValid) {
                    findAllSolutionsHelper(new Solution(unsolvedNodes.nodes), idx + 1, solutions);
                    for (j = idx + 1; (j < unsolvedNodes.nodes[idx].unsolvedNeighbors.length) && isValid; ++j) {
                        unsolvedNodes.nodes[j].reset();
                    }
                //}
                unsolvedNodes.nodes[idx].unsolvedNeighbors = unsolvedNodes.nodes[idx].getNextPossibleConfig();
            }
        }
        /*var tempUnsolvedNodes = [];
        unsolvedNodes.forEach(function(d) { tempUnsolvedNodes.push( d.deepCopy()); })
        var isValid = true;
        if (idx >= unsolvedNodes.length - 1) {
            while (tempUnsolvedNodes[idx].unsolvedNeighbors = unsolvedNodes[idx].getNextPossibleConfig()) {
                console.log(tempUnsolvedNodes[idx]);
                var minesMatch = true;
                for (var i = 0; i < tempUnsolvedNodes.length; ++i) {
                    var numMines = tempUnsolvedNodes[idx].countMines();

                    if (tempUnsolvedNodes[i].numSurround !== numMines) {
                        minesMatch = false;
                        break;
                    }
                }
                if (minesMatch) {
                    tempUnsolvedNodes[idx] = tempUnsolvedNodes[idx].deepCopy();
                    solutions.push(tempUnsolvedNodes);
                }
                tempUnsolvedNodes = [];
                unsolvedNodes.forEach(function(d) { tempUnsolvedNodes.push( d.deepCopy()); })
            }
        } else {
            var tempConfig = unsolvedNodes[idx].getNextPossibleConfig();
            while (tempConfig && tempConfig.length) {
                for (var j = idx + 1; (j < tempUnsolvedNodes.length) && isValid; ++j) {
                    isValid = tempUnsolvedNodes[j].merge(tempConfig);
                }

                if (isValid) {
                    findAllSolutionsHelper(unsolvedNodes, idx + 1, solutions);
                    for (j = idx + 1; (j < tempUnsolvedNodes.length) && isValid; ++j) {
                        isValid = unsolvedNodes[j].reset();
                    }
                }
                tempConfig = unsolvedNodes[idx].getNextPossibleConfig();
            }
        }*/
    }

    function findAllSolutions() {
        var solutions = []; // [Solution(), ...]

        var unsolvedNodes = findAllUnsolvedNodes();
        console.log(unsolvedNodes);

        findAllSolutionsHelper(new Solution(unsolvedNodes), 0, solutions);

        return solutions;
    }

    function combineSolutions() {
        var solutions = findAllSolutions();
        console.log("solutions", solutions);
        var coords = [];

        solutions.forEach(function(s) {
            s.allNeighbors.forEach(function(coord) {
                var idx = coords.indexOfCoord(coord);
                if (idx === -1) {
                    coords.push(coord);
                    coord.mineOdds += +coord.isMine;
                } else {
                    coords[idx].mineOdds += +coord.isMine;
                }
                coord.hits++;
            })
        })

        coords.forEach(function(d) {
            d.mineOdds = d.mineOdds / solutions.length;
        });

        return coords;
    }

    function markGrid(solution) {
        solution.forEach(function(coord){
            if (coord.mineOdds === 0) {
                grid[coord.row][coord.col] = 'o';
            } else if (coord.mineOdds === 1) {
                grid[coord.row][coord.col] = 'x';
            } else {
                grid[coord.row][coord.col] = coord.mineOdds;
            }
        });
    }

    /*function copyGrid(g) {
        var newGrid = [];
        for (var r = 0; r < g.length; ++r) {
            newGrid.push([...g[r]]);
        }
        return newGrid;
    }*/


    /* Main */
    parseHtmlGrid();
    console.log(findAllUnsolvedNodes())
    markGrid(combineSolutions())
    markAll();
    console.log(grid);

    var n = new UnsolvedNode(new Coords(0,0), [new Coords(1,2),new Coords(1,3),new Coords(1,4),new Coords(1,5)],1)
    var an = new UnsolvedNode(new Coords(0,1), [new Coords(1,2),new Coords(1,6),new Coords(1,7),new Coords(1,8)],1)
    var s = new Solution([n, an]);
    console.log(s);
    s.allNeighbors[0].isMine = true;
/*
n = new UnsolvedNode(new Coords(0,0), [new Coords(1,1),new Coords(1,1),new Coords(1,1),new Coords(1,1)],1)
n.configGenerator = n.generateConfig([0,0,0,0],1,0)
n.fixedIdx=[1];
n.configGenerator.next().value

n = new UnsolvedNode(new Coords(0,0), [new Coords(1,1),new Coords(1,1),new Coords(1,1),new Coords(1,1)],1)
an = new UnsolvedNode(new Coords(0,0), [new Coords(1,1),new Coords(1,1),new Coords(1,1),new Coords(1,1)],1)
an.unsolvedNeighbors[1].isMine = true;
n.configGenerator = n.generateConfig([0,1,0,0],1,0)
n.configGenerator.next().value

n = new UnsolvedNode(new Coords(0,0), [new Coords(1,2),new Coords(1,3),new Coords(1,4),new Coords(1,5)],1)
an = new UnsolvedNode(new Coords(0,1), [new Coords(1,2),new Coords(1,6),new Coords(1,7),new Coords(1,8)],1)
n.unsolvedNeighbors[0].isMine = true;
an.merge(n.unsolvedNeighbors)
*/


})();
欢迎访问Greasy Fork镜像
