blog.PanicBlanket.com

さらに続く。今日で終わりだ。

　cf. http://docs.python.jp/2.7/library/itertools.html

組合せジェネレータ

itertools.product は入れ子のループと同じ。

>>> for x in itertools.product('ABC', 'abc'):
...     print x
...
('A', 'a')
('A', 'b')
('A', 'c')
('B', 'a')
('B', 'b')
('B', 'c')
('C', 'a')
('C', 'b')
('C', 'c')

名前つき引数 repeat を与えると、その回数の引数が与えられたのと同じになる。

>>> for x in itertools.product('ABC', 'abc', repeat = 2):
...     print x
...
('A', 'a', 'A', 'a')
('A', 'a', 'A', 'b')
('A', 'a', 'A', 'c')
('A', 'a', 'B', 'a')
('A', 'a', 'B', 'b')
('A', 'a', 'B', 'c')
('A', 'a', 'C', 'a')
('A', 'a', 'C', 'b')
('A', 'a', 'C', 'c')
('A', 'b', 'A', 'a')
('A', 'b', 'A', 'b')
('A', 'b', 'A', 'c')
('A', 'b', 'B', 'a')
('A', 'b', 'B', 'b')
('A', 'b', 'B', 'c')
('A', 'b', 'C', 'a')
('A', 'b', 'C', 'b')
('A', 'b', 'C', 'c')
('A', 'c', 'A', 'a')
('A', 'c', 'A', 'b')
('A', 'c', 'A', 'c')
('A', 'c', 'B', 'a')
('A', 'c', 'B', 'b')
('A', 'c', 'B', 'c')
('A', 'c', 'C', 'a')
('A', 'c', 'C', 'b')
('A', 'c', 'C', 'c')
('B', 'a', 'A', 'a')
('B', 'a', 'A', 'b')
('B', 'a', 'A', 'c')
('B', 'a', 'B', 'a')
('B', 'a', 'B', 'b')
('B', 'a', 'B', 'c')
('B', 'a', 'C', 'a')
('B', 'a', 'C', 'b')
('B', 'a', 'C', 'c')
('B', 'b', 'A', 'a')
('B', 'b', 'A', 'b')
('B', 'b', 'A', 'c')
('B', 'b', 'B', 'a')
('B', 'b', 'B', 'b')
('B', 'b', 'B', 'c')
('B', 'b', 'C', 'a')
('B', 'b', 'C', 'b')
('B', 'b', 'C', 'c')
('B', 'c', 'A', 'a')
('B', 'c', 'A', 'b')
('B', 'c', 'A', 'c')
('B', 'c', 'B', 'a')
('B', 'c', 'B', 'b')
('B', 'c', 'B', 'c')
('B', 'c', 'C', 'a')
('B', 'c', 'C', 'b')
('B', 'c', 'C', 'c')
('C', 'a', 'A', 'a')
('C', 'a', 'A', 'b')
('C', 'a', 'A', 'c')
('C', 'a', 'B', 'a')
('C', 'a', 'B', 'b')
('C', 'a', 'B', 'c')
('C', 'a', 'C', 'a')
('C', 'a', 'C', 'b')
('C', 'a', 'C', 'c')
('C', 'b', 'A', 'a')
('C', 'b', 'A', 'b')
('C', 'b', 'A', 'c')
('C', 'b', 'B', 'a')
('C', 'b', 'B', 'b')
('C', 'b', 'B', 'c')
('C', 'b', 'C', 'a')
('C', 'b', 'C', 'b')
('C', 'b', 'C', 'c')
('C', 'c', 'A', 'a')
('C', 'c', 'A', 'b')
('C', 'c', 'A', 'c')
('C', 'c', 'B', 'a')
('C', 'c', 'B', 'b')
('C', 'c', 'B', 'c')
('C', 'c', 'C', 'a')
('C', 'c', 'C', 'b')
('C', 'c', 'C', 'c')

itertools.permutations は繰り返しを許さない順列、itertools.combinations は繰り返しを許さない組み合わせ。この2つはこの間書いたので省略。

itertools.combinations_with_replacement は繰り返しを許した組み合わせ。

>>> for x in itertools.combinations_with_replacement('ABCD', 2):
...     print x
...
('A', 'A')
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'B')
('B', 'C')
('B', 'D')
('C', 'C')
('C', 'D')
('D', 'D')

まだまだ続くよ。

　cf. http://docs.python.jp/2.7/library/itertools.html

一番短い入力シーケンスで止まるイテレータ（つづき）

これまた map とどう違うのかわからない itertools.imap。ひょっとしてリストを返すか、イテレータを返すかの違いだけなんだろか。

>>> for x in itertools.imap(lambda y: y*2, [1,2,3,4,5]):
...     print x
...
2
4
6
8
10

itertools.starmap は、イテラブルなオブジェクトを引数として受け取り、*つきで展開して関数を適用してくれる。

>>> for x in itertools.starmap(pow, [(2, 3), (3, 3), (10, 3)]):
...     print x
...
8
27
1000

itertools.tee は、1つのイテラブルからn個の独立したイテレータを生成する……ってなんだかよくわからん。

>>> x, y = itertools.tee(range(5), 2)
>>> for i in x:
...     print i
...
0
1
2
3
4
>>> for j in y:
...     print j
...
0
1
2
3
4

第2引数nは省略するとn=2。

itertools.takewhile は Haskell の takeWhile と同じく、条件が真の間だけ値を返す。

>>> for x in itertools.takewhile(lambda y: y < 5, range(10)):
...     print x
...
0
1
2
3
4

itertools.izip。これまた zip と何が違うのか。

>>> for x in itertools.izip(range(5), range(10,14)):
...     print x
...
(0, 10)
(1, 11)
(2, 12)
(3, 13)

短いほうのリストにあわせるのも zip と同じ。

長いほうのリストにあわせるのが itertools.izip_longest。

>>> for x in itertools.izip_longest(range(5), range(10,14)):
...     print x
...
(0, 10)
(1, 11)
(2, 12)
(3, 13)
(4, None)

引数fillvalueを指定すると、Noneの代わりにそれを使う。

>>> for x in itertools.izip_longest(range(5), range(10,14), fillvalue='x'):
...     print x
...
(0, 10)
(1, 11)
(2, 12)
(3, 13)
(4, 'x')

昨日の続き。

一番短い入力シーケンスで止まるイテレータ

itertools.chain は引数をひとつのシーケンスのようにつなげてくれる。

>>> for x in itertools.chain('abc', 'def', 'ghi'):
...     print x
...
a
b
c
d
e
f
g
h
i

itertools.compress は2つのシーケンスを引数にとり、2つ目のシーケンスの要素が真の場合、対応する1つ目のシーケンスの要素を返す。

>>> for x in itertools.compress('abcdef', [0,1,0,1,1,0]):
...     print x
...
b
d
e

itertools.dropwhile は Haskell の dropWhile と同じように先頭の条件が真になる要素を取り除いた残りの要素を返す。

>>> for x in itertools.dropwhile(lambda x: x < 5, [1,3,4,5,7,8,5,3]):
...     print x
...
5
7
8
5
3

itertools.groupby は少しわかりにくい。このイテレータが返すのは、第2引数で指定した関数の返り値と、その返り値で分けられたグループ（itertools._grouperオブジェクト）だ。

>>> for k, g in itertools.groupby([2,4,6,8,10,1,3,5,7,9], lambda x: x % 2):
...     print k
...     print g
...
0
<itertools._grouper object at 0x02127FD0>
1
<itertools._grouper object at 0x02127EB0>

このグループ自体がイテレータになっていて、繰り返し処理をすることができる。

>>> for k, g in itertools.groupby([2,4,6,8,10,1,3,5,7,9], lambda x: x % 2):
...     print 'key: ', k
...     for x in g:
...         print x
...
key:  0
2
4
6
8
10
key:  1
1
3
5
7
9

ちなみに、あらかじめ関数の値でソートされているのが前提のようで、ばらばらなものをまとめてくれたりはしない。

>>> for k, g in itertools.groupby(range(10), lambda x: x % 2):
...     print 'key: ', k
...     for x in g:
...         print x
...
key:  0
0
key:  1
1
key:  0
2
key:  1
3
key:  0
4
key:  1
5
key:  0
6
key:  1
7
key:  0
8
key:  1
9

itertools.ifilter は filter関数と同じ。何が違うんだろ。

>>> for i in itertools.ifilter(lambda x: x%2, range(10)):
...     print i
...
1
3
5
7
9

itertools.ifilter と逆の動作をするのが itertools.ifilterfalse。条件が偽になる要素を返す。

>>> for i in itertools.ifilterfalse(lambda x: x%2, range(10)):
...     print i
...
0
2
4
6
8

itertools.islice はリストのスライスと同じようだ。これもちょっとどう違うのかわからない。
引数は、seq、start、stop、step の順。startとstepは省略できる。

>>> for c in itertools.islice('abcdefghi', 2, 6, 2):
...     print c
...
c
e

今日はここまで。時間があれば続きを書くかも。

先週ちょっと紹介したitertoolsモジュールを少しずつ見ていくことにしよう。

　cf. http://docs.python.jp/2.7/library/itertools.html

無限イテレータ

まずは、itertools.count。初期値から1ずつカウントアップしていく。

>>> for i in itertools.count(0):
...     if i > 10:
...         break
...     print i
...
0
1
2
3
4
5
6
7
8
9
10

第2引数にステップを指定することも可能。

>>> for i in itertools.count(0, 3):
...     if i > 10:
...         break
...     print i
...
0
3
6
9

itertolls.cycle はシーケンスを無限に繰り返す。

>>> i = 0
>>> for x in itertools.cycle(['foo', 'bar', 'baz']):
...     i += 1
...     if i > 10:
...         break
...     print x
...
foo
bar
baz
foo
bar
baz
foo
bar
baz
foo

itertools.repeat は、オブジェクトを無限に繰り返す。

>>> i = 0
>>> for x in itertools.repeat("Hello"):
...     i += 1
...     if i > 10:
...         break
...     print x
...
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello
Hello

第2引数に回数を指定することも可能。

>>> for x in itertools.repeat("hello", 5):
...     print x
...
hello
hello
hello
hello
hello

itertools の関数は数が多いので今日はここまで。

itertools モジュールが使える。
順列は、itertools.permutations。

>>> import itertools
>>> for x in itertools.permutations("ABCDE", 3):
...     print x
...
('A', 'B', 'C')
('A', 'B', 'D')
('A', 'B', 'E')
('A', 'C', 'B')
('A', 'C', 'D')
('A', 'C', 'E')
('A', 'D', 'B')
('A', 'D', 'C')
('A', 'D', 'E')
('A', 'E', 'B')
('A', 'E', 'C')
('A', 'E', 'D')
('B', 'A', 'C')
('B', 'A', 'D')
('B', 'A', 'E')
('B', 'C', 'A')
('B', 'C', 'D')
('B', 'C', 'E')
('B', 'D', 'A')
('B', 'D', 'C')
('B', 'D', 'E')
('B', 'E', 'A')
('B', 'E', 'C')
('B', 'E', 'D')
('C', 'A', 'B')
('C', 'A', 'D')
('C', 'A', 'E')
('C', 'B', 'A')
('C', 'B', 'D')
('C', 'B', 'E')
('C', 'D', 'A')
('C', 'D', 'B')
('C', 'D', 'E')
('C', 'E', 'A')
('C', 'E', 'B')
('C', 'E', 'D')
('D', 'A', 'B')
('D', 'A', 'C')
('D', 'A', 'E')
('D', 'B', 'A')
('D', 'B', 'C')
('D', 'B', 'E')
('D', 'C', 'A')
('D', 'C', 'B')
('D', 'C', 'E')
('D', 'E', 'A')
('D', 'E', 'B')
('D', 'E', 'C')
('E', 'A', 'B')
('E', 'A', 'C')
('E', 'A', 'D')
('E', 'B', 'A')
('E', 'B', 'C')
('E', 'B', 'D')
('E', 'C', 'A')
('E', 'C', 'B')
('E', 'C', 'D')
('E', 'D', 'A')
('E', 'D', 'B')
('E', 'D', 'C')

組み合わせは、itertools.combinations。

>>> for x in itertools.combinations("ABCDE", 3):
...     print x
...
('A', 'B', 'C')
('A', 'B', 'D')
('A', 'B', 'E')
('A', 'C', 'D')
('A', 'C', 'E')
('A', 'D', 'E')
('B', 'C', 'D')
('B', 'C', 'E')
('B', 'D', 'E')
('C', 'D', 'E')

itertools モジュールにはほかにも便利そうな関数があるので、そのうち使ってみたい。

cf. http://docs.python.jp/2.7/library/itertools.html

AOJのこの問題を解くのに次のようなコードを書いた。

import sys
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Vector:
    def __init__(self, p1, p2):
        self.vx = p2.x - p1.x
        self.vy = p2.y - p1.y

    def length(self):
        return math.sqrt(self.vx ** 2.0 + self.vy ** 2.0)

    def degree(self, other):
        theta = math.acos((self.vx * other.vx + self.vy * other.vy)/(self.length() * other.length()))
        return theta

    def show(self):
        return "Vector(%f, %f)" % (self.vx, self.vy)

def solv(points):
    p0 = points[0]
    for p in points[1:]:
        if p.y < p0.y:
            p0 = p
            v1 = Vector(Point(0.0, 0.0), Point(1.0, 0.0))
            p1 = p0
            t = [p1]
    while True:
        min_deg = math.pi
        next_p = None
        next_v = None
        points2 = list(points)
        points2.remove(p1)
        for p2 in points2:
            v2 = Vector(p1, p2)
            deg = v1.degree(v2)
            if deg < min_deg:
                min_deg = deg
                next_p = p2
                next_v = v2
            if next_p == p0:
                break
            p1 = next_p
            t.append(p1)
            v1 = next_v
         return len(points) - len(t)
    while True:
        n = int(sys.stdin.readline())
        if n == 0:
            break
        points = []
        for i in range(n):
            x, y = map(float, sys.stdin.readline().split(','))
        points.append(Point(x, y))
    print solv(points) 

複数の点が与えられて、凸包の中にある点の数を出力する問題で、ググってあちこちのページを参考にしながら書いたので、エレガントじゃないとかそういうことは置いといてたぶんあってる。 簡単に説明しておくと、一番下の点を出発点として左回りに凸包に含まれる点を探索している。この時、すでに凸包に含まれるのが明らかになっている最後の2点を結ぶベクトルと、最後の1点とその他の点を結ぶベクトルのなす角度をそれぞれ求めて、角度が最も小さい点を次の点としている。で、最初の点に戻ってくるまでループしてるわけだ。 さて、これにサンプルのデータを与えて実行するとタイトルのようなエラーが出る。

^o^ > python problem0-0068.py < input0-0068.txt
0
Traceback (most recent call last):
  File "problem0-0068.py", line 70, in 
    print solv(points)
  File "problem0-0068.py", line 48, in solv
    deg = v1.degree(v2)
  File "problem0-0068.py", line 25, in degree
    theta = math.acos((self.vx * other.vx + self.vy * other.vy)/(self.length() *
 other.length()))
ValueError: math domain error

math.acos()のところでエラーになっている。ここには載せないけどサンプルの入力データには2つのデータセットがあって、1つ目のデータセットに対する出力は正常にされている。最初の0がそうだ。これはサンプルの回答ともあっている。だけど2つ目のデータセットではエラーが発生する。
詳しく調べてみると、math.acos()の引数が-1.0の時にエラーになっているんだけど、引数が-1.0になるのは1度じゃなく何度もあって、エラーが発生しないときもある（というか発生しないほうが多い）。実際1つ目のデータセットには正解を返してるわけだし。

ググってみてもこの math domain error というのがどういうエラーなのかよくわからない。

いくら悩んでもわからないので、ダメもとでAOJに提出したら、あっさりとAcceptedになってしまった。

わけがわからないよ。

答え：できるけどちょっと変（Python 2.7の場合）。

たとえばJavaScriptの場合には、次のように素直にクロージャを作れる。

js> function make_counter(init){
  >     i = init
  >     function counter(){
  >         print(i)
  >         i += 1
  >     }
  >     return counter
  > }
js> c = make_counter(3)

function counter() {
    print(i);
    i += 1;
}

js> c()
3
js> c()
4
js> c()
5

同じことをPythonでやってみる。

>>> def make_counter(init):
...     i = init
...     def counter():
...         print i
...         i += 1
...     return counter
...
>>> c = make_counter(3)

という風に一見できているように見えるけど、いざc()を実行すると、

>>> c()
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 4, in counter
UnboundLocalError: local variable 'i' referenced before assignment

エラーになる。i を代入前に参照している、と言ってるようだ。

ググってみたらこんな記事を見つけた。
cf. Python とクロージャ – プログラマのネタ帳

この記事によると、ネストした内側の関数定義から外側の変数を参照することはできるけど変更することはできない、と書いてある。実際次のような例が載っている。

>>> def outer(val):
...     def inner(arg):
...         return val + arg
... return inner
...
>>> inner = outer(10)
>>> inner(20)
30

この例は確かに問題なく動く。
さて、じゃあ、さっきのエラーになったコードに戻ってみよう。報告されたエラーはコードの4行目、print i の部分で、i が代入前に参照された、というエラーだった。「内側の関数定義から外側の変数が参照できるが変更はできない」と言うのが本当なら、このエラーはおかしい。4行目では参照しかしてないはずだ。5行目の i += 1 がエラーになるのなら理解できるんだけど。

で、結局どうやったらクロージャができるかと言うと、利用したい変数をリストに入れておけばいいらしい。

>>> def make_counter(init):
...     tmp = [init]
...     def counter():
...         print tmp[0]
...         tmp[0] += 1
...     return counter
...
>>> c = make_counter(3)
>>> c()
3
>>> c()
4
>>> c()
5

これだと tmp 変数には参照しかしないのでエラーにならない、と言うことらしい。確かにちゃんと動いているけど、なんか釈然としない。

逆ポーランド電卓ってまだあるんだな。アマゾンでも売ってる。
というわけでちょっと作ってみた。

import sys

class InvalidToken(Exception):
    pass

class RPNCalc:
    def __init__(self):
        self.stack = []

    def calc(self, expr):
        try:
            tokens = expr
            if not tokens[-1] in '+-*/':
                raise InvalidToken
            for token in tokens:
                if token.isdigit():
                    self.stack.append(int(token))
                elif token == '+':
                    a = self.stack.pop()
                    b = self.stack.pop()
                    self.stack.append(b + a)
                elif token == '-':
                    a = self.stack.pop()
                    b = self.stack.pop()
                    self.stack.append(b - a)
                elif token == '*':
                    a = self.stack.pop()
                    b = self.stack.pop()
                    self.stack.append(b * a)
                elif token == '/':
                    a = self.stack.pop()
                    b = self.stack.pop()
                    self.stack.append(b / a)
                else:
                    raise InvalidToken
        except:
            print 'Invalid expression'
            exit()
        return self.stack.pop()

calculator = RPNCalc()
expr = sys.argv[1:]
print calculator.calc(expr)

^o^ > rpncalc.py 6 2 + 5  3 - 2 * /
2

やっつけの手抜きなので、正しく入力しないとエラーにならずに間違った答えを返す。そのうち気が向いたら直すかも。

^o^ > rpncalc.py 1 2 3 +
5

AOJのこの問題、evalを使って簡単簡単、だと思いきやジャッジは Wrong Answer だった。原因はタイトルのとおりで、問題では割り算の小数点以下は単に切り捨てることになっている。
Python のマニュアルにはこうある：

(通常および長) 整数の割り算では、結果は整数になります。この場合値は常にマイナス無限大の方向に丸められます

Python て Ruby みたいに演算子の再定義はできないんだろうか。あれば構文解析しなくても eval でいけるんだけど。

結局 Ruby で書いて AC もらった根性なしの俺でした。