JavaScript + Audio Data API を使ってMMLシーケンサーを作った2
JavaScript(Audio Data API)でMMLシーケンサーを書いた
HTML5にはAudio要素って言うのがあって、プラグインを使わずに音声を扱うことができるのだけど、
FireFox4(ベータ版)にはさらに Audio Data API っていうのがあって、これを使うと音声データを生成することすらできる。
このあたりに解説がある
https://wiki.mozilla.org/Audio_Data_API
http://ascii.jp/elem/000/000/564/564098/
こんなこともできる!!すげぇ。
http://weare.buildingsky.net/2010/06/17/html5-audio-data-api
要するにブラウザがシンセサイザーになるわけですな。
色々面白そうなので、練習をかねてMMLを再生するシーケンサーを作ってみた。
JavaScriptだけで音を生成して再生しています。
複雑なことをすると音がブチブチとぎれるけど、きっちりプログラムを書けばもっと良くなりそう。
《もう少し効率よく動くように修正中》
MMLSequencer.js (今のところFireFox4 ベータ版でないと動きません)
http://mohayonao.com/MMLSequencer/
音はこんな感じ。
ソースはGitHubにおいた。
https://github.com/mohayonao/JSMMLSequencer
その他
- コマンドを拡張しすぎておかしなことになってしまった
- フィルタが上手く動かない
- もっと複雑なこともしたい
PyAudio で MMLインタプリタを書いてみた
昨日簡単なMMLのプログラムを書いたけど、
ゴミ収集車みたいな単音しか出ないので、もうちょっと良く動くものを書いてみた。
ソース:
https://github.com/mohayonao/PyMMLPlayer
デモ:
TODO:
- ノイズの音の高低の作り方が分からなくて格好悪い
- ポルタメントの処理が未実装
MMLは下記のものを使わせていただきました。感謝。
Ys2のオープニング曲
Ys2 サルモンの神殿の曲
Ys2 ノルティアの氷壁の曲
Ys2 ムーンドリアの廃墟
Sorcerian 盗賊達の塔 「封印」
Python+PyAudio+MMLでスーパーマリオの地上BGMを
MML http://ja.wikipedia.org/wiki/Music_Macro_Language
PyAudioで何か作ってみようと思って書いた。
簡単な機能しかついていないし、汎用性に欠ける。
音もゴミ収集車みたいだし
#!/usr/bin/env python # -*- coding: utf-8 -*- import re import math import array import itertools import collections import pyaudio class MMLStatus: """テンポとか音符の長さとかの情報を持つ""" def __init__(self, T=120, L=4, O=4, Q=5, V=12): self.T = T self.L = L self.O = O self.Q = Q self.V = V def __str__(self): return 'T=%d, L=%d, O=%d, Q=%d, V=%d' % (self.T, self.L, self.O, self.Q, self.V) def change(self, cmd): if cmd.cmd == '<': if self.O < 7: self.O += 1 elif cmd.cmd == '>': if self.O > 0: self.O -= 1 elif cmd.cmd == 'L': if 1 <= cmd.arg <= 64: self.L = cmd.arg elif cmd.cmd == 'V': if 0 <= cmd.arg <= 16: self.V = cmd.arg elif cmd.cmd == 'T': if 30 <= cmd.arg <= 240: self.T = cmd.arg elif cmd.cmd == 'O': if 0 <= cmd.arg <= 7: self.O = cmd.arg elif cmd.cmd == 'Q': if 1 <= self.Q <= 8: self.Q = cmd.arg - 1 MMLCommand = collections.namedtuple('MMLCommand', 'cmd acci arg dot') ADSR = collections.namedtuple('ADSR', 'A D S R') class MMLPlayer: """MMLプレイヤー""" ACCI = ( 1.0, 1.0/1.06, 1.06, 1.06 ) DOT = ( 1.0, 1.5, 1.75, 1.875 ) def __init__(self, tone, adsr=None): self.tone = tone self.adsr = adsr self.stat = MMLStatus() def fetch_token(self, command): buf = [] for c in command.upper(): if c in (' ', '\n'): continue if c in ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'R', 'T', 'L', 'O', 'V', 'Q', '>', '<'): if buf: yield ''.join(buf) buf = [] buf.append(c) else: if buf: yield ''.join(buf) def conv_token(self, token): m = re.search(r'([A-Z<>])([-=+#]?)(\d*)(\.*)', token) if not m: return cmd = m.group(1).upper() acci = '=-+#'.index(m.group(2)) arg = int(m.group(3) or 0) dot = len(m.group(4)) return MMLCommand(cmd=cmd, acci=acci, arg=arg, dot=dot) def conv_freq(self, cmd): freq = 0 if cmd.cmd == 'C': freq = 261.63 elif cmd.cmd == 'D': freq = 293.66 elif cmd.cmd == 'E': freq = 329.63 elif cmd.cmd == 'F': freq = 349.23 elif cmd.cmd == 'G': freq = 392.00 elif cmd.cmd == 'A': freq = 440.00 elif cmd.cmd == 'B': freq = 493.88 elif cmd.cmd == 'R': freq = 0 freq *= 2 ** (self.stat.O - 4) * self.ACCI[cmd.acci] return freq def conv_length(self, cmd): if 1 <= cmd.arg <= 64: return cmd.arg else: return self.stat.L def calc_tim(self, cmd): return (60.0 / self.stat.T) * (4.0 / self.conv_length(cmd)) * self.DOT[cmd.dot] def play(self, command): p = pyaudio.PyAudio() stream = p.open(rate=44100, channels=1, format=pyaudio.paFloat32, output=True) buf = (0, 0, 0, 0) for token in self.fetch_token(command): cmd = self.conv_token(token) if cmd.cmd not in ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'R'): self.stat.change(cmd) continue freq = self.conv_freq(cmd) tim = self.calc_tim(cmd) tim2 = tim * ((self.stat.Q + 1) / 8.0) velocity = self.stat.V / 16.0 * 0.1 print cmd, self.stat if cmd.cmd != 'R': stream.write(self.tone(buf[0], sec=(buf[1], buf[2]), velocity=velocity, adsr=self.adsr)) buf = (freq, tim, tim2, velocity) else: buf = (buf[0], buf[1] + tim, buf[2], velocity) else: stream.write(self.tone(buf[0], sec=(buf[1], buf[2]), velocity=velocity, adsr=self.adsr)) stream.close() p.terminate() def sine_wave(w, n): """サイン派""" for i in xrange(): yield math.sin(float(i % w) / w * PI2) def sawtooth_wave(w, n): """ノコギリ波""" for i in xrange(n): yield (i % w) / float(w) def square_wave(w, n): """矩形波""" hw = w / 2 for i in xrange(n): yield 1.0 if i % w <= hw else 0.0 def tone(freq, sec=1, velocity=.2, rate=44100, adsr=None): PI2 = math.pi * 2 if isinstance(sec, (int, float)): tim = sec else: sec, tim = sec w = rate / freq if freq else 0 def envelope_generator(): if adsr: length = rate * sec i = 0 attack = rate * adsr.A for i in xrange(int(min(attack, length))): yield i / float(attack) decay = rate * adsr.D sustain = adsr.S for i in xrange(i, int(min(decay, length))): j = i - attack yield 1.0 - ((1.0 - sustain) * j / float(decay)) release_start = rate * tim for i in xrange(i, int(min(release_start, length))): yield sustain release = rate * adsr.R for i in xrange(i, int(min(release, length))): j = i - release_start yield sustain * (1.0 - (j / float(release))) for i in xrange(i, int(length)): yield 0.0 else: for i in xrange(int(rate * sec)): yield 1.0 wgen = square_wave def gen(): if w: for i, j in itertools.izip(wgen(w, int(rate * sec)), envelope_generator()): yield i * j * velocity else: for i in xrange(int(rate * sec)): yield 0 return array.array('f', gen()).tostring() # http://blog.lilyx.net/2007/10/07/javascript-mml-mario-theme/ command = """ T195 L8 O5 eerercergrr4>grr4< crr>grrerrarbrb-arg6<c6g6arfgrercd>br4< crr>grrerrarbrb-arg6<c6g6arfgrercd>br4< r4gf+fd+rer>g+a<c>ra<cd r4gf+fd+rer<crccrr4 >r4gf+fd+rer>g+a<c>ra<cd r4e-rrdrrcrr4r2 r4gf+fd+rer>g+a<c>ra<cd r4gf+fd+rer<crccrr4 >r4gf+fd+rer>g+a<c>ra<cd r4e-rrdrrcrr4r2 ccrcrcdrecr>agrr4 <ccrcrcder1 ccrcrcdrecr>agrr4< eerercergrr4>grr4< crr>grrerrarbrb-arg6<c6g6arfgrercd>br4< crr>grrerrarbrb-arg6<c6g6arfgrercd>br4< ecr>gr4g+ra<frf>arr4 b6<a6a6a6g6f6ecr>agrr4< ecr>gr4g+ra<frf>arr4 b6<f6f6f6e6d6crr2. ecr>gr4g+ra<frf>arr4 b6<a6a6a6g6f6ecr>agrr4< ecr>gr4g+ra<frf>arr4 b6<f6f6f6e6d6crr2. ccrcrcdrecr>agrr4 <ccrcrcder1 ccrcrcdrecr>agrr4< eerercergrr4>grr4< ecr>gr4g+ra<frf>arr4 b6<a6a6a6g6f6ecr>agrr4< ecr>gr4g+ra<frf>arr4 b6<f6f6f6e6d6crr2. T180 c4.>g4.e4 T160 a6b6a6 T150 a-6b-6a-6g1 """ MMLPlayer(tone, adsr=ADSR(0., .4, 0., 0.2)).play(command)
PyAudioでドレミファソラシド
PyAudioというAudio I/Oライブラリがあると知ったのでさっそく使ってみた。
easy_installではエラーになったので、以下のURLからdmgをダウンロードしてインストールしたらOKだった。
http://people.csail.mit.edu/hubert/pyaudio/
とりあえずドレミファソラシド。
全然音楽的なコードじゃないし、クリック音がしてる。。
#!/usr/bin/env python # -*- coding: utf-8 -*- import math import array import pyaudio def tone(freq, sec=1, velocity=.2, rate=44100): w = rate / freq def gen(): for i in xrange(int(rate * sec)): yield math.sin(float(i % w) / w * 2. * math.pi) * velocity return array.array('f', gen()).tostring() p = pyaudio.PyAudio() stream = p.open(rate=44100, channels=1, format=pyaudio.paFloat32, output=True) scale = [ 261.63, # C 293.66, # D 329.63, # E 349.23, # F 392.00, # G 440.00, # A 493.88, # H 261.63 * 2, # C ] for freq in scale: stream.write(tone(freq, sec=.5)) stream.close() p.terminate()
状態空間表現で色々な問題を解く
勉強と練習。
解き方は分からないけどルールとゴールは決まっている。そういう問題を解く場合、与えられた問題を状態空間表現により定義する。
状態空間表現を使うことで問題定義が厳密になるし、直接的解法が分からない問題の解く手続きの探索が簡単になる。
状態空間表現というのは以下の三つによって定義される。
- 初期状態
- ゴール状態
- ルール (現在の状態とそのルールの適用によって生じる新しい状態によって表される)
それだけの知識で問題を解くプログラムを書いてみた。
とりあえず解答を見つけるための簡単な幅優先探索の関数を書いた。
現在の状態から取り得る次の状態(複数ある場合もある)を全部キューに放り込んで
ゴール状態が見つかるか、キューが空になる(解がなかった場合)まで探索する。
この探索アルゴリズムと状態空間表現とがあれば、試行錯誤的に問題を解くことができる。
とりあえず、水差し問題、川渡りの問題(2つ)、8パズルの状態空間表現を書いてやってみた。
import types def breadth_first_search(start, goal, rules, invariant=None): """幅優先探索""" if not invariant: is_invariant = lambda last: True else: is_invariant = lambda last: invariant(*last) if isinstance(goal, types.FunctionType): is_goal = lambda last: goal(*last) else: is_goal = lambda last: last == goal l = [ [(start, None)] ] checked = set(start) while l: path = l.pop(0) last = path[-1][0] # ルールを適用して新しい状態をキューに保存 for cond, action, desc in rules: if not cond(*last): continue next = action(*last) # 不変条件は満たされているか? if not is_invariant(next): continue # すでにチェック済み? if next in checked: continue checked.add(next) # もしかしてゴール状態? new_path = path + [(next, desc)] if is_goal(next): return new_path l.append(new_path)
例1:水差し問題
8ガロンと5ガロンの容器を使って4ガロンの水を用意する
def make_case_water_jug(capacity, target): start = (0, 0) goal = lambda a, b: a == target or b == target cap_a, cap_b = capacity rules = ( (lambda a, b: a > 0, lambda a, b: (0, b), u'aを空にする'), (lambda a, b: b > 0, lambda a, b: (a, 0), u'bを空にする'), (lambda a, b: a < cap_a, lambda a, b: (cap_a, b), u'aを満タンにする'), (lambda a, b: b < cap_b, lambda a, b: (a, cap_b), u'bを満タンにする'), (lambda a, b: a < cap_a and b > 0, lambda a, b: (min(cap_a, a+b), max(a+b-cap_a, 0)), u'aにbを移す'), (lambda a, b: a > 0 and b < cap_b, lambda a, b: (max(a+b-cap_b, 0), min(cap_b, a+b)), u'bにaを移す'), ) invariant = None return start, goal, rules, invariant start, goal, rules, invariant = make_case_water_jug(capacity=(8,5), target=4) path = breadth_first_search(start, goal, rules, invariant) if path: for i, (cur, desc) in enumerate(path): print '%2d %s %s' % (i, cur, desc)
結果
0 (0, 0) None 1 (0, 5) bを満タンにする 2 (5, 0) aにbを移す 3 (5, 5) bを満タンにする 4 (8, 2) aにbを移す 5 (0, 2) aを空にする 6 (2, 0) aにbを移す 7 (2, 5) bを満タンにする 8 (7, 0) aにbを移す 9 (7, 5) bを満タンにする 10 (8, 4) aにbを移す
例2:川渡りの問題
3人の宣教師と3人の人食い人種が、左岸から右岸に2人乗りのボートで川を渡ろうとしている。
川の両岸、あるいはボートの上で宣教師よりも人食い人種の数が多くなった場合、宣教師は人食い人種に食べられてしまう。全員が無事にボートを使って川を渡る手順を考えよ。(http://www.yuge.ac.jp/home/~nagao/teaching/AI/chap2/chap2-2.html)
def make_case_river_01(): LEFT, RIGHT = MISSIONARY, CANNIBAL = 0, 1 start = ((3, 3), (0, 0), LEFT ) goal = ((0, 0), (3, 3), RIGHT) rules = ( # 左から右 (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 2, lambda L, R, boat: ((L[MISSIONARY]-2,L[CANNIBAL]),(R[MISSIONARY]+2,R[CANNIBAL]), RIGHT), u'宣教師2人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 2, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-2),(R[MISSIONARY],R[CANNIBAL]+2), RIGHT), u'人食い2人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1, lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]),(R[MISSIONARY]+1,R[CANNIBAL]), RIGHT), u'宣教師1人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-1),(R[MISSIONARY],R[CANNIBAL]+1), RIGHT), u'人食い1人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1 and L[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]-1),(R[MISSIONARY]+1,R[CANNIBAL]+1), RIGHT), u'宣教師1人と人食い1人が左岸から右岸へ移動'), # 右から左 (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 2, lambda L, R, boat: ((L[MISSIONARY]+2,L[CANNIBAL]),(R[MISSIONARY]-2,R[CANNIBAL]), LEFT), u'宣教師2人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 2, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+2),(R[MISSIONARY],R[CANNIBAL]-2), LEFT), u'人食い2人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1, lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]),(R[MISSIONARY]-1,R[CANNIBAL]), LEFT), u'宣教師1人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+1),(R[MISSIONARY],R[CANNIBAL]-1), LEFT), u'人食い1人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1 and R[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]+1),(R[MISSIONARY]-1,R[CANNIBAL]-1), LEFT), u'宣教師1人と人食い1人が右岸から左岸へ移動'), ) invariant = lambda L, R, boat: not (0 < L[MISSIONARY] < L[CANNIBAL] or 0 < R[MISSIONARY] < R[CANNIBAL]) return start, goal, rules, invariant start, goal, rules, invariant = make_case_river_01() path = breadth_first_search(start, goal, rules, invariant) if path: for i, (cur, desc) in enumerate(path): print '%2d %s %s' % (i, cur, desc)
結果
0 ((3, 3), (0, 0), 0) None 1 ((3, 1), (0, 2), 1) 人食い2人が左岸から右岸へ移動 2 ((3, 2), (0, 1), 0) 人食い1人が右岸から左岸へ移動 3 ((3, 0), (0, 3), 1) 人食い2人が左岸から右岸へ移動 4 ((3, 1), (0, 2), 0) 人食い1人が右岸から左岸へ移動 5 ((1, 1), (2, 2), 1) 宣教師2人が左岸から右岸へ移動 6 ((2, 2), (1, 1), 0) 宣教師1人と人食い1人が右岸から左岸へ移動 7 ((0, 2), (3, 1), 1) 宣教師2人が左岸から右岸へ移動 8 ((0, 3), (3, 0), 0) 人食い1人が右岸から左岸へ移動 9 ((0, 1), (3, 2), 1) 人食い2人が左岸から右岸へ移動 10 ((1, 1), (2, 2), 0) 宣教師1人が右岸から左岸へ移動 11 ((0, 0), (3, 3), 1) 宣教師1人と人食い1人が左岸から右岸へ移動
例3:川渡りの問題2
さっきの問題の4人ずつ、3人乗りボートのバージョン。
def make_case_river_02(): LEFT, RIGHT = MISSIONARY, CANNIBAL = 0, 1 start = ((4, 4), (0, 0), LEFT ) goal = ((0, 0), (4, 4), RIGHT) rules = ( # 左から右 (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 3, lambda L, R, boat: ((L[MISSIONARY]-3,L[CANNIBAL]),(R[MISSIONARY]+3,R[CANNIBAL]), RIGHT), u'宣教師3人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 3, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-3),(R[MISSIONARY],R[CANNIBAL]+3), RIGHT), u'人食い3人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 2 and L[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY]-2,L[CANNIBAL]-1),(R[MISSIONARY]+2,R[CANNIBAL]+1), RIGHT), u'宣教師2人と人食い1人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 2, lambda L, R, boat: ((L[MISSIONARY]-2,L[CANNIBAL]),(R[MISSIONARY]+2,R[CANNIBAL]), RIGHT), u'宣教師2人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 2, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-2),(R[MISSIONARY],R[CANNIBAL]+2), RIGHT), u'人食い2人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1, lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]),(R[MISSIONARY]+1,R[CANNIBAL]), RIGHT), u'宣教師1人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-1),(R[MISSIONARY],R[CANNIBAL]+1), RIGHT), u'人食い1人が左岸から右岸へ移動'), (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1 and L[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]-1),(R[MISSIONARY]+1,R[CANNIBAL]+1), RIGHT), u'宣教師1人と人食い1人が左岸から右岸へ移動'), # 右から左 (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 3, lambda L, R, boat: ((L[MISSIONARY]+3,L[CANNIBAL]),(R[MISSIONARY]-3,R[CANNIBAL]), LEFT), u'宣教師3人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 3, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+3),(R[MISSIONARY],R[CANNIBAL]-3), LEFT), u'人食い3人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 2 and R[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY]+2,L[CANNIBAL]+1),(R[MISSIONARY]-2,R[CANNIBAL]-1), LEFT), u'宣教師2人と人食い1人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 2, lambda L, R, boat: ((L[MISSIONARY]+2,L[CANNIBAL]),(R[MISSIONARY]-2,R[CANNIBAL]), LEFT), u'宣教師2人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 2, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+2),(R[MISSIONARY],R[CANNIBAL]-2), LEFT), u'人食い2人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1, lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]),(R[MISSIONARY]-1,R[CANNIBAL]), LEFT), u'宣教師1人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+1),(R[MISSIONARY],R[CANNIBAL]-1), LEFT), u'人食い1人が右岸から左岸へ移動'), (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1 and R[CANNIBAL] >= 1, lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]+1),(R[MISSIONARY]-1,R[CANNIBAL]-1), LEFT), u'宣教師1人と人食い1人が右岸から左岸へ移動'), ) invariant = lambda L, R, boat: not (0 < L[MISSIONARY] < L[CANNIBAL] or 0 < R[MISSIONARY] < R[CANNIBAL]) return start, goal, rules, invariant start, goal, rules, invariant = make_case_river_02() path = breadth_first_search(start, goal, rules, invariant) if path: for i, (cur, desc) in enumerate(path): print '%2d %s %s' % (i, cur, desc)
結果
0 ((4, 4), (0, 0), 0) None 1 ((4, 1), (0, 3), 1) 人食い3人が左岸から右岸へ移動 2 ((4, 3), (0, 1), 0) 人食い2人が右岸から左岸へ移動 3 ((4, 0), (0, 4), 1) 人食い3人が左岸から右岸へ移動 4 ((4, 1), (0, 3), 0) 人食い1人が右岸から左岸へ移動 5 ((1, 1), (3, 3), 1) 宣教師3人が左岸から右岸へ移動 6 ((2, 2), (2, 2), 0) 宣教師1人と人食い1人が右岸から左岸へ移動 7 ((0, 1), (4, 3), 1) 宣教師2人と人食い1人が左岸から右岸へ移動 8 ((0, 3), (4, 1), 0) 人食い2人が右岸から左岸へ移動 9 ((0, 0), (4, 4), 1) 人食い3人が左岸から右岸へ移動
例4:8パズル
def make_case_eight_puzzle(start=None, goal=None): if start is None: start = (( 5, 4, 3, 2, 1, 6, 7, 0, 8, ),) if goal is None: goal = (( 1, 2, 3, 4, 5, 6, 7, 8, 0, ),) def swap(l, a, b): l = list(l) l[a], l[b] = l[b], l[a] return ( tuple(l), ) rules = ( (lambda l: l[0] == 0, lambda l: swap(l, 0, 1), u'',), (lambda l: l[0] == 0, lambda l: swap(l, 0 ,3), u'',), (lambda l: l[1] == 0, lambda l: swap(l, 1 ,0), u'',), (lambda l: l[1] == 0, lambda l: swap(l, 1, 2), u'',), (lambda l: l[1] == 0, lambda l: swap(l, 1, 4), u'',), (lambda l: l[2] == 0, lambda l: swap(l, 2, 1), u'',), (lambda l: l[2] == 0, lambda l: swap(l, 2, 5), u'',), (lambda l: l[3] == 0, lambda l: swap(l, 3, 0), u'',), (lambda l: l[3] == 0, lambda l: swap(l, 3, 4), u'',), (lambda l: l[3] == 0, lambda l: swap(l, 3, 6), u'',), (lambda l: l[4] == 0, lambda l: swap(l, 4, 1), u'',), (lambda l: l[4] == 0, lambda l: swap(l, 4, 3), u'',), (lambda l: l[4] == 0, lambda l: swap(l, 4, 5), u'',), (lambda l: l[4] == 0, lambda l: swap(l, 4, 7), u'',), (lambda l: l[5] == 0, lambda l: swap(l, 5, 2), u'',), (lambda l: l[5] == 0, lambda l: swap(l, 5, 4), u'',), (lambda l: l[5] == 0, lambda l: swap(l, 5, 8), u'',), (lambda l: l[6] == 0, lambda l: swap(l, 6, 3), u'',), (lambda l: l[6] == 0, lambda l: swap(l, 6, 7), u'',), (lambda l: l[7] == 0, lambda l: swap(l, 7, 4), u'',), (lambda l: l[7] == 0, lambda l: swap(l, 7, 6), u'',), (lambda l: l[7] == 0, lambda l: swap(l, 7, 8), u'',), (lambda l: l[8] == 0, lambda l: swap(l, 8, 5), u'',), (lambda l: l[8] == 0, lambda l: swap(l, 8, 7), u'',), ) invariant = None return start, goal, rules, invariant start, goal, rules, invariant = make_case_eight_puzzle() path = breadth_first_search(start, goal, rules, invariant) if path: for i, (cur, desc) in enumerate(path): print '%2d %s %s' % (i, cur, desc)
結果
0 ((5, 4, 3, 2, 1, 6, 7, 0, 8),) None 1 ((5, 4, 3, 2, 0, 6, 7, 1, 8),) 2 ((5, 0, 3, 2, 4, 6, 7, 1, 8),) 3 ((0, 5, 3, 2, 4, 6, 7, 1, 8),) 4 ((2, 5, 3, 0, 4, 6, 7, 1, 8),) 5 ((2, 5, 3, 4, 0, 6, 7, 1, 8),) 6 ((2, 5, 3, 4, 1, 6, 7, 0, 8),) 7 ((2, 5, 3, 4, 1, 6, 0, 7, 8),) 8 ((2, 5, 3, 0, 1, 6, 4, 7, 8),) 9 ((2, 5, 3, 1, 0, 6, 4, 7, 8),) 10 ((2, 0, 3, 1, 5, 6, 4, 7, 8),) 11 ((0, 2, 3, 1, 5, 6, 4, 7, 8),) 12 ((1, 2, 3, 0, 5, 6, 4, 7, 8),) 13 ((1, 2, 3, 4, 5, 6, 0, 7, 8),) 14 ((1, 2, 3, 4, 5, 6, 7, 0, 8),) 15 ((1, 2, 3, 4, 5, 6, 7, 8, 0),)
8パズルの問題は幅優先探索のような網羅的探索法より発見的探索法ってのを使ったほうが良い。それはまた今度やる。
iPhoneで3G接続できなくなったときのメモ
iPhoneで気がついたら3Gの表示が出ていない。インターネットできない。死ぬ。
ソフトバンクに電話しておねーさんに対応してもらったメモ。
ソフトバンクに問い合わせ
157 にかける(音声案内は下記を参考にスキップ)
http://mb.softbank.jp/mb/support/3G/contact/voice_information/#guidance
[2]料金にかんするお問い合わせ
[2]未払い金のご案内
→ ない
[1]オペレータにつなぐ
「iPhoneを使ってて3Gが使えない。3Gの表記もない。死にそうです。」と伝える。
→ iPhone担当の人に変わります。