Pythonで競プロみたいなことしたい！
ということで一部界隈では有名な世界で闘うプログラミング力を鍛える本をPythonで解いてみました。
問題の解説とか詳しく知りたい方はぜひ本書を買ってみてください（ステマじゃないよ）
ちなみに今回の解き方はテストを実装しているので、無駄に長くなっています。なので前半だけ見れば十分です。
##ではやっていこー1章！
ある文字列が重複のないものかどうか調べよ
1-1.py
import unittest
# ある文字列をSとする
# 言語は日本語、文字コードはUnicode (日本語3byte)を想定
# 解法1: O(N^2)
def unique(S):
if len(S) > 2**24:
return False
for index in range(len(S)):
if S[index] in S[index + 1:]:
return False
break
elif index == len(S) - 1:
return True
# 解法2: 時間はO(N)だが、2^24の長さのリストをつくるのでメモリを喰うゾイ
def unique2(S):
if len(S) > 2**24:
return False
char_set=[False for _ in range(2**24)]
for char in S:
uni_num=ord(char)
if char_set[uni_num]:
return False
char_set[uni_num] = True
return True
class Test(unittest.TestCase):
dataT = [("こんにちは"), ("わたしは"), ("ぺっぱーです")]
dataF = [("ようよう"), ("おれさまのなまえは"), ("じゃいあんだぜい")]
def test_unique(self):
for test_string in self.dataT:
torf = unique(test_string)
self.assertTrue(torf)
for test_string in self.dataF:
torf = unique(test_string)
self.assertFalse(torf)
if __name__ == "__main__":
unittest.main()
２つの文字列があるとき、片方の文字の並び替えでもう片方の文字列は作れるか調べよ！
(未完です。)
1-2.py
# ２つの文字列をS1, S2とする。
# ソートして比較
# 解法1: 文字列をリストにしてソート。比較。
def p_string1(S1, S2):
S1_l = list(S1)
S2_l = list(S2)
if len(S1) != len(S2):
return False
elif S1_l.sort() == S2_l.sort(): # TODO: はいここが駄目。アルファベットと数字が混ざるとソートできないからエラーになる。
return True
# p_string("dog ", "g od") > OK!
# 解法2: 出現回数をカウント
# ここではcounterモジュールを使わずに辞書を用いて実装する
def p_string2(S1, S2):
if len(S1) != len(S2):
return False
counter = {} # 辞書をつくる
for string in S1:
if string in counter: # 辞書は持っていないキーを指定して演算するとエラーを起こすので、キーを持っているか確認が必要
counter[string] += 1
else:
counter[string] = 1
for string in S2:
if string not in counter: # 辞書は持っていないキーを指定して演算するとエラーを起こすので、キーを持っているか確認が必要
return False
if counter[string] == 0:
return False
counter[string] -= 1
return True
# TODO: Test書きたい。
# text1="dogrun"
# text2="godnur"
# print(p_string1(text1,text2))
# print(p_string2(text1,text2))
# 2018/3/16追記
# 上の書き方はいけてない。
import unittest
class test(unittest.TestCase):
dataT = (
('abcd', 'bacd'),
('3563476', '7334566'),
('wef34f', 'wffe34'),
)
dataF = (
('abcd', 'd2cba'),
('2354', '1234'),
('dcw4f', 'dcw5f'),
)
def test_cp(self):
# true check
for test_strings in self.dataT:
result = p_string2(*test_strings)
self.assertTrue(result)
#false check
for test_strings in self.dataF:
result = p_string2(*test_strings)
self.assertFalse(result)
if __name__ == "__main__":
unittest.main()
空白スペースを"%20"で置換せよ
1-3.py
import unittest
def URLify(S , length):
return S.replace(" ", "%20")
# TODO:Test書かなあかん
# text = "google ha sugoi kamo"
# L = len(text)
# print(URLify(text,L))
# 3/21 テスト書いた
class Test(unittest.TestCase):
data = [
('overwatch love is strong', 25,
'overwatch%20love%20%20is%20strong'),
('kakuno mendo', 12,
'kakuno%20mendo')
]
def test_URLify(self):
for [test_string, length, answer] in self.data:
actual = URLify(test_string, length)
self.assertEqual(actual, answer)
if __name__ == "__main__":
unittest.main()
一つの文字列が与えられたとき、文字を並び替えて回文が作れるか調べよ！
1-4.py
# 回文にできるかは文字数が偶数のときそれぞれの文字出現回数cが2|c(偶数回)であることが必要十分
# 文字数が奇数のときはc = oddとなるようなcが一つ。その他は2|cであることが必要十分。
# たぶん回答はASCII想定なので、ここでは言語は英語、コードはASCIIとする。アルファベットずるすぎンゴ
import unittest
def palindrome(string):
string = string.lower()
counter = [0 for _ in range(128)]
if len(string) % 2 == 0:
for char in string:
pos = ord(char)
counter[pos] += 1
for count in counter:
if count % 2 == 1:
return False
return True
else:
for char in string:
pos = ord(char)
counter[pos] += 1
odd_counter = 0
for char in counter:
if char == 1:
odd_counter += 1
return(odd_counter == 1)
text = "wasi hah siwa"
print(palindrome(text))
class Test(unittest.TestCase):
data = [
("I love evole ei ", True),
("Tomato", False),
("Tomamto", True),]
("wasi hah siwa", True)]
# data = [
# ('Tact Coa', True),
# ('jhsabckuj ahjsbckj', True),
# ('Able was I ere I saw Elba', True),
# ('So patient a nurse to nurse a patient so', False),
# ('Random Words', False),
# ('Not a Palindrome', False),
# ('no x in nixon', True),
# ('azAZ', True)]
def test_palindrome(self):
for [test_string, torf] in self.data:
result = palindrome(test_string)
self.assertEqual(result, torf)
if __name__ == "__main__":
unittest.main()
２つの文字列が与えられたとき、文字の挿入、削除、置き換えのどれか1回の操作でもう片方の文字列はつくれるか調べよ！
1-5.py
# 文字数変動が2以上だったらFlase
# 文字数変動が1のとき、文字種変動はS1(文字数おおいほう).pop(i for i in S1)==S2となる。
# 文字数変動がないとき、stringをリストとしみなすとS1,S2では一つの要素以外同じ。
import unittest
def arr_char(S1, S2):
if len(S1) == len(S2):
diff_count = 0
for i in range(len(S1)):
if S1[i] not in S2[i]:
diff_count += 1
if diff_count == 1:
return True
return False
if abs(len(S1) - len(S2)) == 1:
if len(S2) > len(S1):
tmp = S2
S2 = S1
S1 = tmp
S1_l = list(S1)
for i in range(len(S1)):
S1_l.pop(i)
re_S1 = "".join(S1_l)
if re_S1 == S2:
return True
S1_l = list(S1)
return False
return False
class Test(unittest.TestCase):
dataT = [
("pale", "ple", True),
("tre", "true", True),
("truu", "true", True), # u2,e0→u1,e1
("truu", "twue", False) # u2, r1, w0, e0, u1, r0, w1, e1 文字の出現回数でカウントは意味ないか
]
def test_arr_char(self):
for [S1, S2, torf] in self.dataT:
actual = arr_char(S1, S2)
self.assertEqual(actual, torf)
if __name__ == "__main__":
unittest.main()
ある文字列の重複を数字にしろ！
1-6.py
# ポインタつくって動かしていけばええんちゃうか？
# 英語だったらASCII想定で、リストのインデックスと対応させる。日本語だったらUTF8想定で辞書つくったほうがいい。
# 3/24追記。それだめや。aabbaaだとa2b2a2がa4b2となってまう。
import unittest
#
# def zip_string(string):
# sl = list(string)
# count_list=[0 for _ in range(128)]
# counter = 1
# for i in range(len(string)):
# a = sl.pop(i)
# count_list[ord(a)] +=1
# if a == sl[i]:
# count_list[ord(a)] += 1
# sl=list(string)
def zip_string(string):
result = ""
str_result = ""
count = 1
for i in range(0, len(string) - 1):
char = string[i]
if string[i] == string[i + 1]:
count += 1
if i == len(string) - 2:
result += char + str(count)
else:
result += char + str(count)
count = 1
if i == len(string) - 2:
result += string[-1] + str(1)
str_result = result[0::2]
if str_result == string:
return string
else:
return result
class Test(unittest.TestCase):
data = [
("aaaabbcccd", "a4b2c3d1"),
("abcd", "abcd"),
("aaabbbFFFkkk", "a3b3F3k3")
]
def test_zip_string(self):
for [string, answer] in self.data:
self.assertEqual(zip_string(string), answer)
if __name__ == "__main__":
unittest.main()
行列を90度回転させろ！
1-7.py
import unittest
# 問題の意味がわからないが、とりあえず行列を90度回転させるメソッドを書く。
# テストから書き始めるの結構大事かも。
# numpyでやれよって思ったけど、numpyのメソッドなくてビビった。ほえほえ.
# 一回連結させて区切る？
def rotataion(matrix):
rows = len(matrix)
columns = len(matrix[0])
result = []
for i in range(columns):
result.append([])
for n in range(rows):
for m in range(columns):
result[columns - m - 1].append(matrix[n][m])
return result
class Test(unittest.TestCase):
data = [
([
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
], [
[4, 8, 12],
[3, 7, 11],
[2, 6, 10],
[1, 5, 9]
])
]
def test_rotation(self):
for matrix, answer in self.data:
actual = rotataion(matrix)
self.assertEqual(actual, answer)
if __name__ == "__main__":
unittest.main()
行列のある要素が0だったら、その行と列を全部0にしろ！連帯責任だ！
1-8.py
import unittest
# def zero_mat(matrix):
# for n in matrix:
# for m in len(matrix[0]):
# if 0 in n:
# n =[0 for i in n]
# if
#列を扱えないのは辛い。やりなおし。
# 答え引用しました。や、やり方はわかってたんだからね・・・！？
def zero_matrix(matrix):
m = len(matrix)
n = len(matrix[0])
rows = []
cols = []
for x in range(m):
for y in range(n):
if matrix[x][y] == 0:
rows.append(x)
cols.append(y)
for row in rows:
nullify_row(matrix, row)
for col in cols:
nullify_col(matrix, col)
return matrix
def nullify_row(matrix, row):
for i in range(len(matrix[0])):
matrix[row][i] = 0
def nullify_col(matrix, col):
for i in range(len(matrix)):
matrix[i][col] = 0
class Test(unittest.TestCase):
'''Test Cases'''
data = [
([
[1, 2, 3, 4, 0],
[6, 0, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 0, 18, 19, 20],
[21, 22, 23, 24, 25]
], [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[11, 0, 13, 14, 0],
[0, 0, 0, 0, 0],
[21, 0, 23, 24, 0]
])
]
def test_zero_matrix(self):
for [test_matrix, expected] in self.data:
actual = zero_matrix(test_matrix)
self.assertEqual(actual, expected)
if __name__ == "__main__":
unittest.main()
２つの文字列があるとき、片方を切ってつなげたらもう片方の文字列になるか！？
1-9.py
# これは日本語では問題が意味不。
import unittest
def isSubstring(S1,S2):
if S1 in S2:
return True
return False
def once_isSubstring(S1,S2):
return isSubstring(S2, S1+S1)
class Test(unittest.TestCase):
data=[
("abcdefg", "defgabc",True),
("coffeebottle", "bottledcoffe", False)
]
def test_once_isSubstring(self):
for [s1,s2,torf] in self.data:
actual=once_isSubstring(s1,s2)
self.assertEqual(actual,torf)
if __name__=="__main__":
unittest.main()
##Done!
肝は実行時間がどうとかいうことだけど、Pythonでも書けるんだぞってことを示したかった。
ただ2章以降の連結リストとかは食指が進まないので、誰か解いてくださいお願いします。