Np Expect - The Topiary

Np Expect

sample: (abc NEWS) Can You Solve the Hardest-Ever Sudoku?

<head>
  <meta name="viewport" content="width=device-width, initial-scale=1.0"/>
  <style>
  ::-webkit-scrollbar {
    width: 9px;
    height: 9px;
    border: solid 1px rgba(0, 0, 0, .1);
  }
  ::-webkit-scrollbar-thumb {
    background: rgba(50, 50, 50, .3);
  }
  ::-webkit-scrollbar-track {
    background: rgba(0, 0, 0, .1);
  }
  .depth {
    background: #efefef;
    box-shadow: 0 0 3px #333;
    font-size: .7em;
    height: 120px;
    margin: 0;
    overflow-y: auto;
    padding: .5em 2em;
  }
  </style>
</head>
<body>
  <script src="./2"></script>
</body>

(Global => {
  var NumPlace = class {
    constructor(game) {
      this.update(game);
    }
    static ary() {
      return [...Array(9).keys()].map(i => i + 1);
    }
    static groupIndex(X, Y) {
      return Math.floor(X / 3) + Math.floor(Y / 3) * 3;
    }
    update(game) {
      this.game = game.trim();
      this.map = NumPlace.ary().map(x => NumPlace.ary().map(y => NumPlace.ary()));
      this.X = [];
      this.Y = [];
      this.G = [];
      this.game.split(/\n/)
        .filter(v => v)
        .forEach((_, xi) => {
          _.split(/, ?/)
            .join('')
            .split('')
            .filter(v => v)
            .forEach((v, yi) => {
              if(NumPlace.ary().indexOf(Number(v)) > -1) {
                this.map[xi][yi] = [Number(v)];
              }
              this.X[xi] = this.X[xi] || [];
              this.X[xi].push(this.map[xi][yi]);
              this.Y[yi] = this.Y[yi] || [];
              this.Y[yi].push(this.map[xi][yi]);
 
              var gi = NumPlace.groupIndex(xi, yi);
              this.G[gi] = this.G[gi] || [];
              this.G[gi].push(this.map[xi][yi]);
 
              this.map[xi][yi].info = {x: xi, y: yi, g: gi};
            });
        });
    }
    is(x, y) {
      return {value: this.map[x][y], group: NumPlace.groupIndex(x, y)};
    }
    get _step() {
      return ['X', 'Y', 'G'].map(t => this[t]).flat();
    }
    clean() {
      ['X', 'Y', 'G'].forEach(t => {
        this[t].forEach(ary => {
          ary.forEach((v, i, a) => {
            for(var n of v) {
              var x = a.filter(_v => _v.find(_n => _n == n));
              if(x.length == 1) {
                v.length = 0;
                v.push(n);
                break;
              }
            }
 
            v.length == 1 && a.forEach((_v, _i) => {
              if(i != _i) {
                var n = _v.indexOf(v[0]);
                n > -1 && _v.splice(n, 1);
              }
            });
 
          });
        });
      });
      return this;
    }
    pair() {
      ['X', 'Y', 'G'].forEach(t => {
        this[t].forEach(ary => {
          ary.forEach((v, i, a) => {
            if(v.length == 2) {
              var x = v.join(','), _;
              var y = a.find((_v, _i) => (_ = _i, i != _i && _v.join(',') == x));
              y && a.forEach((_v, _i) => {
                if(i != _i && _ != _i) {
                  var n1 = _v.indexOf(v[0]);
                  n1 > -1 && _v.splice(n1, 1);
                  var n2 = _v.indexOf(v[1]);
                  n2 > -1 && _v.splice(n2, 1);
                }
              });
            }
          });
        });
      });
      return this;
    }
    solve(limit=Infinity) {
      this.check(true);
      var _ = self => JSON.stringify(self.map), a = _(this), b = _(this.clean()), i = 0;
      while(a != b && limit > i) {
        a = b;
        this.clean();
        this.pair();
        this.check(true);
        b = _(this);
      }
      return this;
    }
    _copy() {
      return new NumPlace(this + '');
    }
    expect(limit=15, terminate=1000, results={}, i=1) {
      results.limit = limit;
      results.terminate = terminate;
      results.depth = i;
      results.status = 'OK';
      if(i == 1) {
        results[0] = [];
        results[0].try = 0;
 
        try {
          this.solve();
          var s = this._copy().solve();
          results[0].push(s);
          var c = s.check();
          if(c.isOk && c.done) {
            results.depth--;
            results.answer = s;
            return results;
          }
        }catch(e) {
          results.depth--;
          results.status = 'INVALID_INPUT';
          return results;
        }
      }
      if(15 < limit || terminate < results[i - 1].length) {
        results.depth--;
        results.status = 'ABORT';
        results.try_counts = Object.keys(results).reduce((p, n) => p + (results[n].try || 0), 0);
 
        results.placeholder = [];
        for(var x of Array(9).keys()) {
          results.placeholder[x] = [];
          for(var y of Array(9).keys()) {
            results.placeholder[x][y] = (
              results[i] || results[i - 1] || []
            ).map(a => a.X[x][y])
              .flat()
              .filter((v, i, a) => i == a.indexOf(v))
              .sort();
 
          }
        }
 
        return results;
      }
      results[i] = [];
      results[i].try = 0;
      var tgts = results[i - 1], done = false;
      var current = tgts.map(tgt => {
        var x = [...tgt.X].flat().find(v => v.length > 1);
        if(!done && x) {
          var info = x.info;//{x: 0, y: 0, g: 0}
          return x.map(n => {
            var copy = tgt._copy();
            var pl = copy.map[info.x][info.y];
            pl.length = 0;
            pl.push(n);
            try {
              results[i].try++;
              copy.solve();
              var c = copy.check();
              if(c.done) {
                done = copy;
              }
              return copy;
            }catch(e) {
              return false;
            }
          });
        }
      }).flat()
        .filter(v => v);
      results[i].push(...current);
      results.try_counts = Object.keys(results).reduce((p, n) => p + (results[n].try || 0), 0);
      if(done) {
        this.X = done.X;
        this.Y = done.Y;
        this.G = done.G;
        this.map = done.map;
        if(results.answer) {
          results.status = 'MULTIPLE_ANSWERS';
          return results;
        }
        results.answer = done;
      }
      else if(!current.length) {
        if(results.answer) {
          return results;
        }
        results.status = 'EXPLORE_FAILURE';
        return results;
      }
      return this.expect(limit, terminate, results, i + 1);
    }
    check(throwerror=false) {
      var res = [], done = true;
      ['X', 'Y', 'G'].forEach(t => {
        this[t].forEach((ary, i) => {
          var c = ary.find(a => a.length != 1)
            ? (done = false, ary.find(a => a.length == 0))
              ? false
              : ary.map(v => Math.min(...v)).reduce((p, v) => p + v) <= 45
            : ary.map(v => v[0]).reduce((p, v) => p + v) == 45;
          c || res.push(`${t}${i}`);
        });
      });
      if(res.length && throwerror) throw new Error(`Invalid game: ${res.join(', ')}`);
      return {isOk: !res.length, exception: res, done: done};
    }
    toString() {
      return this.X.map(v => v.map(_v => _v.length == 1 ? _v[0] : '-').join(',')).join('\n');
    }
    static format(str) {
      return str.split(/(.{9})/).map(v => v.split('').join(',')).filter(v => v).join('\n')
    }
  }
  Global.NumPlace = NumPlace;
})(this);
 
/*
var sample = NumPlace.format('8----------36------7--9-2---5---7-------457-----1---3---1----68--85---1--9----4--');
var np = new NumPlace(sample);
console.log( np.expect() );
document.body.innerHTML = `
  <pre><code>${np.game}</code></pre>
  <hr />
  <pre><code>${np}</code></pre>
`;
*/
 
var inputs = [];
var label = document.createElement('pre');
 
var padding = (str, len) => (str + `<span style="user-select: none">${' '.repeat(len - str.length)}</span>`);
var _label = (data={}, time='-', status='-') => {
  var flow = [...Array(data.depth || 0).keys()].map(d => `<li><b>depth ${padding(d + 1 + '', 4)}:</b> try=${padding(data[d + 1].try + '', 4)}, remain=${data[d + 1].length}</li>`).join('');
  label.innerHTML = `<p><b>${padding('status', 10)}:</b> ${status}
<b>${padding('time', 10)}:</b> ${time}ms
<b>try_counts:</b> ${padding((data.try_counts || '-') + '', 6)}(max=${data.terminate || '-'}/try)
<b>${padding('depth', 10)}:</b> ${padding((data.depth || '-') + '', 6)}(max=${data.limit || '-'})
<ul class="depth">${flow}</ul></p>`;
}
_label();
 
var vals = document.createElement('pre');
var rst = document.createElement('button');
rst.innerHTML = 'Reset';
var hid = document.createElement('button');
hid.innerHTML = 'Show / Hide';
label.setAttribute('style', 'font-family: Courier, monospace;');
var script = `
  var NumPlace = ${NumPlace.toString()};
  onmessage = function(e) {
    var a = performance.now();
    console.log('[worker]', '\\n' + e.data);
    var np = new NumPlace(e.data);
    var res = np.expect();
    console.log('[worker]', np);
    postMessage([np, res, performance.now() - a]);
  }
`;
var worker_js = new Blob([script], {type: 'text/javascript'});
var worker_url = URL.createObjectURL(worker_js);
var worker = new Worker(worker_url);
var worker_init = () => {
  worker.terminate();
  worker = new Worker(worker_url);
  worker.onmessage = function(e) {
    var d = e.data[1];
    console.log('res:', d);
 
    var COLOR = {
      INVALID_INPUT:    'd71717',
      EXPLORE_FAILURE:  'd71717',
      MULTIPLE_ANSWERS: 'e2a432',
      ABORT:            'e2a432',
      OK:               '159415'
    }[d.status];
 
    inputs.forEach(i => {
      var n = e.data[0].X[i._info.x][i._info.y];
      var x = d.placeholder
        ? d.placeholder[i._info.x][i._info.y]
        : n;
      n.length != x.length && console.log(`X${i._info.x} Y${i._info.y}`, n, x);
      i.placeholder = x.join(', ');
 
      _label(
        d,
        e.data[2],
        `<span style="color: #${COLOR}">${d.status}</span>`
      );
 
    });
 
  };
};
 
worker_init();
 
var callback = e => {
  var n = Number(e.target.value);
  if(n != 0 && (n < 1 || 9 < n || !Number.isInteger(n))) {
    e.target.value = '';
    e.target.focus();
  }
  inputs.forEach(i => {
    i.placeholder = '';
  });
  _label();
  inputs.forEach(i => i.classList.remove('fill'));
  var f = inputs.filter(i => i.value);
  f.forEach(i => i.classList.add('fill'));
  if(!f.length) return;
  _label({}, '-', '<span>NOW INITIATING...</span>');
  var game = inputs.map(i => i.value ? i.value : '-').join('');
  console.log(game);
  worker_init();
  worker.postMessage(NumPlace.format(game));
};
 
var container = document.createElement('div');
container.shadowRoot || container.attachShadow({mode: 'open'});
var style = document.createElement('style');
style.innerHTML = `
 
  :host {
    background: #008080;
    border: 2px solid #008080;
    box-sizing: border-box;
    display: grid;
    grid-template-columns: repeat(9, 2.2em);
    grid-template-rows: repeat(10, 2.2em);
    padding: 1px;
    width: fit-content;
  }
  :host > div {
    box-sizing: border-box;
    display: flex;
  }
  :host > div > input {
    -moz-appearance: textfield;
    -webkit-appearance: none;
    background-color: #008080;
    border: 2px solid #008080;
    border-radius: 0;
    box-shadow: inset 0 0 3px #222;
    box-sizing: border-box;
    color: #aaa;
    font-size: 16px;
    margin: 0;
    padding: 0;
    text-align: center;
    transition: all .25s ease;
    width: 100%;
  }
  :host > div > input.fill {
    background-color: #b01;
    color: #fff;
  }
  :host > div > input.fill::selection {
    background-color: transparent;
    color: #901;
  }
  :host > div > input.fill:focus {
    background-color: #d8d;
    color: #fff;
  }
  :host > div > input:focus {
    outline: none;
  }
  :host > div > input::-webkit-outer-spin-button,
  :host > div > input::-webkit-inner-spin-button {
    -webkit-appearance: none;
    margin: 0;
  }
  :host > div > input::placeholder {
    color: #fff;
    transition: all .25s ease;
  }
  :host > div > input.hide::placeholder {
    color: transparent;
  }
  :host > div > input:focus::placeholder {
    color: transparent;
  }
 
  :host > div.x2 > input,
  :host > div.x5 > input {
    border-bottom-color: #fff;
    border-bottom-style: solid;
  }
 
  :host > div.x3 > input,
  :host > div.x6 > input {
    border-top-color: #fff;
    border-top-style: solid;
  }
 
  :host > div.y2 > input,
  :host > div.y5 > input {
    border-right-color: #fff;
    border-right-style: solid;
  }
 
  :host > div.y3 > input,
  :host > div.y6 > input {
    border-left-color: #fff;
    border-left-style: solid;
  }
  :host > pre {
    background: #fff2;
    border: 2px solid #008080;
    box-shadow: inset 0 0 3px #222;
    box-sizing: border-box;
    color: #fff;
    font-size: .8em;
    font-family: Courier, monospace;
    font-weight: bold;
    grid-column: 1 / 10;
    grid-row: 10 / 11;
    margin: 0;
    padding: .5em;
  }
`;
for(var x of Array(9).keys()) {
  for(var y of Array(9).keys()) {
    var child = document.createElement('div');
    child.setAttribute('style', `
      grid-row: ${x + 1} / ${x + 2};
      grid-column: ${y + 1} / ${y + 2};
    `);
    child.classList.add(`x${x}`, `y${y}`);
    container.shadowRoot.appendChild(child);
    var input = document.createElement('input');
    child.appendChild(input);
    input.type = 'number';
    input.setAttribute('min', 1);
    input.setAttribute('max', 9);
    input.setAttribute('step', 1);
    input._info = {x: x, y: y};
    inputs.push(input);
    input.addEventListener('focus', e => {
      vals.innerHTML = `[X${e.target._info.x + 1} Y${e.target._info.y + 1}]: ${e.target.placeholder}`;
    });
    input.addEventListener('input', callback);
  }
}
 
rst.onclick = e => {
  inputs.map(i => (i.value = ''));
  callback({target: inputs[0]});
  inputs[0].blur();
};
 
hid.onclick = e => {
  inputs.forEach(i => i.classList.toggle('hide'));
};
 
inputs.forEach(i => i.addEventListener('focus', e => e.target.select()));
 
document.body.innerText = '';
container.shadowRoot.appendChild(style);
container.shadowRoot.appendChild(vals);
document.body.appendChild(rst);
document.body.appendChild(hid);
document.body.appendChild(container);
document.body.appendChild(label);
 
//sample
'8----------36------7--9-2---5---7-------457-----1---3---1----68--85---1--9----4--'
  .split('')
  .forEach((v, i) => (inputs[i].value = v == '-' ? '' : v));
callback({target: inputs[0]});
inputs[0].blur();

page revision: 160, last edited: 11 Feb 2023 10:57

Edit Rate (0) Tags Discuss History Files Print Site tools + Options

The Topiary

yes the bees >:)