[PYTHON] Graduate School of Information Science and Technology, The University of Tokyo, Department of Creative Informatics, Summer 2007 Programming Exam
This is an example of the answer to the 2007 summer 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
- Coding
Problem statement
- If the University of Tokyo points out, the problem statement will be deleted. 
Distribution file
q1.txt (actual distribution file)
Sxx, jzf dppx ez slgp qzfyo esp qzwwzhtyr dpypepynpd.
Zyp zq esp dtxawpde pilxawpd zq l dfmdetefetzy ntaspc td esp Nlpdlc
ntaspc, hstns td dlto ez slgp mppy fdpo mj Ufwtfd Nlpdlc ez
nzxxfytnlep htes std lcxj. Nlpdlc td nzydtopcpo ez mp zyp zq esp qtcde
apcdzyd ez slgp pgpc pxawzjpo pyncjaetzy qzc esp dlvp zq dpnfctyr
xpddlrpd. Nlpdlc opntopo esle dstqetyr plns wpeepc ty esp xpddlrp
hzfwo mp std delyolco lwrzctesx, lyo dz sp tyqzcxpo lww zq std
rpypclwd zq std opntdtzy, lyo hld es
(1) As you can see by executing the following with q1.txt, when key = 11, it will be an English sentence
from CharacterCode import *
def isSmall(num):
return num >= 97 and num <= 122
def isBig(num):
return num >= 65 and num <= 90
def decodeChar1(ch, key):
if ch.isalpha():
int_num = AsciiStr2Int(ch)
if isSmall(int_num):
order = int_num - 97
return Hexbytes2Str(Int2hexbytes((order - key) % 26 + 97))
if isBig(int_num):
order = int_num - 65
return Hexbytes2Str(Int2hexbytes((order - key) % 26 + 65))
return ch
def decodeText1(text, key):
ret = ''
for ch in text:
ret += decodeChar1(ch, key)
return ret
def solve1(file_path):
with open(file_path, 'r', encoding='ascii') as f:
tmp = f.readlines()
txt_array = []
for txt in tmp:
if txt[-1] == '\n':
txt_array.append(txt[:-1])
else:
txt_array.append(txt)
for key in range(1, 26):
print('key: ' + str(key))
for txt in txt_array:
print(decodeText1(txt, key))
print('---end---\n')
(2) 2-1
from CharacterCode import *
def isSmall(num):
return num >= 97 and num <= 122
def isBig(num):
return num >= 65 and num <= 90
def decodeChar1(ch, key):
if ch.isalpha():
int_num = AsciiStr2Int(ch)
if isSmall(int_num):
order = int_num - 97
return Hexbytes2Str(Int2hexbytes((order - key) % 26 + 97))
if isBig(int_num):
order = int_num - 65
return Hexbytes2Str(Int2hexbytes((order - key) % 26 + 65))
return ch
def decodeText1(text, key):
ret = ''
for ch in text:
ret += decodeChar1(ch, key)
return ret
class Tmp(object):
def __init__(self, al, cnt):
self.al = al
self.cnt = cnt
def __repr__(self):
return '{0}: {1}'.format(self.al, self.cnt)
def __lt__(self, tmp):
return self.cnt < tmp.cnt
def solve2_1(file_path):
with open(file_path, 'r', encoding='ascii') as f:
text = f.read().lower()
freq = []
for i in range(26):
order = i + 97
al = Hexbytes2Str(Int2hexbytes(order))
cnt = 0
tmp = Tmp(al, cnt)
freq.append(tmp)
for ch in text:
if ch.isalpha():
idx = AsciiStr2Int(ch) - 97
freq[idx].cnt += 1
freq.sort()
freq = freq[::-1]
for tmp in freq:
print(tmp)
2-2 As expected, I could not solve it because there is no q22.txt, but as a method, you can see by looking at the frequency of each alphabet in q1.txt, but the frequency of vowels is high, so try various things using replace etc. You should be able to see it when you see it.
(3) 3-1
from CharacterCode import *
from PriorityQueue import PriorityQueue
def isSmall(num):
return num >= 97 and num <= 122
def isBig(num):
return num >= 65 and num <= 90
freq = []
class Node(object):
#For characters node_id is ascii code
def __init__(self, al, cnt, node_id):
self.al = al
self.cnt = cnt
self.node_id = node_id
# parent, left,right node_id
self.p = None
self.r = None
self.l = None
def __repr__(self):
return '{0}: {1}, ID: {2}\n'.format(self.al, self.cnt, self.node_id) + \
'Parent node: {0}\n'.format(self.p) + \
'Left node: {0},Right node: {1}'.format(self.l, self.r)
def __lt__(self, node):
if self.cnt == node.cnt:
return self.node_id < node.node_id
else:
return self.cnt < node.cnt
def encode3(ch):
ret = ''
global freq
node = freq[AsciiStr2Int(ch)]
while True:
if node.p == None:
break
p = freq[node.p]
if p.l == node.node_id:
ret += '0'
elif p.r == node.node_id:
ret += '1'
node = p
return ret[::-1]
def solve3_1(file_path):
with open(file_path, 'r', encoding='ascii') as f:
text = f.read().lower()
global freq
freq = [None for _ in range(127)]
for i in range(127):
if i == 10:
node = Node('LF', 0, i)
freq[i] = node
elif i == 13:
node = Node('CR', 0, i)
freq[i] = node
elif i == 32:
node = Node('SP', 0, i)
elif i >= 33 and i <= 126:
al = Hexbytes2Str(Int2hexbytes(i))
cnt = 0
node = Node(al, cnt, i)
freq[i] = node
for ch in text:
if ch.isalpha():
idx = AsciiStr2Int(ch)
freq[idx].cnt += 1
pq = PriorityQueue([])
for node in freq:
if node != None:
pq.push(node)
while len(pq) > 1:
new_node_id = len(freq)
r_node = pq.pop()
l_node = pq.pop()
new_node = Node('{0},{1}'.format(r_node.al, l_node.al), r_node.cnt + l_node.cnt, new_node_id)
r_node.p = new_node_id
l_node.p = new_node_id
new_node.r = r_node.node_id
new_node.l = l_node.node_id
freq.append(new_node)
pq.push(new_node)
for i in range(127):
node = freq[i]
if node != None:
code = None
if node.al == 'LF':
code = encode3('\n')
elif node.al == 'CR':
code = encode3('\r')
elif node.al == 'SP':
code = encode3(' ')
else:
code = encode3(node.al)
print('{0}: {1}'.format(node.al, code))
3-2
from CharacterCode import *
from PriorityQueue import PriorityQueue
def isSmall(num):
return num >= 97 and num <= 122
def isBig(num):
return num >= 65 and num <= 90
freq = []
class Node(object):
#For characters node_id is ascii code
def __init__(self, al, cnt, node_id):
self.al = al
self.cnt = cnt
self.node_id = node_id
# parent, left,right node_id
self.p = None
self.r = None
self.l = None
def __repr__(self):
return '{0}: {1}, ID: {2}\n'.format(self.al, self.cnt, self.node_id) + \
'Parent node: {0}\n'.format(self.p) + \
'Left node: {0},Right node: {1}'.format(self.l, self.r)
def __lt__(self, node):
if self.cnt == node.cnt:
return self.node_id < node.node_id
else:
return self.cnt < node.cnt
def encode3(ch):
ret = ''
global freq
node = freq[AsciiStr2Int(ch)]
while True:
if node.p == None:
break
p = freq[node.p]
if p.l == node.node_id:
ret += '0'
elif p.r == node.node_id:
ret += '1'
node = p
return ret[::-1]
def solve3_2(file_path):
with open(file_path, 'r', encoding='ascii') as f:
text = f.read().lower()
global freq
freq = [None for _ in range(127)]
for i in range(127):
if i == 10:
node = Node('LF', 0, i)
freq[i] = node
elif i == 13:
node = Node('CR', 0, i)
freq[i] = node
elif i == 32:
node = Node('SP', 0, i)
elif i >= 33 and i <= 126:
al = Hexbytes2Str(Int2hexbytes(i))
cnt = 0
node = Node(al, cnt, i)
freq[i] = node
for ch in text:
if ch.isalpha():
idx = AsciiStr2Int(ch)
freq[idx].cnt += 1
pq = PriorityQueue([])
for node in freq:
if node != None:
pq.push(node)
while len(pq) > 1:
new_node_id = len(freq)
r_node = pq.pop()
l_node = pq.pop()
new_node = Node('{0},{1}'.format(r_node.al, l_node.al), r_node.cnt + l_node.cnt, new_node_id)
r_node.p = new_node_id
l_node.p = new_node_id
new_node.r = r_node.node_id
new_node.l = l_node.node_id
freq.append(new_node)
pq.push(new_node)
dic = {}
for i in range(127):
node = freq[i]
if node != None:
code = None
if node.al == 'LF':
code = encode3('\n')
elif node.al == 'CR':
code = encode3('\r')
elif node.al == 'SP':
code = encode3(' ')
else:
code = encode3(node.al)
dic[node.al] = len(code)
total = 0
mom = 0
for i in range(127):
node = freq[i]
if node != None:
cnt = node.cnt
size = dic[node.al]
total += (cnt * size)
mom += cnt
print('{0:.2f}'.format(total / mom))
Impressions
――It was a problem for me personally, the type of person I like. --C and c ++ can be added and subtracted directly with char type, but python cannot do that, so I created my own module (Character Code) in advance, so I am solving it using that. (Maybe you should look it up with binascii) ――3-1 is a mountain, but if you use c, c ++ when making a tree, you can use a pointer and apply it a little easier, but when doing this time with python, I made an array and made it so that it points to its index. ――As an aside, I think that the character encoding will probably not exceed the range of ascii because we will do the same English test for international students. (The point is that it does not handle Japanese characters such as utf-8 encoding.)
Recommended Posts