logigate/app/lib/logic/challenges.ts

101 lines
5.3 KiB
TypeScript
Raw Permalink Normal View History

// Challenges in the spirit of "Turing Complete": a target behaviour, you
// build it from NAND (and your earlier parts), the checker runs the tests.
import type { TestStep } from './analyze'
import type { SymbolKind } from './types'
export interface Challenge {
id: string
name: string
goal: string
inputs: string[]
outputs: string[]
symbol?: SymbolKind
/** Combinational: outputs as a function of the inputs, checked for every combination. */
fn?: (ins: number[]) => number[]
/** Sequential: explicit steps, checked in order. */
steps?: TestStep[]
}
const b = (v: boolean) => (v ? 1 : 0)
export const CHALLENGES: Challenge[] = [
{ id: 'not', name: 'NOT', symbol: 'not', inputs: ['A'], outputs: ['Q'], goal: 'Q is the opposite of A.', fn: ([a]) => [b(!a)] },
{ id: 'and', name: 'AND', symbol: 'and', inputs: ['A', 'B'], outputs: ['Q'], goal: 'Q is 1 only when A and B are both 1.', fn: ([a, c]) => [b(!!a && !!c)] },
{ id: 'or', name: 'OR', symbol: 'or', inputs: ['A', 'B'], outputs: ['Q'], goal: 'Q is 1 when A or B (or both) are 1.', fn: ([a, c]) => [b(!!a || !!c)] },
{ id: 'nor', name: 'NOR', symbol: 'nor', inputs: ['A', 'B'], outputs: ['Q'], goal: 'Q is 1 only when both inputs are 0.', fn: ([a, c]) => [b(!a && !c)] },
{ id: 'xor', name: 'XOR', symbol: 'xor', inputs: ['A', 'B'], outputs: ['Q'], goal: 'Q is 1 when exactly one input is 1.', fn: ([a, c]) => [b(a !== c)] },
{ id: 'xnor', name: 'XNOR', symbol: 'xnor', inputs: ['A', 'B'], outputs: ['Q'], goal: 'Q is 1 when both inputs are equal.', fn: ([a, c]) => [b(a === c)] },
{ id: 'and3', name: 'AND 3', symbol: 'and', inputs: ['A', 'B', 'C'], outputs: ['Q'], goal: 'Q is 1 only when all three inputs are 1.', fn: ([a, c, d]) => [b(!!a && !!c && !!d)] },
{ id: 'mux', name: 'Mux', inputs: ['A', 'B', 'S'], outputs: ['Q'], goal: 'Q follows A while S is 0, and B while S is 1.', fn: ([a, c, s]) => [s ? c! : a!] },
{ id: 'demux', name: 'Demux', inputs: ['D', 'S'], outputs: ['A', 'B'], goal: 'Send D to A while S is 0, to B while S is 1. The other output stays 0.', fn: ([d, s]) => [b(!!d && !s), b(!!d && !!s)] },
{ id: 'dec2', name: 'Decoder 2→4', inputs: ['A1', 'A0'], outputs: ['Y0', 'Y1', 'Y2', 'Y3'], goal: 'Exactly one output is 1: the one whose number is A1 A0 in binary.', fn: ([a1, a0]) => { const n = a1! * 2 + a0!; return [0, 1, 2, 3].map(i => b(i === n)) } },
{ id: 'ha', name: 'Half Adder', inputs: ['A', 'B'], outputs: ['S', 'C'], goal: 'A + B as a two-bit number: C is the carry, S the sum bit.', fn: ([a, c]) => { const s = a! + c!; return [s & 1, s >> 1] } },
{ id: 'fa', name: 'Full Adder', inputs: ['A', 'B', 'Cin'], outputs: ['S', 'Cout'], goal: 'A + B + Cin: Cout is the carry, S the sum bit.', fn: ([a, c, d]) => { const s = a! + c! + d!; return [s & 1, s >> 1] } },
{ id: 'eq2', name: 'Equal 2', inputs: ['A1', 'A0', 'B1', 'B0'], outputs: ['EQ'], goal: 'EQ is 1 when the two-bit numbers A1A0 and B1B0 are equal.', fn: ([a1, a0, b1, b0]) => [b(a1 === b1 && a0 === b0)] },
{ id: 'add2', name: 'Adder 2', inputs: ['A1', 'A0', 'B1', 'B0'], outputs: ['C', 'S1', 'S0'], goal: 'Add two 2-bit numbers. C S1 S0 is the 3-bit result.', fn: ([a1, a0, b1, b0]) => { const s = a1! * 2 + a0! + b1! * 2 + b0!; return [(s >> 2) & 1, (s >> 1) & 1, s & 1] } },
{
id: 'sr',
name: 'SR Latch',
inputs: ['S', 'R'],
outputs: ['Q'],
goal: 'Memory! S = 1 sets Q to 1, R = 1 resets Q to 0. With both at 0, Q keeps its value.',
steps: [
{ set: { S: 1, R: 0 }, expect: { Q: 1 } },
{ set: { S: 0, R: 0 }, expect: { Q: 1 } },
{ set: { S: 0, R: 1 }, expect: { Q: 0 } },
{ set: { S: 0, R: 0 }, expect: { Q: 0 } },
{ set: { S: 1, R: 0 }, expect: { Q: 1 } },
{ set: { S: 0, R: 0 }, expect: { Q: 1 } },
],
},
{
id: 'dlatch',
name: 'D Latch',
inputs: ['D', 'E'],
outputs: ['Q'],
goal: 'While E is 1, Q follows D. While E is 0, Q holds the last value.',
steps: [
{ set: { D: 1, E: 1 }, expect: { Q: 1 } },
{ set: { D: 0, E: 1 }, expect: { Q: 0 } },
{ set: { D: 1, E: 0 }, expect: { Q: 0 } },
{ set: { D: 1, E: 1 }, expect: { Q: 1 } },
{ set: { D: 1, E: 0 }, expect: { Q: 1 } },
{ set: { D: 0, E: 0 }, expect: { Q: 1 } },
],
},
{
id: 'dff',
name: 'D Flip-Flop',
inputs: ['D', 'CLK'],
outputs: ['Q'],
goal: 'Q takes the value of D only at the moment CLK goes from 0 to 1 (rising edge), and holds it otherwise.',
steps: [
{ set: { D: 1, CLK: 0 }, expect: {} },
{ set: { D: 1, CLK: 1 }, expect: { Q: 1 } },
{ set: { D: 0, CLK: 1 }, expect: { Q: 1 } },
{ set: { D: 0, CLK: 0 }, expect: { Q: 1 } },
{ set: { D: 0, CLK: 1 }, expect: { Q: 0 } },
{ set: { D: 1, CLK: 1 }, expect: { Q: 0 } },
{ set: { D: 1, CLK: 0 }, expect: { Q: 0 } },
{ set: { D: 1, CLK: 1 }, expect: { Q: 1 } },
],
},
]
/** Test steps for a challenge: explicit ones, or every input combination. */
export function challengeSteps(c: Challenge): TestStep[] {
if (c.steps) return c.steps
const n = c.inputs.length
const steps: TestStep[] = []
for (let i = 0; i < 1 << n; i++) {
const ins = c.inputs.map((_, k) => (i >> (n - 1 - k)) & 1)
const outs = c.fn!(ins)
steps.push({
set: Object.fromEntries(c.inputs.map((l, k) => [l, ins[k]!])),
expect: Object.fromEntries(c.outputs.map((l, k) => [l, outs[k]!])),
})
}
return steps
}