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
Lesson 4- 17: Calculating Costs
下記の定義のようなTupleがあり、最後から2眼目のtotal_costが欲しい。 この場合、一旦変数にいれてやると、可読性が上がる。
tupleの定義
path = [state, (action, total_cost), state, ....]
コード
def path_cost(path) if len(path) < 3: return 0 else: action, total_cost = path[-2] return total_cost
Lesson4-4: Pouring Problem
目次
問題のイメージ
良くありがちな、二つの容器を使用して特定の分量を測定してくださいという問題。
問題を解く方向性としては、探索問題となる。
既に探索した領域を記憶し、新たな領域を探索するイメージ
実装
def pour_problem(X, Y, goal, start=(0, 0)): """ X and Y are the capacity oc glasses; (x, y) is current fill levels and represents a state. Hte goal is a level that can be in either glass. Start at start state and follow successors until we reach the goal. Keep track of frontier and previously explored; fail when no frontier """ if goal in start: return [start] explored = set() # set of states we have visited frontier = [[start]] # ordered list of paths we have blazed while frontier: path = frontier.pop(0) (x, y) = path[-1] for (state, action) in successors(x, y, X, Y).items(): if state not in explored: # the successors state has not be explored(don't re-explored) explored.add(state) path2 = path + [action, state] if goal in path2: return path2 else: frontier.append(path2) return Fail Fail = [] 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'} print(pour_problem(10, 12, (10, 6)))