東京大学大学院情報理工学系研究科 創造情報学専攻 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

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