2008年5月31日土曜日

Google App Engine: アプリ作成のためのSMSによる認証ができない?

このブログ記事をはてなブックマークに追加

Carriers currently experiencing issuesに書かれているけど、携帯電話のSMS(ショートメッセージサービス)によるアプリ作成のための認証が、DoCoMoとauでできないようだ。ソフトバンクも一部できないらしい。Willcomはできるみたい。

Google側も認識しているようだから近いうちに何とかすると思うけど。

続きを読む...

2008年5月30日金曜日

Google App Engine: Images APIとMemcache API

このブログ記事をはてなブックマークに追加

新しいAPIが二つ増えた。どちらも開発者にとっては欲しかったAPIだろう。どちらも基本的な機能のみを提供するものだが、多くの場合それで事足りるかもしれない。個人的にはImages APIはもっと高機能にして欲しかったのだが。また、これに合わせて、以前書いたGoogle App Engine APIクイックリファレンスも更新しておいた。

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

Images APIでは、画像のサイズ変更、回転、水平・垂直反転、部分抜き出しなどができる。面白い機能として、I'm Feeling Luckyというものがあり、暗い部分と明るい部分の自動調節を行う。因みに、開発環境でImages APIを用いる場合は、あらかじめPIL(Python Imaging Library)をインストールしておかなければならない。ただし、Google App Engineで直接PILを使えるわけではない。

Memcache APIは高性能な分散型メモリキャッシュシステムだ。指定のキーが存在するかどうかで、キャッシュの確認を行う。サーバへの負荷も減り、応答も非常に高速になるため使わない手はない。

どちらのAPIもシンプルだが、小気味いい使い方ができそうだ。

続きを読む...

2008年5月28日水曜日

Google App Engine: 簡易掲示板を作ってみた

このブログ記事をはてなブックマークに追加

公開しているウェブサイトの掲示板のスパムが酷くしばらく書込み禁止にしている。そのため、ソースコードを表示できるシンプルな簡易BBSが必要となったので、Google App Engineで作ってみた。チュートリアルのゲストブックに毛が生えたようなものだが、自分の目的には取り敢えず適っているし、これからいろいろと肉付けしていけばいいかな。

チュートリアルのゲストブックではまず長い文章が入れられないし、名前が強制的にGoogleアカウントになるし、日時の表示がないし、なによりもソースコードやリンクの表示ができない。それに、一つのデータベースで複数の掲示板を使いたいが、このままでは無理。

で、やったこと。

・ソースコードのインデントや空白などを崩さずに表示。
・リンクのサポート。
・StringPropertyからTextPropertyにして長文をサポート。
・Googleアカウントでログインするが名前は自由に変更でき、再ログイン時には前回使った名前を表示。
・匿名での投稿ができる。ついでに、禁止もできる。
・URLにIDをつけて複数の掲示板が使える。
・日時の表示。

などなど。あとは、投稿のプレビュー、削除、検索、それに例外処理などを実装すればよいかな。検索はちょっと面倒そうだけど、ほかは簡単だろう。ところで、日時の表示では、日本標準時にするために webapp.template.create_template_register と webapp.template.register_template_library でフィルターを作ってみたんだけど、何故かうまく行かなかった。何か間違っていたかな?

と云うわけで、ここのブログのサイドメニューにメッセージボードを入れておく。不具合の報告、意見や要望などに、是非ご利用を。

以下、構成とソースコード。

アプリケーション名をmessagesとすると、まず、messagesディレクトリにmessages.py, index.html, app.yamlを置く。messages/static/stylesheets に main.css を置く。あとは、appcfg.py update messages を実行すればよい。また、messages.pyの先頭に記述されている、TITLE, LIMIT, ANONYMOUS変数を変更することで、掲示板の追加、最大表示件数、匿名の書き込みの許可・不許可を設定できる。

app.yaml

application: messages version: 1 runtime: python api_version: 1 handlers: - url: /stylesheets static_dir: static/stylesheets - url: /.* script: messages.py

messages.py

#!/usr/bin/env python # -*- coding: utf-8 -*- """ 簡易メッセージボード(掲示板) version 0.02 α版 Copyright (C) 2008 nox """ # 許可するメッセージボードおよびそのタイトル TITLE = { "test": "テスト用メッセージボード" } # 最大表示件数 LIMIT = 50 # 匿名の書き込みを許可 ANONYMOUS = False import os, cgi, re, urlparse, datetime import wsgiref.handlers from google.appengine.api import urlfetch from google.appengine.api import users from google.appengine.ext import webapp from google.appengine.ext import db from google.appengine.ext.webapp import template class MainPage(webapp.RequestHandler): def get(self): self.response.out.write(u""" <html> <head> <title>メッセージボード一覧</title> </head> <body> <div><a href="message?id=test">テスト用メッセージボード</a></div> </body> </html>""") # メッセージボード class Message(db.Model): id = db.StringProperty(multiline=False) author = db.UserProperty() username = db.StringProperty(multiline=False) content = db.TextProperty() date = db.DateTimeProperty(auto_now_add=True) admin = db.BooleanProperty() num = db.IntegerProperty() class MessageBoard(webapp.RequestHandler): def get(self): global TITLE, LIMIT, ANONYMOUS id = self.request.get("id") if id not in TITLE.keys(): return messages = Message.all().order("-date").filter("id =", id).fetch(LIMIT) user = users.get_current_user() messages_current_user = Message.all().order("-date").filter("id =", id).filter("author =", user).fetch(LIMIT) if user: if messages_current_user and messages_current_user[0].username: current_username = messages_current_user[0].username if re.search("<span style=\"color: blue;\">(.*)</span>", current_username): username = re.sub("<span style=\"color: blue;\">(.*)</span>", "\g<1>", current_username) else: username = current_username else: username = user.nickname().replace("@", ".") url = users.create_logout_url(self.request.uri) url_linktext = "Logout" else: if ANONYMOUS: username = "匿名" else: username = "" url = users.create_login_url(self.request.uri) url_linktext = "Login" template_values = { "id": id, "title": TITLE[id], "username": username, "messages": messages, "url": url, "url_linktext": url_linktext, } path = os.path.join(os.path.dirname(__file__), "index.html") self.response.out.write(template.render(path, template_values)) class PostMessage(webapp.RequestHandler): def insert_whitespace(self, matchobj): return re.sub("(?<!<br) ", "&nbsp;", matchobj.group(0).replace("\t", " ")) def post(self): message = Message() message.id = self.request.get("id") if not self.request.get("content").strip(): self.redirect("/message?id=%s" % message.id) return if users.get_current_user(): message.author = users.get_current_user() if self.request.get("username").strip(): message.username = self.request.get("username").strip() else: message.username = message.author.nickname().replace("@", ".") message.content = cgi.escape(self.request.get("content").strip()) message.content = re.sub("\r\n|\r|\n", "<br />", message.content) message.content = re.sub("\[link\](.*)\[/link\]", "<a href=\"\g<1>\">\g<1></a>", message.content) message.content = re.sub("\[code\](.*)\[/code\]", self.insert_whitespace, message.content) message.content = re.sub("\[code\](.*)\[/code\]", "<span style=\"font-family:courier new,monospace;font-size:85%;white-space:pre;color:#0000ff;\">\g<1></span>", message.content) message.admin = users.is_current_user_admin() message.date = message.date + datetime.timedelta(hours=9) max_num_mes = Message.all().order("-date").filter("id =", message.id).fetch(1) if max_num_mes: message.num = max_num_mes[0].num + 1 else: message.num = 1 message.put() self.redirect("/message?id=%s" % message.id) def main(): application = webapp.WSGIApplication([("/", MainPage), ("/message", MessageBoard), ("/message/post", PostMessage)], debug=False) wsgiref.handlers.CGIHandler().run(application) if __name__ == "__main__": main()

index.html

<html> <head> <link type="text/css" rel="stylesheet" href="/stylesheets/main.css" /> <title>{{ title }}</title> </head> <body> <div> <div style="font-weight: bold; font-size: large; padding-bottom: 20px;">{{ title }}</div> {% if username %} <b>{{ username }}</b> さん、こんにちは。 {% else %} こんにちは。書き込みする場合は<a href="https://www.google.com/accounts/">Googleアカウント</a>でログインしてください。 {% endif %} [<a href="{{ url }}">{{ url_linktext }}</a>] </div> {% if username %} <form action="/message/post" method="post"> <div><textarea name="content" rows="5" cols="60"></textarea></div> <div><span style="font-size:70%;color:#666666;">リンク: [link]~[/link], ソースコード: [code]~[/code]</span><br />名前: <input type="text" name="username" size="31" maxlength="255" value="{{ username }}"></input> <input type="submit" value="書き込み"><br /><span style="font-size:70%;color:#666666;">名前を省略した場合はGoogleアカウントのニックネームが表示されます。</span> <input type="hidden" name="id" value="{{ id }}"></div> </form> {% else %} <br /> {% endif %} <div> {% for message in messages %} {% if message.author %} {{ message.num }}. <b>{% if message.admin %}<span style="color: blue;">{{ message.username }}</span>{% else %}{{ message.username }}{% endif %}</b> さんは{{ message.date.year }}年{{ message.date.month }}月{{ message.date.day }}日{{ message.date.hour }}時{{ message.date.minute }}分{{ message.date.second }}秒に書きました: {% else %} {{ message.num }}. 匿名さんは{{ message.date.year }}年{{ message.date.month }}月{{ message.date.day }}日{{ message.date.hour }}時{{ message.date.minute }}分{{ message.date.second }}秒に書きました: {% endif %} <blockquote>{{ message.content }}</blockquote> {% endfor %} </div> <!-- ここより下は変更しないでください。不具合やご意見などがありましたら、下記のnoxのリンク先で報告していただけると嬉しいです。 --> <div><img src="http://code.google.com/appengine/images/appengine-silver-120x30.gif" alt="Powered by Google App Engine" /><br /><span style="font-size:70%;color:#666666;">Copyright &copy; 2008 <a href="http://handasse.blogspot.com/">nox</a>. All rights reserved.</span></div> </body> </html>

main.css

body { color: rgb(20%, 20%, 20%); background-color: rgb(95%, 95%, 95%); font-family: Verdana, Helvetica, sans-serif; font-size: small; margin-left: 10px; margin-right: 10px; } div { line-height: 1.4em; }

続きを読む...

2008年5月26日月曜日

WILLCOM 03はどうかな?

このブログ記事をはてなブックマークに追加

ウィルコムからAdvanced/W-ZERO3[es](アドエス)の後継機、WILLCOM 03が発表された。アドエスでは思ったよりも性能面(機能面ではない)の改善が感じられなくてがっかりしたのだが、今回はどうだろうか。

GIGAZINEのスマートフォン「WILLCOM 03」速攻ムービーレビューを見る限り、かなりサクサク動きそう。これはちょっと食指が動く。正直、WILLCOM D4よりもこちらのほうが興味がある。もちろん、それぞれ使う用途が異なるのだが、とにかく端末がサクサク使えることを最も重要視する自分には、Vista搭載でサクサク動くとは思えないD4に対しては興味が薄れつつある。

アドエスよりもさらに小さく・軽くなっている点も良い。とは云え、もう少し情報が出てこないことにはまだ判断できない。因みに発売は6月下旬らしい。

続きを読む...

Google App Engine: parser_cacheエラー

このブログ記事をはてなブックマークに追加

Issue 205: AttributeError: 'module' object has no attribute 'parser_cache'

だそうで、最新版のGoogle App Engine SDKでチュートリアルすら動かなくなるバグがある。ちなみに、公式サイトのバグリストではVistaで動かないと書いてあるけど、こちらのXpの環境でも動かなかった。

File "C:\Program Files\Google\google_appengine\google\appengine\tools\dev_appserver.py", line 2116, in _ClearTemplateCache template_module.parser_cache.clear() AttributeError: 'module' object has no attribute 'parser_cache'

こんな感じのエラーが出るが、

C:\Program Files\Google\google_appengine\google\appengine\tools\dev_appserver.py

の2116行目をコメントアウトすれば良い。

続きを読む...

2008年5月24日土曜日

Project Eulerを120問解いてみた

このブログ記事をはてなブックマークに追加

ちまちまとProject Eulerを進めているが、さすがにペースが落ちている。今回は問題88が難しかった。しかし、同じように難しかった問題177と違って、いろいろとアルゴリズムを考え出して最後にスパッと解けたので気持ちがよかった。問題177は最初にやり方はわかったけど、途中の組み立てとフィルターに苦労したので解けたときの充実感よりも疲れのほうが大きかった。

ここまで1ヶ月弱かぁ。結構かかるなぁ。現在、195問中120問解いた。世界ランクで24451人中387位、日本人の中では257人中15位。

問題88は、今回もっとも苦労した問題だ。最初はまともに数え上げようと思ったが、それではまったく埒が明かないことにすぐ気付き、別の方法を考えることに。4~5つのアルゴリズムを考え、最後に思いついた方法でやっと解けた。実行時間約8秒はまあ許容範囲だろう。

問題90は組合せの問題。条件が少し変わっているけど、それに気をつければ問題ないかな。

問題93は逆ポーランド記法を使って解いたのだけど、何故か解が二つに。一方が正解だったのだけど、どこか間違えたかな? フォーラムにも自分と同じ結果になっている人がいた。

問題95は100万まで考えるのが大変だったので途中までの解を入れたら正解だった。後でフォーラムで勉強しておこう。

問題96の解き方はすぐに浮かんだけど、実装がちょっと面倒だった。実行時間は約3秒。

問題98は最初にペアグループを作ったけど、ペア自体はそんなに多くない。アナグラム解析は力技で約20秒。

問題103はあるルールに従った数のグループを扱う問題。問題105と問題106も同様の問題。これは力技で解いたので実行時間がかかった。この解き方では問題105と106は難しい。

問題104はPythonで解いた。でかい数を扱うときはPythonがやはり楽。頭とおしりだけを考えればよい。

問題105は問題103と同様の問題。与えられた数列がルールに従っているか調べる。良さそうなアルゴリズムを思い付いたので実行時間は短かった。

問題106は問題103をもう少し難しくしたもの。問題105で使ったアルゴリズムで1秒かからなかった。

問題107は最小木問題。アルゴリズムを知らなかったのでちょっと苦労した。

問題108はアルゴリズムを考え付くまでちょっとかかった。同種の問題110より簡単な問題。

問題109は正解者が少なめだから気合を入れて臨んだが簡単だった。問題文が長いから敬遠しているのかな。

問題110は苦労した。ある程度推測を立ててやらないと解けなかった。

問題111は計算時間が結構かかったかも。

問題113はハッシュで解いて15ミリ秒で解けたと喜んでみたけど、単なる組合せの問題だと知ってショック。

問題118は順列で解いた。約6秒なので許容範囲か。

問題119はPythonで素直に解いた。約1秒。

問題120はある規則を見つければそんなに難しくない。

問題185は解いたは解いたけど実行時間1時間以上ってのは酷すぎる。フォーラムで勉強しよう…。

続きを読む...

Facebookに登録してみた

このブログ記事をはてなブックマークに追加

日本語版がリリースされたということでFacebookに登録してみた。実は、mixiを含めいくつかのSNSに加入しているのだが、現在はほとんど利用してない。以前はあるSNSを結構利用していて、そこのブログも毎日更新し、それなりに好評だったのだが、半年ほどでやめてしまった。確かにブログの更新やそれに対するコメントなどは楽しかったのだが、多忙であったり、別のことに興味が移ってしまったりでそれきりと云う感じである。別に義務感などは持っていなかったし、書き込みに疲れたというわけではないのだが。

続きを読む...

2008年5月21日水曜日

Google App Engineへの招待状がやっと来た

このブログ記事をはてなブックマークに追加

Google App Engineへの申し込みを4月9日の未明に行って、一昨日やっと招待状が届いた。かなり気持ちが萎えていたのだが、これでまたやる気が出てきた。と云うことで早速アプリケーションの登録を行ってみた。

appcfg.py update app_name

とするだけで完了。簡単だ。登録したアプリはどれも単純なものだが、自分にとっては有用なツールだ。一つはテキスト(特にプログラムのソースなど)をウェブで表示できるように文字を変換するツールであり、もう一方はBase64やuuencodeなどのエンコード・デコードを行ってくれるユーティリティだ。

HTMLの文字変換はソースコードなどをこのブログに投稿する際に必要なのだが、自分好みのツールがなかった。コピー&ペーストを使っているので、コマンドラインでは使いづらいし、わざわざツールを起動するのも億劫だ。しかも、それらがインストールされている環境でないと使えない。なので、ウェブで公開されているツールを利用させてもらっていたのだが、表示部分が狭かったり、装飾過多だったりで、あまりシックリ来るものがなかった。そこで、Google App Engineで作ったというわけだ。広告も装飾もなくシンプルで快適に動作する。

また、テキストのエンコードについては、別に秘密ではないが一目ではそれと分からなくしたいテキストに利用する。たとえば、メールアドレスなどに。しかし、エンコードしたテキストをデコードする場合、手元にデコーダがなければ変換できない。ウェブにはそのためのツールがいくつもあるが、重かったり、装飾過多だったり、使いづらかったりで目的に適ったものを見つけられなかった。今回のツールがあれば、相手に R29vZ2xlIEFwcCBFbmdpbmU= のようなエンコードしたメッセージを送ったり、ブログに書き込んだ場合などでも、ここでデコードしてねと云うだけで済むわけだ。

このように、Google App Engineはあたかも個人でシェルスクリプトを作るかのように、ウェブアプリを作成できる。自分にとってこの点がGoogle App Engineの最大の魅力だ。まあ、単純なプログラムだけでは物足りないのでそのうちある程度のアプリを作るかも。アイデアは二つ三つあるけど、時間が取れるかなぁ。

おまけ。

ネコ化計画

以前、ここのブログでGoogle App Engineでネコ化計画という記事を書いた。で、それもついでに公開しておく。もっとも、完成度は低いのでうまく変換できないかもしれないが、悪しからず。

続きを読む...

2008年5月14日水曜日

C++: vector<vector<int> >などの入れ子のSTLコンテナをソートする

このブログ記事をはてなブックマークに追加

vectorクラスやlistクラスなどの入れ子になったSTLコンテナ(vector<vector<int> >など)をソートするやり方。algorithmのsortで可能。ここでは、普通の昇順と降順、和、積、二乗の和の昇順についてソースを示す。基本的には比較関数さえ用意すればどんなソートにでも対応できる。

#include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <functional> using namespace std; // 入れ子のコンテナの表示関数. void print_list(const vector<vector<int> >& v_list) { for (vector<vector<int> >::const_iterator p = v_list.begin(); p != v_list.end(); ++p) { for (vector<int>::const_iterator q = p->begin(); q != p->end(); ++q) cout << *q << " "; cout << endl; } } // 和の比較関数. template<class T> bool less_summation(const vector<T>& a, const vector<T>& b) { return accumulate(a.begin(), a.end(), 0) < accumulate(b.begin(), b.end(), 0); } // 積の比較関数. template<class T> bool less_product(const vector<T>& a, const vector<T>& b) { return accumulate(a.begin(), a.end(), 1, multiplies<T>()) < accumulate(b.begin(), b.end(), 1, multiplies<T>()); } // 二乗の和の関数オブジェクト. template<class T> class add_square : public binary_function<T, T, T> { public: result_type operator()(first_argument_type a, second_argument_type b) { return a + b * b; } }; // 二乗の和の比較関数. template<class T> bool less_add_square(const vector<T>& a, const vector<T>& b) { return accumulate(a.begin(), a.end(), 0, add_square<T>()) < accumulate(b.begin(), b.end(), 0, add_square<T>()); } int main() { vector<int> v; vector<vector<int> > v_list; // 10個の数値の入ったコンテナ(v)を5つ含むコンテナを作成(v_list). for (int i = 0; i < 5; i++) { v.clear(); for (int j = i; j < i + 10; j++) v.push_back(j % 2 == 0 ? j : -j); // 交互に正と負とする. v_list.push_back(v); } cout << "昇順" << endl; sort(v_list.begin(), v_list.end()); print_list(v_list); cout << "降順" << endl; sort(v_list.begin(), v_list.end(), greater<vector<int> >()); print_list(v_list); cout << "和の昇順" << endl; sort(v_list.begin(), v_list.end(), less_summation<int>); print_list(v_list); cout << "積の昇順" << endl; sort(v_list.begin(), v_list.end(), less_product<int>); print_list(v_list); cout << "二乗の和の昇順" << endl; sort(v_list.begin(), v_list.end(), less_add_square<int>); print_list(v_list); return 0; }

以下のように表示される

昇順 -3 4 -5 6 -7 8 -9 10 -11 12 -1 2 -3 4 -5 6 -7 8 -9 10 0 -1 2 -3 4 -5 6 -7 8 -9 2 -3 4 -5 6 -7 8 -9 10 -11 4 -5 6 -7 8 -9 10 -11 12 -13 降順 4 -5 6 -7 8 -9 10 -11 12 -13 2 -3 4 -5 6 -7 8 -9 10 -11 0 -1 2 -3 4 -5 6 -7 8 -9 -1 2 -3 4 -5 6 -7 8 -9 10 -3 4 -5 6 -7 8 -9 10 -11 12 和の昇順 4 -5 6 -7 8 -9 10 -11 12 -13 2 -3 4 -5 6 -7 8 -9 10 -11 0 -1 2 -3 4 -5 6 -7 8 -9 -1 2 -3 4 -5 6 -7 8 -9 10 -3 4 -5 6 -7 8 -9 10 -11 12 積の昇順 4 -5 6 -7 8 -9 10 -11 12 -13 -3 4 -5 6 -7 8 -9 10 -11 12 2 -3 4 -5 6 -7 8 -9 10 -11 -1 2 -3 4 -5 6 -7 8 -9 10 0 -1 2 -3 4 -5 6 -7 8 -9 二乗の和の昇順 0 -1 2 -3 4 -5 6 -7 8 -9 -1 2 -3 4 -5 6 -7 8 -9 10 2 -3 4 -5 6 -7 8 -9 10 -11 -3 4 -5 6 -7 8 -9 10 -11 12 4 -5 6 -7 8 -9 10 -11 12 -13

二乗の和の比較は以下のように変更しても同じ結果となる。

return inner_product(a.begin(), a.end(), a.begin(), 0) < inner_product(b.begin(), b.end(), b.begin(), 0);

続きを読む...

C++: STLコンテナの数値の和、積および二乗の和を求める

このブログ記事をはてなブックマークに追加

vectorクラスやlistクラスなどのSTLコンテナで数値リストの和や積をともめる場合、numericのaccumulateを使う。積などの関数オブジェクトを利用する場合はfunctionalも使う。二乗の和の求め方も示す。

#include <iostream> #include <vector> #include <numeric> #include <functional> using namespace std; // 二乗の和の関数オブジェクト. template<class T> class add_square : public binary_function<T, T, T> { public: result_type operator()(first_argument_type a, second_argument_type b) { return a + b * b; } }; int main() { vector<int> v(5, 3); // 数値3が5つ入ったvectorクラス. // 和. cout << "3 + 3 + 3 + 3 + 3 = "; cout << accumulate(v.begin(), v.end(), 0) << endl; // 積. cout << "3 * 3 * 3 * 3 * 3 = "; cout << accumulate(v.begin(), v.end(), 1, multiplies<int>()) << endl; // 二乗の和. cout << "3^2 + 3^2 + 3^2 + 3^2 + 3^2 = "; cout << accumulate(v.begin(), v.end(), 0, add_square<int>()) << endl; return 0; }

以下のように表示される。

3 + 3 + 3 + 3 + 3 = 15 3 * 3 * 3 * 3 * 3 = 243 3^2 + 3^2 + 3^2 + 3^2 + 3^2 = 45

因みに、二乗の和では関数オブジェクトを使わずに以下のように内積を求めるinner_productでも同じ結果を得ることができる。ただし、三乗の和や対数の積など、任意の計算をしたい場合は、素直に関数オブジェクト作成してaccumulateを利用した方がスマートだと思う。

inner_product(v.begin(), v.end(), v.begin(), 0);

続きを読む...

2008年5月12日月曜日

Project Eulerを100問解いてみた

このブログ記事をはてなブックマークに追加

相変わらずProject Eulerを解いている。これまでは連続して問題を解いていたのだが、今回からはバラバラになってしまった。別に途中に解けない問題があったわけではなく、後半の問題を眺めたところ面白そうな問題が目に付いてしまって、それに手を付けてしまったのだ。具体的には問題188のテトレーションの問題。以前、ここのブログでも虚数のテトレーションというテーマでテトレーションを扱ったことがある。そこで、i がある値に収束するのを発見したのだが、何か意味があるのあるのかな?

今回から順番を気にしないことにしたが、だからと云って簡単そうな問題ばかり手をつけても面白くない。どうせなら一番難しいそうな問題を解いてみようということで、問題177を解いてみた。最近追加された2問を除くと、正解者が100人を切っている唯一の問題だ。自分が解いたときは全体で87番目の正解者だった。一番難しそうな問題を解いて今後の弾みにしようかと考えていたのだが、このレベルの問題ばかりだとさすがにへこたれそうだ…。

現在、193問中100問を解いた。世界ランクで24217人中608位。日本人の中では235人中20位。

問題81問題82問題83はすべてダイクストラ法であっという間。ダイクストラは偉大だ。

問題84は、モノポリーで止まるマスの確率を求める問題。そんなに難しくないけど、正解者は少なめ。面倒だからかな。

問題85は、マスに填まるすべての四角形を数え上げる問題。普通に数えれば解ける。

問題86は、ちょっと考えたけど、解き方がわかれば計算量は僅か。正解者少なめ。

問題87は難しくない。調べる数はそれほど多くないことに気づくはず。

問題89はそんなに難しくないはずなのだけど、間抜けなところでちょっとはまった。IIXが8であると疑わなかったよ…。

問題91は、まともに全部数え上げた。もっと効率のよい方法があると思う。

問題92は簡単。

問題94は結構苦労したな。計算時間が長かった。これはもっと改良せねば。ピタゴラス数を普通に使うだけではダメだ。

問題97は簡単。この手の問題はどれもそうだけど、最後の必要な桁数だけ計算すればよい。

問題99は簡単すぎる。log使え。

問題100はちょっと悩んだ。いろいろいじっているとある数列が浮かび上がったので、それをもとに解いた。有名な数列みたい。

問題101は、問題を把握するのが面倒だった。連立一次方程式を解けば良い。行列演算使えば簡単。SciPyは偉大だなぁ。誤差には注意。

問題102は簡単。なはずなんだけど思ったより時間がかかった。高校数学やり直しだな、こりゃ。

問題112は、問題文が分かりにくかったな。要は数字が降順でも昇順でもない数を数え上げるだけ。

問題123は、Pythonで楽して解いた。

問題177は難問かと。細心の注意が必要なので、自分のように疲れている時にやらない方が無難。一日かかったよ。考え方自体はすぐに浮かんで実際それで正しかったのだけど、適当にコーディングするとはまる。

問題188は、一連の問題を順不同に解く切っ掛けとなった問題。テトレーション(tetration)を扱っている。なんていうかテトレーションにはロマンのようなものを感じる。変?

それにしても最近はProject Eulerばかり扱っているな。本当はGoogle App Engineなどもいじりたいのだけど、未だに招待状が来ない。アプリはいくつか作っているのに…。いい加減、やる気が削がれるなぁ。

写真は問題を解いたときのメモ書きの一部。ペンと紙さえあればなんとかなるかも?

続きを読む...

2008年5月7日水曜日

Project Eulerを問題80まで解いてみた

このブログ記事をはてなブックマークに追加

Project Eulerを前回からちまちまと続けている。連休中は忙しくてあまりできなかったが、それでも合間合間の時間を使って紙と鉛筆でも考えることはできるので、頭の体操にはちょうど良い。前回、結構簡単だと書いたのだが、50問を超えるあたりから難しめの問題が入ってきた。一つ解くのに30分以上かかることもざらだ。計算自体はすぐに終わるのが多いが、いくつかは結構時間がかかってしまった。特に問題60では10分弱かかかってしまう。フォーラムなどを読むと、1秒かからない人もいるので、やはりアルゴリズムが決定的だ。現在192問中80問を解いた。

問題51は素数に関わる問題だけど、数字をいじる問題は結構好きかも。

問題52は数字の並べ替え。

問題53は組み合わせの問題。これは簡単かな。

問題54はポーカーの勝敗判定のプログラム。この手のコードはよく組むけど好きなわけではない。面倒なだけで難しくはない。

問題55も数字をいじる問題。

問題56は数がでかいが、ただそれだけ。

問題57は連分数に関する問題。連分数に関する問題の中では序の口。

問題58は結構数が大きくなった。

問題59は簡単。

問題60は素数で数字を操作する問題なので結構好きだ。でも解くのは結構大変だった。

問題61は素直に解くだけ。

問題62は普通に解いたかな。数字系。

問題63は簡単だった。

問題64~66までは連分数に関する問題。連分数は頭が疲れる…。

問題66が連分数に関する問題なのを知ってちょっと面白かった。

問題68は解いている人がこのあたりの問題の中では少ないから難しいのかと思ったら簡単だった。何も特別なこともしていないし何でだろう? 因みにこの手の図形的な問題も好み。

問題69~73まではオイラーのφ関数に関する問題。解き方がわかればそんなに難しくはないかも。わからないと時間が足りない。

問題74は簡単だった。

問題75ピタゴラス数の問題。解き方はわかったのだけど、変なところでバグをつぶすのに手間取った。

問題76は苦労した。計算時間も結構かかった。フォーラムで知ったのだが、Partition Function P(分配関数)による解法があるようで、これ使ったら一瞬で終わった。凄い。

問題77は76の応用。だけど、76で自分で考えた関数だとコードをほんのちょっといじるだけで解けた。計算時間も一瞬。個人的には76より簡単だった。

問題78も分配関数の問題。これ、計算時間的に結構大変なのですぐに解ける別の方法があるのかと考えたのだが、結局力技で解いた。

問題79は簡単。

問題80開平法を使うだけ。

ここまでは虫食いになるのがいやで順番に解いてきたが、そろそろ難しくなってくるかも。まだ半分も行ってないしなぁ。今までのところ、前回同様にC++メインで解いている。でかい数字が面倒な時だけPythonかな。GMPあたりを使えばよいのだろうけど、何となく標準ライブラリにこだわっている。

続きを読む...