Google code jam Africa 2010 qualification round A. store creditに挑戦する.
この問題を入力と出力で定義すると,
である.
入力と,それに対する正しい出力の例は以下の通りである.
この問題定義だけだと,一般に正しい出力はないかもしれない,あるいは正しい出力が複数になるかもしれないと心配になる. しかし,正しい出力がちょうど1つになるような入力しか用意しないと注意書きがある. 親切である.
今度は,Google code jamで提供されている形式のデータファイル(テキストファイル)を読み込んで,指定された形式のデータファイル(テキストファイル)を書き出す関数を作る.
ボトムアップ形式で関数を作る.
まず入力CとPが与えられたら,正しい出力を返す関数を定義する.
以下の関数answerはその一例である.
def answer(C, P):
'''store creditを本質的に解く関数.
'''
for i in range(len(P) - 1): # i = 0, 1, ..., I - 2のそれぞれのP[i]に関して,
for j in range(i + 1, len(P)): # j = i + 1, i + 2, ..., I - 1のそれぞれのP[j]に注目して
if P[i] + P[j] == C: # 足してちょうどCならば,
return i + 1, j + 1 # その添字を出力する.Pythonのリストの添字は0始まり,Google code jamで指定された形式は1始まりなので,1つずらして出力する.
上記の例で,合っているか試してみる.
C1 = 100
P1 = [5, 75, 25]
answer(C1, P1)
(2, 3)
C2 = 200
P2 = [150, 24, 79, 50, 88, 345, 3]
answer(C2, P2)
(1, 4)
C3 = 8
P3 = [2, 1, 9 ,4, 4, 56, 90, 3]
answer(C3, P3)
(4, 5)
良いようだ.
次に,入力が文字列としてそのまま書き込まれたデータファイルを読み込んで,指定された形式の文字列で解答を書き出す関数all_answerを作ってみる.
準備として,文字列の整数への変換,複数の値の代入を確認する.
(Reverse wordsのところでも紹介したが)組み込み関数intを使うと,文字列を整数に変換できる.
int('123')
123
int('012')
12
int('3.14')
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-7-1456603af047> in <module> ----> 1 int('3.14') ValueError: invalid literal for int() with base 10: '3.14'
組み込み関数intは,整数と解釈できる文字列しか整数に変換してくれない.
次に複数の値の代入を確認する.
x, y = 123, 3.14
x
123
y
3.14
Pythonでは,複数の値を同時に代入できる. これは正確にはタプルの代入であるが,タブルはいずれ説明することにして,ここでは詳しく説明しない.
同時に代入できると,値の入れ替えなども簡単にできる.
x, y = y, x
x
3.14
y
123
xとyの値を1行の命令で入れ替えられた.
複数の値の代入は,複数の値を戻す関数(例えば上記のanswer)の出力を受け取るときに便利である.
以上の準備のもとに,入力データが文字列としてそのまま書き込まれたファイルを読み込んで,指定された形式の文字列で解答を書き出す関数all_answerを以下に定義する. もちろんこれもあくまでも一例である.
いきなり下記のすべてを真似るとわけがわからなくなると思うので,段階的に試すと良いだろう.
def all_answer(input_file_name, output_file_name):
input_file = open(input_file_name) # 入力データファイルを開いて
input_data = input_file.readlines() # 全行をリストとして読み込んで
input_file.close() # ファイルを閉じる.
output_file = open(output_file_name, 'w') # 出力データファイルを開いて,
N = int(input_data.pop(0)) # 最初の行を読み込んでNに代入する.
for n in range(N):
C = int(input_data.pop(0)) # 次の行を読み込んでCに代入する.
I = int(input_data.pop(0)) # 次の行を読み込んでIに代入する.
P = input_data.pop(0) # 次の行を読み込んでPに代入する.この時点ではPは文字列である.
P = P.split() # 文字列Pを,空白で分割したリストにする.
for i in range(len(P)):
P[i] = int(P[i]) # それぞれのP[i]はまだ文字列なので,整数に変換する.
i, j = answer(C, P) # 問題を解き,解答をiとjに代入する.このように,Pythonでは複数の値に同時に代入できる.
output_file.write('Case #' + str(n+1) + ': ' + str(i) + ' ' + str(j) + '\n')
output_file.close() # 出力データファイルを閉じる.
return
データが書き込まれているテキストファイルA-sample.inを用意して,それを読み込み,A-sample.outというファイルに出力を書き込んでみる.
all_answer('A-sample.in', 'A-sample.out')
望みどおりの文字列がA-sample.outに書き出されているか,テキストエディターで見てみよう.
上記の自作関数all_answerは正しく解答を出力する. しかし,解答をファイルに書き出している行
output_file.write('Case #' + str(n+1) + ': ' + str(i) + ' ' + str(j) + '\n')
が少し煩雑である.
変数値が随所に入っている文字列を,これまでの知識で作ろうとすると,読みにくい命令になる.
このようなときは,文字列のフォーマット出力をしてくれるメソッドformatあるいは「フォーマット済み文字列リテラル(formatted string literal)」を使うとよい.
この講義ではPython3.6から導入されたフォーマット済み文字列リテラルを今後用いることにする.
以下に例を示す.
case_number = 3
name_string = 'miyamoto'
f'Case #{case_number}: {name_string}'
'Case #3: miyamoto'
フォーマット済み文字列リテラルの使い方は以下の通りである.
f'文字列'
文字列の中の{変数}となっている部分は「変数の値」で置き換えられる. 先頭のfはフォーマット済み文字列リテラルを表す記号であり,大文字Fでも良い.
上記の{変数}は,より一般には{式}としてよい. フォーマット済み文字列リテラルでは,{式}の部分はその式の評価値で置き換えられる. (変数名のみからなる式の評価値は,変数の値そのものである.)
case_number = 3
name_string = 'miyamoto'
f'Case #{case_number+1}: {name_string*2}'
'Case #4: miyamotomiyamoto'
このフォーマット済み文字列リテラルを利用した先程のall_answerを再定義すると以下の通りとなる. 異なるのは,文字列をファイルに書き込んでいる行だけである. 実質的には全く同じ処理となるので,コメントは省く.
def all_answer(input_file_name, output_file_name):
input_file = open(input_file_name)
input_data = input_file.readlines()
input_file.close()
output_file = open(output_file_name, 'w')
N = int(input_data.pop(0))
for n in range(N):
C = int(input_data.pop(0))
I = int(input_data.pop(0))
P = input_data.pop(0)
P = P.split()
for i in range(len(P)):
P[i] = int(P[i])
i, j = answer(C, P)
output_file.write(f'Case #{n+1}: {i} {j}\n') # この行が見やすくなった.
output_file.close()
return
all_answer('A-sample.in', 'A-sample.out')
望みどおりのデータが出力されているか,A-sample.outをテキストエディターで見てみよう.
関数answerはもっと簡潔に書けるが,今回はここまでにしておく.