[PYTHON] Graduate School of Information Science and Technology, The University of Tokyo, Department of Creative Informatics, Winter 2013 Programming Exam
This is an example of the answer to the 2013 winter hospital exam.
- The content of the description is personally solved by the author and does not guarantee the correct answer, and is not related to the University of Tokyo or the organization involved in providing the content of this examination.
Question theme
--Truth table
- macro
Problem statement
- If the University of Tokyo points out, the problem statement will be deleted.
(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&!Whether a exists
#In group!a to a!Have in the form of
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])
Impressions
--Problems with truth tables disguised as compilers -Up to (3), the analysis was implemented and the solution was found from there, but () appeared from (4), and what is wrong with this is that () in () is possible in this case. Because it ends up, it can no longer be simply split by split etc. It is possible to actually implement an analysis program with () (naturally), but it is a field of language processing theory, and I felt that it was very troublesome to create a derived tree, so I decided to use full search and macros () This method is actually easier from the beginning). ――However, if you use a method that combines full search and macros, you can do it this way until the end, so I was wondering if it was against the intention of the questioner, so I implemented the analysis properly up to (3). I made it. --In the case of full search, a maximum of 2 ^ 26 (alphabet), about 10 ^ 7 ~ 10 ^ 8, is required, but this is tentatively within a realistic range. --Since most programming languages have a priority of not> and> or, it can be said that macros are supposed to be used. ――For additive, you can leave it as it is (4). For multiplication, this is also always included in logic circuit textbooks, so if you know it, use (4) as well as addition. It can be implemented immediately. If you don't know it, it's quite hard to notice from De Morgan's laws on your own.
Recommended Posts