テストドリブンで変形26進法の実装

NISHIO Hirokazu [Translate]
テストドリブンで変形26進法の実装
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進数に違いない」という「解釈」に基づくのではなく、テストケースとその成功失敗という「事実」に基づいて開発した
このテストドリブンの話はわりとも面白い気がするので忘れる前にまとめてみよう

完成形
pythondef 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を呼び出すスニペットを貼った
pythonfrom 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

まずテストケースを書く
pythondef 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.

テストに通るコードを書く
pythondef solve(N):
    """
    >>> solve(1)
    a
    """
    print(ascii_lowercase[N - 1])

テストを実行してOKなのを確認する(doctestはOKの時に何も表示しない)

テストケースを追加する
pythondef 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で割った商とあまりを計算しよう
pythondef 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.

さっき計算した商を使ってないので、とりあえず使ってみる
pythondef 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減らしてつじつまを合わせた。
pythondef 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
新しいテストケースを追加する。
pythondef 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.

さっき書いたコードをコピペして同じように修正した
pythondef 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桁目以降も同じことが続くのでループを使って書き直そう。
pythondef 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.

文字列を伸ばしていくのを忘れていた。修正する
pythondef 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進法ではない
解釈が歪んでいる
テストドリブンな事実に基づく開発をしたら、解釈による歪みが入りにくい
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:36:48 PM[Edit]
Related Pages
