The Last Instruction: Solution

Weekly Puzzle #08 of the Autumn 2026 season presented The Last Instruction, a recovered stack-machine trace wrapped in an ENCOM mainframe bench report. With Weekly Puzzle #09 now active, ranked submissions for Issue 08 have concluded.

Spoiler warning: This post contains the complete solution for Weekly Puzzle #08. If you have not reviewed the transmission yet, you can inspect the archived puzzle record.

1. The Challenge Artifact

The transmission presented an archived bench trace from a zero-address stack machine where four operational mnemonics had been replaced with unknown placeholders (K, M, R, and T). Solvers were asked to calibrate the instruction set against four bench traces, execute the stored program from an empty stack, and submit the resulting output:

ENCOM / ARCHIVED BENCH TRACE
User: FLYNN
Review queue: Master Control Program.

Stacks are written bottom -> top.
PUSH n appends decimal n.
The four other instructions are DUP, ADD,
XOR and OUT, each assigned once to K/M/R/T.
DUP copies the top. ADD and XOR pop two
values and push their sum or bitwise XOR.
OUT pops one value as an ASCII character.

Calibration (each starts independently):
[6]    K -> [6,6]   output: none
[6,3]  M -> [9]     output: none
[6,3]  R -> [5]     output: none
[65]   T -> []      output: A

PROGRAM (start with an empty stack):
PUSH 41
K
M
PUSH 1
M
T
PUSH 85
PUSH 5
R
T
PUSH 32
K
M
PUSH 1
M
T
PUSH 80
PUSH 2
M
T
PUSH 64
PUSH 11
R
T

The virtual machine operates on integer values stored in a last-in, first-out (LIFO) operand stack. The specification establishes five total operations: PUSH n (which directly encodes a literal decimal operand) and four zero-operand instructions (DUP, ADD, XOR, OUT) mapped in some one-to-one bijection to {K, M, R, T}.

2. The Traps: Arithmetic Overlaps and Stack Discipline

Several subtle assumptions can derail manual evaluation before execution completes:

1. Conflating ADD and XOR on disjoint bit patterns: For many pairs of operands, addition and bitwise XOR yield identical results. Whenever two numbers share no set bits in binary ($A \text{ AND } B = 0$), no carry bits are generated, meaning $A + B = A \oplus B$. For example, $4 + 1 = 5$ and $4 \oplus 1 = 5$. Solvers guessing or hastily testing operations on powers of two might treat ADD and XOR as interchangeable.

The calibration author specifically chose the vector [6, 3]: - $6 = 110_2$ - $3 = 011_2$

Bit 1 ($2^1 = 2$) is set in both operands ($6 \text{ AND } 3 = 2 \neq 0$). Consequently, addition generates a carry ($6 + 3 = 9$), whereas XOR clears the overlapping bit ($6 \oplus 3 = 5$). This asymmetry conclusively distinguishes ADD from XOR.

1. Guessing mnemonics from letter names: Mnemonics in custom virtual machines or obfuscated binaries rarely follow standard English naming conventions. Assuming M stands for "Multiply" would compute $6 \times 3 = 18$ instead of $9$. Assuming R stands for "Rotate" or "Remainder" would fail the calibration trace entirely. The mapping must be derived strictly from the state transitions.

2. Stack orientation and operand consumption: The specification states: "Stacks are written bottom -> top." In the notation [6, 3], $6$ sits at the bottom and $3$ is the top element. Although both addition and XOR are commutative ($a + b = b + a$ and $a \oplus b = b \oplus a$), stack orientation is critical for unary instructions like DUP and OUT:

3. DUP copies the top element.

4. OUT pops the top element and converts it to ASCII.

5. Preserving clean stack boundaries: Notice that each program block ends with T (OUT), which consumes an item. If an evaluator fails to pop emitted values or ignores stack depth, lingering values will alter the stack layout of subsequent blocks. Because each block consumes all values it produces, every emission leaves the stack cleanly emptied ([]).

3. Calibrating the Four Mnemonics

The four calibration traces run independently, starting from the specified stack configurations:

1. Identifying K (DUP)

The first calibration trace executes against a stack with one element:

[6] K -> [6, 6]   output: none

The stack grew in depth from 1 to 2, and the value $6$ was copied to the top. Neither ADD nor XOR can increase stack depth (both pop two items and push one), and OUT decreases stack depth while producing terminal output. Only DUP copies the top element without emitting output.

$$\mathbf{K \equiv DUP}$$

2. Identifying T (OUT)

The fourth calibration trace executes against a stack holding the value $65$:

[65] T -> []   output: A

The stack decreases in depth from 1 to 0, and the character 'A' is emitted. In the standard ASCII/UTF-8 character set, decimal $65$ maps directly to uppercase A (chr(65) == 'A'). Only OUT consumes a value and produces character output.

$$\mathbf{T \equiv OUT}$$

3. Disambiguating M (ADD) and R (XOR)

Traces 2 and 3 both take a two-element stack [6, 3] and reduce it to a single value without producing output. They represent the two binary operators:

• Trace 2: [6, 3] M -> [9] $$6 + 3 = 9$$ This matches integer addition. Thus, $\mathbf{M \equiv ADD}$.

• Trace 3: [6, 3] R -> [5] In binary: $$6_{10} = 110_2, \quad 3_{10} = 011_2$$ $$110_2 \oplus 011_2 = 101_2 = 5_{10}$$ This matches bitwise XOR. Thus, $\mathbf{R \equiv XOR}$.

4. Tracing the Program Execution

With the instruction table established, we execute the program step by step starting with an initially empty stack:

Block 1: Emitting the First Character

PUSH 41
K
M
PUSH 1
M
T

1. PUSH 41: Stack becomes [41].
2. K (DUP): Duplicate top value. Stack becomes [41, 41].
3. M (ADD): Pop $41$ and $41$, push $41 + 41 = 82$. Stack becomes [82].
4. PUSH 1: Push literal $1$. Stack becomes [82, 1].
5. M (ADD): Pop $1$ and $82$, push $82 + 1 = 83$. Stack becomes [83].
6. T (OUT): Pop $83$ and output chr(83) $\to$ S. Stack is now empty ([]).

Block 2: Emitting the Second Character

PUSH 85
PUSH 5
R
T

1. PUSH 85: Stack becomes [85].
2. PUSH 5: Stack becomes [85, 5].
3. R (XOR): Pop $5$ and $85$, push $85 \oplus 5$. $$85_{10} = 01010101_2, \quad 5_{10} = 00000101_2$$ $$01010101_2 \oplus 00000101_2 = 01010000_2 = 80_{10}$$ Stack becomes [80].
4. T (OUT): Pop $80$ and output chr(80) $\to$ P. Stack is now empty ([]).

Block 3: Emitting the Third Character

PUSH 32
K
M
PUSH 1
M
T

1. PUSH 32: Stack becomes [32].
2. K (DUP): Duplicate top value. Stack becomes [32, 32].
3. M (ADD): Pop $32$ and $32$, push $32 + 32 = 64$. Stack becomes [64].
4. PUSH 1: Push literal $1$. Stack becomes [64, 1].
5. M (ADD): Pop $1$ and $64$, push $64 + 1 = 65$. Stack becomes [65].
6. T (OUT): Pop $65$ and output chr(65) $\to$ A. Stack is now empty ([]).

Block 4: Emitting the Fourth Character

PUSH 80
PUSH 2
M
T

1. PUSH 80: Stack becomes [80].
2. PUSH 2: Stack becomes [80, 2].
3. M (ADD): Pop $2$ and $80$, push $80 + 2 = 82$. Stack becomes [82].
4. T (OUT): Pop $82$ and output chr(82) $\to$ R. Stack is now empty ([]).

Block 5: Emitting the Fifth Character

PUSH 64
PUSH 11
R
T

1. PUSH 64: Stack becomes [64].
2. PUSH 11: Stack becomes [64, 11].
3. R (XOR): Pop $11$ and $64$, push $64 \oplus 11$. $$64_{10} = 01000000_2, \quad 11_{10} = 00001011_2$$ $$01000000_2 \oplus 00001011_2 = 01001011_2 = 75_{10}$$ Stack becomes [75].
4. T (OUT): Pop $75$ and output chr(75) $\to$ K. Stack is now empty ([]).

Full Execution Trace

Concatenating the output characters yields:

SPARK

Submitting SPARK completed the issue. Letter case and repeated whitespace are ignored by the answer checker.

5. Verifying with Python

We can model the virtual machine and verify the entire trace in a compact Python script:

class StackMachine:
    """Minimal zero-address stack machine emulator."""

    def __init__(self) -> None:
        self.stack: list[int] = []
        self.output: list[str] = []

    def execute_instruction(self, line: str, opcode_map: dict[str, str]) -> None:
        parts = line.strip().split()
        if not parts:
            return

        cmd = parts[0]
        if cmd == "PUSH":
            self.stack.append(int(parts[1]))
            return

        op = opcode_map.get(cmd, cmd)
        if op == "DUP":
            self.stack.append(self.stack[-1])
        elif op == "ADD":
            b = self.stack.pop()
            a = self.stack.pop()
            self.stack.append(a + b)
        elif op == "XOR":
            b = self.stack.pop()
            a = self.stack.pop()
            self.stack.append(a ^ b)
        elif op == "OUT":
            val = self.stack.pop()
            self.output.append(chr(val))
        else:
            raise ValueError(f"Unknown instruction: {op}")


# Calibrated mnemonic mapping
opcode_map = {
    "K": "DUP",
    "M": "ADD",
    "R": "XOR",
    "T": "OUT",
}

# Verify calibration traces
vm = StackMachine()
vm.stack = [6]
vm.execute_instruction("K", opcode_map)
assert vm.stack == [6, 6] and vm.output == []

vm = StackMachine()
vm.stack = [6, 3]
vm.execute_instruction("M", opcode_map)
assert vm.stack == [9] and vm.output == []

vm = StackMachine()
vm.stack = [6, 3]
vm.execute_instruction("R", opcode_map)
assert vm.stack == [5] and vm.output == []

vm = StackMachine()
vm.stack = [65]
vm.execute_instruction("T", opcode_map)
assert vm.stack == [] and vm.output == ["A"]

# Execute challenge program
program = """
PUSH 41
K
M
PUSH 1
M
T
PUSH 85
PUSH 5
R
T
PUSH 32
K
M
PUSH 1
M
T
PUSH 80
PUSH 2
M
T
PUSH 64
PUSH 11
R
T
"""

vm = StackMachine()
for line in program.strip().splitlines():
    vm.execute_instruction(line, opcode_map)

result = "".join(vm.output)
print("Emitted Output:", result)
assert result == "SPARK"
assert vm.stack == []

6. Stack Machines in Practice

The mechanics of The Last Instruction reflect foundational architecture principles used across compilers, runtimes, and security engineering:

Zero-Address Architectures and Forth

In register-based architectures (like x86-64 or ARM), instructions must explicitly designate source and destination registers (e.g., add eax, ebx). In contrast, a zero-address stack machine implicitly operates on the top of the stack (TOS). Concatenative languages such as Forth, PostScript, and Joy pioneered this paradigm. Programs consist of words executed in postfix order (Reverse Polish Notation), eliminating the need for parentheses, temporary register allocation, or abstract syntax tree (AST) precedence tracking during interpretation.

Bytecode Virtual Machines in Production

Stack machines remain the dominant design pattern for virtual machine interpreters and intermediate representations: - JVM and Dalvik/ART: Java compiles source code into JVM stack bytecode (iload, iadd, dup), allowing simple and compact class file formats. - WebAssembly (Wasm): Wasm operates as a structured stack machine designed for near-native execution speed across browser engines. - CPython: The Python virtual machine execution loop (ceval.c) evaluates bytecode using an evaluation stack (PUSH, BINARY_OP, STORE_FAST), balancing implementation clarity with portable execution. - Ethereum Virtual Machine (EVM): The EVM uses a 256-bit word stack machine architecture to execute smart contracts deterministically across decentralized nodes.

VM-Based Code Obfuscation and Deobfuscation

In binary security and malware analysis, VM obfuscation (used by tools like VMProtect and Themida) replaces native machine instructions with custom, randomized bytecode interpreted by an embedded virtual machine. Each compilation randomizes the instruction opcodes and handler entry points.

Reverse engineers analyze such binaries through trace-based instruction recovery—capturing execution traces under controlled inputs, observing stack depth and register side-effects, and synthesizing semantic equivalences. This exact methodology unlocked K, M, R, and T from the bench calibration logs.

TRON Theming

The bench trace header—attributing the log to ENCOM, User FLYNN, and the review queue of the Master Control Program—pays homage to the 1982 science fiction landmark TRON. Kevin Flynn, a talented software developer formerly employed by computer corporation ENCOM, discovered his game code had been appropriated by executive Ed Dillinger. Flynn's efforts to infiltrate ENCOM's mainframe to expose the theft led to him being digitized by the MCP's scanning laser and thrust into the computer gladiatorial arena.

As with the Serenity freight bay in Issue 07 and Wayne Enterprises in Issue 05, the thematic shell contextualizes the recovered artifact, while the challenge itself rests on the clean mechanics of stack virtual machines.

More Weekly Puzzles

Want another technical puzzle? Explore the weekly puzzles →