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

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

出題テーマ

• 真理値表
• マクロ

問題文

※ 東京大学側から指摘があった場合は問題文を削除いたします。

(1)

def solve1(file_path):
    with open(file_path, 'r') as f:
        text = f.read()
        if text[-1] == '\n':
            text = text[:-1]
        ret = text.split('+')
        return ret    
def print1(ret):
    for txt in ret:
        print(txt)

(2)

def solve1(file_path):
    with open(file_path, 'r') as f:
        text = f.read()
        if text[-1] == '\n':
            text = text[:-1]
        ret = text.split('+')
        return ret 

def solve2(file_path):
    txts = solve1(file_path)
    al_set = set()
    groups = []
    for index, txt in enumerate(txts):
        als = txt.split('&')
        group = []
        for al in als:
            group.append(al)
            al_set.add(al)
        group.sort()
        groups.append(group) 

    al_set2 = []   
    for al in al_set:
        al_set2.append(al)
    al_set2.sort()    

    answers = set()
    for group in groups:
        ans = ['']
        for al in al_set2:
            if al in group:
                for i in range(len(ans)):
                    ans[i] += '{0}=true '.format(al)
#                     print(ans)
            else:
                tmp = len(ans)
                ans = ans * 2
                for i in range(tmp):
                    ans[i] += '{0}=true '.format(al)
                    ans[i+tmp] += '{0}=false '.format(al)
        for txt in ans:
            answers.add(txt)
    if len(answers) > 0:
        for a in answers:
            print(a)
    else:
        print('none')

(3)

def solve1(file_path):
    with open(file_path, 'r') as f:
        text = f.read()
        if text[-1] == '\n':
            text = text[:-1]
        ret = text.split('+')
        return ret

# a&!aが存在するかどうか  
# groupでは!aをa!の形で持っている
def isNone(group):
    for al in group:
        if (al+'!') in group:
            return True
    return False    

def solve3(file_path):
    txts = solve1(file_path)
    al_set = set()
    groups = []
    for index, txt in enumerate(txts):
        als = txt.split('&')
        group = []
        for al in als:
            last = al[-1]
            if (len(al) % 2) == 0:
                group.append(last+'!')
            else:
                group.append(last)
            al_set.add(last)
        group.sort()
        groups.append(group)    

    al_set2 = []   
    for al in al_set:
        al_set2.append(al)
    al_set2.sort()    

#     print(al_set2)
#     print(groups)
#     return

    answers = set()
    for group in groups:
        if not isNone(group):
            ans = ['']
            for al in al_set2:
                if al in group:
                    for i in range(len(ans)):
                        ans[i] += '{0}=true '.format(al)
                elif (al+'!') in group:
                    for i in range(len(ans)):
                        ans[i] += '{0}=false '.format(al)
                else:
                    tmp = len(ans)
                    ans = ans * 2
                    for i in range(tmp):
                        ans[i] += '{0}=true '.format(al)
                        ans[i+tmp] += '{0}=false '.format(al)
            for txt in ans:
                answers.add(txt)
    if len(answers) > 0:
        for a in answers:
            print(a)
    else:
        print('none')

(4)

from N_DIGIT import baseNumbers

alpha = ['a', 'b', 'c', 'd', 'e', 
         'f', 'g', 'h', 'i', 'j', 
         'k', 'l', 'm', 'n', 'o',
         'p', 'q', 'r', 's', 't',
         'u', 'v', 'w', 'x', 'y', 'x',
        ]

def get_alpha_set(text):
    ret = []
    for al in alpha:
        if al in text:
            ret.append(al)
    ret.sort()    
    return ret

def macro(text):
        text = text.replace('!', ' not ')
        text = text.replace('&', ' and ')
        text = text.replace('+', ' or ')
        return text       

def solve4(file_path):
    with open(file_path, 'r') as f:
        text = f.read()
        if text[-1] == '\n':
            text = text[:-1]
    al_set = get_alpha_set(text)
    al_dic = {}
    for index, al in enumerate(al_set):
        al_dic[al] = index
    bs = baseNumbers(1 << len(al_set), 2, len(al_set))
    ans = []
    for b in bs:
        tmp = text
        for al in al_set:
            tmp = tmp.replace(al, str(b[al_dic[al]]))
        formatted_tmp = macro(tmp)
        if eval(formatted_tmp):
            ans.append(b)
    for a in ans:
        txt = ''
        for index, boolean in enumerate(a):
            if boolean:
                al = al_set[index]
                txt += '{0}=true '.format(al)
            else:
                al = al_set[index]
                txt += '{0}=false '.format(al)
        print(txt)    

(5)

from N_DIGIT import baseNumbers

alpha = ['a', 'b', 'c', 'd', 'e', 
         'f', 'g', 'h', 'i', 'j', 
         'k', 'l', 'm', 'n', 'o',
         'p', 'q', 'r', 's', 't',
         'u', 'v', 'w', 'x', 'y', 'x',
        ]

def get_alpha_set(text):
    ret = []
    for al in alpha:
        if al in text:
            ret.append(al)
    ret.sort()    
    return ret

def macro(text):
        text = text.replace('!', ' not ')
        text = text.replace('&', ' and ')
        text = text.replace('+', ' or ')
        return text       

def solve5(file_path):
    with open(file_path, 'r') as f:
        text = f.read()
        if text[-1] == '\n':
            text = text[:-1]
    al_set = get_alpha_set(text)
    al_dic = {}
    for index, al in enumerate(al_set):
        al_dic[al] = index
    bs = baseNumbers(1 << len(al_set), 2, len(al_set))
    ans = []
    for b in bs:
        tmp = text
        for al in al_set:
            tmp = tmp.replace(al, str(b[al_dic[al]]))
        formatted_tmp = macro(tmp)
        if eval(formatted_tmp):
            ans.append(b)

    txt = ''
    for a in ans:
        tmp = ''
        for index, boolean in enumerate(a):
            if boolean:
                al = al_set[index]
                tmp += (al+'&')
            else:
                al = al_set[index]
                tmp += ('!'+al+'&')
        txt += (tmp[:-1]+'+')
    print(txt[:-1])

(6)

from N_DIGIT import baseNumbers

alpha = ['a', 'b', 'c', 'd', 'e', 
         'f', 'g', 'h', 'i', 'j', 
         'k', 'l', 'm', 'n', 'o',
         'p', 'q', 'r', 's', 't',
         'u', 'v', 'w', 'x', 'y', 'x',
        ]

def get_alpha_set(text):
    ret = []
    for al in alpha:
        if al in text:
            ret.append(al)
    ret.sort()    
    return ret

def macro(text):
        text = text.replace('!', ' not ')
        text = text.replace('&', ' and ')
        text = text.replace('+', ' or ')
        return text       

def solve6(file_path):
    with open(file_path, 'r') as f:
        text = f.read()
        if text[-1] == '\n':
            text = text[:-1]
    al_set = get_alpha_set(text)
    al_dic = {}
    for index, al in enumerate(al_set):
        al_dic[al] = index
    bs = baseNumbers(1 << len(al_set), 2, len(al_set))
    ans = []
    for b in bs:
        tmp = text
        for al in al_set:
            tmp = tmp.replace(al, str(b[al_dic[al]]))
        formatted_tmp = macro(tmp)
        if not eval(formatted_tmp):
            ans.append(b)

    txt = ''
    for a in ans:
        tmp = '('
        for index, boolean in enumerate(a):
            if boolean:
                al = al_set[index]
                tmp += ('!'+al+'+')
            else:
                al = al_set[index]
                tmp += (al+'+')
        txt += (tmp[:-1]+')&')
    print(txt[:-1])

感想

• コンパイラと見せかけた真理値表の問題
• (3)までは解析を実装して、そこから解を求めていく形にしたが(4)から（）が登場し、これの何がまずいかというと（）内（）がこの場合ありえてしまうのでsplitなどによって単純に分割できなくなった。実際に（）つきの解析プログラムを実装することは可能（当たり前）だがそれは言語処理論の分野であり、導出木の作成が必要で非常に厄介と感じたため、全探索とマクロを使う形にした（最初からこのやり方の方が実は楽）。
• ただ全探索とマクロを組み合わせたやり方だと最後までこのやり方でできてしまうので、出題者の意図に反しているのではないかと迷ったので筆者は(3)まではきちんと解析を実装した形にした。
• 全探索の場合は最大で2^26(アルファベット分)の約10^7~10^8の計算量が必要であるがこれはまぁ現実的な範囲では一応ある。
• 大抵のプログラミング言語はnot > and > orの優先順位であるのでマクロの利用を想定しているとも取れる。
• 加法の方はまぁ(4)そのままでいいだろう、乗法の方はこれも論理回路の教科書などには必ず載っている内容であるので知っていると加法同様に(4)を利用してすぐに実装ができる。知らないとド・モルガンの法則から自力で気付くのは結構きついと思う。