お気楽 Python3 プログラミング超入門

●多重継承

Python は多重継承をサポートしているので、複数のクラスを継承することができる
単一継承の場合、クラスの階層は木構造になるので、適用可能なメソッドの探索はルートの方向をたどるだけですむ
多重継承の場合、クラスの階層がグラフになるため、適用可能なメソッドに到達する経路が複数存在する可能性がある
このため、複数の経路をうまくまとめてメソッドの適用順序を一意に定める処理が必要になる
Python では、これを「メソッド解決順序 (Method Resolution Order, MRO)」という
MRO のアルゴリズムは Python の言語仕様に定められている
MRO のアルゴリズムは複雑で、初心者には理解するのが難しい
Python の MRO は Common Lisp Object System (CLOS) が参考になる
CLOS は Python と同じく動的で多重継承をサポートしているオブジェクト指向システム
参考文献『LISP 原書第 3 版 (1) (2)』によると、CLOS はたいていの場合、次の 3 つの規則を適用した結果とほぼ同じになるとのこと

左優先則
深さ優先則
合流則

実際に試してみると、この規則は Python にも当てはまるようである
概要を理解するにはこれで十分だと思われる
なお、MRO はクラスメソッド cls.mro() で求めることができる

class Foo(Cls1, Cls2, ..., ClsN): ... と定義した場合、MRO は左から右になる
つまり、Cls1 -> Cls2 -> ... -> ClsN になる

リスト : 左優先則 (test.py)

class A:
    def method(self):
        super().method()
        print("A")

class B:
    def method(self):
        print("B")

class C(A, B):
    def method(self):
        super().method()
        print("C")

print(C.mro())
c = C()
c.method()

C>python test.py
[<class '__main__.C'>, <class '__main__.A'>, <class '__main__.B'>,
 <class 'object'>]
B
A
C

MRO は C -> A -> B になるので、C の super() は A に、A の super() は B になる
したがって、method() の呼び出しも C -> A -> B になるので、表示はその逆の B, A, C になる
A にはスーパークラスが定義されていないので、super().method() はエラーになりそうだが、この場合は正常に動作する
ただし、class C(A): ... と定義すると、実行時に method() が見つからずにエラーとなる

スーパークラスが他のクラスを継承している場合は深さ優先

    Ａ    Ｂ    Ｃ
    │    │    │
    │    │    │
    Ｄ    Ｅ    Ｆ
      ＼  │  ／
        ＼│／
          Ｇ

Ｇ→Ｄ→Ａ→Ｅ→Ｂ→Ｆ→Ｃ

  図 : 深さ優先則

クラス G でスーパークラスが (D, E, F) と設定されているとすると、最初にクラス D のメソッドを探索する
次はスーパークラスの方向を優先で探索するので、クラス E ではなくクラス A を探索する
スーパークラスを優先して探索し、それでも見つからないときはクラス E を探索する
したがって、MRO は G → D → A → E → B → F → C となる

リスト : 深さ優先則 (test.py)

class A:
    def method(self):
        super().method()
        print("A")

class B:
    def method(self):
        print("B")

class C(A):
    def method(self):
        super().method()
        print("C")

class D(B):
    def method(self):
        super().method()
        print("D")

class E(C, D):
    def method(self):
        super().method()
        print("E")

print(E.mro())
e = E()
e.method()

C>python test.py
[<class '__main__.E'>, <class '__main__.C'>, <class '__main__.A'>, 
 <class '__main__.D'>, <class '__main__.B'>, <class 'object'>]
B
D
A
C
E

あるクラスからスーパークラスをたどり、複数の経路で到達できるクラスを「合流点」という

      Ａ
    ／  ＼
  ／      ＼
Ｂ          Ｃ    Ｄ→Ｂ→Ｃ→Ａ  
  ＼      ／
    ＼  ／
      Ｄ

  図 : 合流則

上図の場合、クラス A は D - B - A と D - C - A という 2 つの経路があるので合流点になる
メソッドの探索で合流点にぶつかると、そこで探索を中断して次の経路を探索する
そして、最後の経路で合流点に到達したら、それ以降のスーパークラスを探索する
これを「合流則」という
したがって、上図のクラスの MRO は D → B → C → A となる

リスト : 合流則 (test.py)

class A:
    def method(self):
        print("A")

class B(A):
    def method(self):
        super().method()
        print("B")

class C(A):
    def method(self):
        super().method()
        print("C")

class D(B, C):
    def method(self):
        super().method()
        print("D")

print(D.mro())
d = D()
d.method()

C>python test.py
[<class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>,
 <class '__main__.A'>, <class 'object'>]
A
C
B
D

Mix-in

単一継承の場合、クラスの階層は木構造になるので、クラスの優先順位は簡単にわかる
多重継承はグラフになるので、優先順位を理解するのは難しくなる
多重継承の複雑さを緩和する方法に Mix-in がある
Mix-in はインスタンス変数を継承するクラスをひとつだけに限定する
メソッドだけを実装したクラスを用意し、それはいつくでも継承することができる
Mix-in は多重継承を使いこなすための方法論
Python は多重継承をサポートしているので、Mix-in を使うことができる

                Ａ
              ／
            Ｂ
 Mixin A  ／  ＼    Mixin B
    ＼  ／      ＼  ／
      Ｃ          Ｄ

      図 : Mix-in

クラス C はクラス B を継承していて、そこにクラス Mixin A が Mix-in されている
クラス D もクラス B を継承しているが、Mix-in されているクラスは Mixin B
多重継承にはいろいろな問題点があるが、Mix-in ですべて解決できるわけではない
しかしながら、クラスの階層構造がすっきりとしてわかりやすくなることは間違いないと思われる

Enumerable

Mix-in の例題としてクラス Enumerable を作る
Enumerable はコレクションに高階関数 (メソッド) を Mix-in する
これは Ruby のモジュール (Mix-in 用のクラス) Enumerable を参考にした

表 : Enumerable のメソッド
名前	機能
obj.member(func)	func が真となる要素を返す
obj.position(func)	func が真となる要素の位置を返す
obj.count(func)	func が真となる要素の個数を返す
obj.map(func)	要素に func を適用した結果を返すジェネレータを生成する
obj.filter(func)	func が真となる要素を返すジェネレータを生成する
obj.fold(func, init)	すべての要素を func を用いて結合した結果を返す

リスト  : Mix-in 用のクラス Enumerable
  
class Enumerable:
    # 探索
    def member(self, func):
        for x in self.each():
            if func(x): return x
        return False
 
    # 位置を返す
    def position(self, func):
        n = 0
        for x in self.each():
            if func(x): return n
            n += 1
        return -1
  
    # 個数を数える
    def count(self, func):
        n = 0
        for x in self.each():
            if func(x): n += 1
        return n
  
    # マップ
    def map(self, func):
        for x in self.each(): yield(func(x))
  
    # フィルター
    def filter(self, func):
        for x in self.each():
            if func(x): yield(x) 
  
    # 畳み込み
    def fold(self, func, init):
        a = init
        for x in self.each():
            a = func(a, x)
        return a

Enumerable は Mix-in を前提としているので、インスタンス変数の定義は不要でメソッドだけを定義する
コレクションの要素はジェネレータ each() で取り出す
each() は Mix-in するクラスで定義されているものとする
つまり、each() を定義さえすれば、どんなクラスでも Enumberable を Mix-in することができる
each() の代わりにイテレータを使ってもよい
Mix-in するときは次のように行う

class LinkedList(Enumerable): ...
class FixedList(LinkedList, Enumerable): ...
class MyList(FixedList, Enumeraable) ...

いずれの場合も、Enumerable のメソッドは LinkedList で定義されている each() を呼び出すことで動作する
複数のクラスで共通の操作 (メソッド) を定義したい場合、Mix-in はとても役に立つ

>>> from linkedlist import *
>>> from enumerable import *
>>> class MyList(FixedList, Enumerable):
...     def __init__(self, *args):
...         super().__init__(*args)
...
>>> a = MyList(8, 1, 2, 3, 4, 5, 6, 7, 8)
>>> a
FixedList(8, 1, 2, 3, 4, 5, 6, 7, 8)
>>> a.member(lambda x: x % 2 == 0)
2
>>> a.position(lambda x: x % 2 == 0)
1
>>> a.count(lambda x: x % 2 == 0)
4
>>> list(a.map(lambda x: x * x))
[1, 4, 9, 16, 25, 36, 49, 64]
>>> list(a.filter(lambda x: x % 2 == 0))
[2, 4, 6, 8]
>>> a.fold(lambda x, y: x + y, 0)
36

----- 参考文献 -----
Patrick Henry Winston, Berthold Klaus Paul Horn, 『LISP 原書第 3 版 (1) (2)』, 培風館, 1992

●例外処理

例外 (exception) はエラー処理で使われる機能
エラーが発生したことを「例外が発生した」とか「例外が送出された」ということがある
本稿でもこの用語を使うことにする
Python の場合、例外はクラスとして定義されている
Python3 のすべての例外は、BaseException というクラスを継承している
システム終了以外の例外は Exception を継承している
例外クラスのインスタンスを生成するとき、通常は引数に文字列 (エラーメッセージ) を渡す

実際には 0 個以上の引数を渡すことができる
つまり、引数なしでインスタンスを生成することもできる
引数はインスタンス変数 args に格納される

例外の捕捉

Python は送出された例外を捕捉することができる

リスト : 例外処理

try:
    処理A
    処理B
    処理C
except except_type:
    処理D
    処理E
else:
    処理F

try 文は try: のあとに定義されているブロック (try 節) を実行する
try 節が正常に終了した場合、else 節が定義されていればそれを実行して終了する
例外が発生した場合、try 節の実行は中断される
その例外が except で指定した例外と一致すれば、その except 節を実行する
except 節にはタプルで複数の例外を指定することができる
また、try 文には複数の except 節を指定することができる
最後に例外を指定しない except 節だけを定義すると、どんな例外にでも一致するワイルドカードとして機能する
except 節に Exception を指定すれば、システム終了以外の例外を捕捉することができる

>>> def foo(a, b):
...     try:
...         return a / b
...     except ZeroDivisionError:
...         print('Error {} / {}'.format(a, b))
...         return 0
...
>>> foo(10, 2)
5.0
>>> foo(1, 0)
Error 1 / 0
0
>>> foo(1, '0')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in foo
TypeError: unsupported operand type(s) for /: 'int' and 'str'

foo(1, 0) は 0 で除算しているので例外 ZeroDivisionError が送出される
この例外は except 節に指定されているので、その節が実行されてError 1 / 0 を表示して 0 を返す
それ以外の例外は捕捉されない

例外の送出

例外は raise 文で送出することができる

raise exception

引数 exception には例外のクラス名、または例外クラスのインスタンスを指定する
クラスが指定された場合は引数なしでインスタンスを生成する

>>> raise Exception
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
Exception
>>> raise Exception('Oops')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
Exception: Oops
>>> try:
...     raise Exception('oops', 123)
... except Exception as err:
...     print(err.args)
...     print(err)
...
('oops', 123)
('oops', 123)

例外クラスのインスタンスを受け取るときは except 節の後ろに as 変数を付ける
インスタンスは指定した変数に格納される
ユーザーが独自のエラークラスを定義するときは Exception を継承するとよい

>>> class FooError(Exception): pass
...
>>> raise FooError('oops!')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
__main__.FooError: oops!

例外クラスの名前は最後に Error を付けるのが Python の習慣

finally 節

try 文は excetp 節, else 節の後ろに finally 節を定義することができる

リスト : finally 節

try:
    処理A
    処理B
    処理C
except except_type:
    処理D
    処理E
else:
    処理F
finally:
    処理G

finally 節は try 文の処理を終了するときに実行される
正常終了だけではなく例外が送出されたときにも実行される
このとき、同じ例外が再送出される

>>> try:
...     print('oops')
... finally:
...     print('clean up!!')
...
oops
clean up!!
>>> try:
...     raise Exception('oops')
... finally:
...     print("clean up!!")
...
clean up!!
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
Exception: oops

with 文

finally 節のようなクリーンアップ処理は with 文でも実装できる

with expr as var, expr1 as var1, ...:
    処理
    ...

expr as var を複数続けて記述すると、with 文を入れ子にしたことと同じになる
with 文を使うには次に示す 2 つの特殊メソッドを実装したクラスが必要
これを「コンテキストマネージャ」という

def __enter__(self): ...
def __exit__(self, exc_type, exc_value, traceback): ...

with 文は式 expr を実行してコンテキストマネージャのオブジェクトを生成する
次に、オブジェクトのメソッド __enter__() を実行する
__enter__() の返り値が変数 var にセットされる
通常は自分自身 (self) を返せばよい
with 文の処理が終了するとき、メソッド __exit__() を呼び出す
例外が送出された場合も __exit__() が呼び出される
正常終了した場合、3 つの引数には None が渡される
異常終了した場合、3 つの引数には例外の型、値、トレースバック情報が渡される
返り値が偽の場合、同じ例外が再送出される (真の場合、例外は再送出されない)

リスト : with 文の簡単な使用例

class Foo:
    def __init__(self, a):
        self.a = a
        print("init")

    def __enter__(self):
        print("enter")
        return self

    def __exit__(self, exc_type, exc_value, traceback):
        print("exit")
        print(exc_type)
        print(exc_value)
        print(traceback)
        return True

with Foo(123) as a:
    print(a.a)

with Foo(0) as a:
    raise Exception('oops!', a.a)

C> python3 test.py
init
enter
123
exit
None
None
None
init
enter
exit
<class 'Exception'>
('oops!', 0)
<traceback object at 0x0000023D79F61E88>

●二分木

単純な二分木です。詳しい説明は拙作のページ「Algorithms with Python: 二分木とヒープ」をお読みくださいませ。

リスト : 二分木 (tree.py)

# 節
class Node:
    def __init__(self, item, left = None, right = None):
        self.item = item
        self.left = left
        self.right = right

#
# 操作関数
#

# 探索
def search(node, x):
    while node is not None:
        if node.item == x: return True
        elif x < node.item: node = node.left
        else: node = node.right
    return False 

def search_min(node):
    while node.left is not None: node = node.left
    return node.item

def search_max(node):
    while node.right is not None: node = node.right
    return node.item

# 挿入
def insert(node, x):
    if node is None:
        return Node(x)
    elif x < node.item:
        node.left = insert(node.left, x)
    elif x > node.item:
        node.right = insert(node.right, x)
    return node

# 削除
def delete_min(node):
    if node.left is None: return node.right
    node.left = delete_min(node.left)
    return node

def delete_max(node):
    if node.right is None: return node.left
    node.right = delete_max(node.right)
    return node

def delete(node, x):
    if node is None: return node
    if node.item == x:
        if node.left is None: return node.right
        if node.right is None: return node.left
        node.item = search_min(node.right)
        node.right = delete_min(node.right)
    elif x < node.item:
        node.left = delete(node.left, x)
    else:
        node.right = delete(node.right, x)
    return node

# 巡回
def each(node):
    if node is not None:
        yield from each(node.left)
        yield node.item
        yield from each(node.right)

# 二分木
class Tree:
    def __init__(self):
        self.root = None

    # 挿入
    def insert(self, x):
        self.root = insert(self.root, x)

    # 探索
    def search(self, x):
        return search(self.root, x)

    def max(self):
        if self.root is None: return None
        return search_max(self.root)

    def min(self):
        if self.root is None: return None
        return search_min(self.root)

    # 削除
    def delete(self, x):
        self.root = delete(self.root, x)

    def delete_max(self):
        if self.root is not None: delete_max(self.root)
    
    def delete_min(self):
        if self.root is not None: delete_min(self.root)

    # 巡回
    def each(self): return each(self.root)

    # 空か？
    def is_empty(self): return self.root is None

    # 表示
    def __repr__(self):
        if self.root is None: return 'Tree()'
        s = 'Tree('
        for x in each(self.root):
            s += '{}, '.format(x)
        s = s[:-2]
        s += ')'
        return s

# テスト
if __name__ == '__main__':
    import random
    tree = Tree()
    data = [random.randint(0, 100) for x in range(10)]
    print(data)
    print(tree)
    print(tree.is_empty())
    for x in data: tree.insert(x)
    print(tree)
    print(tree.is_empty())
    print('max =', tree.max())
    print('min =', tree.min())
    print("delete max")
    tree.delete_max()
    print(tree)
    print("delete min")
    tree.delete_min()
    print(tree)
    for x in data:
        print('search', x, tree.search(x))
        print('delete', x)
        tree.delete(x)
        print('search', x, tree.search(x))
        print(tree)

[82, 37, 15, 7, 93, 75, 21, 71, 47, 25]
Tree()
True
Tree(7, 15, 21, 25, 37, 47, 71, 75, 82, 93)
False
max = 93
min = 7
delete max
Tree(7, 15, 21, 25, 37, 47, 71, 75, 82)
delete min
Tree(15, 21, 25, 37, 47, 71, 75, 82)
search 82 True
delete 82
search 82 False
Tree(15, 21, 25, 37, 47, 71, 75)
search 37 True
delete 37
search 37 False
Tree(15, 21, 25, 47, 71, 75)
search 15 True
delete 15
search 15 False
Tree(21, 25, 47, 71, 75)
search 7 False
delete 7
search 7 False
Tree(21, 25, 47, 71, 75)
search 93 False
delete 93
search 93 False
Tree(21, 25, 47, 71, 75)
search 75 True
delete 75
search 75 False
Tree(21, 25, 47, 71)
search 21 True
delete 21
search 21 False
Tree(25, 47, 71)
search 71 True
delete 71
search 71 False
Tree(25, 47)
search 47 True
delete 47
search 47 False
Tree(25)
search 25 True
delete 25
search 25 False
Tree()

●経路の探索

スタートからゴールまでの経路を求めるプログラムです。詳しい説明は拙作のページ「Algorithms with Python: 集合、グラフ、経路の探索」をお読みくださいませ。

     １───３───５ 
   ／│      │
 ０  │      │
   ＼│      │
     ２───４───６

       経路図

リスト : 経路の探索 (keiro.py)

# 隣接リスト
adjacent = ((1, 2),    # 0
            (0, 2, 3), # 1
            (0, 1, 4), # 2
            (1, 4, 5), # 3
            (2, 3, 6), # 4
            (3,),      # 5
            (1,))      # 6

# 深さ優先探索
def depth_first_search(goal, path):
    p = path[-1]
    if p == goal:
        print(path)
    else:
        for x in adjacent[p]:
            if x in path: continue
            path.append(x)
            depth_first_search(goal, path)
            path.pop()

print("----- depth first search -----")
depth_first_search(6, [0])

# 幅優先探索
def breadth_first_search(start, goal):
    que = [[start]]
    while len(que) > 0:
        path = que.pop(0)
        p = path[-1]
        if p == goal:
            print(path)
        else:
            for x in adjacent[p]:
                if x in path: continue
                que.append(path + [x])

print("----- breadth first search -----")
breadth_first_search(0, 6)

# 反復深化
def iterative_deepening_search(start, goal):
    def dfs(goal, path, limit):
        if len(path) == limit:
            if path[-1] == goal: print(path)
        else:
            for x in adjacent[path[-1]]:
                if x in path: continue
                path.append(x)
                dfs(goal, path, limit)
                path.pop()
    for limit in range(1, 7):
        print("-----", limit, "-----")
        dfs(goal, [start], limit)

print("----- iterative deepening search -----")
iterative_deepening_search(0, 6)

----- depth first search -----
[0, 1, 2, 4, 6]
[0, 1, 3, 4, 6]
[0, 2, 1, 3, 4, 6]
[0, 2, 4, 6]
----- breadth first search -----
[0, 2, 4, 6]
[0, 1, 2, 4, 6]
[0, 1, 3, 4, 6]
[0, 2, 1, 3, 4, 6]
----- iterative deepening search -----
----- 1 -----
----- 2 -----
----- 3 -----
----- 4 -----
[0, 2, 4, 6]
----- 5 -----
[0, 1, 2, 4, 6]
[0, 1, 3, 4, 6]
----- 6 -----
[0, 2, 1, 3, 4, 6]

●簡単なプログラム (3)

簡単なパズルの解法プログラムです。パズルの説明は以下のページをお読みくださいませ。

Puzzle DE Programming: 小町算
Puzzle DE Programming: N Queens Problem
Haskell 入門: ナンバープレース
Julia 入門: マスターマインド
Puzzle DE Programming: 水差し問題
Puzzle DE Programming: 農夫と山羊と狼とキャベツの問題
Puzzle DE Programming: 三目並べ
Puzzle DE Programming: ペグ・ソリティア

 ●───●───●    ０───１───２  
 │＼  ／│＼  ／│    │＼  ／│＼  ／│  
 │  ●  │  ●  │    │  ３  │  ４  │  
 │／  ＼│／  ＼│    │／  ＼│／  ＼│  
 ●───○───●    ５───６───７  
 │＼  ／│＼  ／│    │＼  ／│＼  ／│  
 │  ●  │  ●  │    │  ８  │  ９  │  
 │／  ＼│／  ＼│    │／  ＼│／  ＼│  
 ●───●───●    10───11───12  

   (1) Hoppers             (2) 座標

    図 : ペグ・ソリティア (Hoppers)

#
# sample03.py : 簡単なプログラム (3)
#
#               Copyright (C) 2018 Makoto Hiroi
#

#
# 小町算
#
def calc_expr(expr):
    n = expr[0]
    for i in range(1, len(expr), 2):
        if expr[i] == '+':
            n += expr[i + 1]
        else:
            n -= expr[i + 1]
    return n

def print_expr(expr):
    for x in expr:
        print('{} '.format(x), end='')
    print('= 100')

def komachi(n, expr):
    if n == 10:
        if calc_expr(expr) == 100: print_expr(expr)
    else:
        komachi(n + 1, expr + ['+', n])
        komachi(n + 1, expr + ['-', n])
        komachi(n + 1, expr[:-1] + [expr[-1] * 10 + n])

print("----- komachi -----")
komachi(2, [1])

#
# N Queens Problem
#

def nqueens(n):
    def attack(q, qs):
        d = 1
        for i in range(len(qs), 0, -1):
            if q + d == qs[i - 1] or q - d == qs[i - 1]: return True
            d += 1
        return False           

    def nqueens_sub(qs):
        if len(qs) == n:
            print(qs)
        else:
            for x in range(1, n + 1):
                if x in qs or attack(x, qs): continue
                qs.append(x)
                nqueens_sub(qs)
                qs.pop()
    nqueens_sub([])

print("----- N Queens Problem -----")
for x in range(4, 9): nqueens(x)

#
# ナンバープレース
#

# 盤面の表示
def print_board(board):
    for xs in board:
        for n in xs: print(n, end = ' ')
        print('') 

# 条件のチェック
def check_number(x, y, n, board):
    for i in range(0, 9):
        if board[i][y] == n or board[x][i] == n: return False
    x1 = (x // 3) * 3
    y1 = (y // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if board[x1 + i][y1 + j] == n: return False
    return True

# ナンバープレースの解法
def numplace(x, y, board):
    if y >= 9:
        print_board(board)
    elif x >= 9:
        numplace(0, y + 1, board)
    elif board[x][y]:
        numplace(x + 1, y, board)
    else:
        for n in range(1, 10):
            if not check_number(x, y, n, board): continue
            board[x][y] = n
            numplace(x + 1, y, board)
            board[x][y] = 0

# 問題 (出典: 数独 - Wikipedia の問題例)
sudoku_board = [
    [5, 3, 0,  0, 7, 0,  0, 0, 0],
    [6, 0, 0,  1, 9, 5,  0, 0, 0],
    [0, 9, 8,  0, 0, 0,  0, 6, 0],

    [8, 0, 0,  0, 6, 0,  0, 0, 3],
    [4, 0, 0,  8, 0, 3,  0, 0, 1],
    [7, 0, 0,  0, 2, 0,  0, 0, 6],

    [0, 6, 0,  0, 0, 0,  2, 8, 0],
    [0, 0, 0,  4, 1, 9,  0, 0, 5],
    [0, 0, 0,  0, 8, 0,  0, 7, 9]]

print('----- number place -----')
print_board(sudoku_board)
print('--------------------')
numplace(0, 0, sudoku_board)

#
# マスターマインド
#
import itertools

# bulls を数える
def count_bulls(xs, ys):
    c = 0
    for i in range(0, 4):
        if xs[i] == ys[i]: c += 1
    return c

# 同じ数の個数を数える
def count_same_numbers(xs, ys):
    c = 0
    for x in xs:
        if x in ys: c += 1
    return c

# 今までの質問と矛盾がないか
def check_query(code, qs):
    for q in qs:
        b = count_bulls(code, q[0])
        c = count_same_numbers(code, q[0]) - b
        if b != q[1] or c != q[2]: return False
    return True

# マスターマインドの解法
def master_mind(answer):
    query_table = []
    for code in itertools.permutations(range(0, 10), 4):
        if check_query(code, query_table):
            b = count_bulls(code, answer)
            c = count_same_numbers(code, answer) - b
            query_table.append((code, b, c))
            print('{}: {}, bulls = {}, cows = {}'.format(len(query_table), code, b, c))
            if b == 4:
                print('Good Job!!!')
                break

print('----- master mind -----')
master_mind([9,8,7,6])
master_mind([9,4,3,1])

#
# 水差し問題
#
MAX_A = 8
MAX_B = 5

# A を空にする
def move1(a, b): return 0, b

# A を満たす
def move2(a, b): return MAX_A, b

# A -> B
def move3(a, b):
    c = MAX_B - b
    if c >= a:
        return 0, a + b
    else:
        return a - c, b + c

# B を空にする
def move4(a, b): return a, 0

# B を満杯にする
def move5(a, b): return a, MAX_B

# B -> A
def move6(a, b):
    c = MAX_A - a
    if c >= b:
        return a + b, 0
    else:
        return a + c, b - c

def water_jug(g):
    que = [[(0, 0)]]
    while len(que) > 0:
        moves = que.pop(0)
        a, b = moves[-1]
        if a == g or b == g:
            print(moves)
            break
        for move_func in [move1, move2, move3, move4, move5, move6]:
            new_state = move_func(a, b)
            if new_state in moves: continue
            que.append(moves + [new_state])

print('----- water jug -----')
water_jug(4)
water_jug(1)

#
# 農夫と山羊と狼とキャベツの問題
#
def check_side(side):
    if 'wolf' in side and 'goat' in side: return False
    if 'goat' in side and 'cabbage' in side: return False
    return True

def move_boat(src, dst):
    src1 = src.difference({'farmer'})
    if check_side(src1):
        yield src1, dst.union({'farmer'})
    for x in ['goat', 'wolf', 'cabbage']:
        if x not in src: continue
        xs = {'farmer', x}
        src1 = src.difference(xs)
        if check_side(src1):
            yield src1, dst.union(xs)

def farmer():
    all = {'farmer', 'goat', 'wolf', 'cabbage'}
    que = [[(all, set())]]
    while len(que) > 0:
        move = que.pop(0)
        left, right = move[-1]
        if right == all:
            for xs in move: print(xs)
            break
        if 'farmer' in left:
            # left -> right
            for state in move_boat(left, right):
                if state not in move:
                    que.append(move + [state])
        else:
            # right -> right
            for r, l in move_boat(right, left):
                state = l, r
                if state not in move:
                    que.append(move + [state])
        
print('----- farmer -----')
farmer()

#
# ペグ・ソリティア (Hoppers)
#

# 定数
SIZE = 13
HOLE = 6
MAX_JUMP = 11

# 跳び先表 (del, to)
jump_table = (
    ((1, 2), (3, 6), (5, 10)),
    ((3, 5), (6, 11), (4, 7)),
    ((1, 0), (4, 6), (7, 12)),
    ((6, 9),),
    ((6, 8),),
    ((3, 1), (6, 7), (8, 11)),
    ((3, 0), (4, 2), (8, 10), (9, 12)),
    ((4, 1), (6, 5), (9, 11)),
    ((6, 4),),
    ((6, 3),),
    ((5, 0), (8, 6), (11, 12)),
    ((8, 5), (6, 1), (9, 7)),
    ((11, 10), (9, 6), (7, 2))
)

def print_move(moves):
    print('[{}, '.format(moves[0][0]), end='')
    p = moves[0][1]
    for a, b in moves[1:]:
        if a == p:
            print('{}, '.format(p), end='')
        else:
            print('{}][{}, '.format(p, a), end='')
        p = b
    print('{}]'.format(p))

def move_peg(board, from_, del_, to):
    board[from_] = 0
    board[del_] = 0
    board[to] = 1

def restore_peg(board, from_, del_, to):
    board[from_] = 1
    board[del_] = 1
    board[to] = 0

def hoppers():
    cnt = 0
    def ids(board, jc, limit, moves):
        nonlocal cnt
        if jc > limit: return
        if len(moves) == MAX_JUMP:
            if board[HOLE]:
                print_move(moves)
                cnt += 1
        else:
            for from_ in range(0, SIZE):
                if not board[from_]: continue
                for del_, to in jump_table[from_]:
                    if not board[del_] or board[to]: continue
                    if moves[-1][1] == from_:
                        new_jc = jc
                    else:
                        new_jc = jc + 1
                    moves.append((from_, to))
                    move_peg(board, from_, del_, to)
                    ids(board, new_jc, limit, moves)
                    moves.pop()
                    restore_peg(board, from_, del_, to)
    # 初手を 0 -> 6 に限定
    board = [1] * SIZE
    board[0] = 0
    board[3] = 0
    for limit in range(2, MAX_JUMP + 1):
        print("-----", limit, "-----")
        ids(board, 1, limit, [(0, 6)])
        if cnt > 0:
            print(cnt)
            break

print('----- Hoppers -----')
hoppers()

#
# 三目並べ
#

# 定数
MARU = 1
BATU = -1
FREE = 0 
MARU_WIN = 1
BATU_WIN = -1
DRAW = 0
MAX_VALUE = 2
MIN_VALUE = -2

# 直線
line = (
    (0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6),
    (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)
)

# 勝敗の判定
def check_winner(board):
    for a, b, c in line:
        piece = board[a]
        if piece != FREE and piece == board[b] == board[c]:
            if piece == MARU:
                return MARU_WIN
            else:
                return BATU_WIN
    return DRAW    

# 先手の指し手
def think_maru(board, n):
    value = MIN_VALUE
    for i in range(len(board)):
        if board[i] != FREE: continue
        board[i] = MARU
        v = check_winner(board)
        if v == DRAW and n < len(board) - 1:
            v = think_batu(board, n + 1)
        if v > value: value = v
        board[i] = FREE
    return value

# 後手の指し手
def think_batu(board, n):
    value = MAX_VALUE
    for i in range(len(board)):
        if board[i] != FREE: continue
        board[i] = BATU
        v = check_winner(board)
        if v == DRAW and n < len(board) - 1:
            v = think_maru(board, n + 1)
        if v < value: value = v
        board[i] = FREE
    return value

def tictactoe():
    board = [FREE] * 9
    for i in range(9):
        board[i] = MARU
        v = think_batu(board, 1)
        print(i, 'value = ', v)
        board[i] = FREE

print('----- tic tac toe -----')
tictactoe()