2013年度夏の院試の解答例です
※記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。

出題テーマ

アセンブリ

問題文

※ 東大の公式アーカイブにはすでにのっていなく、ここでは他のアーカイブサービスから取得したものを公開しますが、東京大学側から指摘があった場合は問題文を削除いたします。

※ prog.txtは公開されていないので以下は筆者が適当に作ったものです(prog5.txtはきついので作りませんでした)

配布ファイル

prog1.txt

SET x 1

prog2.txt

SET x 1
SET y 0
ADD x y
PRN x y
PRN 30 y

prog3.txt

SET x 1
SET y 0
ADD x y
ADD 1 x
CMP x 10
JMP -3 0
PRN x y

prog4.txt(サブルーチンからサブルーチンを呼ぶように後はテキトーに作った)

SET x 0
SET y 1
SUB 4 0
CMP 10 y
ADD y x
JMP 5 0
SUB 2 0
BAK 0 0
ADD 1 y
BAK 0 0
PRN x y

(1)

file_path = 'prog1.txt'
def solve(file_path):
    with open(file_path, encoding='ascii') as f:
        line1 = f.readline()
        code_array = line1.split(' ')
        order = code_array[0]
        operand1 = code_array[1]
        operand2 = code_array[2]    
        print(operand1)

(2)以下のコードを説明するだけ

y = 0
x = 1
while (x != 10):
    y += x
    x += 1
        
print(x, y)

(3)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog2.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    register = { 'x': 0, 'y': 0 }
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)
                
    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            if (isn.isNumber(op1)):
                register[op2] += isn.STRtoNumber(op1)
            else:
                register[op2] += register[op1]
        elif (order == 'PRN'):
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register[op2])
            else:
                if (isn.isNumber(op2)):
                    print(register[op1], isn.STRtoNumber(op2))
                else:
                    print(register[op1], register[op2])
                    
        elif (order == 'SET'):
            if (isn.isNumber(op2)):
                register[op1] = isn.STRtoNumber(op2)
            else:
                register[op1] = register[op2]
    for i in range(0, len(orders)):
        order = orders[i][0]
        op1 = orders[i][1]
        op2 = orders[i][2]        
        compileOrder(order, op1, op2)

(4)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog3.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    register = {}
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)
    
    # python のglobal変数が使い辛すぎるのでこうした
    next_order = { 'num': 0 }        
    
    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                register[op2] += isn.STRtoNumber(op1)
            else:
                register[op2] += register[op1]
        elif (order == 'PRN'):
            next_order['num'] += 1            
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register[op2])
            else:
                print(register[op1], register[op2])
        elif (order == 'SET'):
            next_order['num'] += 1                    
            if (isn.isNumber(op2)):
                register[op1] = isn.STRtoNumber(op2)
            else:
                register[op1] = register[op2]
        elif (order == 'CMP'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    if (isn.STRtoNumber(op1) == isn.STRtoNumber(op2)):
                        next_order['num'] += 1
                else:
                    if (isn.STRtoNumber(op1) == register[op2]):
                        next_order['num'] += 1                        
            else:
                if (isn.isNumber(op2)):
                    if (register[op1] == isn.STRtoNumber(op2)):
                        next_order['num'] += 1                        
                else:
                    if (register[op1] == register[op2]):
                        next_order['num'] += 1                        
        elif (order == 'JMP'):
            if (isn.isNumber(op1)):
                next_order['num'] += isn.STRtoNumber(op1)
            else:
                next_order['num'] += register[op1]            
    
    while (next_order['num'] < len(orders)):
        order = orders[next_order['num']][0]
        op1 = orders[next_order['num']][1]
        op2 = orders[next_order['num']][2]
#         print(order, op1, op2)
        compileOrder(order, op1, op2)

(5)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog4.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    register = {}
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)
    
    # python のglobal変数が使い辛すぎるのでこうした
    next_order = { 'num': 0 } 
    sub_order_stack = []    
    
    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                register[op2] += isn.STRtoNumber(op1)
            else:
                register[op2] += register[op1]
        elif (order == 'PRN'):
            next_order['num'] += 1            
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register[op2])
            else:
                print(register[op1], register[op2])
        elif (order == 'SET'):
            next_order['num'] += 1                    
            if (isn.isNumber(op2)):
                register[op1] = isn.STRtoNumber(op2)
            else:
                register[op1] = register[op2]
        elif (order == 'CMP'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    if (isn.STRtoNumber(op1) == isn.STRtoNumber(op2)):
                        next_order['num'] += 1
                else:
                    if (isn.STRtoNumber(op1) == register[op2]):
                        next_order['num'] += 1                        
            else:
                if (isn.isNumber(op2)):
                    if (register[op1] == isn.STRtoNumber(op2)):
                        next_order['num'] += 1                        
                else:
                    if (register[op1] == register[op2]):
                        next_order['num'] += 1                        
        elif (order == 'JMP'):
            if (isn.isNumber(op1)):
                next_order['num'] += isn.STRtoNumber(op1)
            else:
                next_order['num'] += register[op1]
        elif (order == 'SUB'):
            # 次のorderをstackに保存
            sub_order_stack.append(next_order['num']+1)
            compileOrder('JMP', op1, op2)             
        elif(order == 'BAK'):
            next_order['num'] = sub_order_stack.pop()
    
    while (next_order['num'] < len(orders)):
        order = orders[next_order['num']][0]
        op1 = orders[next_order['num']][1]
        op2 = orders[next_order['num']][2]
#         print(order, op1, op2)
        compileOrder(order, op1, op2)

(6)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog3.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)
    
    # python のglobal変数が使い辛すぎるのでこうした
    next_order = { 'num': 0 } 
    sub_order_stack = []   
    
    # register_stack[0]をglobal register(実際のレジスタ)とする
    register_stack = [{}]
    # register_stackの最後尾のregisterオブジェクトを使用することによって局所レジスタを実現
    
    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                register_stack[len(register_stack)-1][op2] += isn.STRtoNumber(op1)
            else:
                register_stack[len(register_stack)-1][op2] += register_stack[len(register_stack)-1][op1]
        elif (order == 'PRN'):
            next_order['num'] += 1            
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register_stack[len(register_stack)-1][op2])
            else:
                print(register_stack[len(register_stack)-1][op1], register_stack[len(register_stack)-1][op2])
        elif (order == 'SET'):
            next_order['num'] += 1                    
            if (isn.isNumber(op2)):
                register_stack[len(register_stack)-1][op1] = isn.STRtoNumber(op2)
            else:
                register_stack[len(register_stack)-1][op1] = register_stack[len(register_stack)-1][op2]
        elif (order == 'CMP'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    if (isn.STRtoNumber(op1) == isn.STRtoNumber(op2)):
                        next_order['num'] += 1
                else:
                    if (isn.STRtoNumber(op1) == register_stack[len(register_stack)-1][op2]):
                        next_order['num'] += 1                        
            else:
                if (isn.isNumber(op2)):
                    if (register_stack[len(register_stack)-1][op1] == isn.STRtoNumber(op2)):
                        next_order['num'] += 1                        
                else:
                    if (register_stack[len(register_stack)-1][op1] == register_stack[len(register_stack)-1][op2]):
                        next_order['num'] += 1                        
        elif (order == 'JMP'):
            if (isn.isNumber(op1)):
                next_order['num'] += isn.STRtoNumber(op1)
            else:
                next_order['num'] += register_stack[len(register_stack)-1][op1]
        elif (order == 'SUB'):
            # 次のorderをstackに保存
            sub_order_stack.append(next_order['num']+1)
            compileOrder('JMP', op1, op2)             
        elif (order == 'BAK'):
            next_order['num'] = sub_order_stack.pop()
        elif (order == 'CAL'):
            sub_order_stack.append(next_order['num']+1)
            new_register = { 'in': 0 }
            if (isn.isNumber(op2)):
                new_register['in'] = isn.STRtoNumber(op2)
            else:
                new_register['in'] = register_stack[len(register_stack)-1][op2]
            compileOrder('JMP', op1, op2)
            # JMPしてから局所レジスタをスタックに追加
            register_stack.append(new_register)
        elif (order == 'RET'):
            next_order['num'] = sub_order_stack.pop()
            # 局所レジスタを消去
            old_register = register_stack.pop()
            # 局所を抜けた後にoutを使用できるように、抜けた直後の局所registerにoutを追加
            if (isn.isNumber(op1)):
                register_stack[len(register_stack)-1]['out'] = isn.STRtoNumber(op1)
            else:
                register_stack[len(register_stack)-1]['out'] = old_register[op1]
    
    while (next_order['num'] < len(orders)):
        order = orders[next_order['num']][0]
        op1 = orders[next_order['num']][1]
        op2 = orders[next_order['num']][2]
#         print(order, op1, op2)
        compileOrder(order, op1, op2)

感想

正直筆者は知識としてアセンブリ言語を知っているだけで、実際に書いたことはあまりなく（パタヘネやOS自作入門などでちょこちょこと書いたことがあるくらい...）、そのため解くのには結構時間がかかりました。
おそらくアセンブリに全く触れたことがない人はスタックで管理するという概念がないので(5),(6)で詰む気がします。（なんなら(4)で詰むかもしれません）。
(5), (6)については考え方は多分あっていると思うのですが、配布ファイルがないため検証ができないので間違ってる可能性がやや高いです。(特に(6)はあやしいかもしれません...)
教育的にはすごくいい問題だと思いました!