1, 2, 3, …, 26, 27, 28, … を a, b, c, …, z, aa, ab, …に変換する問題が出題された https://atcoder.jp/contests/abc171/tasks/abc171_c
- a-z以外に空白文字が出てくるのだから当然26進数ではないし、空白文字が途中に出てこないのだから27進数でもないわけなのだが、Twitterを見てると26進数だと思い込んだせいでエンバグした人が多そうな気配
- 僕は、あやふやな「26進数に違いない」という「解釈」に基づくのではなく、テストケースとその成功失敗という「事実」に基づいて開発した
- このテストドリブンの話はわりとも面白い気がするので忘れる前にまとめてみよう
完成形 python
def solve(N):
q = N
ret = ""
while True:
q, r = divmod(q - 1, 26)
ret = ascii_lowercase[r] + ret
if q == 0:
print(ret)
return
最初からこのコードを書いたわけではない
最初は「この問題、テストしやすいからテストドリブンしよう」と思ったのでdoctestを呼び出すスニペットを貼った python
from string import ascii_lowercase
def solve(N):
"""
"""
def main():
N = int(input())
solve(N)
def _test():
import doctest
doctest.testmod()
if __name__ == "__main__":
import sys
argv = sys.argv
if len(sys.argv) == 1:
# no option
main()
elif sys.argv[1] == "-t":
_test()
else:
input = open(sys.argv[1]).buffer.readline
まずテストケースを書く python
def solve(N):
"""
>>> solve(1)
a
"""
当然テストはフェイルする python
$ python3 c2.py -t
**********************************************************************
File "c2.py", line 6, in __main__.solve
Failed example:
solve(1)
Expected:
a
Got nothing
**********************************************************************
1 items had failures:
1 of 1 in __main__.solve
***Test Failed*** 1 failures.
テストに通るコードを書く python
def solve(N):
"""
>>> solve(1)
a
"""
print(ascii_lowercase[N - 1])
テストを実行してOKなのを確認する(doctestはOKの時に何も表示しない)
テストケースを追加する python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
"""
print(ascii_lowercase[N - 1])
当然テストはフェイルする。
どういうフェイルをするかをみる。
26個しかない文字列の27番目を読んでIndexError: string index out of rangeになってる
python
$ python3 c2.py -t
**********************************************************************
File "c2.py", line 8, in __main__.solve
Failed example:
solve(27)
Exception raised:
Traceback (most recent call last):
File ".../doctest.py", line 1329, in __run
compileflags, 1), test.globs)
File "<doctest __main__.solve[1]>", line 1, in <module>
solve(27)
File "c2.py", line 11, in solve
print(ascii_lowercase[N - 1])
IndexError: string index out of range
**********************************************************************
1 items had failures:
1 of 2 in __main__.solve
***Test Failed*** 1 failures.
ならばとりあえず26で割った商とあまりを計算しよう python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
"""
q, r = divmod(N - 1, 26)
print(ascii_lowercase[r])
エラーメッセージは変わって、実行時エラーではなく、出力した値がおかしいとのこと。 これを直していこう python
$ python3 c2.py -t
**********************************************************************
File "c2.py", line 8, in __main__.solve
Failed example:
solve(27)
Expected:
aa
Got:
a
**********************************************************************
1 items had failures:
1 of 2 in __main__.solve
***Test Failed*** 1 failures.
さっき計算した商を使ってないので、とりあえず使ってみる python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
"""
q, r = divmod(N - 1, 26)
ret = ascii_lowercase[r]
if q == 0:
print(ret)
else:
print(ascii_lowercase[q] + ret)
aaとなるべきなのにbaになってるというフェイル(伏線1) python
$ python3 c2.py -t
**********************************************************************
File "c2.py", line 8, in __main__.solve
Failed example:
solve(27)
Expected:
aa
Got:
ba
**********************************************************************
1 items had failures:
1 of 2 in __main__.solve
***Test Failed*** 1 failures.
1減らしてつじつまを合わせた。 python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
"""
q, r = divmod(N - 1, 26)
ret = ascii_lowercase[r]
if q == 0:
print(ret)
else:
print(ascii_lowercase[q - 1] + ret)
テストOK 新しいテストケースを追加する。 python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
>>> solve(703)
aaa
"""
q, r = divmod(N - 1, 26)
ret = ascii_lowercase[r]
if q == 0:
print(ret)
else:
print(ascii_lowercase[q - 1] + ret)
当然フェイルする
このIndexError: string index out of rangeってエラーメッセージはさっき見たやつだな、同じように修正しよう
python
$ python3 c2.py -t
**********************************************************************
File "c2.py", line 10, in __main__.solve
Failed example:
solve(703)
Exception raised:
Traceback (most recent call last):
File ".../doctest.py", line 1329, in __run
compileflags, 1), test.globs)
File "<doctest __main__.solve[2]>", line 1, in <module>
solve(703)
File "c2.py", line 18, in solve
print(ascii_lowercase[q - 1] + ret)
IndexError: string index out of range
**********************************************************************
1 items had failures:
1 of 3 in __main__.solve
***Test Failed*** 1 failures.
さっき書いたコードをコピペして同じように修正した python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
>>> solve(703)
aaa
"""
q, r = divmod(N - 1, 26)
ret = ascii_lowercase[r]
if q == 0:
print(ret)
else:
q, r = divmod(q - 1, 26)
ret = ascii_lowercase[r] + ret
if q == 0:
print(ret)
else:
q, r = divmod(q - 1, 26)
ret = ascii_lowercase[r] + ret
print(ret)
テストOK 4桁目以降も同じことが続くのでループを使って書き直そう。 python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
>>> solve(703)
aaa
"""
q = N
while True:
q, r = divmod(q - 1, 26)
ret = ascii_lowercase[r]
if q == 0:
print(ret)
break
書き直してテストしたらフェイル python
$ python3 c2.py -t
**********************************************************************
File "c2.py", line 8, in __main__.solve
Failed example:
solve(27)
Expected:
aa
Got:
a
**********************************************************************
File "c2.py", line 10, in __main__.solve
Failed example:
solve(703)
Expected:
aaa
Got:
a
**********************************************************************
1 items had failures:
2 of 3 in __main__.solve
***Test Failed*** 2 failures.
文字列を伸ばしていくのを忘れていた。修正する python
def solve(N):
"""
>>> solve(1)
a
>>> solve(27)
aa
>>> solve(703)
aaa
"""
q = N
ret = ""
while True:
q, r = divmod(q - 1, 26)
ret = ascii_lowercase[r] + ret
if q == 0:
print(ret)
break
テストOK これで提出した
余談
- 途中(伏線1)でbaになったが、あれが正しい26進法
- 10進法でも初めて二桁になる数は00ではなく10だよね
- 今回の問題はbaではなくaaにならなければいけないので26進数とは違う
- Twitterを見てると、N進法ライブラリを作ろうとしたり、「正しく26進法を実装できなかった」と嘆いてたりする人がいるが、そもそもこの問題が求めてるのは26進法ではない
- 解釈が歪んでいる
- テストドリブンな事実に基づく開発をしたら、解釈による歪みが入りにくい