マスターマインド象とは解答桁を6桁として数値を1から9までにしています(勝手に命名)
前回の記事で一度対象外とした数値を再度計算しないためのデータを
リスト型から集合型にすると爆速になったと紹介しました
1000回検証してみると前回の速度は
total_time 86.84秒
今回さらに高速化させた手順をご紹介します
このゲームでHIT(数値と場所が一致)がないときは
その推測した各数値は、その場所にないことが確定します
これを各桁の判断材料に追加すると、さらに無駄が減ります
total_time 15.03秒
推測の数値作成ルーチンは小さいものから作っていて
過去の推測とヒントから、矛盾のないものから答えてます
なので前に推測した値より小さい値が解答にはなりません
対象外とした数値をデータに残す必要もなくなり
さらにとんでもなくなるんじゃないか?
ワクワクして試します
total_time 14.18秒
そんなに早くならない...
よくあることです
最後に記念撮影
サーバー側
クライアント側
実行結果
平均解答回数を最後に追加
関連記事
Python 60行ほどでゲームサーバとクライアントを作る
Python リスト型から集合型にすると暴走かと思うぐらい速くなった話
CodinGame Wordleでアルゴリズムを作っていく過程を小公開
テキスト版 うーんインデントがくずれる
サーバ側
import subprocess
import random
import time
# master mind server
def make_q(s): # 答え 数値6桁 1から9まで
if len(s)==6:return s
ns=list("123456789")
random.shuffle(ns)
for n in ns:
if n not in s:return make_q(s+n)
# クライアントを起動する
p = subprocess.Popen(['python3', 'mind.py'],\
stdin=subprocess.PIPE, stdout=subprocess.PIPE, universal_newlines=True)
def game(): # 正解までのターンを返す
p.stdin.write("-1 -1" + '\n') # ゲーム開始情報送信
p.stdin.flush()
print("Q",question)
turn = 0
while True:
turn+=1
answer = p.stdout.readline().strip() # クライアントからの解答を受け取る
if len(answer)!=6:return -1 # ザルチェック
# ヒント作成してクライアントに送信する
hit,brow=0,0
for n1,n2 in zip(question,answer):
if n1==n2:hit+=1
elif n2 in question:brow+=1
hint=str(hit)+" "+str(brow)
print(answer,hint)
p.stdin.write(hint + '\n') # 送信
p.stdin.flush()
if hit==6:return turn # 正解時 解答回数を戻す
times=[];score=0
for i in range(1000):
st=time.time() # 時間計測
question=make_q("") # 問題作成
score+=game() # ゲームを行い、解答回数を加算
times+=[(time.time()-st,question)]
times.sort()
print("total_time",sum(t for t,q in times),"avg_score",score/1000)
クライアント側
import sys
guess_s=[];hint_s=[];use_num="";answer="";length=6 # 全解答、全ヒント、使用数値…
line_not_num=[[],[],[],[],[],[]];last_guess="000000" # 列ごとに使用できない数値
def get_guess(s): # 解答作成
global answer # 解答数値
if answer=="": # 解答数値が確定していない時
if len(s)==length: # 列数がそろった
if check(s): answer=s # 過去とそごがないとき解答
else:
last_guess_line=last_guess[:len(s)+1] # 切り捨て用
for c in use_num:
if c in line_not_num[len(s)]:continue # その列には使用できない
# まだ列に使っていない数値で過去探索の行っていない状態の時 次の列へ
if c not in s and last_guess_line<=s+c:get_guess(s+c)
def check(check_s):
for s,hint in zip(guess_s,hint_s): # 過去との突き合わせ
check_hit=check_blow=0
for c,cc in zip(s,check_s):
if c==cc:check_hit+=1
elif c in check_s:check_blow+=1
if hint!=(check_hit,check_blow):return False # 過去の突き合わせと矛盾
return True
def a_game():
global answer,guess_s,hint_s,use_num,line_not_num,last_guess
line_not_num=[[],[],[],[],[],[]];last_guess="000000"
guess="";guess_s=[];hint_s=[];use_num="123456789"
while True:
try: h,b =[int(i) for i in input().split()] # ヒント受信
except: sys.exit() # サーバー側の終了
if h+b==6:use_num="".join(sorted(list(guess))) # 全ての必要な数値が決定
if h==0: # その列にその数値はない
for i,n in enumerate(guess):
line_not_num[i]+=[n]
if h!=-1: # 初回以外は推測、ヒント追加
guess_s+=[guess]
hint_s+=[(h,b)]
if h==6:break # 正解
answer="" # 解答作成
get_guess("")
guess=answer
last_guess=guess
print(guess) # 解答送信
while True: a_game()