re,
après avoir un peu (beaucoup) transpiré...
j'ai implem un bot qui ressemble (à priori?) à ce qu'on fait:
on essaie de déduire.
puis si on peut plus, on tente de choisir un elem, et on regarde si ca marche ou pas.
puis si ca marche pas on en tente un autre.
ci-dessous le code nodejs
En particulier, quand il y a des guess à faire, il retourne le nombre minimal de guess à faire.
- Code: Tout sélectionner
//h.js
function H(M, b){
this.K = M.map((x,i)=>x.slice().concat(b[i]));//the equations
this.G = [];//atleast
this.L = [];//atmost
var N = M[0].length;
this.Card = new Array(N).fill(1);
this.X = new Array(N).fill('_');
}
H.prototype._strArr = function(S){
return S.map((y,i)=>this.rowStr(y,this.bound(y)))
}
H.prototype._add = function(r,S){
var dupe = S.some((row,i)=>{
return JSON.stringify(row)==JSON.stringify(r)
});
if(dupe){
return false;
}
S.push(r);
return true;
}
H.prototype._rm = function(i, S){
S.splice(i,1);
}
H.prototype.log = function(...v){
if(this._log){
this._log(...v)
}else{
console.log.apply(console, v);
}
}
H.prototype.rowStr = function(r){
return [].concat(r.slice(0,-1)).concat(['|', this.bound(r)]).join(' ');
}
H.prototype.xStr = function(){
return this.X.map((x,i)=>{
return x+(this.Card[i]?'+ ':' ');
}).join('');
}
H.prototype.disp = function(){
var s = [
'###',
this.xStr()
];
s.push(...this._strArr(this.K))
s.push('--')
s.push(...this._strArr(this.G))
s.push(
'--',
'###'
);
s.map(l=>this.log(l));
}
H.prototype.dispRow = function(r){
this.log(this.rowStr(r));
};
H.prototype.setAtLeast = function(n){
[this.K, this.G, this.L].forEach(S=>{
S.forEach((r,i)=>{
if(r[n]){
/*if(S == this.G){
console.log('phoque')
this.dispRow(r)
}*/
var r0=r.slice(0);
if(this.row(r).reduce((acc,x)=>acc+x,0)<r[r.length-1]){
console.log('------------------------WHAT THE MOTHER FUCK', n);
this.dispRow(r0)
this.dispRow(r);
console.log('endwhat');
}
r[n]--;
var b = this.bound(r);
if(b > 0){
//positive shit
r[r.length-1]--;
if(r[r.length-1]==0 && S==this.G){
//the condition is now obsolete, anybody fulfills it
this._rm(i, S)
}
}
if(this.row(r).reduce((acc,x)=>acc+x,0)<r[r.length-1]){
console.log('WHAT THE MOTHER FUCK', n);
this.dispRow(r0)
this.dispRow(r);
console.log('endwhat');
}
return true;
}
})
})
if(this.X[n] == '_'){
this.X[n] = 1;
}else{
this.X[n]++;
}
return true;
}
H.prototype.setNoMore = function(n){
var actionTaken = false;
if(this.X[n] == '_'){
actionTaken = true;
this.X[n] = 0;
}
//you cant apply nomore on the greater cond,
//EXCEPT if the given index represents the original eq
//since we dont know from how we belong, just ignore it
[this.K,
//this.G, this.L
].forEach(S=>{
S.forEach((r,i)=>{
if(r[n]!=0){
actionTaken = true;
r[n] = 0;
}
})
})
if(this.Card[n]!=0){
actionTaken = true;
}
this.Card[n] = 0;
return actionTaken;
}
H.prototype.setMax = function(n, max){
[this.K, this.G, this.L].forEach(S=>{
S.forEach(r=>{
if(r[n] > max){
r[n] = max;
}
})
})
}
H.prototype.row = function(r){
return r.slice(0,-1);
}
H.prototype.bound = function(r){
return r[r.length-1];
}
H.prototype.flush = function(){
var actionTaken = false;
[this.K,this.G,this.L].forEach(S=>{
S.forEach((r,i)=>{
if(S[i].every(x=>x==0)){
actionTaken = true;
this._rm(i, S);
}
})
})
return actionTaken;
}
/**
* 1 if at least one elem of type i in a and b
* bound arbitrarily 0
* @param {[type]} a [description]
* @param {[type]} b [description]
* @return {[type]} [description]
*/
H.prototype.common = function(a,b){
var ra = this.row(a);
var rb = this.row(b);
var r = [];
ra.forEach((c,i)=>{
if(c && rb[i]){
r.push(1);
}else{
r.push(0);
}
})
r.push(1);
return r;
}
H.prototype.singleElem = function(r){
return this.row(r).reduce((acc,x)=>acc+(x?1:0),0)==1
}
H.prototype.atL = function(i){
return this.L[i];
}
H.prototype.atG = function(i){
return this.G[i];
}
H.prototype.atK = function(i){
return this.K[i];
}
H.prototype.forL = function(f){
return this.L.forEach(f);
}
H.prototype.someG = function(f){
return this.G.some(f);
}
H.prototype.someK = function(f){
return this.K.some(f);
}
H.prototype.someKK = function(f){
return this.K.some(r=>{
return this.K.some(r2=>{
if(r==r2){return};
return f(r,r2);
})
})
}
H.prototype.sum = function(r){
var row = this.row(r);
return row.reduce((acc,x)=>acc+x, 0);
}
H.prototype.rmK = function(r){
var idx = this.K.indexOf(r);
if(idx!=-1){
this.K.splice(idx, 1);
}
}
H.prototype.fork = function(opts){
var h = new H([[]],[]);
h.K = this.K.map(x=>x.slice());
h.G = this.G.map(x=>x.slice());
h.L = this.L.map(x=>x.slice());
h.Card = this.Card.slice();
h.X = this.X.slice();
h._log = opts && opts.log;
return h;
}
H.prototype.isValid = function(){
return [this.K,this.G].every(S=>{
return S.every(r=>{
var b = this.bound(r);
return this.sum(r) >= b;
})
})
}
H.prototype.substitute = function(a,b){
//if a substitution exists
//then ALL elems of a are included in b
//(this implies that if bounds are m_a and m_b, necessarily m_a <= m_b)
var ra = this.row(a);
var rb = this.row(b);
var r = [];//substition
var ok = ra.every((c,i)=>{
if(!c){
r.push(rb[i]);
return true;
}
if(rb[i]<c){
//we can not include all elems of a
return false;
}
r.push(rb[i]-c);
return true;
})
if(!ok)return false;
r.push(this.bound(b)-this.bound(a))
return r;
}
H.prototype.atLeastEq = function(a,b){
var ra = this.row(a);
var rb = this.row(b);
var r = [];
var common = 0;
ra.forEach((c,i)=>{
if(!(c && rb[i])){
r.push(rb[i]);
return;
}
//how many in common
var min = Math.min(c, rb[i]);
common += min;
r.push(rb[i] - min);
});
var taken = Math.min(common, this.bound(a), this.bound(b));
if(taken == 0){
//nothing was simplified,r == b
return false;
}
var rbound = this.bound(b)-taken;
if(rbound == 0){
//anything >=0 is always true, no need to generate
return false;
}
r.push(rbound);
return r;
}
H.prototype.atMostEq = function(a,b){
var ra = this.row(a);
var rb = this.row(b);
var outCommon = 0;
var r = [];
ra.forEach((c,i)=>{
if(!c){
r.push(rb[i]);
return;
}
if(!b){
r.push(rb[i]);
outCommon+=c;
return
}
var min = Math.min(c, rb[i]);
outCommon += (c - min);
r.push(rb[i]-min);
});
if(outCommon >= this.bound(a)){
return false;
}
//we need common to contain ATLEAST ba-outCommon elems
//|common| >= ba-outCommon when the minimum card is ba-outCommon
//(this implies bb > |common| otherwise you cant satisfy egality)
var rbound = this.bound(b) - (this.bound(a)-outCommon);
if(rbound < 0){
throw 'unfeasible problem';
return false;
}
r.push(rbound);
return r;
}
H.prototype.addL = function(r){
return this._add(r, this.L);
}
H.prototype.addG = function(r){
return this._add(r, this.G);
}
H.prototype.addK = function(r){
return this._add(r, this.K);
}
H.init = function(...v){
var M = [];
var B = [];
v.forEach(l=>{
var [k,b] = l.split('|');
var r = k.trim().split(/\s+/).map(x=>parseInt(x),10);
b = parseInt(b.trim(),10)
M.push(r);
B.push(b);
})
return new H(M, B);
}
module.exports = H;//toadjs.js
var txt = `
2,2,4,5,5,5,7
1,2,4,4,5,7,7
1,4,5,5,7,8,8
1,2,3,3,3,5,5
1,1,4,5,5,6,8
1,2,3,3,4,5,8
1,2,4,5,5,7,8
4,4,5,6,6,7,8
`;
var b = [2,3,4,2,4,4,4,5];
/*
var txt = `
1 1 1 4 6 8 9
0 3 5 6 6 7 9
1 2 3 3 5 8 9
0 2 2 5 6 7 7
2 2 5 7 8 9 9
0 2 3 4 6 6 9
4 5 7 8 8 8 9
`;
var b = [3,3,3,3,3,3,3]*/
var txt = `
1 1 2 2 2
1 1 2 2 3
1 2 3 4 4
3 3 4 4 5
3 4 4 5 5
`;
var b = [3,4,3,1,3]
/*
var txt = `
1 2 2 4 5
1 2 2 5 5
2 4 1 1 5
4 4 4 1 1
5 5 4 3 3
`;
var b = [3, 3, 3, 3, 3]*/
var txt = `
1 3 3 3
3 4 4 4
1 3 3 4
1 1 1 4
`;
var b = [1,2,2,3];/*
var txt = `
2 2 3 3
2 3 4 4
1 2 2 3
1 2 3 4
`;
var b = [2,2,2,2]*/
/*
var txt = `
4 4 4 4 6 7 7 9 9
2 2 2 3 3 5 6 6 7
2 2 3 3 4 4 6 8 9
2 2 3 6 7 8 8 8 9
1 1 1 1 5 6 6 7 9
1 1 5 6 6 8 8 9 9
3 3 5 6 7 7 9 9 9
1 3 3 4 6 7 9 9 9
3 5 5 5 6 6 7 9 9
`;
var b = [3, 3 ,3 ,3, 3, 3, 3, 3, 3]*/
var txt = `
1 2 4 5 5 6 6 9 1
1 3 6 6 9 1 1 1 1
2 5 5 6 6 8 2 2 2
2 4 6 6 8 9 2 2 2
3 3 3 3 3 3 3 3 3
2 3 5 5 7 9 2 2 2
3 4 5 5 7 3 3 3 3
1 5 5 6 6 8 9 1 1
1 2 4 5 5 6 6 7 9
`;
var b = [6,4,5,5,1,5,5,6,7]
function toAdj(){
var min = 20;
var max = 0;
var M = txt.trim().split('\n').map(x=>{
return x.trim().split(/[ ,]/).reduce((dic,y)=>{
y = parseInt(y,10);
if(y > max){
max = y;
}
if(y < min){
min = y;
}
if(dic[y]){
dic[y]++;
}else{
dic[y] = 1;
}
return dic;
},{})
});
M = M.map(dic=>{
var r = [];
var z = 0;
for(var i = min; i<=max; ++i){
if(dic[i]){
r[z] = dic[i];
}else{
r[z] = 0;
}
++z;
}
return r;
})
return M;
}
function toB(){
return b;
}
if(!module.parent){
var M = toAdj();
console.log(M.map(x=>x.join(',')).join('\n'))
console.log('----')
var adj = M.map(x=>{
return JSON.stringify(x.map(y=>y?1:0));
}).join(',\n')
console.log('['+adj+']')
}else{
module.exports = {
toAdj:toAdj,
toB
};
}//test.js
var assert = require('assert');
var H = require('./h');
var Bot = require('./bot');
var describe = function(l,f){console.log('#'+l);f()}
var it = function(l,f){try{f();console.log('ok '+l)}catch(e){console.log('ko ',l);throw e}}
describe('bot',_=>{
/*it('does not fails at most',_=>{
var a = '0 0 1 3 | 1'
var b = '1 1 2 0 | 2'
var c = '1 1 0 0 | 1'
var h = H.init(a,b,c);
h.disp();
var {r,b} = h.to(0,1);
h.dispRow(0)
h.dispRow(1)
h.dispRow(r,b)
})*/
it('simplifyK', _=>{
var a = '0 0 1 3 | 4'
var b = '1 1 2 0 | 2'
var h = H.init(a,b);
var b = new Bot(h);
var atLeastCount = 0;
var noMoreCount = 0;
h.setAtLeast = function(i){
assert(i==2 || i==3);
atLeastCount++;
}
h.setNoMore = function(i){
noMoreCount++;
}
b.simplifyK();
assert.equal(atLeastCount, 4);
assert.equal(noMoreCount, 2);
})
it('simplifyK', _=>{
var a = '3 0 0 0 | 1'
var b = '2 0 0 0 | 1'
var h = H.init(a,b);
var b = new Bot(h);
var atLeastCount = 0;
var noMoreCount = 0;
//we expect that at least 1 is taken
//and then nomore 1
h.setAtLeast = function(i){
assert(i==0);
atLeastCount++;
}
h.setNoMore = function(i){
noMoreCount++;
}
b.simplifyK();
assert.equal(atLeastCount, 1)
assert.equal(noMoreCount, 1)
})
it('simplifyK do not if invalid', _=>{
var a = '3 0 0 0 | 1'
var b = '2 0 0 0 | 0'
var h = H.init(a,b);
var b = new Bot(h);
var atLeastCount = 0;
var noMoreCount = 0;
//we expect that at least 1 is taken
//and then nomore 1
h.setAtLeast = function(i){
assert(i==0);
atLeastCount++;
}
h.setNoMore = function(i){
noMoreCount++;
}
b.simplifyK();
//on above, we could simplify atleast for singleElem
//but actually, second condition implies that
//you should ALWAYS do noMore before atLeast
assert.equal(atLeastCount, 0)
assert.equal(noMoreCount, 1)
})
it('simplifyG', _=>{
var a = '0 0 0 4 | 4'
var b = '1 1 2 0 | 2'
var h = H.init(b);
var b = new Bot(h);
h.addG([0,0,0,4,4]);
var atLeastCount = 0;
h.setAtLeast = function(i){
assert.equal(i,3);
atLeastCount++;
}
b.simplifyG();
assert.equal(atLeastCount, 4);
})
it('simplifyG', _=>{
var a = '0 0 0 4 | 4'
var b = '1 1 2 0 | 2'
var h = H.init(b);
var b = new Bot(h);
h.addG([0,0,0,4,4]);
var atLeastCount = 0;
h.setAtLeast = function(i){
assert.equal(i,3);
atLeastCount++;
}
b.simplifyG();
assert.equal(atLeastCount, 4);
})
/*it('simplifyL', _=>{
var a = '0 0 0 4 | 4'
var b = '1 1 2 0 | 2'
var h = H.init(b);
var b = new Bot(h);
h.addL([0,0,0,4,2]);
var c = 0;
h.setMax = function(i, val){
assert.equal(i,3);
assert.equal(val,2);
c++;
}
b.simplifyL();
assert.equal(c, 1);
})*/
it('deriveKK', _=>{
var a = '2 0 0 0 | 1';
var b = '3 0 0 0 | 1';//we should only be allowed to do nothing because bound is 0
h = H.init(a,b);
var bot = new Bot(h);
bot.deriveKK();
assert.equal(h.rowStr(h.atK(1)), '3 0 0 0 | 1')
assert.equal(h.K.length, 2)
})
it('deriveKK ffs atleast', _=>{
var a = '0 2 1 0 | 1';
var b = '0 2 2 0 | 2';
h = H.init(a,b);
var bot = new Bot(h);
h.disp();
assert(bot.deriveKK());
assert.equal(h.rowStr(h.atK(0)), '0 2 0 0 | 0')
})
})
describe('init', _=>{
it('loads', _=>{
var a = '0 0 1 3 | 1'
var b = '1 1 2 0 | 2'
var c = '1 1 0 0 | 1'
var h = H.init(a,b,c);
//h.disp();
})
it('rowStr', _=>{
var a = '0 0 1 3 | 1';
h = H.init(a);
var r = h.atK(0);
assert.equal(h.rowStr(r), '0 0 1 3 | 1');
})
it('setAtLeast', _=>{
var a = '0 0 1 3 | 2';
var b = '0 0 1 0 | 1';
var c = '0 0 1 1 | 1';
h = H.init(a,b,c);
h.addG([2,2,1,2,2])
h.addL([2,2,5,1,3])
h.setAtLeast(3);
assert.equal(h.rowStr(h.atK(0)), '0 0 1 2 | 1');
assert.equal(h.rowStr(h.atK(1)), '0 0 1 0 | 1');//not touched
assert.equal(h.rowStr(h.atK(2)), '0 0 1 0 | 0');
assert.equal(h.rowStr(h.atG(0)), '2 2 1 1 | 1');
assert.equal(h.rowStr(h.atL(0)), '2 2 5 0 | 2');
assert.equal(h.xStr().trim(), '_+ _+ _+ 1+');
var a = '0 1 0 2 1 0 2 0 | 2';
var b = '0 0 0 1 2 0 1 1 | 2';
h = H.init(a,b);
h.setAtLeast(3);
h.setAtLeast(7);
assert.equal(h.rowStr(h.atK(0)), '0 1 0 1 1 0 2 0 | 1')
assert.equal(h.rowStr(h.atK(1)), '0 0 0 0 2 0 1 0 | 0')
})
it('setNoMore', _=>{
var a = '0 0 1 3 | 2';
var b = '0 0 1 0 | 1';
var c = '0 0 1 1 | 1';
h = H.init(a,b,c);
h.addG([2,2,1,2,2])
h.addL([2,2,5,1,3])
h.setNoMore(3);
assert.equal(h.rowStr(h.atK(0)), '0 0 1 0 | 2');
assert.equal(h.rowStr(h.atK(1)), '0 0 1 0 | 1');
assert.equal(h.rowStr(h.atK(2)), '0 0 1 0 | 1');
h.disp()
assert.equal(h.rowStr(h.atG(0)), '2 2 1 2 | 2', 'NO IMPACT ON G because G {3+} can be less than original eq');
assert.equal(h.rowStr(h.atL(0)), '2 2 5 1 | 3', 'so is for L');
assert.equal(h.xStr().trim(), '_+ _+ _+ 0');
h.setAtLeast(2);
assert.equal(h.xStr().trim(), '_+ _+ 1+ 0');
h.setNoMore(2);
assert.equal(h.xStr().trim(), '_+ _+ 1 0');//+ removed
})
it('bound', _=>{
var a = '0 0 1 3 | 2';
h = H.init(a);
assert.equal(h.bound(h.atK(0)), 2);
})
it('flush', _=>{
var a = '0 0 1 3 | 2';
var b = '0 0 0 0 | 0';
var c = '0 0 1 1 | 1';
h = H.init(a,b,c);
var d = h.atK(0).slice(0);
var e = h.atK(1).slice(0);
var f = h.atK(2).slice(0);
h.addG(d)
h.addG(e)
h.addL(e)
h.addL(f)
h.flush();
assert.equal(h.K.length, 2);
assert.equal(h.G.length, 1);
assert.equal(h.L.length, 1);
assert.equal(h.rowStr(h.atK(0)), '0 0 1 3 | 2')
assert.equal(h.rowStr(h.atK(1)), '0 0 1 1 | 1')
assert.equal(h.rowStr(h.atG(0)), '0 0 1 3 | 2')
assert.equal(h.rowStr(h.atL(0)), '0 0 1 1 | 1')
})
it('singleElem', _=>{
var a = '0 0 1 0 | 2';
var b = '0 0 0 0 | 0';
var c = '0 0 1 1 | 1';
h = H.init(a,b,c);
assert( h.singleElem(h.atK(0)));
assert(!h.singleElem(h.atK(1)));
assert(!h.singleElem(h.atK(2)));
})
it('someK', _=>{
var a = '0 0 1 0 | 2';
var b = '0 0 0 0 | 0';
var c = '0 0 1 1 | 1';
h = H.init(a,b,c);
var z = 0;
var rows = [
'0 0 1 0 | 2',
'0 0 0 0 | 0',
'0 0 1 1 | 1',
]
h.someK((r,i)=>{
assert.equal(i,z);
z++;
assert.equal(rows[i], h.rowStr(r))
return false;
})
assert.equal(z,3)
})
it('addK no dupe', _=>{
var a = '0 0 1 0 | 2';
var b = '0 0 0 0 | 0';
h = H.init(a);
h.addK(b);
h.addK(b);
h.addL(b);
h.addG(b);
assert.equal(h.K.length, 2)
assert.equal(h.L.length, 1)
assert.equal(h.G.length, 1)
})
it('setMax', _=>{
var a = '0 0 1 3 | 2';
var b = '0 0 0 0 | 0';
h = H.init(a,b);
h.addG([0,0,1,2,1]);
h.addL([0,0,1,3,3]);
h.setMax(3, 2);
assert.equal(h.rowStr(h.atK(0)), '0 0 1 2 | 2')
assert.equal(h.rowStr(h.atK(1)), '0 0 0 0 | 0')
assert.equal(h.rowStr(h.atG(0)), '0 0 1 2 | 1')
assert.equal(h.rowStr(h.atL(0)), '0 0 1 2 | 3')
})
it('substitute', _=>{
var a = '0 0 1 3 | 2';
h = H.init(a);
//assert.equal(h.substitute([1,1,1,1,3],[1,1,0,4,3]), false);//missing an el
//assert.equal(h.substitute([1,2,1,1,3],[1,1,1,1,3]), false);//not enough el in b
var r = h.substitute([1,2,1,1,3],[1,2,1,1,3]);
assert(r);//ok
assert.equal(h.rowStr(r), '0 0 0 0 | 0');
var r = h.substitute([1,2,1,0,3],[1,2,1,0,4]);
assert.equal(h.rowStr(r), '0 0 0 0 | 1');//ok if no el in a
var r = h.substitute([1,2,0,0,3],[1,2,2,0,4]);
assert.equal(h.rowStr(r), '0 0 2 0 | 1');//ok if no el in a
var r = h.substitute([2,0,0,0,1],[3,0,0,0,1]);
assert.equal(h.rowStr(r), '1 0 0 0 | 0');//when substituing, you only have equivalence if the kept
//row is disjoint from b. Here this is not the case
//this row basically mean that given a set {1}=0 we wont pick _that_ 1
//but it does not mean that in the original set {1 1 1} we won't pick one.
//so you can't call atLeast
})
it('rmk', _=>{
var a = '0 0 1 3 | 1';
var b = '0 0 1 3 | 2';
var c = '0 0 1 3 | 3';
h = H.init(a,b,c);
var r = h.atK(1);
h.rmK(r);
assert.equal(h.K.length, 2);
assert.equal(h.bound(h.atK(0)), 1)
assert.equal(h.bound(h.atK(1)), 3)
})
it('atLeastEq', _=>{
var a = '0 0 1 3 | 1';
var b = '0 0 1 3 | 2';
var c = '0 0 1 3 | 3';
h = H.init(a,b,c);
assert(! h.atLeastEq([1,2,0,1],[0,0,1,2]) );//nothing in common
assert(! h.atLeastEq([1,2,3,0,4],[1,1,0,1,2]) );//useless deduction
var r = h.atLeastEq([1,2,3,0,4],[1,1,0,1,3]);
assert.equal(h.rowStr(r), '0 0 0 1 | 1')
var r = h.atLeastEq([1,2,3,0,2],[1,2,0,1,3]);//bound is less then nb in common
assert.equal(h.rowStr(r), '0 0 0 1 | 1')
var r = h.atLeastEq([1,2,3,0,2],[1,3,0,1,3]);//has some el left
assert.equal(h.rowStr(r), '0 1 0 1 | 1')
h = H.init(
'1 1 3 0 2 0 0 0 | 2',
'1 1 2 1 1 0 0 1 | 4'
);
var r = h.atLeastEq(h.atK(0),h.atK(1));
assert.equal(h.rowStr(r), '0 0 0 1 0 0 0 1 | 2')
})
it('atMostEq', _=>{
var a = '0 0 1 3 | 1';
h = H.init(a);
assert(! h.atMostEq([1,2,0,1],[0,0,1,2]) );//nothing in common, outCommon >=ba
assert(! h.atMostEq([1,2,3,8,4],[1,1,0,0,2]) );//in common, but still outCommon too big
var r = h.atMostEq([1,1,2,0,3],[1,1,1,1,2]);//in common
assert.equal(h.rowStr(r), '0 0 0 1 | 0')
})
})
//run.js
var Bot = require('./bot');
var H = require('./h');
var toAdj = require('./toadjs');
const MAX_ITER = 100;
function deductions(b){
var count = 0;
var action = true;
while(count++<MAX_ITER && action && b.isValid()){
action = b.step();
b.disp();
}
if(count == MAX_ITER){
throw 'learn to code';
}
//return true IF
//the board could be solved
//that is no eq anymore
return b.solved();
}
//return true if b could be solved
//false otherwise
function solve(b, cache, solutions){
//b.disp()
var ok = deductions(b);
if(ok){
//serialize the pickups, should they be different
//(less deductions needed)
var k = b.image();
var picks = b.history.sort((a,b)=>a-b).join(';');
if(!solutions.has(k)){
var s = new Set;
s.add(picks);
solutions.set(k, {b,spicks:s});
}else{
var {b,spicks} = solutions.get(k);
if(!spicks.has(picks)){
spicks.add(picks);
}
}
return true;
}
if(!b.isValid()){
//console.log('invalid board')
return false;
}
//we reached a X unresolvable
//we don't know which pickup will lead to a resolution different than X
//however, if we mark that X as being resolved, we don't need to
//resolve it twice
if(cache.has(b.image())){
//console.log('board has already been solved')
return true;
}
cache.add(b.image());
//try to pick an element!
//order matters if you only want one solution
//but here we process everybody
var pickups = b.orderPickups();
var hasSolution = false;
pickups.forEach(p=>{
//console.log(b.pre, 'pickup ', p)
var hope = b.fork();
hope.h.setAtLeast(p);
hope.history.push(p);
var ok = solve(hope, cache, solutions);
hasSolution |= ok;
});
return hasSolution;
}
var h = new H(toAdj.toAdj(), toAdj.toB());
var b = new Bot(h);
//b.verbose = true;
var X = new Set;
var solutions = new Map;
solve(b, X, solutions);
console.log('solutions: ', solutions.size)
solutions.forEach((v,k)=>{
v.b.pre = '';
v.b.verbose = true;
v.b.disp();
//best guess was:
var res = [...v.spicks].sort((a,b)=>a.length-b.length)[0];
if(res.length){
console.log('guess forced. best picks were', res)
}
})//bot.js
function Bot(h){
this.verbose = false;
this.h = h;
this.pre = '';
this.h._log = this.log.bind(this);
this.history = [];
}
Bot.prototype.image = function(){
return this.h.X.join(';')+this.h.Card.join(';');
}
Bot.prototype.simplifyK = function(){
var h = this.h;
//first get rows with no more
var nomoreDone = h.someK(r=>{
if(h.bound(r)==0){
if(h.sum(r) == 0){
this.log('simplifyK::flush before dude ');
h.dispRow(r);
h.rmK(r);
return true;
}
//nomore path
var row = h.row(r);
row.forEach((c,i)=>{
h.dispRow(r)
if(c){
this.log('simplifyK::nomore ', i)
h.setNoMore(i);
}
})
return true;
}
});
if(nomoreDone){
return true
};
return h.someK(r=>{
//we know that bound is not 0
var row = h.row(r);
var s = row.reduce((acc,x)=>acc+x,0);
var bound = h.bound(r);
if(s == bound){
this.log('simplifyK::sumbound')
h.dispRow(r)
return row.some((c,i)=>{
if(c){
this.log('simplifyK::setAtLeast', i)
h.setAtLeast(i);
return true;
}
})
}
if(h.singleElem(r)){//bound //0
return row.some((c,i)=>{
if(c){
this.log('simplifyK::sse')
h.dispRow(r)
if(c < bound){
this.log('WTF!!')
return false;
}
this.log('simplifyK::sse::atleast ', i);
h.setAtLeast(i);
return true;
}
})
}
});
}
Bot.prototype.simplifyG = function(){
var h = this.h;
var ok = h.someG(r=>{
var bound = h.bound(r);
if(h.singleElem(r)){
return h.row(r).some((c,i)=>{
if(c){
this.log('simplifyG::singleElem')
if(c<bound){
this.log('WTF');
}
h.dispRow(r)
for(var j=0; j<bound; ++j){
this.log('simplifyG::atLeast single', i)
h.setAtLeast(i);
}
//IN CASE we get an eq with 0, resimplify K
actionTaken = true;
return true;
}
})
}
var row = h.row(r);
if(row.reduce((acc,x)=>acc+x,0) == bound){
var actionTaken = false;
this.log('simplifyG::sumeq')
h.dispRow(r)
row.forEach((c,i)=>{
if(c){
for(var j=0; j<c; ++j){
this.log('simplifyG::atLeast bound', i, 'and size is : ', h.G.length)
actionTaken = h.setAtLeast(i);
}
}
})
this.log('finiiiished')
return actionTaken;
}
});
if(ok){
h.G = [];
return ok;
}
}
Bot.prototype.simplifyL = function(){
/*
You cannot simplify L has of modelized
given a tuple _ _ 3 _ |2
namely {3,3,3} maximum el 2
you cannot derive anything.
Someone who gets {3,3,3,3,3} can arbitrarily take |{3,3,3}|=2 + |{3,3}|=0..2
eventually you could derive some random guy who gets
{3,3,3,3,3,3,3}<=6, and use {3,3,3}<=1 such that |{3(7+)}| = |{3(3)}| + |{3(4)}| <= 1+4
there is low probability of such occurrence, dropping it
*/
var actionTaken = false;
return actionTaken;
}
Bot.prototype.deriveKK = function(){
var actionTaken = false;
var h = this.h;
return h.someKK((a,b)=>{
var eq = h.substitute(a,b);
if(eq){
//you cant just replace, because the added row is not an equivalence but an implication
//you can ONLY replace if the resulting row has no elements from the common elements
//that is it only contains the numbers from b which can not be found in a
//if there is common. you thus cant use noMore (because the commonElem does not represent the whole set)
//but you can use at least
//if there is no common, you can use both
//
//for this discrepancy handle it separately here
actionTaken = false;
var common = h.common(a,b);
var com2 = h.common(common, eq);
var hasCommon = com2.some(x=>x!=0);
h.dispRow(a)
h.dispRow(b)
h.dispRow(eq)
if(!hasCommon){
//we can substitue
this.log('deriveKK::substitute')
h.rmK(b);
return h.addK(eq);
}
this.log('deriveKK::ffs')
//we cannot substitute.
//however we can still use atleast (should the sum...)
//AND atmost only on non common
var r = h.row(eq);
var b = h.bound(eq);
var s = r.reduce((acc,x)=>acc+x,0);
if(b == 0){
//noMore only on external elems
r.forEach((c,i)=>{
if(com2[i]){return;}
if(c){
this.log('deriveKK::nomore ',i)
actionTaken |= h.setNoMore(i);
}
});
}else{
if(b == s){
//only at least
r.forEach((c,i)=>{
if(c){
for(var j = 0; j<c; ++j){
this.log('deriveKK::atleast ', i);
actionTaken |= h.setAtLeast(i);
}
}
});
}
}
return actionTaken;
}
var geq = h.atLeastEq(a,b);
if(geq){
this.log('deriveKK::atleasteq')
h.dispRow(a);
h.dispRow(b);
h.dispRow(geq)
actionTaken |= h.addG(geq);
return false;
}
}) || actionTaken;
}
Bot.prototype.log = function(...v){
if(this.pre){
v.unshift(this.pre);
}
if(this.verbose){
console.log.apply(console, v);
}
}
Bot.prototype.flush = function(){
var flushed = this.h.flush();
if(this.h.K.length == 0){
//if you don't have equations
//there is no constraint anymore, just drop them
//this is a workaround because we don't track parents of
//contraints. See setAtLeast
this.h.G = [];
}
return flushed;
}
Bot.prototype.disp = function(){
return this.h.disp();
}
Bot.prototype.fork = function(){
var b = new Bot(this.h.fork());
b.h._log = b.log.bind(b);
b.pre = this.pre+' ';
b.history = this.history.slice();
return b;
}
Bot.prototype.orderPickups = function(){
//DUMB as fuck: just take no empty columns
var rowBase = this.h.row(this.h.atK(0));
var t = new Array(rowBase.length).fill(0);
this.h.someK(r=>{
var row = this.h.row(r);
row.forEach((c,i)=>{
if(c){
t[i] = 1;
}
})
});
return t.reduce((acc,x,i)=>{
if(x){acc.push(i)}
return acc;
},[]);
}
Bot.prototype.isValid = function(){
return this.h.isValid();
}
Bot.prototype.solved = function(){
return this.h.K.length == 0;
}
Bot.prototype.step = function(){
//possibilities are:
//from K
// simplify(K and G and L)
//
//from KxK -> G
//from KxK -> L
//
//by deriving L we would then create some G by substituting in K
//but conditions are harsh:
//the part common in L and K defines C. all the elem type of C in K must
//be included in L e.g
//120 K
//110 L => not substitutable because K holds a "1" more than L (two vs one)
//
//from G
//G inter K -> L
//from L
//L inter K -> G
//
//from GxL -> K (equalities)
var actionTaken = false;
var heuristics = {
flush: this.flush,
simpleK: this.simplifyK,
deriveKK: this.deriveKK,
simpleG: this.simplifyG
}
this.log('step start')
return Object.keys(heuristics).some(k=>{
var ok = heuristics[k].call(this);
if(ok){
this.log('step::taken : ',k);
return true;
}
})
}
module.exports = Bot;
ex d'output:
- Code: Tout sélectionner
//pour
//var txt = `
//4 4 4 4 6 7 7 9 9
//2 2 2 3 3 5 6 6 7
//2 2 3 3 4 4 6 8 9
//2 2 3 6 7 8 8 8 9
//1 1 1 1 5 6 6 7 9
//1 1 5 6 6 8 8 9 9
//3 3 5 6 7 7 9 9 9
//1 3 3 4 6 7 9 9 9
//3 5 5 5 6 6 7 9 9
//`;
//var b = [3, 3 ,3 ,3, 3, 3, 3, 3, 3]
node run.js
solutions: 2
###
1 1 0 1 2 0 2+ 1 0
--
--
###
guess forced. best picks were 0;3
###
0 0 0 1 1 1 1 1 0
--
--
###
guess forced. best picks were 3;5;6
ex2 d'output verbeux:
- Code: Tout sélectionner
//pour
//var txt = `
//1 2 4 5 5 6 6 9 1
//1 3 6 6 9 1 1 1 1
//2 5 5 6 6 8 2 2 2
//2 4 6 6 8 9 2 2 2
//3 3 3 3 3 3 3 3 3
//2 3 5 5 7 9 2 2 2
//3 4 5 5 7 3 3 3 3
//1 5 5 6 6 8 9 1 1
//1 2 4 5 5 6 6 7 9
//`;
//var b = [6,4,5,5,1,5,5,6,7]
node run.js
step start
simplifyK::sse
0 0 9 0 0 0 0 0 0 | 1
simplifyK::sse::atleast 2
step::taken : simpleK
###
_+ _+ 1+ _+ _+ _+ _+ _+ _+
2 1 0 1 2 2 0 0 1 | 6
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 2 2 0 1 0 | 5
0 4 0 1 0 2 0 1 1 | 5
0 0 8 0 0 0 0 0 0 | 0
0 4 0 0 2 0 1 0 1 | 4
0 0 4 1 2 0 1 0 0 | 4
3 0 0 0 2 2 0 1 1 | 6
1 1 0 1 2 2 1 0 1 | 7
--
--
###
step start
0 0 8 0 0 0 0 0 0 | 0
0 0 8 0 0 0 0 0 0 | 0
0 0 8 0 0 0 0 0 0 | 0
simplifyK::nomore 2
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
step::taken : simpleK
###
_+ _+ 1 _+ _+ _+ _+ _+ _+
2 1 0 1 2 2 0 0 1 | 6
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 2 2 0 1 0 | 5
0 4 0 1 0 2 0 1 1 | 5
0 0 0 0 0 0 0 0 0 | 0
0 4 0 0 2 0 1 0 1 | 4
0 0 0 1 2 0 1 0 0 | 4
3 0 0 0 2 2 0 1 1 | 6
1 1 0 1 2 2 1 0 1 | 7
--
--
###
step start
step::taken : flush
###
_+ _+ 1 _+ _+ _+ _+ _+ _+
2 1 0 1 2 2 0 0 1 | 6
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 2 2 0 1 0 | 5
0 4 0 1 0 2 0 1 1 | 5
0 4 0 0 2 0 1 0 1 | 4
0 0 0 1 2 0 1 0 0 | 4
3 0 0 0 2 2 0 1 1 | 6
1 1 0 1 2 2 1 0 1 | 7
--
--
###
step start
simplifyK::sumbound
0 0 0 1 2 0 1 0 0 | 4
simplifyK::setAtLeast 3
step::taken : simpleK
###
_+ _+ 1 1+ _+ _+ _+ _+ _+
2 1 0 0 2 2 0 0 1 | 5
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 2 2 0 1 0 | 5
0 4 0 0 0 2 0 1 1 | 4
0 4 0 0 2 0 1 0 1 | 4
0 0 0 0 2 0 1 0 0 | 3
3 0 0 0 2 2 0 1 1 | 6
1 1 0 0 2 2 1 0 1 | 6
--
--
###
step start
simplifyK::sumbound
0 0 0 0 2 0 1 0 0 | 3
simplifyK::setAtLeast 4
step::taken : simpleK
###
_+ _+ 1 1+ 1+ _+ _+ _+ _+
2 1 0 0 1 2 0 0 1 | 4
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 1 2 0 1 0 | 4
0 4 0 0 0 2 0 1 1 | 4
0 4 0 0 1 0 1 0 1 | 3
0 0 0 0 1 0 1 0 0 | 2
3 0 0 0 1 2 0 1 1 | 5
1 1 0 0 1 2 1 0 1 | 5
--
--
###
step start
simplifyK::sumbound
0 0 0 0 1 0 1 0 0 | 2
simplifyK::setAtLeast 4
step::taken : simpleK
###
_+ _+ 1 1+ 2+ _+ _+ _+ _+
2 1 0 0 0 2 0 0 1 | 3
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 0 2 0 1 0 | 3
0 4 0 0 0 2 0 1 1 | 4
0 4 0 0 0 0 1 0 1 | 2
0 0 0 0 0 0 1 0 0 | 1
3 0 0 0 0 2 0 1 1 | 4
1 1 0 0 0 2 1 0 1 | 4
--
--
###
step start
simplifyK::sumbound
0 0 0 0 0 0 1 0 0 | 1
simplifyK::setAtLeast 6
step::taken : simpleK
###
_+ _+ 1 1+ 2+ _+ 1+ _+ _+
2 1 0 0 0 2 0 0 1 | 3
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 0 2 0 1 0 | 3
0 4 0 0 0 2 0 1 1 | 4
0 4 0 0 0 0 0 0 1 | 1
0 0 0 0 0 0 0 0 0 | 0
3 0 0 0 0 2 0 1 1 | 4
1 1 0 0 0 2 0 0 1 | 3
--
--
###
step start
step::taken : flush
###
_+ _+ 1 1+ 2+ _+ 1+ _+ _+
2 1 0 0 0 2 0 0 1 | 3
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 0 2 0 1 0 | 3
0 4 0 0 0 2 0 1 1 | 4
0 4 0 0 0 0 0 0 1 | 1
3 0 0 0 0 2 0 1 1 | 4
1 1 0 0 0 2 0 0 1 | 3
--
--
###
step start
deriveKK::atleasteq
2 1 0 0 0 2 0 0 1 | 3
0 4 0 0 0 2 0 1 1 | 4
0 3 0 0 0 0 0 1 0 | 1
deriveKK::atleasteq
2 1 0 0 0 2 0 0 1 | 3
3 0 0 0 0 2 0 1 1 | 4
1 0 0 0 0 0 0 1 0 | 1
deriveKK::atleasteq
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 0 2 0 1 0 | 3
0 4 0 0 0 0 0 1 0 | 1
deriveKK::atleasteq
5 0 0 0 0 2 0 0 1 | 3
0 4 0 0 0 2 0 1 1 | 4
0 4 0 0 0 0 0 1 0 | 1
deriveKK::atleasteq
5 0 0 0 0 2 0 0 1 | 3
3 0 0 0 0 2 0 1 1 | 4
0 0 0 0 0 0 0 1 0 | 1
deriveKK::atleasteq
0 4 0 0 0 2 0 1 0 | 3
5 0 0 0 0 2 0 0 1 | 3
5 0 0 0 0 0 0 0 1 | 1
0 4 0 0 0 2 0 1 0 | 3
0 4 0 0 0 2 0 1 1 | 4
0 0 0 0 0 0 0 0 1 | 1
deriveKK::ffs
deriveKK::atleast 8
step::taken : deriveKK
###
_+ _+ 1 1+ 2+ _+ 1+ _+ 1+
2 1 0 0 0 2 0 0 0 | 2
5 0 0 0 0 2 0 0 0 | 2
0 4 0 0 0 2 0 1 0 | 3
0 4 0 0 0 2 0 1 0 | 3
0 4 0 0 0 0 0 0 0 | 0
3 0 0 0 0 2 0 1 0 | 3
1 1 0 0 0 2 0 0 0 | 2
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
0 4 0 0 0 0 0 0 0 | 0
0 4 0 0 0 0 0 0 0 | 0
simplifyK::nomore 1
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
step::taken : simpleK
###
_+ 0 1 1+ 2+ _+ 1+ _+ 1+
2 0 0 0 0 2 0 0 0 | 2
5 0 0 0 0 2 0 0 0 | 2
0 0 0 0 0 2 0 1 0 | 3
0 0 0 0 0 2 0 1 0 | 3
0 0 0 0 0 0 0 0 0 | 0
3 0 0 0 0 2 0 1 0 | 3
1 0 0 0 0 2 0 0 0 | 2
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
step::taken : flush
###
_+ 0 1 1+ 2+ _+ 1+ _+ 1+
2 0 0 0 0 2 0 0 0 | 2
5 0 0 0 0 2 0 0 0 | 2
0 0 0 0 0 2 0 1 0 | 3
0 0 0 0 0 2 0 1 0 | 3
3 0 0 0 0 2 0 1 0 | 3
1 0 0 0 0 2 0 0 0 | 2
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
simplifyK::sumbound
0 0 0 0 0 2 0 1 0 | 3
simplifyK::setAtLeast 5
step::taken : simpleK
###
_+ 0 1 1+ 2+ 1+ 1+ _+ 1+
2 0 0 0 0 1 0 0 0 | 1
5 0 0 0 0 1 0 0 0 | 1
0 0 0 0 0 1 0 1 0 | 2
0 0 0 0 0 1 0 1 0 | 2
3 0 0 0 0 1 0 1 0 | 2
1 0 0 0 0 1 0 0 0 | 1
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
simplifyK::sumbound
0 0 0 0 0 1 0 1 0 | 2
simplifyK::setAtLeast 5
step::taken : simpleK
###
_+ 0 1 1+ 2+ 2+ 1+ _+ 1+
2 0 0 0 0 0 0 0 0 | 0
5 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
3 0 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 0 0 | 0
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
2 0 0 0 0 0 0 0 0 | 0
simplifyK::nomore 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
step::taken : simpleK
###
0 0 1 1+ 2+ 2+ 1+ _+ 1+
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 0 0 | 0
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
step::taken : flush
###
0 0 1 1+ 2+ 2+ 1+ _+ 1+
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
step::taken : flush
###
0 0 1 1+ 2+ 2+ 1+ _+ 1+
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
0 3 0 0 0 0 0 1 0 | 1
1 0 0 0 0 0 0 1 0 | 1
0 4 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
simplifyK::sumbound
0 0 0 0 0 0 0 1 0 | 1
simplifyK::setAtLeast 7
step::taken : simpleK
###
0 0 1 1+ 2+ 2+ 1+ 1+ 1+
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
0 0 0 0 0 0 0 0 0 | 0
--
1 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
step::taken : flush
###
0 0 1 1+ 2+ 2+ 1+ 1+ 1+
0 0 0 0 0 0 0 0 0 | 0
--
1 0 0 0 0 0 0 1 0 | 1
0 0 0 0 0 0 0 1 0 | 1
--
###
step start
step::taken : flush
###
0 0 1 1+ 2+ 2+ 1+ 1+ 1+
--
--
###
step start
###
0 0 1 1+ 2+ 2+ 1+ 1+ 1+
--
--
###
solutions: 1
###
0 0 1 1+ 2+ 2+ 1+ 1+ 1+
--
--
###
à titre de comparaison, par force "brute" (cpp):
- Code: Tout sélectionner
#include <vector>
#include <bitset>
#include <algorithm>
#include <set>
#include <sstream>
#include <iostream>
//https://www.maths-forum.com/enigmes/simili-trouver-code-secret-t208803.html#p1368419
class Tuple{
public:
Tuple(){};
Tuple(size_t n, int value);
Tuple(const std::vector<int>& iv):v(iv){};
Tuple operator+(const Tuple& t)const;
bool isValid()const;
std::vector<int> v;//-20 means no condition, -x means x is ok, and upper than x too
size_t size()const{return v.size();}
int operator[](const size_t &i)const{return v[i];}
int& operator[](const size_t &i){return v[i];}
std::string toString()const;
static const int neutral = -20;
static const int invalid = -21;
bool operator<(const Tuple& b)const;
};
Tuple::Tuple(size_t n, int value){
v = std::vector<int>(n, value);
}
Tuple Tuple::operator+(const Tuple &b)const{
Tuple r(v.size(), Tuple::invalid);
for(size_t i = 0; i<v.size(); ++i){
if(v[i] == neutral){
r[i] = b[i];
}else if(b[i]==neutral){
r[i] = v[i];
}else if(v[i] < 0 && b[i] < 0){
r[i] = v[i]<=b[i]?v[i]:b[i];
}else if(v[i] < 0 && -v[i] <= b[i]){
r[i] = b[i];
}else if(b[i] < 0 && -b[i] <= v[i]){
r[i] = v[i];
}else if(v[i] == b[i]){
r[i] = v[i];
}else{
//incompatible cond
std::cout<<"incomp "<<toString()<<" X "<<b.toString()<<std::endl;
return r;
}
}
std::cout<<"compat "<<toString()<<" X "<<b.toString()<<"->"<<r.toString()<<std::endl;
return r;
}
bool Tuple::isValid()const{
for(const auto&el: v){
if(el == Tuple::invalid){
return false;
}
}
return true;
}
bool Tuple::operator<(const Tuple& b)const{
for(size_t i=0;i<v.size(); ++i){
if(v[i] - b.v[i] <0){
return true;
}
if(v[i] - b.v[i] >0){
return false;
}
}
return false;
}
std::string Tuple::toString()const{
std::stringstream oss;
for(const auto&el: v){
if(el == Tuple::neutral){
oss <<"_ ";
}else if(el >= 0){
oss<<el<<" ";
}else{
oss<<(-el)<<"+";
}
oss<<" ";
}
return oss.str();
}
std::string toString(const std::vector<Tuple>& layer){
std::string s;
for(const auto& t: layer){
s += t.toString()+"\n";
}
return s;
}
typedef std::vector<std::bitset<16>> combs_type;
combs_type perms(size_t r, size_t n, size_t offset){
std::vector<bool> v(n);
std::fill(v.begin(), v.begin() + r, true);
combs_type combs;
do {
combs_type::value_type C;
for (int i = 0; i < n; ++i) {
if (v[i]) {
C[offset+i] = 1;
}
}
combs.push_back(C);
} while (std::prev_permutation(v.begin(), v.end()));
return combs;
}
void run(std::vector<std::vector<int>> rrows, std::vector<int> similis){
int biggestElement = 0;
int minElement = 100;
{
for(const auto& rrow: rrows){
for(const auto&el: rrow){
if(el > biggestElement){
biggestElement = el;
}
if(el < minElement){
minElement = el;
}
}
}
}
int NElems = biggestElement - minElement +1;
std::vector<std::vector<Tuple>> layers(rrows.size());
int row_size = rrows[0].size();
for(size_t i = 0; i<rrows.size(); ++i){
//generate the tuple associated to that row
const auto& rrow = rrows[i];
Tuple t(NElems,0);
{
for(const auto& el: rrow){
t.v[el-minElement] += 1;
}
}
//get combi of
const auto& combs = perms(similis[i], row_size, 0);
std::set<Tuple> hashes;
auto& layer = layers[i];
std::cout<<"-----------\nref "<<t.toString()<<std::endl;
for(const auto& c: combs){
//for given tuple, generate its associated condition tuple
Tuple cond(NElems, Tuple::neutral);
for(size_t i = 0; i<c.size(); ++i){
if(c[i] == 1){//we must pick i-element from rrow
const auto& el = rrow[i];
if(cond.v[el-minElement] != Tuple::neutral){
cond.v[el-minElement]++;
}else{
cond.v[el-minElement] = 1;
}
}
}
//for all the values in t, if t[i], put 0 for cond if no cond specified
for(size_t i = 0; i< t.size(); ++i){
const auto& el = t[i];
if(el > 0){
if(cond.v[i] == Tuple::neutral){
cond.v[i] = 0;
}
}
}
//if cond[i] specified, if cond[i] == t[i], then put -cond[i] (meaning it is a lower bound)
for(size_t i = 0; i<cond.size(); ++i){
if(cond[i]>0){
if(cond[i] == t[i]){
cond[i] = -cond[i];
}
}
}
//add that tuple to current layer
if(hashes.find(cond)!=hashes.end()){
continue;
}
hashes.insert(cond);
layer.push_back(cond);
}
std::cout<<toString(layer)<<std::endl;
}
//foreach layer
auto acc = layers[0];
for(size_t i = 1; i<layers.size(); ++i){
std::cout<<"process layer "<<toString(layers[i])<<std::endl;
decltype(acc) v;
for(const auto& t_acc: acc){
for(const auto& t_cur: layers[i]){
const Tuple& cond = t_acc + t_cur;
if(cond.isValid()){
v.push_back(cond);
}
}
}
acc = v;
std::cout<<"kept layer\n"<<toString(acc)<<std::endl;
}
std::cout<<"solutions:"<<std::endl;
std::set<std::string> hashes;
for(auto& cond:acc){
hashes.insert(cond.toString());
}
for(const auto& hash: hashes){
std::cout<<hash<<std::endl;
}
}
int main(){
std::vector<std::vector<int>> aRows({
{1, 1, 1, 4, 6, 8, 9},
{0, 3, 5, 6, 6, 7, 9},
{1, 2, 3, 3, 5, 8, 9},
{0, 2, 2, 5, 6, 7, 7},
{2, 2, 5, 7, 8, 9, 9},
{0, 2, 3, 4, 6, 6, 9},
{4, 5, 7, 8, 8, 8, 9},
});
std::vector<int> aSim({3,3,3,3,3,3,3});
std::vector<std::vector<int>> bRows({
{2,2,4,5,5,5,7},
{1,2,4,4,5,7,7},
{1,4,5,5,7,8,8},
{1,2,3,3,3,5,5},
{1,1,4,5,5,6,8},
{1,2,3,3,4,5,8},
{1,2,4,5,5,7,8},
{4,4,5,6,6,7,8}
});
std::vector<int> bSim({2,3,4,2,4,4,4,5});
std::vector<std::vector<int>> cRows({
{1, 1, 2, 2, 2},
{1, 1, 2, 2, 3},
{1, 2, 3, 4, 4},
{3, 3, 4, 4, 5},
{3, 4, 4, 5, 5}
});
std::vector<int> cSim({3,4,3,1,3});
std::vector<std::vector<int>> dRows({
{1, 2, 2, 4, 5},
{1, 2, 2, 5, 5},
{2, 4, 1, 1, 5},
{4, 4, 4, 1, 1},
{5, 5, 4, 3, 3}
});
std::vector<int> dSim({3,3,3,3,3});
std::vector<std::vector<int>> eRows({
{2, 2, 3, 3},
{2, 3, 4, 4},
{1, 2, 2, 3},
{1, 2, 3, 4}
});
std::vector<int> eSim({2,2,2,2});
std::vector<std::vector<int>> fRows({
{4, 4, 4, 4, 6, 7, 7, 9, 9},
{2, 2, 2, 3, 3, 5, 6, 6, 7},
{2, 2, 3, 3, 4, 4, 6, 8, 9},
{2, 2, 3, 6, 7, 8, 8, 8, 9},
{1, 1, 1, 1, 5, 6, 6, 7, 9},
{1, 1, 5, 6, 6, 8, 8, 9, 9},
{3, 3, 5, 6, 7, 7, 9, 9, 9},
{1, 3, 3, 4, 6, 7, 9, 9, 9},
{3, 5, 5, 5, 6, 6, 7, 9, 9}
});
std::vector<int> fSim({3, 3 ,3 ,3, 3, 3, 3, 3, 3});
std::vector<std::vector<int>> gRows({
{1, 2, 4, 5, 5, 6, 6, 9, 1},
{1, 3, 6, 6, 9, 1, 1, 1, 1},
{2, 5, 5, 6, 6, 8, 2, 2, 2},
{2, 4, 6, 6, 8, 9, 2, 2, 2},
{3, 3, 3, 3, 3, 3, 3, 3, 3},
{2, 3, 5, 5, 7, 9, 2, 2, 2},
{3, 4, 5, 5, 7, 3, 3, 3, 3},
{1, 5, 5, 6, 6, 8, 9, 1, 1},
{1, 2, 4, 5, 5, 6, 6, 7, 9}
});
std::vector<int> gSim({6,4,5,5,1,5,5,6,7});
run(gRows, gSim);
}
Concernant les déductions mises en place:
j'ai copié test.js qui contient plus de informations, mais des les grandes lignes:
Je n'ai que trois déductions:
1) une inégalité >=
2) une substitution.
3) un nomore
4) cas d'égalité
J'appele eq le couple
combinaison|b
si on sait que il faut saisir exactement b elem dans combinaison
J'appele geq (greater than eq) le couple
combinaison>=b
si on sait que il faut au moins saisir b elems dans la combinaison
1) création d'ineg
en regardant l'exemple l4/l6 de sa majesté
1233355|2
1233458|4
la création de l'inégalité procède ainsi:
je trouve la partie commune au deux eq
12335
je déduis les restants dans la deuxieme eq:
48 >= 2
qui signifie je dois piocher au moins deux el dans {4,8} ...
A chaque fois que je peux déduire que je peux piocher un elem, j'enleve cet elem à chaque eq, et je décrois b de l'eq en question (de un)
2) la substition
dans un cas comme
12|1
123|1
on sait que il faudra pas prélever 3.
jenlève alors tous les 3 dans toutes les eq.
il y a des cas un peu edgies par exemple:
112|2
1112|2
la substitution donne 1|0, mais on peut pas enlever le 1 de tout le monde (évidemment).
3) le nomore
dans une eq
1223|0
signifie qu'il ne faut plus piocher ni 1, ni 2, ni 3.
je mets à jour les eq (en enlevant tous les 1, 2, 3)
4) égalité
pour une eq,
si la somme de ma combi vaut exactement b, alors je peux prendre un elem de la combi! (et ce autant de fois qu'il y en a dans ma combi)
ex:
1233|4
Concernant la résolution:
j'ai ma liste d'eq, je dérive des égalités, inégalités ou des substitutions.
je déduis tant que je peux
Si j'ai plus d'eq, alors j'ai trouvé une solution.
Si il m'en reste, alors je peux pas conclure et suis obligé de tenter un nombre.
je teste un et je recommence.
Si j'arrive sur un cas impossible:
la cardinalité de la combi est inférieure à b (idem on pourra jamais assez prélever suffisamment d'élément) alors la grille/élément pioché est pas bon.
j'ai eu pas mal de bugs, donc avec pincettes
)
