Let's ポケモンしりとり！

日曜の夜はポケモン見ています。
最近のアニポケのEDは「[ポケモンしりとり(ピカチュウ→ミュウVer.)](https://www.youtube.com/watch?v=uvOfXoQxT2o)」という曲で、
ポケモンの名前でしりとりをしています。
そこでふと思ったのですが、ポケモンだけでしりとりをした場合、最大何匹まで繋げられるのか？
気になった調査隊はポナヤツングスカ地方へと調査へと向かうのだった…。

# 使用するポケモンの定義
- 使用するのは現在判明している890種のポケモン
- リージョンフォーム、なんとかフォルム等姿が複数いるものは1体とカウント  
例えばロコンは通常ロコンとアローラロコンがいますが1体とカウント。
またデオキシスは通常フォルムの他にアタックやディフェンスがありますがこちらも1体とします。
メガシンカポケモンも使用しません。

- 長音の場合は長音直前の文字を使用（ハクリュー -> 「ユ」）
- 「♂」「♀」はそれぞれ、オ「ス」、メ「ス」を使用
- 小文字の場合は大文字に変換（ウインディ -> 「イ」）
- 「2」「Z」はそれぞれの呼び方「ツー」「ゼット」の最後の字を取る（ツー -> 「ツ」、Z -> 「ト」）

890体のポケモンを一から入力するのは面倒なので、こちらから名前データを利用します。
https://github.com/towakey/pokedex/blob/master/pokedex.json
ちなみにこちら、私が編集しています。
興味がある方、ぜひご協力をお願いします。

# とりあえずJSONを読み込むようにする

```python:letspokemonshiritori.py
# coding: utf-8
import json

pokedex_path = 'pokedex.json'

with open(pokedex_path,encoding='utf-8') as f:
    pokedex = json.load(f)

print(pokedex[0]['name'])
```
これでコンソールに「フシギダネ」と表示されれば成功。

# しりとりの下準備
ポケモン名の頭文字でまとめた連想配列を作ります。
具体的にはこんな感じ。

```json:
{
    "ア": {
        "アーボ": {
            "lastword": "ボ",
            "flag": False
        },
        "アーボック": {
            "lastword": "ク",
            "flag": False
        }
    }
}
```
flagは、一度使われるとTrueが入るようになります。

さあ先ほど読み込んだjsonを使ってしりとり用配列を作りましょう。

```python:letspokemonshiritori.py
shiritori = {}
for word in pokedex:
    set_pokemon = {}

    # 基本的には最後の文字を使用する
    lastplace = -1

    # ニドラン♂、ニドラン♀の時
    if word['name'][lastplace] == '♂' or word['name'][lastplace] == '♀':
        set_pokemon['lastword'] = 'ス'
    # ポリゴン2の時
    elif word['name'][lastplace] == '2':
        set_pokemon['lastword'] = 'ツ'
    # ポリゴンZの時
    elif word['name'][lastplace] == 'Z':
        set_pokemon['lastword'] = 'ト'
    else:
        # 最後の文字が長音の時は、直前の文字を使用する
        if word['name'][lastplace] == 'ー':
            lastplace = -2
        # カタカナの小文字は大文字にする
        if word['name'][lastplace] == "ァ":
            set_pokemon['lastword'] = "ア"
        elif word['name'][lastplace] == "ィ":
            set_pokemon['lastword'] = "イ"
        elif word['name'][lastplace] == "ゥ":
            set_pokemon['lastword'] = "ウ"
        elif word['name'][lastplace] == "ェ":
            set_pokemon['lastword'] = "エ"
        elif word['name'][lastplace] == "ォ":
            set_pokemon['lastword'] = "オ"
        elif word['name'][lastplace] == "ッ":
            set_pokemon['lastword'] = "ツ"
        elif word['name'][lastplace] == "ャ":
            set_pokemon['lastword'] = "ヤ"
        elif word['name'][lastplace] == "ュ":
            set_pokemon['lastword'] = "ユ"
        elif word['name'][lastplace] == "ョ":
            set_pokemon['lastword'] = "ヨ"
        elif word['name'][lastplace] == "ヮ":
            set_pokemon['lastword'] = "ワ"
        elif word['name'][lastplace] == "ヵ":
            set_pokemon['lastword'] = "カ"
        elif word['name'][lastplace] == "ヶ":
            set_pokemon['lastword'] = "ケ"
        else:
            # それ以外の場合はそのまま使用する
            set_pokemon['lastword'] = word['name'][lastplace]
    # フラグのデフォルト値はFalse
    set_pokemon['flag'] = False
    # 頭文字の配列が無ければ連想配列として初期化
    if word['name'][0] not in shiritori:
        shiritori[word['name'][0]] = {}
    # ポケモンの名前で配列を保存
    shiritori[word['name'][0]][word['name']] = set_pokemon
```
これで準備はできました。

# Let's ポケモンしりとり!

「shiritori_word」という変数に繋げるワードを格納します。

```python:letspokemonshiritori.py
shiritori_list = []
shiritori_max = []
# 最初の文字（カタカナ）
shiritori_word = "ア"

flag,shiritori_max = shiritori_run(shiritori,shiritori_word,shiritori_list,True,shiritori_max)
print(shiritori_max)
with open("shiritori.txt",mode="w",encoding="utf-8") as f:
    f.write(str(shiritori_max))
```

「shiritori_run」という関数を作り、それを再帰的に繋げることにより総当たりでしりとりを検証していきます。

```python:letspokemonshiritori.py
def shiritori_run(shiritori,shiritori_word,shiritori_list,flag,shiritori_max):
    # 頭文字のポケモンがいるか検査する
    if shiritori_word in shiritori:
        for key,word in shiritori[shiritori_word].items():
            if word['flag'] == False:
                shiritori[shiritori_word][key]['flag'] = True
                shiritori_list.append(key)
                flag,shiritori_max = shiritori_run(shiritori,word['lastword'],shiritori_list,flag,shiritori_max)
                # もし返ってきたらFalseになっていたら…
                if flag == False:
                    # 現在の状態を保存
                    print(str(len(shiritori_list))+" : "+str(len(shiritori_max)))
                    if int(len(shiritori_list)) > int(len(shiritori_max)):
                        shiritori_max = copy.deepcopy(shiritori_list)
                        with open("temp/shiritori-"+str(len(shiritori_max))+".txt",mode="w",encoding="utf-8") as f:
                            f.write(str(shiritori_max))
                    # 最後の名前を削除
                    del shiritori_list[-1]
                    # フラグを戻す
                    shiritori[shiritori_word][key]['flag'] = False

    else:
        flag = False
    return flag,shiritori_max

```
実装していて躓いたのがList型のコピーでした。
最初は俗に言う「浅いコピー」をしていたのですが、浅いコピーだとアドレス参照になる為
copyモジュールのdeepcopyでコピーしています。

```python:
shiritori_max = copy.deepcopy(shiritori_list)
```

この「shiritori_max」にポケモンしりとりの最大値が保存されます。

ちなみにこれを書きながらプログラムを動かしていますが、未だに総当たりが終わりません(´・ω・｀)
ポケモントレーナーの皆さん、暇があったらシミュレーションしてみてください。

Let's Play ポケモンしりとり！

ちなみに「ア」から始めた場合で現時点で分かってる最長しりとりが下記(312匹)


```
アーボ→ボスゴドラ→ラッタ→タマタマ→マンキー→キャタピー→ピジョット→トランセル→ルージュラ→ライチュウ→ウインディ→イシツブテ→テッポウオ→オニスズメ→メノクラゲ→ゲンガー→ガーディ→イワーク→クサイハナ→ナゾノクサ→サンド→ドククラゲ→ゲノセクト→トサキント→トゲピー→ピカチュウ→ウツボット→トゲチック→クラブ→ブーバー→バタフリー→リザード→ドードー→ドードリオ→オニドリル→ルギア→アーボック→クロバット→トロピウス→スピアー→アズマオウ→ウソッキー→キングラー→ラフレシア→アリゲイツ→ツボツボ→ボーマンダ→ダグトリオ→オコリザル→ルンパッパ→パラス→スリープ→プテラ→ラッキー→キレイハナ→ナッシー→シェルダー→ダーテング→グライガー→ガラガラ→ラプラス→スリーパー→パラセクト→トドグラー→ライコウ→ウパー→パウワウ→ウリムー→ムウマ→マダツボミ→ミニリュウ→ウソハチ→チコリータ→タッツー→ツタージャ→ヤンヤンマ→マタドガス→スターミー→ミュウツー→ツンベアー→アリアドス→ストライク→クヌギダマ→マグマラシ→シードラ→ラグラージ→ジュプトル→ルリリ→リングマ→マリル→ルクシオ→オムナイト→トドゼルガ→ガルーラ→ラルトス→スバメ→メガニウム→ムチュール→ルカリオ→オムスター→タネボー→ボルトロス→スボミー→ミュウ→ウォーグル→ルチャブル→ルナアーラ→ラクライ→イーブイ→イノムー→ムクバード→ドガース→スカンプー→プロトーガ→ガバイト→トリデプス→スカタンク→クチート→トゲキッス→スコルピ→ピッピ→ピクシー→シャワーズ→ズバット→トルネロス→スワンナ→ナマケロ→ロゼリア→アチャモ→モンジャラ→ラブカス→スナバァ→アメタマ→マリルリ→リリーラ→ラティアス→スナヘビ→ビリリダマ→マグマッグ→グラエナ→ナックラー→ラティオス→ストリンダー→ダイノーズ→ズルッグ→グレイシア→アーマルド→ドゴーム→ムクホーク→クレセリア→アグノム→ムウマージ→ジグザグマ→マグカルゴ→ゴルダック→クルマユ→ユンゲラー→ラムパルド→ドジョッチ→チョンチー→チャーレム→ムーランド→ドクロッグ→グソクムシャ→ヤルキモノ→ノコッチ→チェリンボ→ボクレー→レディバ→バリヤード→ドテッコツ→ツンデツンデ→ディグダ→ダークライ→イルミーゼ→ゼニガメ→メガヤンマ→マッスグマ→マユルド→ドレディア→アギルダー→ダイケンキ→キマワリ→リーフィア→アシマリ→リグレー→レジロック→クズモー→モココ→コラッタ→タマザラシ→シェイミ→ミルタンク→クレッフィ→イシズマイ→イワンコ→コダック→クスネ→ネイティ→イオルブ→ブースター→タマンタ→タブンネ→ネイティオ→オタチ→チェリム→ムンナ→ナゲキ→キリンリキ→キャモメ→メグロコ→コノハナ→ナマコブシ→シママ→マクノシタ→タマゲタケ→ケムッソ→ソルガレオ→オオタチ→チャオブー→ブラッキー→キルリア→アシレーヌ→ヌオー→オドシシ→シキジカ→カイリキー→キノココ→コロボーシ→シュバルゴ→ゴーリキー→キノガッサ→サンダー→ダンゴロ→ロズレイド→ドヒドイデ→デンリュウ→ウデッポウ→ウツロイド→ドロバンコ→コアルヒー→ヒノアラシ→シシコ→コジョフー→フシギダネ→ネマシュ→ユキワラシ→シズクモ→モグリュー→ユキノオー→オオスバメ→メブキジカ→カモネギ→ギルガルド→ドラメシヤ→ヤミラミ→ミノムッチ→チョロネコ→コジョンド→ドロンチ→チュリネ→ネクロズマ→マスキッパ→パルキア→アマカジ→ジュペッタ→タタッコ→コオリッポ→ポッポ→ポニータ→タチフサグマ→マラカッチ→チョボマキ→キバニア→アーマーガア→アップリュー→ユキハミ→ミツハニー→ニャルマー→マーイーカ→カメテテ→テッカグヤ→ヤナッキー→キュワワー→ワンリキー→キバゴ→ゴンベ→ベイリーフ→フラベベ→ベロバー→バクーダ→ダルマッカ→カムカメ→メラルバ→バケッチャ→ヤバチャ→ヤヤコマ→マケンカニ→ニャビー→ビブラーバ→バチンウニ→ニョロゾ→ゾロア→アママイコ→コフキムシ→シザリガー→ガマゲロゲ→ゲコガシラ→ランプラー→ライボルト→トゲデマル→ルナトーン
```