[Python] 最長ポケモンしりとりを探索してみた

はじめに

完全に他人のふんどしで相撲を取る行為。
Let's ポケモンしりとり！ - Qiita

コメントに「何らかの最適化問題に落とし込まないと厳しいと思います」とあったので、以前駅名でしりとりを試したコードを参考に（というかほぼそのまま）、最適化問題でポケモンしりとりを探索するコードを書きました。

検証環境

• Ubuntu 18.04
• Python 3.6.9
• PuLP 2.1

プログラム

ロジックは過去に書いた記事と全く同じですので、そちらをご覧ください。
Pythonで最長駅名しりとりを探索してみた - Qiita

それだけだと芸がないので、無駄にPython 2→Python 3に移行しました。
また、レギュレーションを最初の記事のものに合わせてあります（濁点・半濁点は区別するように変更）。

データは最初の記事で紹介されていたものを使わせていただきます。（全890匹）
https://github.com/towakey/pokedex/blob/master/pokedex.json

shiritori.py

#!/usr/bin/env python3

# modules
import sys
import itertools
import collections
import pulp
import json

# 正規化テーブル
# 小文字->大文字
regtable = dict(zip("ァィゥェォャュョ", "アイウエオヤユヨ"))

# ソース（始まり）とシンク（終わり）
SOURCE = "s"
SINK = "t"

## 指定した点を通る閉路を1つ見つける関数
## 見つけた閉路は edges から除かれる (見つからなければそのまま)
def one_cycle(edges, start):
    path = [start]
    # 深さ優先探索（スタック）
    # start からの枝を列挙
    stack = [e[1] for e, cnt in edges.items() if e[0] == start and cnt > 0]
    while len(stack) > 0:
        # 枝を1つ選ぶ
        e_new = (path[-1], stack[-1])
        edges[e_new] -= 1
        path.append(stack[-1])
        # 元の点に戻れたら終了
        if stack.pop() == start:
            return path
        # 今の地点から始まる枝を列挙
        dest_avail = [e[1] for e, cnt in edges.items() if e[0] == e_new[1] and cnt > 0]
        if len(dest_avail) == 0:
            # 行き止まり: 1ステップ巻き戻す
            edges[e_new] += 1
            path.pop()
        else:
            # 行き先を列挙する
            stack += dest_avail
    # 閉路見つからず
    return None

## Euler 閉路を取り出す
def euler_cycle(edges, start):
    edges_tmp = edges.copy()
    # まず1個閉路を探す: 深さ優先探索 (edges_tmp から取り出した閉路が除かれる)
    cycle = one_cycle(edges_tmp, start)
    assert cycle is not None
    cycle_add = cycle
    while len(edges_tmp) > 0:
        # 閉路上の点のうち、出ていく枝の残っているものを選ぶ
        next_start = [v for v in set(cycle) if any(e[0] == v and cnt > 0 for e, cnt in edges_tmp.items())]
        if len(next_start) == 0:
            # 別の連結成分があるので、諦める
            break
        else:
            # 別の閉路を探せ
            cycle_add = one_cycle(edges_tmp, next_start[0])
            assert cycle_add is not None
            # 選んだ開始点で元の閉路とつなげる
            idx = cycle.index(next_start[0])
            cycle = cycle[:idx] + cycle_add + cycle[idx+1:]
    return cycle

# solver の初期化と制約条件の設定
def make_solver(edges, vertexes, constraints):
    solver = pulp.LpProblem("Shiritori", pulp.LpMaximize)

    # 各枝に流すフローが変数に相当
    # 整数変数
    variables = dict((e, pulp.LpVariable(e, lowBound=0, cat="Integer")) for e in edges.keys())

    # 目的関数: フロー総和最大
    solver += sum(variables.values())

    # 制約条件
    # ソースから出るフロー、シンクに入るフローは1
    solver += sum([variables[e] for e in edges if e[0] == SOURCE]) == 1
    solver += sum([variables[e] for e in edges if e[1] == SINK]) == 1

    # 頂点ごとに出るフローと入るフローの総和が一致 (s, t以外)
    for v in vertexes:
        solver += sum([variables[e] for e in edges if e[0] == v]) \
               == sum([variables[e] for e in edges if e[1] == v]) 

    # フロー量制限
    for e, maxflow in edges.items():
        solver += 0 <= variables[e] <= maxflow

    # 分枝限定法に関する制約条件の追加
    # 「cycle に含まれる点から、それ以外の点への遷移が1つ以上ある」
    for cons in constraints:
        solver += sum(variables[e] for e in cons) >= 1

    return solver, variables

def main():
    with open("pokedex.json", "r") as f:
        pokedex = json.load(f)

    pokemons = []
    for p in pokedex:
        # 読みを正規化
        yomi_norm = "".join([regtable.get(c, c) for c in p["name"]])
        if yomi_norm[-1] == "ー": yomi_norm = yomi_norm[:-1]
        # ニドラン♂、ニドラン♀の時
        yomi_norm = yomi_norm.replace("♂", "オス")
        yomi_norm = yomi_norm.replace("♀", "メス")
        # ポリゴン2の時
        yomi_norm = yomi_norm.replace("2", "ツ")
        # ポリゴンZの時
        yomi_norm = yomi_norm.replace("Z", "ゼツト")

        pokemons.append((p["name"], yomi_norm, p["id"]))

    ## しりとり用グラフ作成
    # 枝リスト（と本数）: 有向グラフ
    # 枝（最初の文字と終わりの文字）ごとのリストも作成
    edges = collections.defaultdict(int)
    edges_pokemon = collections.defaultdict(set)
    for name, yomi_norm, pokedex_id in pokemons:
        t = (yomi_norm[0], yomi_norm[-1])
        edges[t] += 1
        edges_pokemon[t].add((name, pokedex_id))

    # ソースとシンクを加える
    vertexes = set(itertools.chain(*edges.keys()))
    for v in vertexes:
        edges[(SOURCE, v)] = 1
        edges[(v, SINK)] = 1

    # *****
    # 最大流問題として整数計画法で解く

    length_tmp = 0
    solution_tmp = None
    constraints = []
    while True:
        solver, variables = make_solver(edges, vertexes, constraints)
        solver.solve()
        if solver.status != pulp.constants.LpStatusOptimal:
            # そのような解は無い: 現時点の解が最終的な解
            break

        # sから出る枝とtに入る枝を除いたものが、
        # （飛び地がないと仮定した場合の）しりとりの長さ（単語数）
        length_upper = int(pulp.value(solver.objective)+0.01) - 2

        # *****
        # 結果を加工

        # 使う枝を列挙
        # 簡単のため t -> s のパスを加えて閉路にしておく
        #edges_sub = dict(itertools.ifilter(lambda _, sol: sol > 0,
        #                                   ((e, variables[e].value()) for e in edges.keys())))
        edges_sub = dict((e, variables[e].value()) for e in edges.keys() if variables[e].value() > 0)
        edges_sub[(SINK, SOURCE)] = 1

        # Euler 閉路を探す（どこから始めてもよいのでsに固定）
        cycle = euler_cycle(edges_sub, SOURCE)
        # cycle: s -> X1 -> ... -> Xn -> t -> s で、X1からXnまでの -> の数は len(cycle)-4
        length_lower = len(cycle) - 4
        sys.stderr.write("{0}/{1} ".format(length_lower, length_upper))
        if length_lower == length_upper:
            # 連結グラフ
            print("連結グラフ", file=sys.stderr)
            if length_tmp < length_lower:
                # 解の更新
                length_tmp = length_lower
                solution_tmp = cycle
            # 今の解で確定
            break
        else:
            # 連結グラフでない
            # 解の更新ができないなら終わり
            print("非連結グラフ", file=sys.stderr)
            if length_upper <= length_tmp:
                break
            if length_tmp < length_lower:
                # 少なくとも今の解より良い解は見つかった
                length_tmp = length_lower
                solution_tmp = cycle
            print("新たな解の探索を試みます", file=sys.stderr)

            # 次回以降「cycle に含まれる点から、それ以外の点への遷移が1つ以上ある」
            # という条件を追加
            vertexes_cycle = [v for v in vertexes if v in cycle]
            vertexes_outofcycle = [v for v in vertexes if v not in cycle]
            # そのような遷移を列挙
            list_added_edges = [e for e in itertools.product(vertexes_cycle, vertexes_outofcycle) if e in edges]
            if len(list_added_edges) == 0:
                # 初めからそのような遷移がなければ終了
                break
            constraints.append(list_added_edges)

    # *****
    ## リストに変換

    print("ポケモン数", length_tmp, file=sys.stderr)
    for e1, e2 in zip(solution_tmp[1:-3], solution_tmp[2:-2]):
        # 与えられた最初と最後の文字に当てはまるポケモンを1つ選んで出力
        used = edges_pokemon[(e1, e2)].pop()
        print("{0} {1} {2:03d} {3}".format(e1, e2, used[1], used[0]))

if __name__ == "__main__":
    main()

結果（全370匹）

最長しりとりの作り方は一通りとは限りません。以下は最長しりとりの一例です。

ペ フ 684 ペロッパフ
フ エ 795 フェローチェ
エ コ 300 エネコ
コ ポ 875 コオリッポ
ポ ポ 016 ポッポ
ポ マ 393 ポッチャマ
マ デ 851 マルヤクデ
デ シ 719 ディアンシー
シ イ 773 シルヴァディ
イ ブ 826 イオルブ
ブ キ 197 ブラッキー
キ ワ 764 キュワワー
ワ コ 189 ワタッコ
コ ド 620 コジョンド
ド ト 887 ドラパルト
ト ガ 365 トドゼルガ
ガ イ 058 ガーディ
イ テ 074 イシツブテ
テ オ 223 テッポウオ
オ メ 277 オオスバメ
メ マ 469 メガヤンマ
マ ミ 069 マダツボミ
ミ ツ 150 ミュウツー
ツ ボ 213 ツボツボ
ボ ラ 306 ボスゴドラ
ラ タ 020 ラッタ
タ マ 102 タマタマ
マ キ 056 マンキー
キ ピ 010 キャタピー
ピ ピ 035 ピッピ
ピ シ 036 ピクシー
シ ダ 090 シェルダー
ダ オ 051 ダグトリオ
オ メ 021 オニスズメ
メ ゲ 072 メノクラゲ
ゲ ガ 094 ゲンガー
ガ ラ 105 ガラガラ
ラ ウ 026 ライチュウ
ウ ト 071 ウツボット
ト ル 777 トゲデマル
ル ラ 124 ルージュラ
ラ ウ 243 ライコウ
ウ イ 059 ウインディ
イ イ 133 イーブイ
イ イ 557 イシズマイ
イ ク 095 イワーク
ク ナ 044 クサイハナ
ナ サ 043 ナゾノクサ
サ ゴ 222 サニーゴ
ゴ キ 067 ゴーリキー
キ キ 203 キリンリキ
キ リ 192 キマワリ
リ ド 005 リザード
ド ド 084 ドードー
ド ゲ 073 ドククラゲ
ゲ ガ 658 ゲッコウガ
ガ ラ 115 ガルーラ
ラ ス 754 ラランテス
ス ク 123 ストライク
ク マ 204 クヌギダマ
マ タ 296 マクノシタ
タ ボ 273 タネボー
ボ ス 642 ボルトロス
ス ク 435 スカタンク
ク ト 169 クロバット
ト ス 468 トゲキッス
ス ミ 121 スターミー
ミ ム 413 ミノマダム
ム ド 508 ムーランド
ド ラ 436 ドーミラー
ラ ス 381 ラティオス
ス ミ 406 スボミー
ミ チ 412 ミノムッチ
チ ム 308 チャーレム
ム ド 397 ムクバード
ド ラ 532 ドッコラー
ラ ス 645 ランドロス
ス パ 097 スリーパー
パ ア 484 パルキア
ア ダ 617 アギルダー
ダ キ 539 ダゲキ
キ ア 318 キバニア
ア ム 482 アグノム
ム ル 238 ムチュール
ル リ 298 ルリリ
リ マ 217 リングマ
マ ド 756 マシェード
ド チ 339 ドジョッチ
チ ム 421 チェリム
ム ル 396 ムックル
ル パ 272 ルンパッパ
パ ウ 086 パウワウ
ウ パ 194 ウパー
パ ト 047 パラセクト
ト ク 176 トゲチック
ク ト 303 クチート
ト ピ 175 トゲピー
ピ ユ 172 ピチュー
ユ シ 361 ユキワラシ
シ ラ 117 シードラ
ラ ス 380 ラティアス
ス プ 434 スカンプー
プ ル 592 プルリル
ル ア 249 ルギア
ア ド 348 アーマルド
ド チ 886 ドロンチ
チ チ 170 チョンチー
チ タ 152 チコリータ
タ ツ 870 タイレーツ
ツ ラ 731 ツツケラ
ラ ス 280 ラルトス
ス プ 096 スリープ
プ ラ 142 プテラ
ラ ス 370 ラブカス
ス ア 015 スピアー
ア マ 283 アメタマ
マ ド 802 マーシャドー
ド ム 294 ドゴーム
ム マ 200 ムウマ
マ ド 268 マユルド
ド オ 085 ドードリオ
オ タ 139 オムスター
タ ツ 116 タッツー
ツ ア 614 ツンベアー
ア モ 255 アチャモ
モ コ 877 モルペコ
コ ク 054 コダック
ク ブ 098 クラブ
ブ バ 126 ブーバー
バ ダ 323 バクーダ
ダ ズ 476 ダイノーズ
ズ ト 041 ズバット
ト ト 118 トサキント
ト ル 011 トランセル
ル ラ 792 ルナアーラ
ラ ス 131 ラプラス
ス ア 769 スナバァ
ア ツ 159 アリゲイツ
ツ ヤ 495 ツタージャ
ヤ マ 193 ヤンヤンマ
マ マ 264 マッスグマ
マ ゴ 219 マグカルゴ
ゴ ヤ 076 ゴローニャ
ヤ マ 661 ヤヤコマ
マ シ 156 マグマラシ
シ ラ 561 シンボラー
ラ キ 113 ラッキー
キ ア 281 キルリア
ア ウ 119 アズマオウ
ウ キ 185 ウソッキー
キ メ 278 キャモメ
メ コ 551 メグロコ
コ タ 019 コラッタ
タ マ 862 タチフサグマ
マ シ 655 マフォクシー
シ ラ 609 シャンデラ
ラ ア 045 ラフレシア
ア ボ 023 アーボ
ボ ダ 373 ボーマンダ
ダ グ 275 ダーテング
グ ガ 207 グライガー
ガ ゲ 537 ガマゲロゲ
ゲ ラ 657 ゲコガシラ
ラ ラ 608 ランプラー
ラ ド 409 ラムパルド
ド ヤ 885 ドラメシヤ
ヤ ヤ 854 ヤバチャ
ヤ デ 850 ヤクデ
デ ネ 702 デデンネ
ネ マ 800 ネクロズマ
マ ニ 739 マケンカニ
ニ ビ 725 ニャビー
ビ ニ 494 ビクティニ
ニ ア 700 ニンフィア
ア ユ 841 アップリュー
ユ ミ 872 ユキハミ
ミ ユ 778 ミミッキュ
ユ コ 478 ユキメノコ
コ フ 619 コジョフー
フ ベ 669 フラベベ
ベ バ 859 ベロバー
バ ニ 871 バチンウニ
ニ マ 431 ニャルマー
マ カ 686 マーイーカ
カ メ 833 カムカメ
メ タ 648 メロエッタ
タ コ 852 タタッコ
コ ヒ 580 コアルヒー
ヒ カ 829 ヒメンカ
カ メ 834 カジリガメ
メ バ 636 メラルバ
バ ヤ 710 バケッチャ
ヤ ム 674 ヤンチャム
ム ナ 890 ムゲンダイナ
ナ イ 598 ナットレイ
イ コ 744 イワンコ
コ リ 527 コロモリ
リ レ 605 リグレー
レ ザ 384 レックウザ
ザ タ 889 ザマゼンタ
タ ケ 590 タマゲタケ
ケ ソ 265 ケムッソ
ソ オ 791 ソルガレオ
オ ゲ 861 オーロンゲ
ゲ ト 649 ゲノセクト
ト ラ 364 トドグラー
ラ ト 310 ライボルト
ト ス 641 トルネロス
ス ダ 849 ストリンダー
ダ カ 554 ダルマッカ
カ フ 786 カプ・テテフ
フ デ 543 フシデ
デ ド 225 デリバード
ド コ 749 ドロバンコ
コ リ 528 ココロモリ
リ ア 470 リーフィア
ア ア 823 アーマーガア
ア グ 799 アクジキング
グ ヤ 768 グソクムシャ
ヤ キ 512 ヤナッキー
キ マ 760 キテルグマ
マ ヨ 618 マッギョ
ヨ シ 746 ヨワシ
シ ナ 770 シロデスナ
ナ キ 538 ナゲキ
キ ゴ 610 キバゴ
ゴ ダ 812 ゴリランダー
ダ ロ 524 ダンゴロ
ロ ム 479 ロトム
ム ナ 518 ムシャーナ
ナ ラ 328 ナックラー
ラ ト 814 ラビフット
ト ス 357 トロピウス
ス ビ 843 スナヘビ
ビ バ 329 ビブラーバ
バ オ 550 バスラオ
オ モ 752 オニシズクモ
モ ウ 873 モスノウ
ウ ド 793 ウツロイド
ド デ 748 ドヒドイデ
デ ウ 181 デンリュウ
ウ ウ 845 ウッウ
ウ ウ 692 ウデッポウ
ウ チ 438 ウソハチ
チ キ 616 チョボマキ
キ サ 286 キノガッサ
サ ヤ 844 サダイジャ
ヤ ミ 302 ヤミラミ
ミ ミ 504 ミネズミ
ミ ニ 415 ミツハニー
ニ ゾ 061 ニョロゾ
ゾ ア 570 ゾロア
ア ヨ 763 アマージョ
ヨ リ 506 ヨーテリー
リ ル 447 リオル
ル ル 701 ルチャブル
ル オ 404 ルクシオ
オ ド 611 オノンド
ド ロ 691 ドラミドロ
ロ ド 407 ロズレイド
ド ア 549 ドレディア
ア コ 762 アママイコ
コ シ 401 コロボーシ
シ モ 751 シズクモ
モ ユ 529 モグリュー
ユ オ 460 ユキノオー
オ シ 234 オドシシ
シ プ 682 シュシュプ
プ ガ 564 プロトーガ
ガ ス 689 ガメノデス
ス ナ 581 スワンナ
ナ ロ 287 ナマケロ
ロ ア 315 ロゼリア
ア ジ 761 アマカジ
ジ ゴ 783 ジャランゴ
ゴ ベ 446 ゴンベ
ベ フ 153 ベイリーフ
フ テ 425 フワンテ
テ ヤ 797 テッカグヤ
ヤ グ 199 ヤドキング
グ ア 471 グレイシア
ア シ 736 アゴジムシ
シ コ 667 シシコ
コ シ 664 コフキムシ
シ ゴ 589 シュバルゴ
ゴ ヨ 293 ゴニョニョ
ヨ ク 164 ヨルノズク
ク ネ 827 クスネ
ネ ラ 775 ネッコアラ
ラ イ 309 ラクライ
イ ゼ 314 イルミーゼ
ゼ カ 523 ゼブライカ
カ テ 688 カメテテ
テ ド 597 テッシード
ド ツ 533 ドテッコツ
ツ デ 805 ツンデツンデ
デ ダ 050 ディグダ
ダ キ 503 ダイケンキ
キ コ 285 キノココ
コ シ 767 コソクムシ
シ カ 585 シキジカ
カ ギ 083 カモネギ
ギ モ 860 ギモー
モ ボ 465 モジャンボ
ボ レ 708 ボクレー
レ バ 165 レディバ
バ ブ 325 バネブー
ブ タ 136 ブースター
タ ネ 531 タブンネ
ネ ユ 755 ネマシュ
ユ リ 459 ユキカブリ
リ ラ 345 リリーラ
ラ ジ 260 ラグラージ
ジ コ 782 ジャラコ
コ ラ 304 ココドラ
ラ ス 579 ランクルス
ス ピ 451 スコルピ
ピ ク 440 ピンプク
ク イ 707 クレッフィ
イ ム 221 イノムー
ム ナ 517 ムンナ
ナ シ 771 ナマコブシ
シ マ 522 シママ
マ ウ 594 ママンボウ
ウ ム 220 ウリムー
ム ジ 429 ムウマージ
ジ ビ 496 ジャノビー
ビ マ 100 ビリリダマ
マ チ 556 マラカッチ
チ ノ 573 チラチーノ
ノ チ 206 ノコッチ
チ ネ 548 チュリネ
ネ オ 178 ネイティオ
オ チ 161 オタチ
チ コ 509 チョロネコ
コ ク 402 コロトック
ク モ 690 クズモー
モ コ 180 モココ
コ ク 403 コリンク
ク ユ 541 クルマユ
ユ シ 480 ユクシー
シ ミ 492 シェイミ
ミ ム 856 ミブリム
ム ク 398 ムクホーク
ク ア 488 クレセリア
ア ヌ 730 アシレーヌ
ヌ マ 759 ヌイコグマ
マ ネ 439 マネネ
ネ イ 177 ネイティ
イ ル 717 イベルタル
ル オ 448 ルカリオ
オ チ 162 オオタチ
チ ブ 499 チャオブー
ブ タ 693 ブロスター
タ タ 458 タマンタ
タ シ 363 タマザラシ
シ ガ 342 シザリガー
ガ ト 444 ガバイト
ト ス 411 トリデプス
ス メ 276 スバメ
メ カ 586 メブキジカ
カ ギ 798 カミツルギ
ギ ド 681 ギルガルド
ド グ 454 ドクロッグ
グ ナ 262 グラエナ
ナ シ 103 ナッシー
シ ズ 134 シャワーズ
ズ グ 559 ズルッグ
グ ル 210 グランブル
ル ン 745 ルガルガン