const fc = require('fast-check');
function xyToIndex(x, y, datasetLength) {
return x * datasetLength + y;
}
function indexToXY(index, datasetLength) {
return {x: Math.floor(index / datasetLength), y: index % datasetLength};
}
function computeF(x, y, datasetLength, outputForIndexes) {
return outputForIndexes[xyToIndex(x, y, datasetLength)];
}
function tryBuildAssociativeFunction(sourceOutputForIndexes, datasetLength, randNat) {
const firstHoleIndex = sourceOutputForIndexes.findIndex(out => out === -1);
if (firstHoleIndex === -1) {
return sourceOutputForIndexes;
}
const possibilities = [...Array(datasetLength)].map((_, index) => index);
while (possibilities.length !== 0) {
// Take one of the possibilities we have not tried yet
const outputForIndexes = [...sourceOutputForIndexes];
const possibilityIndex = randNat() % possibilities.length;
outputForIndexes[firstHoleIndex] = possibilities.splice(possibilityIndex, 1)[0];
let illegalAssignment = false;
// For each assignment try to infer linked assignment based on:
// f(f(x,y),i) === f(x,f(y,i)) and f(i,f(x,y)) === f(f(i,x),y)
const recentlyAssigned = new Set([firstHoleIndex]);
while (recentlyAssigned.size !== 0) {
const assignment = recentlyAssigned[Symbol.iterator]().next().value;
recentlyAssigned.delete(assignment);
const {x,y} = indexToXY(assignment, datasetLength);
const fxy = computeF(x, y, datasetLength, outputForIndexes);
for (let i = 0 ; i !== datasetLength ; ++i) {
// f(f(x,y),i) === f(x,f(y,i))
const fxy_i = computeF(fxy, i, datasetLength, outputForIndexes);
if (fxy_i !== -1) {
const fyi = computeF(y, i, datasetLength, outputForIndexes);
if (fyi !== -1) {
const affectedIndex = xyToIndex(x, fyi, datasetLength);
if (outputForIndexes[affectedIndex] === -1) {
recentlyAssigned.add(affectedIndex);
outputForIndexes[affectedIndex] = fxy_i;
} else if (outputForIndexes[affectedIndex] !== fxy_i) {
illegalAssignment = true;
break;
}
}
}
// f(i,f(x,y)) === f(f(i,x),y)
const fi_xy = computeF(i, fxy, datasetLength, outputForIndexes);
if (fi_xy !== -1) {
const fix = computeF(i, x, datasetLength, outputForIndexes);
if (fix !== -1) {
const affectedIndex = xyToIndex(fix, y, datasetLength);
if (outputForIndexes[affectedIndex] === -1) {
recentlyAssigned.add(affectedIndex);
outputForIndexes[affectedIndex] = fi_xy;
}
else if (outputForIndexes[affectedIndex] !== fi_xy) {
illegalAssignment = true;
break;
}
}
}
}
if (illegalAssignment) {
break;
}
}
// We added our value (taken from possibilities) and impacted the outputs based on it
// We now need to try to add another value randomly by calling tryBuildAssociativeFunction
const extended = !illegalAssignment ? tryBuildAssociativeFunction(outputForIndexes, datasetLength, randNat) : null;
if (extended !== null) {
return extended;
}
}
return null;
}
function buildAssociativeFunction(datasetLength, randNat) {
const outputForIndexes = tryBuildAssociativeFunction(
Array(datasetLength * datasetLength).fill(-1),
datasetLength,
randNat);
return (x, y) => computeF(x, y, datasetLength, outputForIndexes);
}
function binaryAssociativeFunction(arb) {
return fc.tuple(
fc.set(arb, {minLength: 1, compare: (a, b) => fc.stringify(a) === fc.stringify(b)}),
fc.infiniteStream(fc.nat()).noBias()
)
.map(([dataset, randomStream]) => {
const associativeF = buildAssociativeFunction(
dataset.length,
() => randomStream.next().value
);
const stringifiedDataset = dataset.map(d => fc.stringify(d));
return (a, b) => {
// compute index for a
const stringifiedA = fc.stringify(a);
let indexA = stringifiedDataset.indexOf(stringifiedA);
if (indexA === -1) indexA = fc.hash(stringifiedA) % dataset.length;
// compute index for b
const stringifiedB = fc.stringify(b);
let indexB = stringifiedDataset.indexOf(stringifiedB);
if (indexB === -1) indexB = fc.hash(stringifiedB) % dataset.length;
// compute answer
const indexResult = associativeF(indexA, indexB);
if (!(indexA in dataset)) throw new Error('unexpected: invalid indexA');
if (!(indexB in dataset)) throw new Error('unexpected: invalid indexB');
if (!(indexResult in dataset)) throw new Error('unexpected: invalid indexResult');
return dataset[indexResult];
};
})
}
// Just trying with one of the generated functions
const a = 'a';
const b = 'b';
const c = 'c';
const f1 = fc.sample(binaryAssociativeFunction(fc.string()), 1)[0];
console.log('a,b -> ' + f1(a, b));
console.log('(a,b),c -> ' + f1(f1(a, b), c));
console.log('b,c -> ' + f1(b, c));
console.log('a,(b,c) -> ' + f1(a, f1(b, c)));
// Property to confirm it works
fc.assert(fc.property(
binaryAssociativeFunction(fc.string()), fc.string(), fc.string(), fc.string(),
(f, a, b, c) => f(f(a,b),c) === f(a,f(b,c))))
no comments
sign in to comment