jyanjayakaの日記

はやめのリリース、しょっちゅうリリース

Numeronアルゴリズムのpythonソースコード

ここで議論したNumeronアルゴリズム(戦術T2')をpythonで実装した。
一行一行注釈を付けていく。*1*2


main.py

# -*- coding: utf-8 -*-
N = 3 #ゲームで扱う桁数

import functions

P = []
f = []
c = [[]]

a = [7,1,9]

#setup
functions.Generate_P(P)
functions.Generate_P0(P)
print 'possible = ', functions.Calc_P_size(P)
print ''

count = 0
while True:
    functions.Make_call(P, c)
    count += 1
    print 'c = ', c[0]

    functions.Make_feedback(f, c[0], a)
    print 'feedback = ', f

    if f[1] == 3:
        print 'answer is ...', c[0]
        print 'try = ', count
        break
    else:
        functions.Generate_next(P,f)
        f = []
        print 'possible = ', functions.Calc_P_size(P)
        print ''



functions.py

# -*- coding: utf-8 -*-
N = 3

#推測値cと正解値aを比べてfeedback fを作成する
def Make_feedback(f, c, a):
    f.append(c)
    f.append(Eat(c,a))
    f.append(Bite(c,a))

#Pから推測値を抽出する
#Pの最初の数を推測値とする
#推測値はcに格納する
def Make_call(P, c):
    for i in range(10 ** N):
        if P[2 * i] == True:
            c[0] = P[2 * i + 1]
            break
        else:
            pass

def Generate_next(P, f):
    for i in range(10 ** N):
        if P[2 * i] == True: #signがTrueの場合のみ考えれば良い。Falseならそれ以上触れる必要がない。
            P[2 * i] = Sign(P[2 * i + 1], f)
        if P[2 * i] == False:
            pass

#P0を生成する
def Generate_P0(P):
    for i in range(10 ** N):
        if Judge(P[2 * i + 1]) == True:
            pass
        if Judge(P[2 * i + 1]) == False:
            P[2 * i] = False

#numがゲームルールに適合しているか判定する
def Judge(num):
    for i in range(N):
      for j in range(N):
        if i != j and num[i] == num[j]: #桁は異なるのに数字は一致する=重複あり
          return False
        else:
          pass
    return True

#Pを生成する
def Generate_P(P):
    num = []
    for i in range(10 ** N):
        P.append(True)
        Convert_int_to_num(num,i)
        P.append(num)
        num = [] #初期化

#integer intを各桁毎に分解してデータ型numへ変換する
def Convert_int_to_num(num, int):
    for i in range(N):
        num.append(int % 10)
        int /= 10
    num.reverse()

#|P|を計算をする
#|P|を返す
def Calc_P_size(set_num):
    count = 0
    for i in range(10 ** N):
        if set_num[2 * i] == True:
            count += 1
        else:
            pass
    P_size = count
    return P_size

#num gの feedback fに対するsign sを計算する
#num gがfeedback fに適合していればTrue, 適合していなければFalseを返す
def Sign(num_sbj, feedback):
    if Eat(num_sbj, feedback[0]) == feedback[1] and Bite(num_sbj, feedback[0]) == feedback[2]:
        s = True
    else:
        s = False
    return s

#num gがnum cに対して返すeatを計算する
#eatは桁数も数字も合っているものの数
def Eat(num_sbj, num_src):
    count = 0 #初期化
    for i in range(N):
        if num_sbj[i] == num_src[i]:
            count += 1
        else:
            pass
    eat = count
    return eat

#num gがnum cに対して返すbiteを計算する
#biteは数字はあっているが桁数が異なるものの数
def Bite(num_sbj, num_src):
    count = 0
    for i in range(N):
        for j in range(N):
            if j != i and num_sbj[j] == num_src[i]: #桁数が一緒の時はたとえ数字が一致してもカウントしない
                count += 1
            else:
                pass
    bite = count
    return bite



実行結果

possible =  720

c =  [0, 1, 2]
feedback =  [[0, 1, 2], 1, 0]
possible =  126

c =  [0, 3, 4]
feedback =  [[0, 3, 4], 0, 0]
possible =  40

c =  [5, 1, 6]
feedback =  [[5, 1, 6], 1, 0]
possible =  9

c =  [5, 7, 2]
feedback =  [[5, 7, 2], 0, 1]
possible =  4

c =  [7, 1, 8]
feedback =  [[7, 1, 8], 2, 0]
possible =  1

c =  [7, 1, 9]
feedback =  [[7, 1, 9], 3, 0]
answer is ... [7, 1, 9]
try =  6



main.pyについての注釈

  • ソースコードを意味の単位で記述したいので関数を多用する。
  • メインのコードをmain.pyとし、関数定義を集めたものをfunctions.pyとする。
  • オブジェクト指向プログラミング(OOP)は一切使っていない。そのため完全に意味の単位で記述できていない。


# -*- coding: utf-8 -*-

pythonが日本語と相性が悪いので、最初にこう書いておくと良いおまじない。これ無しだとコメントすら日本語で書けない。

N = 3

Nは桁数を表す。Numeronでは3桁の数を用いているが、別に4桁でも構わない。ソースコードは一般的にN桁の数当てゲームのアルゴリズムとなっている。4桁の数当てがやりたいならN=4とすればよい。

P = []
f = []
c = [[]]

ここでの記法に従う。ソースコードで数学のように簡潔な記号法を使う問題点はコードの視認性の低下である。コードの視認性を高めるためには、変数の名前を一目見て内容が分かるようなものにするのが望ましい。ただ今回はここの議論を前提とするので、あえて数学的な記号法を用いている。本来は、例えばPはPossible、fはfeedbackとか省略しない方が良いのかもしれない。

a = [7,1,9]

正解数を719と設定する。
正解数を設定し直す度にコードを書き直すのは面倒だし、コードを変更すること自体望ましくないように思える。
コンソールから正解数を取得するようなプログラムを書くことも出来るが、(面倒なので)やめておいた。このプログラムにUI等の完成度は求めない。

while True:

数を当てるまで推測をし続けるので、ループを設定する必要がある。
ループの回数は不明なのでwhileを使う。無限ループで、答えが見つかったらループを抜ける。

if f[1] == 3:

fの構造上、f[1]にはeat数が保管されている。
それが3であるということは、推測と答えが一致したことを意味する。
なのでここでbreakによりループを抜ける。

functions.pyについての注釈

  • どんな関数を定義するかはセンスの問題。
  • なるべく意味の単位で関数化したつもり。
  • ここで定義したデータ構造が、いかにアルゴリズムに影響を与えるかが良く分かる

*1:ソースコードはpython2系での記述。

*2:ソースコードにはコメントが入っていたが後で注釈を付けるので省いた。

文章の書き方

解説しようとして変にアレンジせずに、自分が理解している通りに書く。着飾らずに、コアをそのまま書く。

オブジェクト指向プログラミングとは何か

プログラムとはそもそも何か。*1

 

プログラムとは、何らかの方法で保管されたデータを、何らかの方法で操作・加工することである

 

a→b→c→...→x

 

入力したaというデータを加工していって、最終的にxというデータを得る。aからxを得るのがプログラムの目的である。*2

 

オブジェクト指向プログラミング(OOP)以前のプログラマは、二つの指揮を同時に行なっていた:

  1. データ加工i→jが具体的にどんなプロセスで行われるべきか
  2. aからxに到るまでのデータ加工の工程がどうあるべきか

厄介なのは1と2は相互作用していることだ。データ構造や加工の方法を変更すると、それが工程にも影響を与えるし、逆もまた然りである。

二つの変数があると問題は難しくなる。そこでよく採られる常套手段は、どちらか一方を固定するというものである。それがOOPのアイデアに他ならない。

 

OOP以後のプログラマは、二つの指揮を個別に行えばよくなった:

  1. オブジェクトの中身の設計
  2. オブジェクト間の情報の流れの制御

要はプログラムをオブジェクトの内と外に分けて、困難を分割したのである。このオブジェクトの内と外に分けるというのが、カプセル化という概念が表している意味である。

2の作業、つまりデータの流れ (stream) の制御を行なっているとき、プログラマは1について知る必要がない。知るべきなのは単にiというデータがjに加工されるという事実のみである。具体的にどうやってi→jが実現されるのかは(2の作業中は)どうでもよい。このことを指して、オブジェクトはブラックボックスなどと言われたりもする。つまりオブジェクトがブラックボックになって、中身が見えなくなってしまっても一向に構わないということだ。

オブジェクトがカプセル化され、中身が見えなくなったことによって、プログラマは2の作業に専念出来る。また、他人が作ったオブジェクトの中身をわざわざ理解しなくても、「iを入れたらjが出る」という情報(これをインターフェースと呼ぶ*3)が分かってさえいればそれが使える。こうしてプログラムの再利用も容易になる。

 

また逆に1の作業中は2を気にする必要はない。オブジェクトが持つべきインターフェース(=iを入れたらjが出る)さえ実現すれば、どんな設計をしても良い。*4*5

これらの利点はすべてコードをオブジェクトの内と外に分けるというカプセル化の概念から出てきた。したがって次が言える:

 

オブジェクト指向プログラミングの本質はカプセル化にある*6

 

OOPは上で述べたようなものだが、そこではクラスベースとか継承や多様性といった概念は登場してこなかった。なぜならクラスベースや継承や多様性といった概念はOOPの本質ではないからである。それは単にOOPをより効率的に実現するためのテクニックでしかない。しかしそれはあまりに便利であるから、OOPを行うときには必ずといって良いほど紹介される。だが、何度も繰り返すがそれはOOPの本質ではない。

 

最後に

残念ながらOOPの本質を理解しても、OOPが出来るようになるわけではない。OOPを実際に行うためには、用いる言語でOOPを行うための仕様を理解し、それを覚えて使えるようにしなければならない。それにクラスベースや継承、多様性といった概念も身につける必要がある。そのためには練習 (practice)あるのみだ。ただ練習する上でOOPのアイデアを理解しておくのはとても有用であるのは間違いない。

*1:以下では特定の言語に依らない説明を心がける。言語を決めてしまうと、その言語仕様に気が取られたり、そもそもその言語を知らないといったことが足かせになってしまう。オブジェクト指向プログラミング (OOP) はプログラム記述方法のアイデアであり、その記述方法で具体的にプログラムを書くときにやっと言語が問題になってくる。OOPの本質的アイデア自体は特定の言語を設定しなくても語れるし、そうするべきだとも思う。

*2:もちろん実際のプログラムはこのような単純な一本道とは限らない。入力がたくさんあったり、道が分岐したり、ループしたりするだろう。ただ一本道としても議論の本質は失われない。

*3:元々インターフェースというのは外界とのやりとりを司る部分という意味である。別の言い方をすれば「上っ面」だ。OOPでは物事の上っ面だけみればよいから楽なのだ。

*4:もちろん効率の良い設計が望ましいだろうが。

*5:ただもちろんその肝心のインターフェースがどんなものか知るためには、2についての理解が必要にはなるだろう。しかしそれでも1が2に影響することはない。これが肝心であり、カプセル化の利点である。

*6:カプセル化という言葉には別の使い方もあるようなので、ここでの使い方と混同しないように。

戦術T2'の実装を通じて学んだこと

プログラミング初心者が学んだこと

 

1.プログラミングの心得

まずこの本のすごさを改めて実感した。

 

 

プログラムを作る上でのモノの見方を教えてくれる。個々の技術的アドバイスよりも、こういった考え方それ自身を教えてくれる本は貴重である。

  1. 手を付けられる部分から初める。あるいは、手を付けられるよう問題を変形して小さくする。
  2. 知識は必要になった時に学べば良い

 

2.名前の重要性

変数や関数に付ける名前は、非常に重要。一目見て分かるようになるべく情報量が多く、なおかつ簡潔な名前にするとよい。良い名前の付け方については

 

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

 

 

3.データ構造とオブジェクトの重要性

データ構造が決まるとアルゴリズムが自ずと定まるというのは、大きな発見だった。

戦術T2'の実装

前回からの続き。

 

戦術T2'の実装

 

ソースコードの良い構造とは

コードはなるべく意味の単位で分割されていることが望ましい。そのためには関数を適宜定義したりするのも良いが、最も効果的なのはオブジェクトを用いる方法である。今回はまずオブジェクトを用いないでプログラミングをして、そこから逆にオブジェクトの有用性を考察する。

 

データ構造

アルゴリズムを決定する上で、データ構造が重要となる。実際、データ構造を決定するとアルゴリズムは自ずと定まる場合が多い。逆に言うとデータ構造について十分な考察をしないまま始めて、後々データ構造を変更するということになると、アルゴリズムの大部分を書き換える必要が出て来る。なのでデータ構造は予め決めておきたいところだが、難しいのはある程度アルゴリズムが決まらないとデータ構造の良し悪しが判断できないという点である。実は、この点もオブジェクトを用いれば解決できる。

 

戦術T2'はciをPiの最小数として決定する。Piのデータ構造が決まっていれば、Piの最小数を探す方法=アルゴリズムは自ずと定まってくる。それではPiのデータ構造はどうやって定めるのが良いだろうか。そのためにはPiが他にどんな操作を加えられるのか見てみるのが良い。

PiはP(i-1)からフィードバックf(i-1)によって生成される。*1要はP(i-1)の中でf(i-1)に適合する数だけを集めたのがPiである。

こういう扱われ方をするPiのデータ構造には色々な方法があるだろうが、ここでは次のようにデータ構造setを定める:

 

[[sign], num, [sign], num, [sign], num, ..., [sign], num]

 

ただしここでsignはbool型でnumは配列である。

setがどのようにしてPiを表すのか説明する。i番目のnumは自然数iを各桁毎に格納した配列である。i番目のsignはi番目のnumがPiに含まれている場合はTrueで含まれない場合はFlaseである。

 

P1はsetによって次のように表現される:

[[False], [0,0,0], [False], [0,0,1], ..., [True], [0,1,2], ..., [False], [9,9,9]]

 

データ構造setが集合Piを表す最善のものと言うつもりは全く無い。ただ採用するデータ構造がいかにアルゴリズムに影響するかを見るためには丁度よい。

*1:数学ではこのような動的な記述は嫌われるかもしれない。ただ今は具体的な手順を考察する立場なので、このような動的な記述のほうが役に立つ。

Numeron(数当てゲーム)最強アルゴリズム

ゲームの分析

ゲームの分析を通して、適切な用語や記号を導入する。

 

ゲームのルール

Numeronというゲームについての説明はここ。ゲームのルールは次の通り:*1

  • それぞれのプレイヤーが、0-9までの数字が書かれた10枚のカードのうち3枚を使って、3桁の番号を作成する。カードに重複は無いので「550」「377」といった同じ数字を2つ以上使用した番号は作れない。
  • 先攻のプレイヤーは相手の番号を推理してコールする。相手はコールされた番号と自分の番号を見比べ、コールされた番号がどの程度合っているかを発表する。数字と桁が合っていた場合は「EAT」(イート)、数字は合っているが桁は合っていない場合は「BITE」(バイト)となる。例として相手の番号が「765」・コールされた番号が「746」であった場合は、3桁のうち「7」は桁の位置が合致しているためEAT、「6」は数字自体は合っているが桁の位置が違うためBITE。EATが1つ・BITEが1つなので、「1EAT-1BITE」となる。
  • これを先攻・後攻が繰り返して行い、先に相手の番号を完全に当てきった(3桁なら3EATを相手に発表させた)プレイヤーの勝利となる。

簡単にいえば、このゲームは「数当てゲーム」である。

相手の数を推測し、そのフィードバックを得る。そしてその情報を元に新しい推測を行う。それまでに得た情報からより良い推測を行うことが鍵となる。

 

ゲームの流れ

ゲームの流れを簡潔に述べ、同時に幾つか用語を定義しておく。

  1. 二人のプレイヤーが自分の数を設定する
  2. 先攻後攻を決める
  3. 先攻のプレイヤーが相手の数を推測し発表する
  4. 先攻のプレイヤーは相手プレイヤーから推測に対するフィードバックを得る
  5. 後攻のプレイヤーが相手の数を推測し発表する
  6. 後攻のプレイヤーは相手プレイヤーから推測に対するフィードバックを得る
  7. 3へ戻る
  8. 最初に相手プレイヤーの数を当てたプレイヤーが勝者となる

 

定義1

  • ゲームをプレイする二人をp1, p2とする。p1が先攻、p2が後攻とする。
  • p1, p2が設定した自身の数をa1, a2とする。
  • プレイヤーが相手プレイヤーの数を推測し発表することをコール (call) と呼ぶ。また、piのj回目のコールで発表された数をcijと表す。
  • cijに対して得られるフィードバックをfijと表す。fijはcijとEAT, BITEの数の組みとして表す。fij = (cij, eij, bij).

 

 

ゲーム攻略の本質

このゲームに勝利する上で本質的重要性を持つのは、それまでに与えられた相手の数についての情報(それは自分がコールした数とそれに対するEATとBITEの数として与えられる)から、次にどんな推測を行うのか、その戦略である

上で定義した用語を用いると次のような問いを考えることになる:piにとってcijをそれまでに得たフィードバックの系列fi1, fi2, fi3,...,fi(j-1)からどのように定めるのが最善か。*2

 

定義2

任意のフィードバックの系列fi1, fi2, fi3,...,fi(j-1)に対して数cを対応させる写像のことをpiの戦術と呼ぶ。

 

戦術の優劣は相手の数に到達するまでのコール数の期待値で決まる。

理論的に最善の戦術を求めるのも面白そうだが、ここでは(最善とは限らない)簡単な戦術を考え、それをアルゴリズム化してpythonによって実装することを目標とする。*3

 

ゲームの簡略化

アルゴリズムを考える上で、議論を簡単にするため、ゲームを簡略化する。プレイヤーは一人(コンピュータ)であり、彼が答えの数を推測してゆくというゲームにする。このゲームの流れは次のようになる:

  1. 答えの数が決定される
  2. プレイヤーが数を推測する
  3. プレイヤーは推測に対するフィードバックを得る
  4. プレイヤーが数を推測する
  5. 答えの数が当たるまで続ける

 

定義3

  • この簡略化したゲームを1人数当てゲームと呼ぶ
  • 答えの数をaで表す
  • ゲームのプレイヤーをpで表す
  • プレイヤーがi回目のコールで発表する数をciで表す
  • ciに対して与えられるフィードバックをfiと表す。
  • ciに対して与えられるEAT, BITEの数をそれぞれei, biと表す。よってfi = (ci, ei, bi)
  • 任意のフィードバックの系列f1, f2, f3, ..., f(i-1)に対してciを対応させる写像をプレイヤーの戦術と呼び、Tで表す

 

次の問題を提起する:プレイヤーpにとって最善の戦術とは何か

ただしここでは冒頭で述べたように、この問題の解決を目指すのではなく、適当な(実装のし易い)戦術を考え、それをpythonによって実装することを目標とする。

 

道具立て

適当な戦術を考えるために便利な概念を定義する。

 

定義4

プレイヤーpがi回目のコール行う前に、答えの数として可能性のある数全体をPiと表す。

 

Piはフィードバックの系列f1, f2, f3, ..., f(i-1)によって定まるから、厳密にPiを書けばP(f1, f2, f3, ..., f(i-1))である。

 

P1は0~999までの自然数の集合と一致しない。実際、例えば000はルール上除外されるから、P1には含まれない。要はP1は0~999の数の中でルール上許される数の全体である。*4プレイヤーは最初のコールをする前であっても、答えの数についての情報「答えの数はゲームのルールに従う」を持っているわけである。

 

ゲームの流れに沿って、Pは(大抵の場合)小さくなる。P1から1回目のコールを行うことで答えの数の可能性は絞られるから  P_1 \supset P_2となる。同様に考えれば

 

 P_1 \supset P_2 \supset \dots \supset P_{i} \supset \dots

 

が成立していることが分かる。

 

幾つかの戦術

T0

最も単純な戦術はP1から予め一つ数cを選んで、常にそれをコールをし続けるものである。つまりc = c1 = c2 = ... これをT0と呼ぶ。T0は明らかに最も弱い戦術である。もしコールする数として選ぶ数が正解でなければ、永遠に答えに達することがない。T0のような戦術は理論的には考察の対象となるかもしれない(実際それはこのゲームが終了しないことがあるという一番簡単な例となっている)が、今の考察の立場からすると、考えるに値しない戦術である。

 

T1

次に考えられるのはT0を少し改善して、ciをP1からランダムに決定する戦術である。これをT1と呼ぶ。T1は明らかに弱い戦術である。実際T1はそれまでに与えられているフィードバックを全く考慮しない。与えられている情報を活用出来ていない。

 

T2

T1を改良して、ciをPiからランダムに決定する戦術をT2と呼ぶ。ここまで来ると、ある程度フィードバックの情報を活かしていると言える。しかしT2が最善の戦略と言えるかどうかはかなり疑問である。実際次のような点は考慮に値する:

  • ciをPiからランダムに決定するよりも、良い決定方法があるのではないか? 例えばPiの各要素に対して得られるP(i+1)の大きさの期待値を計算し、それが最小になるようなciを選ぶとか。
  • ciをそもそもPiから選ぶ必要もない。Piに含まれていなければ確かに答えとしてあり得ないが、可能性を絞る上ではPiのどの要素より優れているということはあり得る。

 

T2'

T2の亜種として、ciをPiの一番小さな数として決定する戦術T2'を考える。*5

T2やT2'には上で述べたような疑問点はあるにせよ、今回はT2'を実装することを目標とする。

*1:他にも追加ルールが存在するが、今回は無視する。そうしてもゲームの面白さは変わらないと思える。

*2:問題を分析し、適当な記号と用語を導入し、議論を整理する。これだけで非常に大きく前進したことになる。最初から適切な記号や用語を導入したり、問題の過不足ない分析ができるわけではない。まずとにかく分析を始めてみる。そうすると少しずつ議論でネックになる部分が分かってくる。それはよく出てくる単語や概念だったりする。次にそれに名前や記号をつける。すると議論の見通しがよくなり、少し遠くまで見通せるようになる。そしてまたネックが分かってきて...というように進んでゆく。最初から完璧にやろうと思わないことだ。地道に地盤を固めてゆくしかない。

*3:この問題を考え始めたのは数学的な動機からではなく、プログラミングを練習する上で何か良い題材がないか探していたから。

*4:|P1| = 720である。

*5:ランダムに決定するプログラムを実装するのが面倒だった。

基本のUIを作る

基本のUIを作る

ご飯記録アプリの簡単なUIを作りながらXcodeに慣れ親しもう。

 

学習目標

  • Xcodeでプロジェクトを作成出来る
  • Xcodeプロジェクトテンプレートとともに作成されるキーファイルの目的を理解する
  • プロジェクト内のファイルを開いたり切り替えたり出来る
  • iOSシミュレーターでアプリを起動できる
  • ストーリーボードでUI要素を追加、移動、リサイズ出来る
  • 属性インスペクターでストーリーボードにおけるUI要素の属性を編集できる
  • アウトラインビューでUI要素を表示したり再加工出来る
  • Assistant editor’s Preview modeを利用してストーリーボードUIをプレヴュー出来る
  • オートレイアウトを使って、アプリ使用者のデバイスサイズに自動的に適応するように、UIをレイアウト出来る。