Posted at

東京大学大学院情報理工学系研究科 創造情報学専攻 2017年度 実技試験

東京大学大学院情報理工学系研究科 創造情報学専攻の2017年度 実技試験(プログラミング)の解答例(Python3)です。

https://www.i.u-tokyo.ac.jp/common/file/edu/course/ci/2016-8-program.pdf

※公開元ページはこちら

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


(1)

プログラムと実行結果は以下になります。

import sys 

import numpy as np
import re

digits = np.array([
[[1,1,1,1],[1,0,0,1],[1,0,0,1],[1,0,0,1],[1,1,1,1]],
[[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]],
[[1,1,1,1],[0,0,0,1],[1,1,1,1],[1,0,0,0],[1,1,1,1]],
[[1,1,1,1],[0,0,0,1],[1,1,1,1],[0,0,0,1],[1,1,1,1]],
[[1,0,0,1],[1,0,0,1],[1,1,1,1],[0,0,0,1],[0,0,0,1]],
[[1,1,1,1],[1,0,0,0],[1,1,1,1],[0,0,0,1],[1,1,1,1]],
[[1,0,0,0],[1,0,0,0],[1,1,1,1],[1,0,0,1],[1,1,1,1]],
[[1,1,1,1],[0,0,0,1],[0,0,0,1],[0,0,0,1],[0,0,0,1]],
[[1,1,1,1],[1,0,0,1],[1,1,1,1],[1,0,0,1],[1,1,1,1]],
[[1,1,1,1],[1,0,0,1],[1,1,1,1],[0,0,0,1],[0,0,0,1]]
])

def showDigits(n):
s = digits.shape
cn = s[2]
rn = s[1]
f = open('out1.txt','w')
for i in range(rn):
p = ""
for j in range(len(n)):
a = int(n[j:j+1])
d = digits[a]
for k in range(cn):
if d[i][k]==1:
if i%2==0:
p = p + '*'
else:
p = p + '|'
else:
p = p + ' '
if a==1:
break
if j+1 < len(n):
p = p + ' ' # spacex2
print(p)
f.write(p + "\n")

showDigits(sys.argv[1])

冒頭にあるdigitsという配列は、要素数が10個で0~9の表示を表します。

一つの要素は最大値に合わせて、5行4列の行列であり、"*"と"|"の二つがありますが、単に行数の順番で決まるので、両方とも1としてセットしています。

$ python 1.py 813

**** * ****
| | | |
**** * ****
| | | |
**** * ****
$ cat out1.txt
**** * ****
| | | |
**** * ****
| | | |
**** * ****
$ python 1.py 256
**** **** *
| | |
**** **** ****
| | | |
**** **** ****
$ cat out1.txt
**** **** *
| | |
**** **** ****
| | | |
**** **** ****


(2)

digitsの配列は同じなため、そちら除いたプログラムと実行結果が以下になります。

def showDigitsFromFile(fn):

f = open(fn,'r')
mat = []
for row in f:
arr = []
s = row
for i in range(len(s)):
c = s[i:i+1]
if c==" ":
arr.append(0)
elif c!="\n":
arr.append(1)
if len(mat)==0:
mat = [arr]
else:
mat = np.insert(mat,len(mat),[arr],axis=0)
mat = mat.T
s = mat.shape
cn = s[1]
rn = s[0]
print(mat)
o = ""
compared = []
i = 0
while(1):
if (i >= rn):
break
if len(compared)==0:
compared = mat[i:i+2,:]
if not np.any(compared):
compared = []
elif np.array_equal(digits[1].T[0:2],compared):
o = o + "1"
i = i + 1
compared = []
else:
compared = np.insert(compared,len(compared),mat[i:i+2,:],axis=0)
for d in range(len(digits)):
if np.array_equal(digits[d].T,compared):
o = o + str(d)
break
compared = []
i = i + 2
print(o)

showDigitsFromFile('out1.txt')

$ python 2.py

[[1 0 1 1 1]
[1 0 1 0 1]
[1 0 1 0 1]
[1 1 1 0 1]
[0 0 0 0 0]
[0 0 0 0 0]
[1 1 1 0 1]
[1 0 1 0 1]
[1 0 1 0 1]
[1 0 1 1 1]
[0 0 0 0 0]
[0 0 0 0 0]
[1 1 1 1 1]
[0 0 1 0 1]
[0 0 1 0 1]
[0 0 1 1 1]]
256


(3)

(1)について、描画位置を指定する問題になります。

プログラムと実行結果は以下になります。

def showDigits():

n = num
f = open('out3.txt','w')

i = 0
for i in range(int(mh)+5):
p = ""
k = 0
for j in range(len(n)):
a = int(n[j:j+1])
arg = args[j]
d = digits[a]
if (i>=int(arg["h"])):
bk = k
ii = i - int(arg["h"])
while(1):
try:
if d[ii][k-bk]==1:
if ii%2==0:
p = p + '*'
else:
p = p + '|'
else:
p = p + ' '
except IndexError:
p = p + ' '
k = k + 1
if a==1:
break
if k-bk>3:
break
else:
if a==1:
p = p + " "
else:
p = p + " "
if j+1 < len(n):
for l in range(int(arg["s"])):
p = p + " "
k = k + int(arg["s"])
print(p)
f.write(p + "\n")

try:
if sys.argv[1]:
a = sys.argv[1]
except IndexError:
a = list(map(str,input()))
a = ','.join(a)

args = {}
a = a.split(',')
num = a[0]
c = 0
mh = 0
print(a)

cn = 0
for i in range(len(num)):
if (num[i]=="1"):
cn = cn + 1
else:
cn = cn + 4
while(1):
d = {'h':a[c+1]}
if (int(a[c+1])>int(mh)):
mh = a[c+1]
if c+2 < len(num)*2:
d["s"] = a[c+2]
cn = cn + int(a[c+2])
args[c/2] = d
else:
args[c/2] = d
break
c = c + 2

showDigits()

$ python 3.py 813,0,4,1,3,2

['813', '0', '4', '1', '3', '2']
****
| | *
**** | ****
| | * |
**** | ****
* |
****
$ cat out3.txt
****
| | *
**** | ****
| | * |
**** | ****
* |
****


(4)

(3)の逆パターンになります。

def showDigitsFromFile(fn):

f = open(fn,'r')
mat = []
for row in f:
arr = []
s = row
for i in range(len(s)):
c = s[i:i+1]
if c==" ":
arr.append(0)
elif c!="\n":
arr.append(1)
if len(mat)==0:
mat = [arr]
else:
mat = np.insert(mat,len(mat),[arr],axis=0)
mat = mat.T
s = mat.shape
cn = s[1]
rn = s[0]
o = ""
compared = []
i = 0
while(1):
if (i >= rn):
break
if len(compared)==0:
if not np.any(mat[i:i+1,:]):
i = i + 1
continue
compared = mat[i:i+2,:]
ret = compared[:, ~np.all(np.equal(compared,0), axis=0)]
if not np.any(compared):
compared = []
elif np.array_equal(digits[1].T[0:2],ret):
o = o + "1"
i = i + 1
compared = []
else:
compared = np.insert(compared,len(compared),mat[i:i+2,:],axis=0)
ret = compared[:, ~np.all(np.equal(compared,0), axis=0)]
for d in range(len(digits)):
if np.array_equal(digits[d].T,ret):
o = o + str(d)
break
compared = []
i = i + 2
print(o)

showDigitsFromFile('out3.txt')

$ python 4.py 

813


(5)

少し崩したout5.txtを読み込んで認識する問題になります。

仮にout5.txtを以下としたい場合のプログラムと実行結果を下記に示します。


  • out5.txt

****            ****

| | * * |
**** | | *
| | * **** |
**** | | | *
* ****


  • プログラム、実行結果

def showDigitsFromFile(fn):

f = open(fn,'r')
mat = []
mcn = 0
lines = f.readlines()
for row in lines:
if (len(row)>mcn):
mcn = len(row)
for row in lines:
arr = []
s = row
if (len(s)<mcn):
for i in range(mcn-len(s)):
s = s + " "
for i in range(len(s)):
c = s[i:i+1]
if c==" ":
arr.append(0)
elif c!="\n":
arr.append(1)
if len(mat)==0:
mat = [arr]
else:
mat = np.insert(mat,len(mat),[arr],axis=0)
mat = mat.T
s = mat.shape
rn = s[0]
o = ""
compared = []
i = 0
while(1):
if (i >= rn):
break
if len(compared)==0:
if not np.any(mat[i:i+1,:]):
i = i + 1
continue
compared = mat[i:i+1,:]
ret = compared[:, ~np.all(np.equal(compared,0), axis=0)]
if not np.any(compared):
compared = []
else:
compared = np.insert(compared,len(compared),mat[i:i+1,:],axis=0)
ret = compared[:, ~np.all(np.equal(compared,0), axis=0)]
if len(compared)<4: # 2 or 3
lr = ret[-1]
if np.all(np.equal(lr,0),axis=0):
o = o + "1"
compared = []
else:
min = -1
od = ""
for d in range(len(digits)):
if (d==1):
continue
diff = 0
ds = digits[d].T.shape
for r in range(ds[0]):
for c in range(ds[1]):
if (digits[d].T[r][c]!=ret[r][c]):
diff = diff + 1
if (min==-1 or diff<min):
min = diff
od = d
o = o + str(od)
compared = []
i = i + 1
print(o)

showDigitsFromFile('out5.txt')

$ python 5.py

8167

他にも解き方があるかもしれないのですが、ポイントとしては転置行列を使って計算をする点となっています。