Lessen6-7:Extend Prefix

ポイント

・再帰検索時の検索結果の格納 　再帰を用いた検索で、各末端での検索結果を最上段の関数に返す場合は、基本的にreturnを使用して値の返しを行う。

def foo(x):
   if x > 100:
      return x
   else:
      return x + foo(x + 1)

しかし、ひとつの関数で複数の結果を生成し、それを最上段に返さなければいけない時「参照渡し」を利用すれば簡単に行える。

def find_words(letters):
    extend_prefix(letters)

def extend_prefix(letters, w='', results=None):
    if results: results = set()
    if w in WORDS: results.add(w)
    if w in PREFIXES:
        for L in letters: extend_prefix(w + L, letters.replace(L, '', 1))
    return results

resultがset()なので、extend_prefix()で参照渡しされる。 よって、結果は最上段のresultに格納される。

Lesson1-25:Allmax

ポイント

keyでFunctionを指定する際に、初期入力がNoneの時の対象法

Key指定時の注意点

pythonにおいてmax(a, key=function)など、基準として関数を指定することが可能。 このような関数を独自で実装するとき、key指定がない場合のfunctionをどうするかが問題になる。 この時lambda関数をデフォルト指定にしたい場合の実装をまとめる。

def allmax(iterable, key=None):
    "Return a list of all items equal to the max of the iterable."
    result, maxval = [], None
    key = key or (lambda x: x) # keyがNoneの場合、lambdaを指定する。
    for x in iterable:
        xval = key(x)
        if not result or xval > maxval:
            result, maxval = [x], xval
        elif xval == maxval:
            result.append(x)
    return result

Lesson1-7:UsingMax

今回のポイント

MaxはKeyにFunctionを指定することが出来る。指定されたFunctionは最大値算出時にMapのように一つずつ値を算出し、比較をしすることで最大値を算出する。

例

def poker(hands):
    "Return the best hand; poker([hand, ...]) => hand"
    return max(hands, key=hand_rank) # hand_rankを評価基準にして最大値を算出する。

def hand_rank(hand):
    pass

Lesson1-3:Outlining The Problem

はじめに

Design of Computer ProgramsのLesson1-3についてまとめる。

ここでの目標

今回作成するのは、ポーカーの手札を複数引数として取り込んで、そのなかから一番いい手を返すプログラム。

Dependency Injection

はじめに

---

Dependency Injectionについて自分なりにまとめてみる。 (Dependency Injection コンテントにつていは記述していません。) 修正箇所があれば、Updateをしていく。

そもそも

---

Dependency Injection(DI)をWikiで調べてみると…

コンポーネント間の依存関係をプログラムのソースコードから排除し、外部の設定ファイルなどで注入できるようにするソフトウェアパターンである。英語の頭文字からDIと略される。 依存性の注入 - Wikipedia

簡単に言うと、下記の様にクラス内でインスタンス発行（定数など）をせずに、引数として渡しましょうと言っているだけ。 なのに名前が仰々しすぎる…

非DIコード

import random

possible_moves = ['roll', 'hold']
other = {1: 0, 0: 1}
goal = 50


def clueless(state):
    "A strategy that ignores the state and chooses at random from possible moves."
    return random.choice(possible_moves)


def hold(state):
    """Apply the hold action to a state to yield a new state:
    Reap the 'pending' points and it becomes the other player's turn."""
    (p, me, you, pending) = state
    return (other[p], you, me + pending, 0)


def roll(state, d):
    """Apply the roll action to a state (and a die roll d) to yield a new state:
    If d is 1, get 1 point (losing any accumulated 'pending' points),
    and it is the other player's turn. If d > 1, add d to 'pending' points."""
    (p, me, you, pending) = state
    if d == 1:
        return (other[p], you, me + 1, 0)  # pig out; other player's turn
    else:
        return (p, me, you, pending + d)  # accumulate die roll in pending


def play_pig(A=clueless, B=clueless):
    """Play a game of pig between two players, represented by their strategies.
    Each time through the main loop we ask the current player for one decision,
    which must be 'hold' or 'roll', and we update the state accordingly.
    When one player's score exceeds the goal, return that player."""
    # your code here
    strategies = [A, B]
    state = (0, 0, 0, 0)

    while True:
        (p, me, you, _) = state
        if me >= goal:
            return strategies[p]
        elif you >= goal:
            return strategies[other[p]]
        elif strategies[p](state) == 'roll':
            state = roll(state, random.randint(1, 6)) #randomが毎回変わるのでテストができない・・・
        else:
            state = hold(state)

def always_roll(state):
    return 'roll'


def always_hold(state):
    return 'hold'

DIにする。 変更部分のみを記述。

def dierolls():
    "Generate die rolls."
    while True:
        yield random.randint(1, 6)

def play_pig(A=clueless, B=clueless, die=dierolls()): # generaterは、dierolls()の様に括弧付きでよい。
    """Play a game of pig between two players, represented by their strategies.
    Each time through the main loop we ask the current player for one decision,
    which must be 'hold' or 'roll', and we update the state accordingly.
    When one player's score exceeds the goal, return that player."""
    # your code here
    strategies = [A, B]
    state = (0, 0, 0, 0)

    while True:
        (p, me, you, _) = state
        if me >= goal:
            return strategies[p]
        elif you >= goal:
            return strategies[other[p]]
        elif strategies[p](state) == 'roll':
            state = roll(state, next(die))
        else:
            state = hold(state)

Problem set 4-2:More Pour Problem

目次

---

• 問題の説明
• ポイント
• ソース

問題の説明

---

PouringProblemの拡張版を今回は作成する。 前回の(PouringProblem)jsakusan.hatenablog.comは、2つの容器を使用した場合で解決方法を探索した。 しかし、今回は容器の数をフレキシブルに変化可能にする。 容器の状態はtupleを用いて、羅列することで表現する。例えば、5個の容器を使用する場合は(0, 0, 0, 0, 2)のように表現する。 探索後、答えは、(state, action ,state2, action, …..)と表現する。具体的には、((0, 0, 0, 0), ('fill', 2), (0, 0, 4, 0)) 関数の引数として、startの状態、endの状態、それぞれ容器のcapacityを与える。

ポイント

---

1, 各状態の探索方法

前回は、2つの容器ないでの表現だったので

def successors(x, y, X, Y):
    assert x <= X and y <= Y
    return {(0, x + y) if x + y < Y else (x - (Y - y), y + (Y - y)) : 'x => y',
             (x + y, 0) if x + y < X else (x + (X - x), y - (X - x)) : 'x <= y',
             (x, Y): 'fill up y', (X, y): 'Fill up x',
             (0, y): 'empty y', (x, 0): 'empty x'}

x, y(現在の状態)からX, Y(各容器の容量)内での状態遷移をすべて表現することができた。 しかし、今回は任意の個数容器があるので別の実装方法を実現しなければいけない。

今回は、def successors(state)(state => (0, 0, 0, 0, 0))として、listのn番目を異なる状態に変化させる処理を行うことで pour, full, emptyを表現する。

コード

def more_pour_problem(capacities, goal, start=None):

    def is_goal(state): return goal in state

    def more_pour_successors(state):
        indices = range(len(state))
        succ = {}
        for i in indices:
            succ[replace(state, i, capacities[i])] = ('fill', i)
            succ[replace(state, i, 0)] = ('empty', i)

            for j in indices:
                amount = min(state[i], capacities[j] - state[j])
                state2 = replace(state, i, state[i] - amount)
                succ[replace(state2, j, state[j] + amount)] = ('pour', i, j)

        return succ

    if start is None: start = (0,) * len(capacities)
    return shortest_path_search(start, more_pour_successors, is_goal)


def replace(sequence, i, val):
    "Return copy of sequence, with sequence[i] replace by val"
    s = list(sequence)
    s[i] = val
    return type(sequence)(s)


def shortest_path_search(start, successors, is_goal):
    """Find the shortest path from start state to a state
    such that is_goal(state) is true."""
    if is_goal(start):
        return [start]
    explored = set()
    frontier = [[start]]
    while frontier:
        path = frontier.pop(0)
        s = path[-1]
        for (state, action) in successors(s).items():
            if state not in explored:
                explored.add(state)
                path2 = path + [action, state]
                if is_goal(state):
                    return path2
                else:
                    frontier.append(path2)
    return Fail


Fail = []


def test_more_pour():
    assert more_pour_problem((1, 2, 4, 8), 4) == [
        (0, 0, 0, 0), ('fill', 2), (0, 0, 4, 0)]
    assert more_pour_problem((1, 2, 4), 3) == [
        (0, 0, 0), ('fill', 2), (0, 0, 4), ('pour', 2, 0), (1, 0, 3)]
    starbucks = (8, 12, 16, 20, 24)
    assert not any(more_pour_problem(starbucks, odd) for odd in (3, 5, 7, 9))
    assert all(more_pour_problem((1, 3, 9, 27), n) for n in range(28))
    assert more_pour_problem((1, 3, 9, 27), 28) == []
    return 'test_more_pour passes'


print(test_more_pour())

Lesson4-26:Cleaning Up Mc Problem

引数の値に応じて、関数を指定したい時のコードの書き方の話。 下記の様なコードがあった場合、

def mc_problem(start=(3, 3, 1, 0, 0, 0), goal=None):
    if goal == None:
       goal_fn = lambda state: (0, 0, 0) == state[:3]
    else:
       goal_fn = lambda state: goal == state

もしくは、下記の様にdefを用いて内部関数を宣言してもよい。

def mc_problem(start=(3, 3, 1, 0, 0, 0), goal=None):
    if goal == None:
       def goal_fn(state): return (0, 0, 0) == state[:3]
    else:
       def goal_fn(state): return goal == state