スキップしてメイン コンテンツに移動

投稿

4月, 2008の投稿を表示しています

Project Eulerをやってみた

ちょっと流行っているということで、Project Euler(プロジェクト・オイラー)(日本語Wiki)をやってみた。とりあえず3日で50問以上解いてみたが、結構面白いかも。問題自体は今までのところどれも簡単でコーディングを含めて1問につき数分もあれば解けるものばかり。しかし、すぐに解けてしまうので止め時が難しい。今後、難しくなっていくのかもしれないが。ただし、最適なアルゴリズムを考えて解こうとすると難易度は上がる。

これはプログラミングの勉強や教育にはいいかも。以前、学生にダイクストラ法を教えたことがあったけど、まさにそれを使う問題(Problem 67)も出てきた。

使用言語はC++にしている。しかし、1~2割程度はPythonで解いた。Pythonのワンライナーで解けるような問題だとついつい楽してしまうなぁ。一方、C++だと力技が結構効いたりと、使い分けの重要性を再認識した。

少しコメント。Problem 14はここのブログの自己紹介にあるコードが使える。Problem 19は、C言語のFAQで有名な以下のコードが使える。

int day_of_week(int y, int m, int d) // 0 = Sunday { static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}; y -= m < 3; return (y + y / 4 - y / 100 + y / 400 + t[m - 1] + d) % 7; }

あとは、素数を扱う問題が多いからエラトステネスの篩を使うとちょっと楽になるかもしれない。

Python: クイックソート

Pythonクックブックに載っている3行クイックソート。

def qsort(L): if len(L) <= 1: return L return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + qsort([ge for ge in L[1:] if ge >= L[0]])

これは美しい。ぱっと見て(自分にとっては)意味がすぐに読み取れるところも素晴らしい。

さらに短く1行に。

q=lambda x:(lambda o=lambda s:[i for i in x if cmp(i,x[0])==s]:len(x)>1 and q(o(-1))+o(0)+q(o(1)) or x)()

打って変わって邪悪感が漂うコード。これは(自分にとっては)一目では意味が掴めない…。

ただし、どちらも実際のコーディングには用いるべからず。高速な組み込みのsortedを使うこと。

これらはすべてPythonクックブックから。こんな珠玉のコードのちりばめられたPython クックブック 第2版はPythonista必携の書といえる。



ところで自分はPythonクックブックの初版を(ついでに英語版も)持っているが、3行クイックソートのコードに意味不明な Ä という文字が入っている。これは \ の誤植。今の版では直っているのかな。

Python: PaSoRiでSuicaの履歴を読み出す・その後

以前、PaSoRiでSuicaの履歴を読み出すという記事を書いたけど、酷いバグを見つけた。物販で購入時の時刻を間違えるというもの。言い訳になるが、つい最近まで古いSuicaを使っていて、駅の自販機などでSuicaが使えず、テストしていなかったのだ。申し訳ない。

と云うわけで、修正したソースを公開しておく。バグだけ修正しても面白くないので、少し改良した。以前は残高しか出なかったが、使用した金額も併せて表示するようにした。また、以下に示す出力のように日時が先頭に来るように変更した。等々。

2008年xx月xx日 ○○駅 ××駅 540円 4160円 改札機 運賃支払(改札出場) 2008年xx月xx日 ○○駅 +2000円 6160円 券売機等 チャージ 2008年xx月xx日 xx時xx分xx秒 買物 120円 6040円 自販機 物販

以下、ソースコード。まだテストが足りないのでバグがあるかもしれない。見つけ次第、訂正する。

#!/usr/bin/env python # -*- coding: shift_jis -*- """ read_felica.py version 0.02 by nox Suicaの履歴を出力するプログラム. """ from ctypes import * POLLING_ANY = 0xffff POLLING_SUICA = 0x0003 POLLING_EDY = 0xfe00 SERVICE_SUICA = 0x090f SERVICE_EDY = 0x170f # 端末種 TERMINAL = {3: "精算機", 4: "携帯型端末", 5: "車載端末", 7: "券売機", 8: "券売機", 9: "入金機", 18: "券売機", 20: "券売機等", 21: "券売機等&…

Python: モンティ・ホール問題

モンティ・ホール(Monty Hall)問題とは以下のような問題のことだ。

「プレイヤーは、三つのドアを見せられる。ドアの一つの後ろにはプレイヤーが獲得できる車(アタリ)があり、一方、他の二つのドアには山羊(ハズレ)が入っている。ホストであるモンティは、それぞれのドアの後ろに何があるか知っているのに対し、もちろんプレイヤーは知らない。

プレイヤーはまず三つのドアの一つを選ぶ。次にモンティは他の二つのドアのうち一つを開け、山羊をみせる。そしてモンティはプレイヤーに、初めの選択のままでよいか、もう一つの閉じているドアに変更するか、どちらかの選択権を提供する。プレイヤーは、選択を変更すべきだろうか?」

(モンティ・ホール問題より一部修正)
続きを読む前に、まずは自分で正解を予想して頂きたい。
正解は、「ドアを変更すべき」なのだが、これに引っかかる人は多いらしい。10年ほど前にこの問題を聞いたときは、変更したほうが当たる確率が上がることに気が付いたが、ちょっと考えればそれは当たり前のようにも感じた。一緒に聞いていた人の一人は最後まで納得いかない様子で、こちらが即席で作ったのCのプログラムを実行してみせても信じようとはしなかった。

以下、Pythonでのプログラムを示す。

#!/usr/bin/env python # -*- coding: utf-8 -*- from random import choice DOORS = [1, 2, 3] # ドアの数. N = 1000 # 試行回数. win_picked, win_switch = 0, 0 for i in range(N): # ドアの一つに車を入れる. car = choice(DOORS) # ドアを選ぶ. picked_door = choice(DOORS) # 残りのドアで山羊の入っている方を開ける. open_door = choice(list(set(DOORS) - set([picked_door, car]))) # ドアを変更した場合. switch_door = choice(list(set(DOORS) - set([picked_door, open_door]))) # 車を…

Python: 続・簡単ステガノグラフィ…画像を画像に埋め込む

前回のなんちゃってステガノグラフィはあまりにも酷い出来だと思ったので、少しばかり改良してみた。画像データのアルファ値を利用していたのをRGBに置き換え、最下位ビットを利用する方法に変更した。アルファ値だと生データを見れば一発で怪しいと分かるが、RGBだと余程注意深くないと分からないだろう。また、入力データにはテキストだけではなく、バイナリファイルも指定できるようにした。ファイル名は保存されるので、隠したデータを取り出す際もファイル名の指定が不要だ。

使い方は前回と一緒。ただし、上記の理由で出力ファイルの指定はない。

で、上のネコの画像(kitten01.png)に下のモルモットの画像(guinea01.jpg)を隠してみる。

covgraph.py kitten01.png kitten01g.png guinea01.jpg

画像を隠し入れた画像(kitten01g.png)を下に示す。最初の画像と見た目はほとんど変わらない。

取り出すときは以下のようにする。

covgraph.py kitten01g.png

ステガノグラフィについての知識なんてほとんど持ち合わせていないので、これがどの程度有効かなんて分からないし、きっと世の中にはもっと効率の良いアルゴリズムなんかがあるのだと思うけど、気にしない。だってお遊びのプログラミングだから。作る過程でいろいろ考えることが楽しいのだ。

追記: 出力画像ファイルにはPNGかBMPを利用するのが良い。JPEGは非可逆圧縮により埋め込むデータが壊れるし、GIFはパレットの制限に引っ掛かるためだ。因みに、入力画像ファイルはどのフォーマットでも問題ないはず。また、このサイトはアップロードした画像を非可逆圧縮するので本記事の画像をそのまま利用してもデータを取り出すことはできません。

以下、ソース(covgraph.py)。

#!/usr/bin/env python # -*- coding: utf-8 -*- """covgraph.py by nox, 2008.4.17""" import sys, os, bz2, zlib from PIL import Image def embed_data(data, in_data, offset=0):…

Python: 簡単ステガノグラフィ…テキストを画像に埋め込む

Pythonでなんちゃってステガノグラフィを作ってみた。画像データにテキストを埋め込んで、メッセージを隠してしまうというわけだ。お遊びで適当に作っただけなので、本格的な使用に耐えうるものではないことをお断りしておく。

上に示す画像は何も埋め込まれていないもの。下に示す画像にはPython: PaSoRiでSuicaの履歴を読み出すの全文が埋め込まれている。

これなら変更したことを誰にも気づかれないだろう。使用したソース(covgraph.py)は下に示す。使い方は、

covgraph.py cover.png stego.png input.txt

とする。cover.pngにinput.txtの中身を埋め込み、stego.pngとして出力する。input.txtに代えて直接文字列を指定することもできる。

covgraph.py cover.png stego.png "hello, world"

とすれば、stego.pngには"hello, world"が埋め込まれることになる。

埋め込まれた画像からテキストを取り出す場合は、

covgraph.py stego.png

もしくは、

covgraph.py stego.png output.txt

とする。前者は標準出力、後者はファイルに書き出す。

追記: 今回のソースは書き殴りで汚いしアルゴリズムとしてもよくないと思うので、修正版のPython: 続・簡単ステガノグラフィ…画像を画像に埋め込むの方がましだと思う。

#!/usr/bin/env python # -*- coding: utf-8 -*- """covgraph.py by nox, 2008.4.15""" import sys, os, bz2, base64 from PIL import Image def cover(input_image, output_image, text_data): """テキストデータを画像ファイルに埋め込む. input_image: 入力画像ファイル. output_image: 出力画像ファイル(PNG等、アルファ画像…

WILLCOM D4 (WS016SH)

以前、こちらでもWillcomが新しいモバイルコミュニケーションマシンを開発という記事を書いたが、本日、その全容が明らかになった。

ウィルコム、Vista搭載の小型端末「WILLCOM D4」(ケータイWatchより)

PCと同等に使えるのは良い。いわゆる、UMPC(Ultra-Mobile PC)だね。問題はどれだけ快適に使えるかだなぁ。キビキビ・サクサク使えるなら買う価値ありかな。キーボードは難しいだろうから、ちゃんと使おうと思うならUSBキーボードをセットかな。逆に言えば、キーボードさえクリアすれば、プライベートでも仕事でもそれなりに使えるかも(もちろんサクサク動くこと前提)。あと携帯電話型のヘッドセットはカッコ良い。5月下旬に予約開始、6月中旬に発売らしい。

以下、主な仕様。

名称: WILLCOM D4 (WS016SH)
OS: Windows Vista Home Edition
CPU: Atom Z520(1.33GHz)
ディスプレイ: タッチパネル対応1,024×600ドット、262,144色、5インチワイドTFT液晶
メモリ: 1GB
40GB HDD
198万画素カメラ
microSDカードスロット装備
ワンセグサポート
W-OAM対応W-SIM
ワイヤレスLAN
USB端子(miniAB)
Office Word/Excel/PowerPoint
別売クレードル(外部ディスプレイ出力, オーディオ出力, LAN端子, 4ポートのUSB端子)

Google App Engine APIクイックリファレンス

Developer's Guideより。自分用メモ。

Datastore API: google.appengine.ext.db

Modelクラス: データモデルの定義を扱う基底クラス。
class Model(parent=None, key_name=None, **kw)クラスメソッドModel.get(keys)Model.get_by_id()Model.get_by_key_name(key_names, parent=None)Model.get_or_insert(key_name, **kwds)Model.all()Model.gql(query_string, *args, **kwds)Model.kind()Model.properties()インスタンスメソッドkey()put()delete()is_saved()parent()parent_key()to_xml()Expandoクラス: インスタンスが任意の属性を追加できるModelクラス。
class Expando(parent=None, key_name=None, **kw)Propertyクラス: データモデルのプロパティ定義を扱う基底クラス。
class Property(verbose_name=None, name=None, default=None, required=False, validator=None, choices=None)属性data_typeインスタンスメソッドdefault_value()validate(value)empty(value)get_value_for_datastore(model_instance)make_value_from_datastore(value)Queryクラス: データストアのクエリインターフェイス。
class Query(model_class)インスタンスメソッドfilter(property_operator, value)order(property)ancestor(ancestor)get()fetch(limit, offset=0)count(limit)GqlQueryクラス: GQLによるデータストアのクエリインターフェイス。
GqlQuery(query_string, *arg…

なぜGoogle App Engineは凄いのか?

Google App Engineがなぜ凄いのかを書いてみる。これを書くのは、自分用にGoogle App Engineでシンプルなユーティリティを作ったのだが、アカウントが取れなかったせいでまだ使えないから。気を紛らわしているだけなので、あまり深い意味はない。

閑話休題。まあ、Google App Engineはそこら中で凄い凄いと云われているから、なんとなく凄いんだろうなということは誰でも察していると思う。で、本当のところ、どこがどれだけ凄いのか。それを今から自分の解釈で書いてみる。もっとも、ウェブアプリについては素人同然の自分を物差しにしているので、人によってはその限りではないかも。

まず、準備がとてつもなく楽だということが凄い。今までは、何らかのウェブサービスを個人で始めようと思ったら、レンタルサーバから見つけなくてはならない。無料とは云わなくても適当なレンタルサーバでは環境すら整っていないことが多い。自分で整えようとしても制限が強く理想とするものを作り上げるのが難しかったりする。その点、Google App Engineでは何もしなくてよいのだ。

次に、アプリケーションを作る、その容易さが凄い。従来の環境であれば、アプリケーションの中身以外のところで苦労させられる。自分はこれをしたいのに、これをするにはまずはあれもそれも考慮しなくてはならない。以前、Pythonで簡単なアップローダを書いたことがあるが、やっぱりシンプルじゃない。拡張子がcgiってのも嫌だ(これはちょっと趣旨が違う)。その点、Google App Engineではしたいことだけ書く。シンプル。

最後に、Pythonが使えるということ(特に今はこれのみサポート)、そのパフォーマンスが凄い。個人的にはここが一番凄いところで、Google側が用意しているモジュールは非常に強力だ。もともとGoogleはPythonを自社システムで利用しているだけあって、その親和性は驚くほど高い。そしてPython自体による使い勝手の良さと、生産性の高さが、その効果をいやがうえにも高めてくれている。これでPython使いが増えるといいなぁ。←この記事でのホンネ。

ほかにも、至れり尽くせりな管理ツールだとか、世界最高レベルを誇るスケーラビリティだとか、その辺は凄いと思うのだが、実際に自分が体感しているわけじゃ…

Google App Engineでネコ化計画

Google App Engineが楽しい。ちょっと忙しいということもあって、まだほとんど触っていないんだけど、それでも簡単なお遊びウェブアプリを作ってみた。作るというのがおこがましいような落書きだけど。で、起動するとPython: ワンライナーでマンデルブロ集合を描くのページの文章をネコっぽくして、画像もネコの画像に置き換える。


以下に示すように、ソースコード(kitten.py)はいたってシンプル。アイデアさえあれば、大抵のことはできそうだ。まだアカウントがないので稼働できないけど。早く欲しいなぁ。

#!/usr/bin/env python # -*- coding: utf-8 -*- import re import wsgiref.handlers from google.appengine.api import urlfetch from google.appengine.ext import webapp class MainPage(webapp.RequestHandler): def get(self): result = urlfetch.fetch("http://handasse.blogspot.com/2008/04/python.html") if result.status_code == 200: content = re.sub("。|\&#12290;", "にゃ。", result.content) content = re.sub("な", "にゃ", content) img_list = re.findall('<img (?:.*)src="([a-zA-Z0-9\-/.:_]+)"', content) for img in img_list: content = re.sub(img, "images/kitten.jpg", content) self.response.out.…

Google App Engine

Google App Engineが面白そう。簡単に云うと、Googleをインフラとするウェブサービスで、すべてのリソースはGoogleに置かれる。利点としては、トラフィックやスケーラビリティの心配をしなくても良い、一度アプリケーションを書けばどこでも実行できる、Googleのサービスとの親和性が高いということだろう。現在のところベータ版であり、使用言語はPythonに限られる(これは自分にとっては嬉しいのだが)。

だがしかし、乗り遅れてしまった…。先着順に1万組が募集されたのだが早々に締め切られてしまった。とはいってもアプリケーションの開発はSDKをダウンロードすればできるけど。ちょっと遊んでみようかなぁ。

The Python Challenge全問制覇、そしてヒント集

ついにThe Python Challengeを全問(34問)解いた。これだけ面白いものには滅多に出逢えないだろう。3年近く?、長かったなぁ。まあ、期間は長かったけれど、度々中断してたので(数ヶ月から一年以上とか)、実際は3週間ぐらいかな? フォーラムPython Challenge Hintsには助けられたけど、逆に混乱することも。ちょっとしたひらめきが重要なので、本当は一緒に考えてくれる仲間が周りにいれば良かったと思うんだけど、残念ながらいなかったので一人で解いた。これから挑戦する方は、できるだけ複数人で解くことをお勧めする。Pythonの勉強にもなるし。三人寄れば文殊の知恵。

と云うわけで、ネタバレにならない程度…というか戯言程度のヒントを書いておく。これを読んで却って混乱しても責任は持てないので悪しからず。もし、ヒントについての質問などがあれば本記事のコメントでお願いしたい。返答は問題をスポイルしない程度(多分、フォーラム程度)になると思う。

以下、ヒント集。読むのは詰まったときに。

level 0: 238じゃない。もっと大きい。

level 1: 手で変換は面倒だ。

level 2: 読めないものは読まなくていいよね。

level 3: でかいのが周りにいると自分が小さく感じる。

level 4: そりゃ、手で書いていたら疲れるね。

level 5: 笛鳴らしてから蹴る…かな?

level 6: 日本語だとチャックだよね。

level 7: PILの出番です。

level 8: 忙しい?

level 9: 子供の頃にやったなぁ。

level 10: 数え方。

level 11: 1と2、3と4…

level 12: 何人に配ろうか。

level 13: 悪者をコールしろ。

level 14: ぐるぐる。

level 15: 何年何月何日?

level 16: あれに見えるはピンクじゃないか?

level 17: クッキーには2種類ある。美味しいクッキーと美味しくないクッキーだ。

level 18: 違うのだよ。

level 19: 何で謝るの? 聴けば分かる。

level 20: 中に入りたいのだが…

level 21: 包みを回せ!

level 22: よく見ると見える?

level 23: どのモジュール?

level 24: 迷いそうだ。

l…

Python: ワンライナーでマンデルブロ集合を描く

Pythonでマンデルブロ集合(Mandelbrot Set)を描いてみた。ただ、描くだけではつまらないので、ワンライナー(1行プログラム)で書いてみた。Pythonでワンライナーってのは邪悪以外のナニモノでもないと思うので、まともな方はまねしないほうがいいかと。

ワンライナーにしたと云ってもスクラッチからではなく、Python FAQで有名なワンライナーのマンデルブロ集合を流用させてもらった。ただ、オリジナルのものはアスキー文字で表現していたのでPython Imaging Library (PIL)を利用してグラフィカルなものに修正した。もし、PILが入っていないようなら、それはPythonistaの名折れだと思う。コマンドラインで以下の通りに実行すればOK。

python -c "import Image,math;im=Image.new('L',(480,480));im.fromstring((lambda Ru,Ro,Iu,Io,IM,Sx,Sy:reduce(lambda x,y:x+y,map(lambda y,Iu=Iu,Io=Io,Ru=Ru,Ro=Ro,Sy=Sy,L=lambda yc,Iu=Iu,Io=Io,Ru=Ru,Ro=Ro,i=IM,Sx=Sx,Sy=Sy:reduce(lambda x,y:x+y,map(lambda x,xc=Ru,yc=yc,Ru=Ru,Ro=Ro,i=i,Sx=Sx,F=lambda xc,yc,x,y,k,f=lambda xc,yc,x,y,k,f:(k<=0)or (x*x+y*y>=4.0)or 1+f(xc,yc,x*x-y*y+xc,2.0*x*y+yc,k-1,f):f(xc,yc,x,y,k,f):chr(256-int(math.sqrt(F(Ru+x*(Ro-Ru)/Sx,yc,0,0,i))*256/math.sqrt(i))),range(Sx))):L(Iu+y*(Io-Iu)/Sy),range(Sy))))(0.383,0.384,0.2337,0.2347,800,480,480));im.save('m.gif');im.show()"

これで、最初に示した画像を画面に出力し、m.gifという画像ファ…