mult_8bit_2reg.py

mult_8bit_2reg.py

from dataclasses import dataclass
from typing import Iterable


@dataclass(frozen=True, slots=True)
class Program:
    state: tuple[int, int]
    instructions: list[str]

    @property
    def length(self) -> int:
        return len(self.instructions)

    def __repr__(self) -> str:
        a, b = self.state
        # return f"({a:>4}, {b:>4}) {' '.join(self.instructions)}"
        return " ".join(self.instructions)


def get_longer_programs(p: Program) -> Iterable[Program]:
    a, b = p.state
    if p.length == 0:
        yield Program((0, b), p.instructions + ["-a"])
    yield Program(((a + a) % 0x100, b), p.instructions + ["+a"])
    yield Program(((a + b) % 0x100, b), p.instructions + ["+b"])
    yield Program(((a - b) % 0x100, b), p.instructions + ["-b"])
    yield Program((a, a), p.instructions + [">b"])


programs: dict[tuple[int, int], Program] = {}
progs_of_current_length = [Program((1, 0), [])]

for length in range(1, 14):
    for prog in reversed(progs_of_current_length):
        programs[prog.state] = prog

    longer_programs = [
        child for prog in progs_of_current_length for child in get_longer_programs(prog) if child.state not in programs
    ]
    print(length, len(longer_programs))

    progs_of_current_length = longer_programs


optimal_programs = []

for value in range(0x100):
    progs = sorted((prog for (a, _), prog in programs.items() if a == value), key=lambda p: (p.length, p.state))
    optimal_programs.append(progs[0])


for value, prog in enumerate(optimal_programs):
    print(f"{value:>3}: {prog}")