Bookmark this: tool.io/generate/3sat-instance/source-code
3SAT Instance Generator Source Code
Browse the implementation files for 3SAT Instance Generator.tool.ts typescript
// Tool: 3SAT Instance Generator
type GenerationMode = 'planted-satisfiable' | 'unrestricted';
const MAX_CLAUSES = 10_000;
const MAX_VARIABLES = 10_000;
const MODES: GenerationMode[] = [
'unrestricted',
'planted-satisfiable'
];
const parsePositiveInteger = (
input: unknown,
maximum: number
): number | null => {
if (
(typeof input !== 'string' && typeof input !== 'number') ||
(typeof input === 'string' && input.trim() === '')
) {
return null;
}
const value = Number(input);
return Number.isSafeInteger(value) &&
value >= 1 &&
value <= maximum
? value
: null;
};
const parseProbability = (input: unknown): number | null => {
if (
(typeof input !== 'string' && typeof input !== 'number') ||
(typeof input === 'string' && input.trim() === '')
) {
return null;
}
const value = Number(input);
return Number.isFinite(value) && value >= 0 && value <= 1
? value
: null;
};
const createRandom = (seed: string): (() => number) => {
let state = 2166136261;
for (let index = 0; index < seed.length; index += 1) {
state ^= seed.charCodeAt(index);
state = Math.imul(state, 16777619);
}
return () => {
state += 0x6d2b79f5;
let value = state;
value = Math.imul(value ^ (value >>> 15), value | 1);
value ^= value + Math.imul(value ^ (value >>> 7), value | 61);
return ((value ^ (value >>> 14)) >>> 0) / 4294967296;
};
};
const randomInteger = (
minimum: number,
maximum: number,
random: () => number
): number =>
minimum + Math.floor(random() * (maximum - minimum + 1));
export const generate3satInstance = (
variableCountInput: unknown,
clauseCountInput: unknown,
positiveLiteralProbabilityInput: unknown,
distinctVariablesInput: unknown,
modeInput: unknown,
seedInput: unknown
): string => {
const variableCount = parsePositiveInteger(
variableCountInput,
MAX_VARIABLES
);
const clauseCount = parsePositiveInteger(
clauseCountInput,
MAX_CLAUSES
);
const positiveLiteralProbability = parseProbability(
positiveLiteralProbabilityInput
);
if (
variableCount === null ||
clauseCount === null ||
positiveLiteralProbability === null ||
(distinctVariablesInput !== 'yes' &&
distinctVariablesInput !== 'no') ||
!MODES.includes(modeInput as GenerationMode) ||
typeof seedInput !== 'string' ||
seedInput.trim() === '' ||
(distinctVariablesInput === 'yes' && variableCount < 3)
) {
return '';
}
const mode = modeInput as GenerationMode;
const random = createRandom(seedInput);
const plantedAssignment =
mode === 'planted-satisfiable'
? Array.from(
{ length: variableCount },
() => random() < 0.5
)
: undefined;
const clauses: number[][] = [];
for (let clauseIndex = 0; clauseIndex < clauseCount; clauseIndex += 1) {
const variables: number[] = [];
while (variables.length < 3) {
const variable = randomInteger(1, variableCount, random);
if (
distinctVariablesInput === 'no' ||
!variables.includes(variable)
) {
variables.push(variable);
}
}
const clause = variables.map((variable) =>
random() < positiveLiteralProbability
? variable
: -variable
);
if (
plantedAssignment !== undefined &&
!clause.some(
(literal) =>
(literal > 0) ===
plantedAssignment[Math.abs(literal) - 1]
)
) {
const literalIndex = randomInteger(0, 2, random);
const variable = Math.abs(clause[literalIndex]);
clause[literalIndex] = plantedAssignment[variable - 1]
? variable
: -variable;
}
clauses.push(clause);
}
return JSON.stringify(
{
clauseCount,
clauses,
distinctVariables: distinctVariablesInput === 'yes',
mode,
positiveLiteralProbability,
...(plantedAssignment === undefined
? {}
: { plantedAssignment }),
seed: seedInput,
variableCount
},
null,
2
);
};
export const Tool: TypeTool = {
name: '3SAT Instance Generator',
slug: 'generate/3sat-instance',
intro: 'Generate a reproducible Boolean 3SAT instance as JSON.',
tool: generate3satInstance,
i: [
{
example: '20',
label: 'Variable Count',
placeholder: 'Number of Boolean variables',
type: 'number',
value: 20
},
{
example: '80',
label: 'Clause Count',
placeholder: 'Number of three-literal clauses',
type: 'number',
value: 80
},
{
example: '0.5',
help: 'Probability that a generated literal is positive before satisfiability adjustment.',
label: 'Positive Literal Probability',
placeholder: 'Probability from 0 to 1',
type: 'number',
value: 0.5
},
{
example: 'yes',
label: 'Distinct Variables per Clause',
placeholder: 'Require distinct variables',
type: 'select',
value: 'yes',
options: [
{ value: 'yes', text: 'Yes', selected: true },
{ value: 'no', text: 'No' }
]
},
{
example: 'unrestricted',
label: 'Generation Mode',
placeholder: 'Select a generation mode',
type: 'select',
value: 'unrestricted',
options: [
{
value: 'unrestricted',
text: 'Unrestricted',
selected: true
},
{
value: 'planted-satisfiable',
text: 'Planted satisfiable'
}
]
},
{
example: 'tool.io',
label: 'Seed',
placeholder: 'Random seed',
type: 'text',
value: 'tool.io'
}
],
o: [
{
example: '{ "clauses": [[1, -2, 3]] }',
label: '3SAT Instance',
placeholder: 'Generated JSON will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title: 'Boolean satisfiability problem - Wikipedia',
url: 'https://en.wikipedia.org/wiki/Boolean_satisfiability_problem'
}
]
};
export default Tool;
Description
Browse the implementation files for 3SAT Instance Generator.