Spaces:
Running
Running
| import { components, validateMap, type ArgumentMap } from './map.ts'; | |
| export const SEMANTICS = [ | |
| 'grounded', | |
| 'complete', | |
| 'preferred', | |
| 'stable', | |
| ] as const; | |
| export type Semantics = (typeof SEMANTICS)[number]; | |
| export type Label = 'in' | 'out' | 'undecided'; | |
| export const integer = (value: string) => BigInt(value); | |
| export type Component = { | |
| ids: string[]; | |
| outgoing: number[]; | |
| incoming: number[]; | |
| families: Record<Semantics, number[]>; | |
| trace: number[]; | |
| examined: number; | |
| }; | |
| export type Analysis = { | |
| engine: 'standpoint-exact-v1'; | |
| components: Component[]; | |
| examined: number; | |
| counts: Record<Semantics, string>; | |
| }; | |
| export function semantics(value: unknown): Semantics { | |
| if (!SEMANTICS.includes(value as Semantics)) | |
| throw new Error( | |
| 'Choose grounded, complete, preferred or stable semantics.', | |
| ); | |
| return value as Semantics; | |
| } | |
| function attacksOf(mask: number, outgoing: number[]): number { | |
| let out = 0; | |
| while (mask) { | |
| const bit = mask & -mask; | |
| out |= outgoing[31 - Math.clz32(bit)]; | |
| mask ^= bit; | |
| } | |
| return out; | |
| } | |
| export function characteristic( | |
| mask: number, | |
| c: Pick<Component, 'incoming' | 'outgoing'>, | |
| ): number { | |
| const out = attacksOf(mask, c.outgoing); | |
| let defended = 0; | |
| for (let i = 0; i < c.incoming.length; i++) | |
| if ((c.incoming[i] & ~out) === 0) defended |= 1 << i; | |
| return defended; | |
| } | |
| function solve(ids: string[], map: ArgumentMap): Component { | |
| const n = ids.length, | |
| size = 2 ** n, | |
| full = size - 1, | |
| indices = new Map(ids.map((id, i) => [id, i])); | |
| const outgoing = Array<number>(n).fill(0), | |
| incoming = Array<number>(n).fill(0); | |
| for (const e of map.attacks) | |
| if (indices.has(e.from)) { | |
| const from = indices.get(e.from)!, | |
| to = indices.get(e.to)!; | |
| outgoing[from] |= 1 << to; | |
| incoming[to] |= 1 << from; | |
| } | |
| const unions = new Uint32Array(size), | |
| admissible = new Uint8Array(size); | |
| const complete: number[] = [], | |
| stable: number[] = [], | |
| preferred: number[] = []; | |
| for (let mask = 0; mask < size; mask++) { | |
| if (mask) { | |
| const bit = mask & -mask; | |
| unions[mask] = unions[mask ^ bit] | outgoing[31 - Math.clz32(bit)]; | |
| } | |
| const out = unions[mask]; | |
| if (mask & out) continue; | |
| let defended = 0; | |
| for (let i = 0; i < n; i++) if (!(incoming[i] & ~out)) defended |= 1 << i; | |
| if ((mask & ~defended) === 0) admissible[mask] = 1; | |
| if (mask === defended) complete.push(mask); | |
| if ((mask | out) === full) stable.push(mask); | |
| } | |
| // Downward dynamic programming asks about every strict admissible superset, | |
| // including those that require adding several arguments simultaneously. | |
| const hasSuperset = new Uint8Array(admissible); | |
| for (let mask = full; mask >= 0; mask--) { | |
| let strict = 0; | |
| for (let absent = full ^ mask; absent; absent &= absent - 1) { | |
| const bit = absent & -absent; | |
| if (hasSuperset[mask | bit]) { | |
| strict = 1; | |
| break; | |
| } | |
| } | |
| if (admissible[mask] && !strict) preferred.push(mask); | |
| hasSuperset[mask] |= strict; | |
| } | |
| preferred.reverse(); | |
| const trace = [0]; | |
| for (;;) { | |
| const next = characteristic(trace[trace.length - 1], { | |
| incoming, | |
| outgoing, | |
| }); | |
| if (next === trace[trace.length - 1]) break; | |
| trace.push(next); | |
| } | |
| return { | |
| ids, | |
| incoming, | |
| outgoing, | |
| families: { | |
| grounded: [trace[trace.length - 1]], | |
| complete, | |
| preferred, | |
| stable, | |
| }, | |
| trace, | |
| examined: size, | |
| }; | |
| } | |
| export function analyze( | |
| input: unknown, | |
| progress: (done: number, total: number) => void = () => {}, | |
| ): Analysis { | |
| const map = validateMap(input), | |
| groups = components(map), | |
| total = groups.reduce((s, c) => s + 2 ** c.length, 0); | |
| let examined = 0; | |
| const result = groups.map((ids) => { | |
| const c = solve(ids, map); | |
| examined += c.examined; | |
| progress(examined, total); | |
| return c; | |
| }); | |
| const counts = Object.fromEntries( | |
| SEMANTICS.map((s) => [ | |
| s, | |
| result.reduce((p, c) => p * BigInt(c.families[s].length), 1n).toString(), | |
| ]), | |
| ) as Record<Semantics, string>; | |
| return { | |
| engine: 'standpoint-exact-v1', | |
| components: result, | |
| examined, | |
| counts, | |
| }; | |
| } | |
| export function rankIndices(indices: number[], radices: number[]): bigint { | |
| if (indices.length !== radices.length) | |
| throw new Error('Position factors do not match.'); | |
| let rank = 0n; | |
| for (let i = 0; i < radices.length; i++) { | |
| if ( | |
| !Number.isSafeInteger(radices[i]) || | |
| radices[i] < 1 || | |
| !Number.isSafeInteger(indices[i]) || | |
| indices[i] < 0 || | |
| indices[i] >= radices[i] | |
| ) | |
| throw new Error('Invalid position factor.'); | |
| rank = rank * BigInt(radices[i]) + BigInt(indices[i]); | |
| } | |
| return rank; | |
| } | |
| export function unrank(rank: bigint, radices: number[]): number[] { | |
| if ( | |
| typeof rank !== 'bigint' || | |
| rank < 0n || | |
| radices.some((k) => !Number.isSafeInteger(k) || k < 1) | |
| ) | |
| throw new Error('No position exists at this index.'); | |
| const indices = Array<number>(radices.length); | |
| for (let i = radices.length - 1; i >= 0; i--) { | |
| const k = BigInt(radices[i]); | |
| indices[i] = Number(rank % k); | |
| rank /= k; | |
| } | |
| if (rank !== 0n) throw new Error('Position index is outside this family.'); | |
| return indices; | |
| } | |
| export function position( | |
| analysis: Analysis, | |
| s: Semantics, | |
| index: string, | |
| ): { index: string; in: string[]; out: string[]; undecided: string[] } { | |
| semantics(s); | |
| if (typeof index !== 'string' || !/^(0|[1-9][0-9]{0,39})$/.test(index)) | |
| throw new Error( | |
| 'Position index must be a nonnegative decimal integer without leading zeros.', | |
| ); | |
| const indices = unrank( | |
| BigInt(index), | |
| analysis.components.map((c) => c.families[s].length), | |
| ); | |
| const labels = { | |
| index, | |
| in: [] as string[], | |
| out: [] as string[], | |
| undecided: [] as string[], | |
| }; | |
| analysis.components.forEach((c, j) => { | |
| const mask = c.families[s][indices[j]], | |
| out = attacksOf(mask, c.outgoing); | |
| c.ids.forEach((id, i) => | |
| labels[ | |
| mask & (1 << i) ? 'in' : out & (1 << i) ? 'out' : 'undecided' | |
| ].push(id), | |
| ); | |
| }); | |
| return labels; | |
| } | |
| export function acceptance( | |
| analysis: Analysis, | |
| s: Semantics, | |
| ): Record<string, Record<Label, string> | null> { | |
| semantics(s); | |
| const total = BigInt(analysis.counts[s]), | |
| result: Record<string, Record<Label, string> | null> = Object.create(null); | |
| for (const c of analysis.components) { | |
| if (total === 0n) { | |
| c.ids.forEach((id) => { | |
| result[id] = null; | |
| }); | |
| continue; | |
| } | |
| const counts = c.ids.map(() => ({ in: 0, out: 0, undecided: 0 })); | |
| for (const mask of c.families[s]) { | |
| const out = attacksOf(mask, c.outgoing); | |
| c.ids.forEach( | |
| (_, i) => | |
| counts[i][ | |
| mask & (1 << i) ? 'in' : out & (1 << i) ? 'out' : 'undecided' | |
| ]++, | |
| ); | |
| } | |
| const multiplier = total / BigInt(c.families[s].length); | |
| c.ids.forEach((id, i) => { | |
| result[id] = { | |
| in: (BigInt(counts[i].in) * multiplier).toString(), | |
| out: (BigInt(counts[i].out) * multiplier).toString(), | |
| undecided: (BigInt(counts[i].undecided) * multiplier).toString(), | |
| }; | |
| }); | |
| } | |
| return result; | |
| } | |
| export function witness( | |
| analysis: Analysis, | |
| s: Semantics, | |
| id: string, | |
| label: Label, | |
| ): string { | |
| semantics(s); | |
| if (!['in', 'out', 'undecided'].includes(label)) | |
| throw new Error('Choose an IN, OUT or UNDECIDED witness.'); | |
| if (analysis.counts[s] === '0') | |
| throw new Error('This semantics has no positions; no witness exists.'); | |
| const component = analysis.components.findIndex((c) => c.ids.includes(id)); | |
| if (component < 0) throw new Error('Unknown argument.'); | |
| const c = analysis.components[component], | |
| bit = 1 << c.ids.indexOf(id); | |
| const local = c.families[s].findIndex((mask) => { | |
| const out = attacksOf(mask, c.outgoing); | |
| return (mask & bit ? 'in' : out & bit ? 'out' : 'undecided') === label; | |
| }); | |
| if (local < 0) throw new Error('No position gives this argument that label.'); | |
| const indices = analysis.components.map(() => 0); | |
| indices[component] = local; | |
| return rankIndices( | |
| indices, | |
| analysis.components.map((c) => c.families[s].length), | |
| ).toString(); | |
| } | |
| export function defence( | |
| map: ArgumentMap, | |
| selected: ReturnType<typeof position>, | |
| id: string, | |
| ) { | |
| if (!map.arguments.some((a) => a.id === id)) | |
| throw new Error('Unknown argument.'); | |
| return map.attacks | |
| .filter((e) => e.to === id) | |
| .map((e) => ({ | |
| attacker: e.from, | |
| defenders: map.attacks | |
| .filter((d) => d.to === e.from && selected.in.includes(d.from)) | |
| .map((d) => d.from), | |
| })); | |
| } | |