Created
February 10, 2022 14:28
-
-
Save CookieBox26/377e36d2bfa26223075d85698ff95e59 to your computer and use it in GitHub Desktop.
Untitled.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"入力可能ポケモン 847 ['フシギダネ', 'フシギソウ', 'フシギバナ'] ... ['レジドラゴ', 'ブリザポス', 'レイスポス']\n", | |
"正答候補ポケモン 511 ['フシギダネ', 'フシギソウ', 'フシギバナ'] ... ['レジドラゴ', 'ブリザポス', 'レイスポス']\n" | |
] | |
} | |
], | |
"source": [ | |
"import re\n", | |
"katakana = re.compile('[\\u30A1-\\u30FF]+')\n", | |
"\n", | |
"'''\n", | |
"そのポケモンが入力可能か=5文字以下かつ全てカタカナか\n", | |
"'''\n", | |
"def is_inputable(s):\n", | |
" return (len(s)<=5) and (katakana.fullmatch(s) is not None)\n", | |
"\n", | |
"'''\n", | |
"ポケモンの取得\n", | |
"'''\n", | |
"def get_pokemons():\n", | |
" pokemons = [] # 入力可能ポケモン \n", | |
" pokemons_kouho = [] # 正答候補ポケモン \n", | |
" # ウィキペディアから剣盾のポケモンまでコピーし各行を「番号\\tポケモン名」にする\n", | |
" with open('poke.txt', encoding='utf8') as ifile:\n", | |
" for line in ifile:\n", | |
" pokemon = line.strip().split('\\t')[1]\n", | |
" if is_inputable(pokemon):\n", | |
" pokemons.append(pokemon)\n", | |
" if len(pokemon) == 5:\n", | |
" pokemons_kouho.append(pokemon)\n", | |
" return pokemons, pokemons_kouho\n", | |
"\n", | |
"pokemons, pokemons_kouho = get_pokemons()\n", | |
"print('入力可能ポケモン', len(pokemons), pokemons[:3], '...', pokemons[-3:])\n", | |
"print('正答候補ポケモン', len(pokemons_kouho), pokemons_kouho[:3], '...', pokemons_kouho[-3:])" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"黒黒黄黄黒\n" | |
] | |
} | |
], | |
"source": [ | |
"from collections import defaultdict\n", | |
"\n", | |
"'''\n", | |
"正答ポケモンが pokemon_answer の条件下で\n", | |
"入力ポケモン pokemon_input を入力したときの返却画面\n", | |
"'''\n", | |
"def get_gamen(pokemon_input, pokemon_answer):\n", | |
" gamen = ['黒'] * 5 # デフォルトですべて黒にしておく\n", | |
" d = defaultdict(list)\n", | |
" for i, s in enumerate(pokemon_input): # 入力ポケモンを{ 使用文字: 使用位置, ... } の形の辞書にする\n", | |
" d[s].append(i)\n", | |
" for k, v in d.items(): # 入力ポケモン中の文字ごとに処理する\n", | |
" if k not in pokemon_answer: # 正解ポケモン中で使われていない文字ならば色塗り処理なし\n", | |
" continue\n", | |
" index_ = [i for i, s in enumerate(pokemon_answer) if s == k] # 正解ポケモン側での使用位置を抽出する\n", | |
" match = list(set(index_) & set(v))\n", | |
" for m in match: # 正解側と入力側の使用位置の共通部分は必ず緑に塗る\n", | |
" gamen[m] = '緑'\n", | |
" v.remove(m)\n", | |
" index_.remove(m)\n", | |
" for i in range(len(index_)): # 共通部分除去しても正解側にまだ使用位置があるときその個数まで黄に塗る\n", | |
" if i >= len(v): # 入力側にもう塗る位置がないなら終わる\n", | |
" break\n", | |
" gamen[v[i]] = '黄'\n", | |
" return ''.join(gamen)\n", | |
"\n", | |
"pokemon_input = 'キノココ'\n", | |
"pokemon_answer = 'ココロモリ'\n", | |
"print(get_gamen(pokemon_input, pokemon_answer))" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"from collections import Counter\n", | |
"from collections import OrderedDict\n", | |
"\n", | |
"# { 入力ポケモン: { 画面: [候補], 画面: [候補], ...}, } の形式のデータの作成\n", | |
"results_ = {}\n", | |
"n_kouho_worst = {}\n", | |
"for pokemon_input in pokemons: # 入力可能ポケモン\n", | |
" result = defaultdict(set)\n", | |
" for pokemon_answer in pokemons_kouho: # 正答候補ポケモン\n", | |
" gamen = get_gamen(pokemon_input, pokemon_answer)\n", | |
" result[gamen].add(pokemon_answer)\n", | |
" result = sorted(result.items(), key=lambda x:-len(x[1]))\n", | |
" results_[pokemon_input] = OrderedDict()\n", | |
" for k, v in result:\n", | |
" results_[pokemon_input][k] = v\n", | |
" n_kouho_worst[pokemon_input] = len(result[0][1])\n", | |
"results_ = sorted(results_.items(), key=lambda x: n_kouho_worst[x[0]])\n", | |
"results = OrderedDict()\n", | |
"for k, v in results_:\n", | |
" results[k] = v" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"ジーランス\n", | |
" 黒黒黒黒黒 (26.61%) 候補数 136 ['ビリリダマ', 'クサイハナ', 'フシギソウ', 'ポッタイシ', 'トドゼルガ']\n", | |
" 黒黄黒黒黒 (13.89%) 候補数 71 ['ニドリーナ', 'ファイヤー', 'ニドリーノ', 'エアームド', 'カイオーガ']\n", | |
" 黒黒黒黄黒 (10.76%) 候補数 55 ['ヒトデマン', 'カクレオン', 'クリムガン', 'クワガノン', 'デンヂムシ']\n", | |
" 黒黒黒黒緑 ( 7.05%) 候補数 36 ['ボルトロス', 'フォレトス', 'ホシガリス', 'カブトプス', 'カメックス']\n", | |
" 黒黒黄黒黒 ( 4.70%) 候補数 24 ['ラムパルド', 'ライボルト', 'ラフレシア', 'ドラミドロ', 'ワタシラガ']\n", | |
" ...\n", | |
"レントラー\n", | |
" 黒黒黒黒黒 (27.98%) 候補数 143 ['ビリリダマ', 'クサイハナ', 'オノノクス', 'フシギソウ', 'ポッタイシ']\n", | |
" 黒黒黒黒黄 (10.57%) 候補数 54 ['ニドリーナ', 'ニドリーノ', 'エアームド', 'ブーピッグ', 'カイオーガ']\n", | |
" 黒黄黒黒黒 (10.57%) 候補数 54 ['クリムガン', 'クワガノン', 'ニョロボン', 'メガヤンマ', 'ママンボウ']\n", | |
" 黒黒黒黒緑 ( 7.44%) 候補数 38 ['ファイヤー', 'ジャノビー', 'アギルダー', 'ミュウツー', 'ニャルマー']\n", | |
" 黒黒黒黄黒 ( 4.31%) 候補数 22 ['ラムパルド', 'ラティオス', 'ケララッパ', 'ドラミドロ', 'サクラビス']\n", | |
" ...\n", | |
"ルナトーン\n", | |
" 黒黒黒黒黒 (28.38%) 候補数 145 ['ビリリダマ', 'ラティオス', 'オノノクス', 'ラフレシア', 'フシギソウ']\n", | |
" 黒黒黒黄黒 (10.96%) 候補数 56 ['ファイヤー', 'エアームド', 'ブーピッグ', 'ダークライ', 'ツタージャ']\n", | |
" 黄黒黒黒黒 ( 9.20%) 候補数 47 ['ラムパルド', 'バリコオル', 'ミルホッグ', 'グレッグル', 'アマルルガ']\n", | |
" 黒黒黒黒黄 ( 7.63%) 候補数 39 ['ヤンヤンマ', 'デンヂムシ', 'メガヤンマ', 'ママンボウ', 'バンバドロ']\n", | |
" 黒黒黒緑黒 ( 6.65%) 候補数 34 ['ニドリーノ', 'カイオーガ', 'ムクホーク', 'ダイノーズ', 'アバゴーラ']\n", | |
" ...\n", | |
"...\n" | |
] | |
} | |
], | |
"source": [ | |
"for i, (pokemon_input, result) in enumerate(results.items()):\n", | |
" if i == 3:\n", | |
" print('...')\n", | |
" break\n", | |
" print(pokemon_input)\n", | |
" for j, (gamen, kouho) in enumerate(result.items()):\n", | |
" if j == 5:\n", | |
" print(' ...')\n", | |
" break\n", | |
" count = len(kouho)\n", | |
" prob = float(count) / 511.0\n", | |
" print(' ', gamen, f'({prob:6.2%}) 候補数 {count: >3}', list(kouho)[:5])" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"metadata": { | |
"scrolled": false | |
}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"----- START -----\n", | |
"◆ 1手目終了後に残る候補数の期待値\n", | |
" 1位 ジーランス 1手目終了後に残る候補数の期待値: 58.90019569471623\n", | |
" 2位 レントラー 1手目終了後に残る候補数の期待値: 59.21330724070448\n", | |
" 3位 ルナトーン 1手目終了後に残る候補数の期待値: 61.60861056751469\n", | |
" 4位 ネンドール 1手目終了後に残る候補数の期待値: 63.616438356164366\n", | |
" 5位 ランクルス 1手目終了後に残る候補数の期待値: 65.03326810176124\n", | |
" 6位 デスカーン 1手目終了後に残る候補数の期待値: 68.30528375733851\n", | |
" 7位 デスバーン 1手目終了後に残る候補数の期待値: 71.10371819960858\n", | |
" 8位 エルフーン 1手目終了後に残る候補数の期待値: 71.14285714285711\n", | |
" 9位 グラードン 1手目終了後に残る候補数の期待値: 71.9060665362035\n", | |
" 10位 ハンテール 1手目終了後に残る候補数の期待値: 72.64579256360075\n", | |
"838位 エネコ 1手目終了後に残る候補数の期待値: 389.3639921722114\n", | |
"839位 パウワウ 1手目終了後に残る候補数の期待値: 390.7221135029356\n", | |
"840位 ゴニョニョ 1手目終了後に残る候補数の期待値: 404.324853228963\n", | |
"841位 ベベノム 1手目終了後に残る候補数の期待値: 404.5733855185911\n", | |
"842位 ブビィ 1手目終了後に残る候補数の期待値: 408.0841487279845\n", | |
"843位 モノズ 1手目終了後に残る候補数の期待値: 414.9726027397261\n", | |
"844位 モココ 1手目終了後に残る候補数の期待値: 420.54990215264195\n", | |
"845位 ミネズミ 1手目終了後に残る候補数の期待値: 423.857142857143\n", | |
"846位 ツボツボ 1手目終了後に残る候補数の期待値: 453.23874755381615\n", | |
"847位 ピィ 1手目終了後に残る候補数の期待値: 470.28767123287673\n", | |
"----- STOP 0.04 -----\n" | |
] | |
} | |
], | |
"source": [ | |
"import collections\n", | |
"import time\n", | |
"\n", | |
"class StopWatch:\n", | |
" def __init__(self):\n", | |
" print('----- START -----')\n", | |
" self.time0 = time.time()\n", | |
" self.last = self.time0\n", | |
" def lap(self):\n", | |
" current = time.time()\n", | |
" lap = current - self.last\n", | |
" print(f'----- LAP {lap:.2f} -----')\n", | |
" self.last = current\n", | |
" def stop(self):\n", | |
" duration = time.time() - self.time0\n", | |
" print(f'----- STOP {duration:.2f} -----')\n", | |
"\n", | |
"sw = StopWatch()\n", | |
"kitaichis = {}\n", | |
"n_pokemons_kouho = float(len(pokemons_kouho))\n", | |
"for pokemon_input, result in results.items():\n", | |
" kitaichi = 0.0\n", | |
" for gamen, kouho in result.items():\n", | |
" if gamen == '緑緑緑緑緑':\n", | |
" continue\n", | |
" count = len(kouho)\n", | |
" kitaichi += float(count * count) / n_pokemons_kouho\n", | |
" kitaichis[pokemon_input] = kitaichi\n", | |
"kitaichis = sorted(kitaichis.items(), key=lambda x:x[1])\n", | |
"print('◆ 1手目終了後に残る候補数の期待値')\n", | |
"for i, (k, v) in enumerate(kitaichis):\n", | |
" if (i + 1 < 11) or (i + 1 > 837): \n", | |
" print(f'{(i+1):>3}位', f'{k: <5}', ' 1手目終了後に残る候補数の期待値:', v)\n", | |
"sw.stop()" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": null, | |
"metadata": { | |
"scrolled": false | |
}, | |
"outputs": [], | |
"source": [ | |
"def check_drop(kitaichis_kijun, kitaichi, top_k):\n", | |
" if len(kitaichis_kijun) < top_k:\n", | |
" return False\n", | |
" elif kitaichi > kitaichis_kijun[-1]:\n", | |
" return True\n", | |
" return False\n", | |
"\n", | |
"top_k = 5\n", | |
"sw = StopWatch()\n", | |
"kitaichis_kijun = []\n", | |
"kitaichis = {}\n", | |
"for pokemon_input1, result1 in results.items():\n", | |
" kitaichi = 0.0\n", | |
" for gamen1, kouho1 in result1.items():\n", | |
" drop1 = check_drop(kitaichis_kijun, kitaichi, top_k)\n", | |
" if drop1:\n", | |
" break\n", | |
" if gamen1 == '緑緑緑緑緑': # 1手目終了\n", | |
" continue\n", | |
" count1 = len(kouho1)\n", | |
" prob1 = float(count1) / n_pokemons_kouho # pokemon_input で gamen を引く確率\n", | |
"\n", | |
" kitaichi_min = 1000\n", | |
" pokemon_input2_kitaichi_min = None\n", | |
" for pokemon_input2 in pokemons:\n", | |
" kitaichi_ = 0.0\n", | |
" result2 = results[pokemon_input2]\n", | |
" for gamen2_, kouho2_ in result2.items():\n", | |
" drop2 = False\n", | |
" if (kitaichi_min != 1000) and (kitaichi_min < kitaichi_):\n", | |
" drop2 = True\n", | |
" break\n", | |
" kouho2 = kouho1 & kouho2_\n", | |
" if len(kouho2) == 0:\n", | |
" continue\n", | |
" if gamen2_ == '緑緑緑緑緑': # 2手目終了\n", | |
" continue\n", | |
" count2_ = len(kouho2)\n", | |
" prob2_ = float(count2_) / count1\n", | |
"\n", | |
" kitaichi_min_ = 1000\n", | |
" pokemon_input_kitaichi_min_ = None\n", | |
" for pokemon_input3 in pokemons:\n", | |
" kitaichi__ = 0.0\n", | |
" result3 = results[pokemon_input3]\n", | |
" for gamen3_, kouho3_ in result3.items():\n", | |
" drop3 = False\n", | |
" if (kitaichi_min_ != 1000) and (kitaichi_min_ < kitaichi__):\n", | |
" drop3 = True\n", | |
" break\n", | |
" kouho3 = kouho2 & kouho3_\n", | |
" if len(kouho3) == 0:\n", | |
" continue\n", | |
" if gamen3_ == '緑緑緑緑緑': # 3手目終了\n", | |
" continue\n", | |
" count3_ = len(kouho3)\n", | |
" prob3_ = float(count3_) / count2_\n", | |
" kitaichi__ += prob3_ * float(count3_)\n", | |
" if drop3:\n", | |
" continue\n", | |
" if kitaichi__ < kitaichi_min_:\n", | |
" kitaichi_min_ = kitaichi__\n", | |
" pokemon_input_kitaichi_min_ = pokemon_input3\n", | |
"\n", | |
" kitaichi_ += prob2_ * kitaichi_min_\n", | |
" if drop2:\n", | |
" continue\n", | |
" if kitaichi_ < kitaichi_min:\n", | |
" kitaichi_min = kitaichi_\n", | |
" pokemon_input_kitaichi_min = pokemon_input2\n", | |
"\n", | |
" kitaichi += prob1 * kitaichi_min\n", | |
"\n", | |
" if drop1:\n", | |
" print(pokemon_input1, ' --> drop')\n", | |
" sw.lap()\n", | |
" continue\n", | |
" kitaichis[pokemon_input1] = kitaichi\n", | |
" print(pokemon_input1, kitaichi)\n", | |
" sw.lap()\n", | |
" if (len(kitaichis_kijun) < top_k) or (kitaichi < kitaichis_kijun[-1]):\n", | |
" kitaichis_kijun.append(kitaichi)\n", | |
" kitaichis_kijun = sorted(kitaichis_kijun)[:top_k]\n", | |
"\n", | |
"kitaichis = sorted(kitaichis.items(), key=lambda x:x[1])\n", | |
"print('◆ 3手目終了後に残る候補数の期待値 (2, 3手目は終了後の候補数の期待値が最小になる手を選択)')\n", | |
"for i, (k, v) in enumerate(kitaichis):\n", | |
" if (i + 1 < 21): \n", | |
" print(f'{(i+1):>3}位', f'{k: <5}', ' 3手目終了後に残る候補数の期待値:', v)\n", | |
"sw.stop()" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.6.8" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
残る候補のパターン(1匹の場合を除く)。
import collections
def hash_kouho(kouho):
return ','.join(sorted(list(kouho)))
d_kouho = collections.defaultdict(set)
li_kouho = []
for pokemon_input, result in results.items():
for gamen, kouho in result.items():
if len(kouho) == 1:
continue
hash_ = hash_kouho(kouho)
li_kouho.append(hash_)
d_kouho[hash_].add(pokemon_input + ' --> ' + gamen)
c = collections.Counter(li_kouho)
for v in c.most_common()[:10]:
print(v)
('デスカーン,デスバーン', 15)
('ニドリーナ,ニドリーノ', 15)
('グライガー,ブラッキー', 11)
('ラティアス,ラティオス', 11)
('サメハダー,ミツハニー', 10)
('スカタンク,ミルタンク', 10)
('アイアント,ウインディ,コイキング,ダイケンキ', 10)
('カイリキー,カイリュー', 10)
('バオッキー,バタフリー,バチンキー', 10)
('ストライク,ボスゴドラ', 10)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
最後が20位までプリントされるようになっているが合っていることが保証されるのは上位5位までなのでこれはミスである。