Skip to content

Instantly share code, notes, and snippets.

@pvdz
Created August 24, 2017 17:12
Show Gist options
  • Save pvdz/e7f14c45581c416fb896b0fa495269f0 to your computer and use it in GitHub Desktop.
Save pvdz/e7f14c45581c416fb896b0fa495269f0 to your computer and use it in GitHub Desktop.
This takes an fdq input problem, solves it, and confirms the result is correct. I use it to test whether transformation tricks are valid, where I don't care about the actual results as long as they are valid. This will automate this process, prevent me from having to write a zillion results by hand, and of course maintain them as they can change…
import Solver from '../../src/solver';
import {
domain__debug,
domain_arrToSmallest,
domain_createValue,
domain_divby,
domain_intersection,
domain_mul,
} from '../../src/domain';
import domain_plus from '../../src/doms/domain_plus';
import domain_minus from '../../src/doms/domain_minus';
function max(v) {
if (typeof v === 'number') return v;
if (!(v instanceof Array)) throw new Error('bad value ['+v+']');
return v[v.length-1];
}
function min(v) {
if (typeof v === 'number') return v;
if (!(v instanceof Array)) throw new Error('bad value ['+v+']');
return v[0];
}
function all(v, f) {
if (typeof v === 'number') return f(v, 0);
if (!(v instanceof Array)) throw new Error('bad value ['+v+']');
v.forEach(f);
}
function dom(v) {
if (typeof v === 'number') return domain_createValue(v);
if (!(v instanceof Array)) throw new Error('bad value ['+v+']');
return domain_arrToSmallest(v);
}
function scrubStack(stack) {
let s = '';
if (stack) {
s = '\n' + stack.split(/\n/g).filter(s => s.indexOf('.spec.js') >= 0 && s.indexOf('Suite') >= 0).join('\n');
}
return s;
}
function verify(dsl, ifThrowThenTheseOps='', _stack) {
if (!_stack) throw 'wtf?'
let solution;
try {
solution = Solver.pre(dsl);
} catch(e) {
if (!ifThrowThenTheseOps || ifThrowThenTheseOps === 'reject') {
throw new Error(e.message + '; stack=' + scrubStack(_stack));
}
if (e.message.indexOf('ops: '+ifThrowThenTheseOps+' #') < 0) {
throw new Error('Expected [' + ifThrowThenTheseOps + '] got [' + e.message + scrubStack(_stack) + ']');
}
return;
}
console.log('verifying solution...');
if (ifThrowThenTheseOps === 'reject') {
if (solution !== false) {
throw new Error('should reject but didnt' + scrubStack(_stack));
}
} else if (solution === false) {
throw new Error('should not reject but did anyways' + scrubStack(_stack));
} else {
dsl
.split(/\n/g)
.map(s => s.trim())
.filter(s => !!s && s[0] !== '#' && s[0] !== '@' && s[0] !== ':')
.forEach(s => line(s, solution));
}
}
function line(line, solution) {
console.log('a line:', line);
// assume this func is only used for simplified constraints. no complex nesting/naming/spacing blabla
// A @@ B
// @@@(A B ...)
// R = A @@ B
// R = @@@(A B)
let m = line.match(/([\w\d]+)\s*([^\w]+?)\s*([\w\d]+)/);
if (m && m[2] !== '=') return verifyAB(m[1], m[2], m[3], solution, line);
m = line.match(/([\w\d]+)\s*=\s*(\w+\?)\((.*?)\)/);
if (m && m[2] !== '=') return verifyCR(m[1], m[2], m[3], solution, line);
m = line.match(/([\w\d]+)\s*=\s*([\w\d]+)\s*([^\w]+?)\s*([\w\d]+)/);
if (m && m[2] !== '=') return verifyABR(m[1], m[2], m[3], m[4], solution, line);
throw new Error('implement me too!');
}
function verifyAB(A, op, B, solution, _line) {
console.log('verifyAB:', [A, op, B, solution]);
let va = parseInt(A, 10);
let vb = parseInt(B, 10);
let a = va + '' === A ? va : solution[A];
let b = vb + '' === B ? vb : solution[B];
switch (op) {
case '==':
if (typeof a !== 'number' || typeof b !== 'number' || a !== b) throw new Error('same fail');
break;
case '!=':
if (!domain_intersection(dom(a), dom(b))) break;
throw badAB(a,b, 'neq fail');
case '<':
if (max(a) < min(b)) break;
throw badAB(a,b, 'lte fail');
case '<=':
if (max(a) <= min(b)) break;
throw badAB(a,b, 'lte fail');
case '>':
if (min(a) > max(b)) break;
throw badAB(a,b, 'gt fail');
case '>=':
if (min(a) >= max(b)) break;
throw badAB(a,b, 'gte fail');
case '&':
if ((min(a) !== 0) && (min(b) !== 0)) break;
throw badAB(a,b, 'AND fail');
case '^':
if ((min(a) === 0) != (min(b) === 0)) break;
throw badAB(a,b, 'xor fail');
case '|':
if ((min(a) !== 0) || (min(b) !== 0)) break;
throw badAB(a,b, 'OR fail');
case '!&':
if ((min(a) === 0) || (min(b) === 0)) break;
throw badAB(a,b, 'nand fail');
case '!^':
if ((min(a) === 0) === (min(b) === 0)) break;
throw badAB(a,b, 'xnor fail');
case '!|':
if ((min(a) === 0) === (min(b) === 0)) break;
throw badAB(a,b, 'NONE fail');
case '->':
if ((min(a) === 0) || (min(b) !== 0)) break;
throw badAB(a,b, 'IMP fail');
case '!->':
if ((min(a) !== 0) || (min(b) === 0)) break;
throw badAB(a,b, 'nimp fail');
default:
throw new Error('verifyAB; implement me pleaaaase: ' + op + '; [' + _line + ']');
}
}
function verifyABR(R, A, op, B, solution, _line) {
console.log('verifyAB:', [A, op, B, '=', R, solution]);
let va = parseInt(A, 10);
let vb = parseInt(B, 10);
let vr = parseInt(R, 10);
let a = va + '' === A ? va : solution[A];
let b = vb + '' === B ? vb : solution[B];
let r = vr + '' === R ? vr : solution[R];
switch (op) {
case '==?':
if ((min(r) > 0) === (typeof a === 'number' && typeof b === 'number' && a === b)) break;
throw badABR(a,b,r, 'issame fail');
case '!=?':
if ((min(r) > 0) === !domain_intersection(dom(a), dom(b))) break;
throw badABR(a,b,r, 'isdiff fail');
case '&?':
if ((min(r) > 0) === (min(a) > 0 && min(b) > 0)) break;
throw badABR(a,b,r, 'isall fail');
case '!&?':
if ((min(r) > 0) !== (min(a) > 0 && min(b) > 0)) break;
throw badABR(a,b,r, 'isnall fail');
case '|?':
if ((min(r) > 0) === (min(a) > 0 || min(b) > 0)) break;
throw badABR(a,b,r, 'issome fail');
case '!|?':
if ((min(r) > 0) !== (min(a) > 0 || min(b) > 0)) break;
throw badABR(a,b,r, 'isnone fail');
case '<?':
if ((min(r) > 0) === (max(a) < min(b))) break;
throw badABR(a,b,r, 'islt fail');
case '<=?':
if ((min(r) > 0) === (max(a) <= min(b))) break;
throw badABR(a,b,r, 'islte fail');
case '+':
if (dom(r) === (domain_plus(dom(a), dom(b)))) break;
throw badABR(a,b,r, 'sum fail');
case '-':
if (dom(r) === (domain_minus(dom(a), dom(b)))) break;
throw badABR(a,b,r, 'minus fail');
case '*':
if (dom(r) === (domain_mul(dom(a), dom(b)))) break;
throw badABR(a,b,r, 'mul fail');
case '/':
if (dom(r) === (domain_divby(dom(a), dom(b)))) break;
throw badABR(a,b,r, 'div fail');
default:
throw new Error('verifyABR; implement me pleaaaase: ' + op + '; [' + _line + ']');
}
}
function verifyCR(R, op, args, solution, _line) {
console.log('verifyAB:', [R, op, args, solution]);
let vr = parseInt(R, 10);
let r = vr + '' === R ? vr : solution[R];
let vars = args.split(/ +/g).map(v => {
let va = parseInt(v, 10);
return va + '' === v ? va : solution[v];
});
switch (op) {
case 'all?':
if ((min(r) === 0) !== vars.some(v => min(v) === 0)) throw 'isall fail';
break;
default:
throw 'verifyCR; implement me pleaaaase: ' + op + '; [' + _line + ']';
}
}
function badAB(a,b, desc) {
return new Error(desc + '; ['+[a,b]+'] [' + domain__debug(dom(a)) + ' @ ' + domain__debug(dom(b)) + ']');
}
function badABR(a,b, r, desc) {
return new Error(desc + '; ['+[r,a,b]+'] [' + domain__debug(dom(r)) + ' = ' + domain__debug(dom(a)) + ' @ ' + domain__debug(dom(b)) + ']');
}
export default verify;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment