東京大学大学院情報理工学系研究科 創造情報学専攻 2013年度夏 プログラミング試験

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

### 出題テーマ
- アセンブリ

### 問題文
※ 東大の公式アーカイブにはすでにのっていなく、ここでは他のアーカイブサービスから取得したものを公開しますが、東京大学側から指摘があった場合は問題文を削除いたします。
![Screen Shot 2019-11-10 at 15.51.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226167/3751292e-9067-a24f-0913-37c26610baca.png)
![Screen Shot 2019-11-10 at 18.11.14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226167/13335348-cf2e-4c60-96bf-74a43f5ee1ea.png)

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

### 配布ファイル
#### prog1.txt
```text
SET x 1
```
#### prog2.txt
```text
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(サブルーチンからサブルーチンを呼ぶように後はテキトーに作った)
```text
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)
```python
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)以下のコードを説明するだけ
```python
y = 0
x = 1
while (x != 10):
    y += x
    x += 1
        
print(x, y)
```

### (3)
```python
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)
```python
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)
```python
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)
```python
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)
```
### 感想
- 正直筆者は知識としてアセンブリ言語を知っているだけで、実際に書いたことはあまりなく（[パタヘネ](https://www.amazon.co.jp/%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%81%AE%E6%A7%8B%E6%88%90%E3%81%A8%E8%A8%AD%E8%A8%88-%E7%AC%AC5%E7%89%88-%E4%B8%8A-%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BBL-%E3%83%98%E3%83%8D%E3%82%B7%E3%83%BC/dp/4822298426/ref=sr_1_1?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&crid=2AYMYC67XORO&keywords=%E3%83%91%E3%82%BF%E3%83%98%E3%83%8D&qid=1573369857&sprefix=%E3%83%91%E3%82%BF%E3%83%98%E3%83%8D%2Caps%2C285&sr=8-1)や[OS自作入門](https://www.amazon.co.jp/30%E6%97%A5%E3%81%A7%E3%81%A7%E3%81%8D%E3%82%8B-OS%E8%87%AA%E4%BD%9C%E5%85%A5%E9%96%80-%E5%B7%9D%E5%90%88-%E7%A7%80%E5%AE%9F/dp/4839919844/ref=sr_1_1?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&crid=3AFCH381UQPGM&keywords=os%E8%87%AA%E4%BD%9C%E5%85%A5%E9%96%80&qid=1573369893&sprefix=OS%E8%87%AA%E4%BD%9C%2Caps%2C279&sr=8-1)などでちょこちょこと書いたことがあるくらい...）、そのため解くのには結構時間がかかりました。
- おそらくアセンブリに全く触れたことがない人はスタックで管理するという概念がないので(5),(6)で詰む気がします。（なんなら(4)で詰むかもしれません）。
- (5), (6)については考え方は多分あっていると思うのですが、配布ファイルがないため検証ができないので間違ってる可能性がやや高いです。(特に(6)はあやしいかもしれません...)
- 教育的にはすごくいい問題だと思いました!