023: 「ラベル付きSSCで最大値を求める」の解答

問題 / ヒント

難易度: ☆☆☆

方針

ラベルは、後ろにある番地を前から参照できるようにする仕組みです。 そのため、先にすべてのラベルと番地を集めます。 2回目の走査で、命令や Data を実際の整数に変換します。

最大値のプログラムでは、a - b が正なら a を答えにします。 正でなければ、同じか b が大きいので、b を答えにします。

実装

def clean_line(line):
    return line.split(";", 1)[0].strip()


def split_label(line):
    if ":" not in line:
        return (None, line)
    label, rest = line.split(":", 1)
    return (label.strip(), rest.strip())


def operand_value(text, labels):
    try:
        return int(text)
    except ValueError:
        if text not in labels:
            raise ValueError("undefined label: " + text)
        return labels[text]


def assemble_program(lines):
    labels = {}
    address = 0
    cleaned_lines = []

    for raw_line in lines:
        line = clean_line(raw_line)
        if line == "":
            continue
        label, body = split_label(line)
        if label is not None:
            if label in labels:
                raise ValueError("duplicate label: " + label)
            labels[label] = address
        if body != "":
            cleaned_lines.append(body)
            address += 1

    program = []
    for body in cleaned_lines:
        if body == "Stop":
            program.append(encode_instruction("Jump", 0))
            continue

        parts = body.split()
        if parts[0] == "Data":
            program.append(int(parts[1]))
        else:
            name = parts[0]
            operand = operand_value(parts[1], labels)
            program.append(encode_instruction(name, operand))

    return program


def maximum_program():
    return [
        "Read a",
        "Read b",
        "Load a",
        "Sub b",
        "Jump use_a",
        "Load b",
        "Store answer",
        "Load one",
        "Jump output",
        "use_a: Load a",
        "Store answer",
        "output: Write answer",
        "Stop",
        "a: Data 0",
        "b: Data 0",
        "answer: Data 0",
        "one: Data 1",
    ]


def max_with_ssc(a, b):
    program = assemble_program(maximum_program())
    outputs = run(program, [a, b])
    return outputs[0]

確認

program = assemble_program([
    "Load value",
    "Shift 1",
    "Store value",
    "Write value",
    "Stop",
    "value: Data 21",
])
assert run(program) == [42]

assert max_with_ssc(7, 9) == 9
assert max_with_ssc(12, 4) == 12
assert max_with_ssc(5, 5) == 5
assert max_with_ssc(-3, -8) == -3

発展

3つの入力に拡張するには、まず2つの最大値を求め、その結果と3つ目の値をもう一度比較します。 同じ比較ブロックをどう再利用するかが課題になります。