アルゴリズムの問題にチャレンジ!
本記事は @_tanzaku_氏主催の、Competitive Programming Advent Calendar の記事です。
簡単な問題を作問したので、出題してみます。
ぜひチャレンジしてみてください!
Problem Statement
今年もクリスマスの季節がやってきた。クリスマスと言えばアドベントカレンダー。アドベントカレンダーとは、12月1日から、クリスマスの12月25日まで毎日窓を開けていくカレンダーのことである。それにちなんで、アドベントカレンダーイベントでは、参加者は一人一日ずつブログ記事を発表する。最初の参加者は12/1に、次の参加者は12/2に、といったように、a人目の参加者は12/a日(1 <= a <= 25)に記事を発表する。
あなたは競技プログラミングをテーマとしたアドベントカレンダーイベントを主催することにしたが、この企画は大変人気を博し、参加希望者数が25名を上回った。だが、なるだけ多くの人に参加してほしいとの思いから、1日に2つ以上の記事ができてもよいことにし、希望者全員が参加できるようにした。ここであなたは、各参加者を(各々が記事を発表する日である)1つの日付に割り当てなければならない。
ここで、あなたのタスクは参加者を適切に割り当てることでこのイベントにおける「(12/1から12/25までの中で)一日に発表される最大記事数」を最小化し、その値を出力するプログラムを書くことである。なお、参加者の中には「特定の日付以降に割り当てて欲しい」と言う者もいる。イベントの主催者であるあなたはすべての参加者の希望を満たすように割り当てを行う必要がある。
Input
入力は次のようなデータセットから構成される。
n x1 x2 ..... xn
各データセットは n という正の整数から始まり、 1 <= n <= 1000 と仮定して良い。nはイベントの参加者数を表す。nの次の行には参加者データが続き、これらが各参加者の情報を表している。参加者データは半角スペース区切りの xi(1 <= xi <= 25) という正の整数n個で表され、この参加者は「xi日目以降に割り当てて欲しい」ことを示す。入力の終わりは 0 で表す。
入力の各データセットに対して、「一日に発表される最大記事数の最小値」を1行に出力せよ。
Sample Input
26 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 29 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 25 25 25 25 31 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20 20 20 20 20 1 25 0
Expected Output for Sample Input
2 5 2 1
データセット1
25人目までを1 〜 25日に、26人目をいづれかの日に割り当てることで最大記事数は最小になり、その値は 2 となる。
データセット2
24人目までを1 〜 24日に、25人目以降を25日に割り当てる。
データセット3
参加者データは日付順に並んでいるとは限らない。
データセット4
㍆㌋㌉㌏㌉㌸㌾㌋㌞㌹㌅
Judge Data
補足
参加者の要望を、「xi日以降かつyi日以前」とする問題も思いついたのですが、ゴリゴリ全探索する以外の効率的な解法がわかりませんでした。
そちらの問題の解法も募集しています。
CentOS5.5 に libsvm-ruby を導入する方法まとめ
題の通りです。libsvm-ruby + rmagick で画像処理やりたかった。
導入が色々と面倒だったのでまとめ。
ruby、その他開発ツール(gcc, g++とか) は既に入ってるものとします
ホントは良くないけど全部rootで作業しました。
まず、大元のライブラリ libsvm をインストールする。
yum install libsvm libsvm-devel
「そんなパッケージ無いよ」と言われる。そこで、EPELリポジトリを追加してやる。(既に追加してる人はこの操作を飛ばしてください。)
wget http://download.fedora.redhat.com/pub/epel/RPM-GPG-KEY-EPEL rpm --import RPM-GPG-KEY-EPEL vim /etc/yum.repos.d/epel.repo
[epel] name=EPEL RPM Repository for Red Hat Enterprise Linux baseurl=http://download.fedora.redhat.com/pub/epel/$releasever/$basearch/ gpgcheck=1 enabled=0
yum --enablerepo=epel install libsvm libsvm-devel
これでlibsvmがインストールできた。
次に、libsvmのrubyラッパーである libsvm-ruby をインストールする。
ダウンロード
現時点(2011/9)での最新バージョンは2.8.5
wget http://debian.cilibrar.com/debian/pool/main/libs/libsvm-ruby/libsvm-ruby_2.8.5.orig.tar.gz tar xvzf libsvm-ruby_2.8.5.orig.tar.gz cd libsvm-ruby_2.8.5
configure
別途、libsvmのソース(svm.cpp)が必要なので公式からダウンロードする。また、svm.hにもパスが通っている必要がある。
wget http://www.csie.ntu.edu.tw/~cjlin/cgi-bin/libsvm.cgi?+http://www.csie.ntu.edu.tw/~cjlin/libsvm+tar.gz tar xvzf libsvm-3.1.tar.gz cd libsvm-3.1 cp svm.cpp ~/libsvm-ruby_2.8.5/ cp svm.h /usr/include/
cd ~/libsvm-ruby_2.8.5/ ./configure
makeする
make
なんと、このままではコンパイルが通らない。エラーが二つ出るので、それらを修正する。
redefinition of ‘struct svm_model’
main.cpp:585: error: redefinition of ‘struct svm_model’
みたいな感じのエラーが出たはず。
そこで、main.cpp を編集してエラーを回避する。
vim main.cpp
585行目に、
/* To be removed in next version */ struct svm_model { svm_parameter param; // parameter int nr_class; // number of classes, = 2 in regression/one class svm int l; // total #SV svm_node **SV; // SVs (SV[l]) double **sv_coef; // coefficients for SVs in decision functions (sv_coef[n-1][l]) double *rho; // constants in decision functions (rho[n*(n-1)/2]) // for classification only int *label; // label of each class (label[n]) int *nSV; // number of SVs for each class (nSV[n]) // nSV[0] + nSV[1] + ... + nSV[n-1] = l // XXX int free_sv; // 1 if svm_model is created by svm_load_model // 0 if svm_model is created by svm_train };
という記述があるが、これは既に svm.h に書いてあるため、コメントアウトする。
‘svm_destroy_model’ was not declared in this scope
次に、main.cpp:374: error: ‘svm_destroy_model’ was not declared in this scope
というエラー。
svm_destroy_model(rp->m);
という箇所で文句を言われているみたいだ。svm.h を見ると、確かにこのような関数はない。しかし、よく見ると
void svm_free_and_destroy_model(struct svm_model **model_ptr_ptr);
のような関数が。ひょっとしてこれを呼び出せばいいのかな?
そこで、この関数を
static void svmpm_free(void *ptr) { struct RSVM_Model *rp = (struct RSVM_Model *) ptr; svm_destroy_model(rp->m); free(rp); }
このように変更。
static void svmpm_free(void *ptr) { struct RSVM_Model *rp = (struct RSVM_Model *) ptr; svm_free_and_destroy_model(&(rp->m)); }
以上の作業を行えば、make & make install は成功する。
make
make install
付属の test.rb が動くかどうかテストする。
ruby test.rb
/usr/local/lib/ruby/site_ruby/1.8/i686-linux/SVM.so: /usr/local/lib/ruby/site_ruby/1.8/i686-linux/SVM.so: undefined symbol: __cxa_pure_virtual - /usr/local/lib/ruby/site_ruby/1.8/i686-linux/SVM.so (LoadError)
と怒られる。調べると、configureしたときにできた Makefile を編集する必要があるとのこと。めんどくせー
vim Makefile
真ん中の方に、
LIBS = -lrt -ldl -lcrypt -lm -lc
とあるが、これを
LIBS = -lrt -ldl -lcrypt -lm -lc -lstdc++
に変更する。(-lstdc++ を追加)
もう一度チャレンジ!
make clean make make install ruby test.rb
OK、動いた!めでたしめでたし。
Google App Engine用フレームワークtipfyの紹介とチュートリアル その3
このエントリについて
Google App Engine用に作られたフレームワーク「tipfy」の使い勝手がよかったので
チュートリアル形式で簡単に紹介をしたいと思います。
前々回と前回の続きの内容になってます。
その1:http://d.hatena.ne.jp/hama_DU/20101206/1291644589
その2:http://d.hatena.ne.jp/hama_DU/20101212/1292120224
前回まで
- エントリ一覧機能
- エントリ作成機能
を作りました。
今回は
- エントリ編集機能
- エントリ削除機能
- その他いろいろ
を作ります。
エントリ編集画面を作る
エントリ編集画面といっても、実はエントリ作成画面が使い回せます。
フォームから与えられたデータを受け取って、エントリを更新する機能を作ればいいことになります。
しかし、使い回せるとはいっても、編集機能を作るには
フォーム入力画面に一工夫してやる必要があります。
それは、エントリのデータストアの一意なIDをフォームに埋め込むことです。
Google App Engineでは、データストア内のオブジェクトを表す一意なIDとしてキーオブジェクトが用意されています。
リクエストハンドラを編集
EditHandlerを編集します。
リクエストパラメータ「entry_key」を受け取り、コンテキストに追加します。
def get(self): entry_key = self.request.args.get('entry_key', '') context = { 'form': FindForm(self.request), 'entry_key': entry_key, } return render_response('entry/edit.html', **context)
テンプレートを編集
<form method="post" action="{{ url_for('entry/edit') }}" enctype="multipart/form-data"> <input type="hidden" name="entry_key" value="{{ entry_key }}"> <p> {{ form_field(form.title) }} </p> <p> {{ form_field(form.content) }} </p> <p> <input type="submit" value="投稿!"/> </p> </form>
受け取ったパラメータ entry_key を隠し持っておきます。
リクエストハンドラを編集
def post(self): sentform = FindForm(self.request) context = { 'form': sentform, } if not sentform.validate(): return render_response('entry/edit.html', **context) entry_key = self.request.form.get('entry_key', None) if not entry_key: Entry( title=sentform.title.data, content=sentform.content.data, ).put() else: entry_model = Entry.get(db.Key(entry_key)) if not entry_model: return render_response('entry/edit.html', **context) entry_model.title = sentform.title.data entry_model.content = sentform.content.data entry_model.put() return render_response('entry/complete.html')
フォームがpostされてきたとき、entry_keyを見てもしも空っぽだったら新規登録、
値が入っていたらそのキーを持つオブジェクトを探してきて更新します。
もし、値が入っていても対応するオブジェクトが見つからない場合は更新しません。
エントリのオブジェクトを取得してる部分
entry_model = Entry.get(db.Key(entry_key))
についてですが、ここで entry_key はあくまでもパラメータから取得した文字列なので、検索するときはキーの文字列に対応したオブジェクトを作らなければなりません。ここでは、
db.Key(entry_key)
とすることで文字列に対応したオブジェクトを作成しています。詳しくは
http://code.google.com/intl/ja/appengine/docs/python/datastore/keyclass.html
をご覧ください。
エントリ一覧画面の編集
エントリ一覧画面に、編集画面へのリンクを追加します。
モデルのキーオブジェクトは、
model.key()
とすることでアクセス可能です。このキーをパラメータに渡します。
{% extends 'layout.html' %} {% block body %} {% if not entry_list %} 現在、まだエントリはありません {% else %} <table border="1"> <tr> <th>title</th> <th>created</th> <th>edit</th> </tr> {% for entry in entry_list %} <tr> <td>{{ entry.title|e }}</td> <td> {% if entry.created_at %} {{ entry.created_at.replace(tzinfo=utc).astimezone(jst) }} {% endif %} </td> <td> <a href="{{ url_for('entry/edit') }}?entry_key={{ entry.key() }}">edit</a> </td> </tr> {% endfor %} </table> {% endif %} {% endblock %}
エントリ削除機能を作る
設計
/entry/delete?entry_key=(削除したいエントリーのキー)
にアクセスすると、指定されたキーを持つエントリが削除されるようにします。
リクエストハンドラの編集
DeleteHandlerを追加します。
class DeleteHandler(RequestHandler): def get(self): entry_key = self.request.args.get('entry_key', '') entry_model = Entry.get(db.Key(entry_key)) if not entry_model: return self.redirect('entry/list') entry_model.delete() context = { } return render_response('entry/deletecomplete.html')
編集機能のpostメソッドと同じようなコードになります。
もし、指定されたキーに対するオブジェクトが見つからなかったら一覧画面へリダイレクトさせます。
テンプレートを作る
{% extends 'layout.html' %} {% block body %} <p>削除が完了しました。</p> <p><a href="{{ url_for('entry/list') }}">一覧へ</a></p> {% endblock %}
ルーティング設定
rules = [ Rule('/entry/list', endpoint='entry/list', handler='apps.entry.handlers.ListHandler'), Rule('/entry/edit', endpoint='entry/edit', handler='apps.entry.handlers.EditHandler'), Rule('/entry/delete', endpoint='entry/delete', handler='apps.entry.handlers.DeleteHandler'), ]
エントリ一覧画面の編集
エントリ一覧画面に、削除画面へのリンクを追加します。
{% extends 'layout.html' %} {% block body %} {% if not entry_list %} 現在、まだエントリはありません {% else %} <table border="1"> <tr> <th>title</th> <th>created</th> <th>edit</th> <th>delete</th> </tr> {% for entry in entry_list %} <tr> <td>{{ entry.title|e }}</td> <td> {% if entry.created_at %} {{ entry.created_at.replace(tzinfo=utc).astimezone(jst) }} {% endif %} </td> <td> <a href="{{ url_for('entry/edit') }}?entry_key={{ entry.key() }}">edit</a> </td> <td> <a href="{{ url_for('entry/delete') }}?entry_key={{ entry.key() }}">delete</a> </td> </tr> {% endfor %} </table> {% endif %} {% endblock %}
雑多なこと
hello_worldアプリケーションの削除
もう使わないので、削除しちゃっても大丈夫です。
時刻を整形して表示する
一覧画面で、エントリの作成時刻が表示されていますが、
2010-12-10 12:58:41.952249+09:00
という風に、秒数やタイムゾーンなどの余計な情報が含まれているので、整形して表示させるようにしてみます。
一覧画面のテンプレートを修正します。
{% for entry in entry_list %} <tr> <td>{{ entry.title|e }}</td> <td> {% if entry.created_at %} {{ entry.created_at.replace(tzinfo=utc).astimezone(jst).strftime('%Y/%m/%d %H:%M') }} {% endif %} </td> <td> <a href="{{ url_for('entry/edit') }}?entry_key={{ entry.key() }}">edit</a> </td> <td> <a href="{{ url_for('entry/delete') }}?entry_key={{ entry.key() }}">delete</a> </td> </tr> {% endfor %}
strftimeを使うことで形式を指定して時間を文字列に変換できます。
詳しくは
http://www.python.jp/doc/2.5/lib/module-time.html
をご覧ください。
エントリ一覧を更新日時の降順で表示させる
一般的に、ブログは最新のものから表示されるようになってます。
エントリ数が多くなった場合スクロールするのが面倒なので、
このシステムでも最新のエントリが一番上に表示されるようにしてみます。
リクエストハンドラのデータフェッチ部分を変更します。
class ListHandler(RequestHandler): def get(self): entry_list = Entry.all().order('-updated_at').fetch(100) context = { 'entry_list': entry_list, 'utc': utc(), 'jst': jst(), } return render_response('entry/list.html', **context)
all() でデータストアのクエリオブジェクトが得られるので、
クエリオブジェクトに用意された関数 order() を使うだけで並び順が指定できます。
カラムのデータの昇順に並び替えたい時は
order(カラム名)
と指定するのですが、カラム名の先頭に「-」をつけると降順で並び替えてくれます。
Google App Engine用フレームワークtipfyの紹介とチュートリアル その2
このエントリについて
Google App Engine用に作られたフレームワーク「tipfy」の使い勝手がよかったので
チュートリアル形式で簡単に紹介をしたいと思います。
前回の続きの内容になってます。
その1:http://d.hatena.ne.jp/hama_DU/20101206/1291644589
前回まで
前回はtipfyの導入と、管理アプリとして、
- テストデータを追加する「internal/addentry」
- データストアを削除する「internal/init」
を作り、それぞれアクセスできるようにしました。
今回は
- エントリ一覧機能
- エントリ追加機能
を作ります。
エントリ一覧画面を作る
エントリを扱うためのアプリ「entry」をappsに追加します。
hello_worldかinternalからコピペするのがいいでしょう。
config.pyの編集
config.pyのapps_installedに忘れずに追加しておきます。
'apps_installed': [ 'apps.hello_world', 'apps.internal', 'apps.entry', ],
リクエストハンドラを作る
apps/entry/handlers.pyを編集します。
「一覧」機能なので、リクエストハンドラ名はListHandlerとでもしましょう。
class ListHandler(RequestHandler): def get(self): entry_list = Entry.all().fetch(100) context = { 'entry_list': entry_list, } return render_response('entry/list.html', **context)
モデル Entryから全てのデータを取得し、先頭の100件をとって entry_list に代入しています。
render_response の引数指定方法についてですが、
return render_response('entry/list.html', var_x=x, var_y=y, ....)
このような感じに (変数名 = 値) のペアをたくさんつなげて指定することもできるのですが、
これは次のように、辞書オブジェクトを渡してやることもできます。
context = { 'var_x': x, 'var_y': y, } return render_response('entry/list.html', **context)
この方が、テンプレートに渡したい引数が増えても対応が楽ですし、
何より見やすいのでオススメです。
テンプレートを作る
新しくtemplates以下にentryフォルダを用意し、list.htmlというファイルを作成し、出力時のテンプレートとします。
<!DOCTYPE html> <head> <title>tipfy sample app!</title> </head> <body> <table border="1"> <tr> <th>title</th> <th>created</th> </tr> {% for entry in entry_list %} <tr> <td>{{ entry.title }}</td> <td>{{ entry.created_at }}</td> </tr> {% endfor %} </table> </body> </html>
{% for %} と {% endfor %} で囲まれた部分がforループになっていて、
{% for item in list %} と、文法的にpythonと同じように使うことができます。
このように、jinja2では{% 〜〜 %} というかたちで様々な制御構文をテンプレート上で扱うことができます。
詳しくは
http://jinja.pocoo.org/templates/
に使える文法の一覧が載っています。
内容的には、データストアから取得したentry_listに入っているEntryオブジェクトに対して、
タイトルと作成日時をテーブル状に表示させるものになっています。
ルーティング設定
apps/entry/urls.py に忘れずに記述します。
rules = [ Rule('/entry/list', endpoint='entry/list', handler='apps.entry.handlers.ListHandler'), ]
テスト
http://localhost:8080/entry/list
にアクセスして試してみましょう!
テンプレートを修正
さて、ここで一つ問題が。データストアが空っぽのときに entry/list を表示させようとすると、
表のヘッダだけが表示されるというなんとも間の抜けた感じになってしまいます。
entry_list が 空っぽ( )なので、{% for entry in entry_list %} の中身が一度も実行されないからです。
ここで、entry_listが空の時は、「現在、まだエントリはありません」と表示させるように
テンプレートを改造したいと思います。
ここでは、{% if %} 構文を使って((さっきのリファレンスを見てください))、entry_listが空であるかどうかを判定します。
pythonでは、真偽値として空のリスト()を False として扱うので、entry_listが空であるかどうかは次のように書けます。
{% if not entry_list %} # entry_listは空 {% else %} # 処理 {% endif %}
これを使って templates/entry/list.html を書き換えると、次のようになりました。
<!DOCTYPE html> <head> <title>tipfy sample app!</title> </head> <body> {% if not entry_list %} 現在、まだエントリはありません {% else %} <table border="1"> <tr> <th>title</th> <th>created</th> </tr> {% for entry in entry_list %} <tr> <td>{{ entry.title }}</td> <td>{{ entry.created_at }}</td> </tr> {% endfor %} </table> {% endif %} </body> </html>
エントリ登録画面を作る
エントリ一覧の機能作成が終わったので、次はエントリの登録機能を作ります。
一般的に、登録フォーム機能はWebサービスを作る上でとてもメンドクサイ(笑)のですが、
tipfyにはフォームを扱う便利なプラグインが用意されています。
さっそく、インストール方法と使い方を見ていきましょう。
tipfy.ext.wtformsをインストール
/path/to/project/buildout.cfg をエディタで開いてみてください。
途中にこんな感じの設定が書かれている部分があるかと思います。
# Define the libraries. We include all official extensions by default, but you # can remove the ones you won't use. The only required package is tipfy. eggs = babel tipfy tipfy.ext.appstats tipfy.ext.auth tipfy.ext.blobstore tipfy.ext.db tipfy.ext.debugger tipfy.ext.i18n tipfy.ext.jinja2 tipfy.ext.mail tipfy.ext.session tipfy.ext.taskqueue tipfy.ext.xmpp
ここには、tipfy本体をビルドする時に一緒にインストールする拡張機能が書かれています。
この末尾に、
# Define the libraries. We include all official extensions by default, but you # can remove the ones you won't use. The only required package is tipfy. eggs = babel tipfy tipfy.ext.appstats (省略) tipfy.ext.taskqueue tipfy.ext.xmpp tipfy.ext.wtforms
と、wtformsを追加して、本体をビルドし直せば拡張機能がインストールされます。
ビルド自体はプロジェクト直下(/path/to/project)で以下の手順で行います。
$ python2.5 bootstrap.py --distribute $ bin/buildout
実は、wtforms自体は
http://wtforms.simplecodes.com/
で単品提供されているpython用のライブラリで、tipfyのプラグインはこの機能に加えて
を扱う機能が追加されています。
フォームをhandlers.pyで定義する
apps/entry/handlers.py に次のコードを追加します。
from tipfy.ext.wtforms import Form, fields, validators class FindForm(Form): title = fields.TextField('タイトル', [ validators.required(), validators.Length(max=40), ]) content = fields.TextAreaField('内容', [ validators.required(), ])
Formを継承したフォームFindFormを作りました。
FindFormにはフィールドが二つ定義されています。
- タイトルフォーム (input type="text")
- 内容入力フォーム (textarea)
field_name = fields.XxxxField('ラベル', [入力検証のリスト])
とすることで、フォームのフィールドを定義できます。
XxxxFieldの部分はフォームのタイプを表していて、
- TextField (input type="text")
- TextAreaField (textarea)
の他にも、
- BooleanField (input type="checkbox")
- HiddenField (input type="hidden")
- PasswordField (input type="password")
- SelectField (select)
などが用意されています。
フィールドの定義方法の詳細に関しては、公式ドキュメント
http://wtforms.simplecodes.com/docs/0.6.1/fields.html
を参照するのがいいでしょう。
リクエストハンドラを作る
フォームをテンプレートで使えるようにするために、
handlers.pyに以下のコードを追加します。
class EditHandler(RequestHandler): def get(self): context = { 'form': FindForm(), } return render_response('entry/edit.html', **context)
ルーティング設定
rules = [ Rule('/entry/list', endpoint='entry/list', handler='apps.entry.handlers.ListHandler'), Rule('/entry/edit', endpoint='entry/edit', handler='apps.entry.handlers.EditHandler'), ]
テンプレートを作る
templates/entry/edit.html を作成し、以下の内容を追記します。
<!DOCTYPE html> <head> <title>tipfy sample app!</title> </head> <body> <form method="post" action="{{ url_for('entry/edit') }}" enctype="multipart/form-data"> <p> <label for="{{ form.title.id }}">{{ form.title.label.text }}</label><br/> {{ form.title }} </p> <p> <label for="{{ form.content.id }}">{{ form.content.label.text }}</label><br/> {{ form.content }} </p> <p> <input type="submit" value="投稿!"/> </p> </form> </body> </html>
{{ form.フィールド名 }} とすることでフォーム本体を表示できます。
また、フィールドを作るとき第一引数に指定したラベルを表示するには、 {{ form.フィールド名.label.text }} とします。
また、フォームのアクション先を指定する部分では、tipfyに用意されている関数「url_for」を用いています。
この関数は、urls.py の endpoint に指定した文字列を実際のURLに変換してくれるものです。
例えば今回の場合、
form action="{{ url_for('entry/edit') }}"
と、'entry/edit' を指定しているので、endpoint に 'entry/edit' を指定した
Rule('/entry/edit', endpoint='entry/edit', handler='apps.entry.handlers.EditHandler'),
このルールがヒットし、
form action="/entry/edit"
に置き換わります。
試しに実行
http://localhost:8080/entry/edit
にアクセスして、出力された内容を確認してみましょう。投稿フォームが表示されているでしょうか?
試しに、投稿ボタンを押してみましょう。すると
werkzeug.exceptions.MethodNotAllowed MethodNotAllowed: 405: Method Not Allowed
こんなエラー(例外)が表示されたはずです。
これは、宛先URLは正しくルーティングされ、リクエストハンドラに到達したものの、
メソッドが足りないため実行できなかった時に起こるエラーです。
今回、フォームを送信する際は
<form method="post" action="{{ url_for('entry/edit') }}" enctype="multipart/form-data">
と、method に ”post” を指定しました。しかし、リクエストハンドラでは、
class EditHandler(RequestHandler): def get(self): context = { 'form': FindForm(), } return render_response('entry/edit.html', **context)
getメソッドしか用意されていません。ここで、postメソッドを追加してやれば
エラーが起きず、フォーム送信を受けた時の処理を記述できます。
フォームの処理
EditHandlerにpostメソッドを追加します。
from datetime import datetime, date, time class EditHandler(RequestHandler): def post(self): sentform = FindForm(self.request) context = { 'form': sentform, } if not sentform.validate(): return render_response('entry/edit.html', **context) Entry( title=sentform.title.data, content=sentform.content.data, ).put() return render_response('entry/complete.html')
リクエストハンドラでは、 self.request にリクエストの情報が含まれています。
これを丸ごとフォームのコンストラクタに渡してあげることで、
フォームの入力状況を再現することができます。
例えば、タイトルに入力した内容を知りたければ、
sentform = FindForm(self.request)
print sentform.title.data
などできます。しかし、これは内容未チェックのデータです。
ユーザはブラウザ上のフォームでの制限があっても、任意の内容を送ることができるので、
この段階でそのままデータを登録することはできません。
そこで、フォームの内容の検証(バリデーション)を行う必要があります。
wtformsでは、次のメソッドを実行するだけでOKです。
form.validate()
結果が True だった場合は、入力内容が正しかった、ということになります。
もし False であった場合は、入力内容が間違っているので、
その旨をユーザに知らせるためにもう一度入力画面を表示させる必要があるでしょう。
入力内容が正しかったとき
入力内容が正しかった場合は、実際に Entryモデルのデータをデータストアに挿入します。
そして、ユーザには投稿完了画面(/templates/entry/complete.html)を表示させます。
入力内容が間違っていたとき
form.validate() を実行し結果が False だったとき、
form.fieldname.error にはどのようなエラーが起きたか、という情報がリストになって含まれています。
なので入力内容が間違っていたときは、投稿内容入力画面に戻して、
そのエラーの情報をユーザに表示させるようにします。
/templates/entry/edit.html を以下のように書き換えます。
<form method="post" action="{{ url_for('entry/edit') }}" enctype="multipart/form-data"> <p> <label for="{{ form.title.id }}">{{ form.title.label.text }}</label><br/> {{ form.title }} {% if form.title.errors %} <ul> {% for error in form.title.errors %} <li>{{ error }}</li> {% endfor %} </ul> {% endif %} </p> <p> <label for="{{ form.content.id }}">{{ form.content.label.text }}</label><br/> {{ form.content }} {% if form.content.errors %} <ul> {% for error in form.content.errors %} <li>{{ error }}</li> {% endfor %} </ul> {% endif %} </p> <p> <input type="submit" value="投稿!"/> </p> </form>
とりあえずリストにして表示させてみました。
ここで、タイトルや内容を空にして投稿ボタンを押してみると、
・This field is required.
というエラーが表示されたかと思います。ばんざい!
時間を調整する
試しに、データを追加してみて、entry/listを表示させてみると、
時間が9時間ほどずれていることが分かると思います。
実は、pythonの時間は協定世界時(UTC)しか用意されていなくて、
各国のローカル時間を表すには「UTCからどのぐらいずれているか」を表すクラスを作らなければなりません。
「日本時間」を表す、tzinfoを拡張したクラスを新たに作成します。
場所は timezone/jst.py とでもしておきます。
from datetime import datetime, date, time, tzinfo, timedelta class jst(tzinfo): def utcoffset(self, dt): return timedelta(hours=9) def dst(self, dt): return timedelta(0) def tzname(self, dt): return 'jst'
utcoffsetは、UTCからどれだけ進んでいるか、
dstは夏時間用の調整、
tznameはこの時間設定の名前を返すようにします。
また、「協定世界時」を表すクラスも作っておきます。(timezone/utc.py)
from datetime import datetime, date, time, tzinfo, timedelta class utc(tzinfo): def utcoffset(self, dt): return timedelta(0) def dst(self, dt): return timedelta(0) def tzname(self, dt): return 'utc'
Google App Engineのデータストアでは、
タイムゾーンを変更したdatetimeオブジェクトを入れようとしても、
強制的にUTCになってしまうため、日本時間を表示させるには
- UTCで保存されたデータを取り出し
- 日本時間に変更し
- 表示させる
という流れになります。
ListHandlerのgetメソッドを次のように書き換えます。
from timezone.jst import jst from timezone.utc import utc class ListHandler(RequestHandler): def get(self): entry_list = Entry.all().fetch(100) context = { 'entry_list': entry_list, 'utc': utc(), 'jst': jst(), } return render_response('entry/list.html', **context)
UTCとJSTのオブジェクトをコンテキストに含んでおいて、
{% for entry in entry_list %} <tr> <td>{{ entry.title }}</td> <td> {% if entry.created_at %} {{ entry.created_at.replace(tzinfo=utc).astimezone(jst) }} {% endif %} </td> </tr> {% endfor %}
テンプレートでこのように使います。
これで、世界標準時刻を日本時間にして表示させることができました。
テンプレートの重複を防ぐ
テンプレートマクロ
フォームのテンプレートファイル /templates/entry/edit.html をよく見ると、
<p> <label for="{{ form.title.id }}">{{ form.title.label.text }}</label><br/> {{ form.title }} {% if form.title.errors %} <ul> {% for error in form.title.errors %} <li>{{ error }}</li> {% endfor %} </ul> {% endif %} </p>
ここと、
<p> <label for="{{ form.content.id }}">{{ form.content.label.text }}</label><br/> {{ form.content }} {% if form.content.errors %} <ul> {% for error in form.content.errors %} <li>{{ error }}</li> {% endfor %} </ul> {% endif %} </p>
この部分が、表示させる内容が違うだけで、
構造は全く同じであることが分かります。
この部分をすっきり書くために、jinja2の機能「テンプレートマクロ」を導入します。
マクロ用のファイル「templates/_form_macros.html」を作成します。
{% macro form_field(field) %} <label for="{{ field.id }}">{{ field.label.text }}</label><br/> {{ field }} {% if field.errors %} <ul> {% for error in field.errors %} <li>{{ error }}</li> {% endfor %} </ul> {% endif %} {% endmacro %}
ひとつのフィールドを出力する部分をまるごと持って来て、
フィールドを引数に持つマクロを作ってみました。form_field というのがマクロの名前で、
テンプレートファイルからインポートすることで使えるようになります。
{% from '_form_macros.html' import form_field %} <!DOCTYPE html> <head> <title>tipfy sample app!</title> </head> <body> <form method="post" action="{{ url_for('entry/edit') }}" enctype="multipart/form-data"> <p> {{ form_field(form.title) }} </p> <p> {{ form_field(form.content) }} </p> <p> <input type="submit" value="投稿!"/> </p> </form> </body> </html>
すっきりまとめることができました。
他にも、ラベル部分のみ表示するマクロ、エラー部分のみ表示するマクロ等を用意しておくと便利でしょう。
例えばこんな風にしておけば、
{% macro form_field(field) %} {{ form_label(field) }}<br/> {{ field }} {{ form_error(field) }} {% endmacro %} {% macro form_label(field) %} <label for="{{ field.id }}">{{ field.label.text }}</label> {% endmacro %} {% macro form_error(field) %} {% if field.errors %} <ul> {% for error in field.errors %} <li>{{ error }}</li> {% endfor %} </ul> {% endif %} {% endmacro %}
ラベルだけ自分で書きたいとき、エラー表示をカスタマイズしたい時でも対応できます。
ブロックを使う
今回、機能を作るにあたってテンプレートファイルを3つほど使いましたが、
その3つのファイルは共通して
<!DOCTYPE html> <head> <title>tipfy sample app!</title> </head> <body> <!-- 内容 --> </body> </html>
という形になっており、重複しています。
この重複を解消するため、jinja2の便利な機能が使えます。
まず、「templates/layout.html」に全体のレイアウトを定めておきます。
<!DOCTYPE html> <head> <title>tipfy sample app!</title> </head> <body> {% block body %} {% endblock %} </body> </html>
大枠のみを指定し、中身は実際の処理で使われるテンプレートファイルに任せる、といった格好です。
このレイアウトを使うには次のようにします。
{% extends 'layout.html' %} {% block body %} {% if not entry_list %} 現在、まだエントリはありません {% else %} <table border="1"> <tr> <th>title</th> <th>created</th> </tr> {% for entry in entry_list %} <tr> <td>{{ entry.title }}</td> <td>{{ entry.created_at }}</td> </tr> {% endfor %} </table> {% endif %} {% endblock %}
エントリ一覧画面を例にしてみました。
先ほど作ったレイアウト用のファイルを一行目でextendsし、
bodyという名前のブロックの中身を実際に指定しています。
これで、突然
- タイトルを変えたくなった
- 新しいjavascriptのライブラリを使いたくなった
となったときも、layout.htmlを編集すればおkで、
全テンプレートファイルを修正せずに済みます。
今回はここまで。
次回は
- エントリ編集機能
- エントリ削除機能
- 全体の仕上げ
をして、ひとまずブログシステムを完成させます。
Google App Engine用フレームワークtipfyの紹介とチュートリアル
このエントリについて
Google App Engine用に作られたフレームワーク「tipfy」の使い勝手がよかったので
チュートリアル形式で簡単に紹介をしたいと思います。
先日エントリにした「するめダイアリー」もGAE/Python + tipfyで作ってます。
おことわり
ちなみに、当方の開発環境は、
- Max OS 10.6
- GoogleAppEngineLauncher
- TextMate
なので、説明もこれに準じたものになってます。
また、
- Pythonの文法
- html、cssの書き方
- Google App Engineのデータストア
に関しては説明を省略させていただきます。
追記しました(12/10)
- テンプレートエンジン jinja2 について
- エントリのデータストアモデルの変更
導入
tipfyのダウンロード
公式サイト
http://www.tipfy.org/
の右側、All-in-one packをダウンロードします。現時点での最新バージョンは0.6.4です。
ダウンロード・解凍が終わったら「project」フォルダを適当な場所に配置・リネームします。
これがプロジェクト全体のフォルダになります。(このパスを「/path/to/project」とします。)
GoogleAppEngineLauncherでプロジェクトをインポート
GoogleAppEngineLauncherを起動し、「Add Existing Application」を選択。
Pathに「/path/to/project/app」を指定します。以降、説明でパスを指定する時はこのフォルダが基準になります。
これで開発を進める準備は完了です。さっそく、左上の「Run」ボタンを押し、
ブラウザで「http://localhost:8080/pretty」にアクセスしてみましょう。
中央に大きく水色で「Hello, World」と表示されたらセットアップは完了です。簡単でしょ?
今回作るもの
早速、開発を進めたいと思います!
今回は例として、簡単なブログシステムを作りたいと思います。
作る画面(機能)一覧。
- ブログのエントリ一覧
- 投稿、更新、削除
- エントリ詳細
データストアモデルの作成(12/10編集)
lib の下に datastore という名前のフォルダ*1を作成します。
そのフォルダの下に
- __init__.py
- model.py
の二つのファイルを作成します。
__init__.pyはPythonにここがパッケージのあるディレクトリであることを教えるためのものです。
model.pyには以下のようにモデルを定義します。
from google.appengine.ext import db class Entry(db.Model): title = db.StringProperty(required=True) content = db.TextProperty() created_at = db.DateTimeProperty(auto_now_add=True) updated_at = db.DateTimeProperty(auto_now=True)
ブログのエントリを表すEntryモデルを定義しました。
- エントリのタイトル
- 内容
- 作成日時
- 更新日時
これがあればとりあえず十分でしょうか。
作成日時には、作成したら自動で現在時刻をつけてくれるオプション「auto_now_add」、
更新日時には、データを更新したら自動で現在時刻をつけてくれるオプション「auto_now」を指定しています。
モデル定義の方法、使えるタイプなどについては
http://code.google.com/intl/ja/appengine/docs/python/datastore/entitiesandmodels.html
http://code.google.com/intl/ja/appengine/docs/python/datastore/typesandpropertyclasses.html
などが詳しいです。
管理者用アプリの作成
一覧機能…を作る前に
さっそく、エントリ一覧機能を作りたい所なのですが、
まだ機能を作ってもデータストアの中身が空っぽなので一覧機能の動作確認ができません。
なので、ここは管理者用のモジュールを別に作って、
そこにテストデータをデータストアに入れる処理を書いていこうと思います。
アプリの追加
apps以下に internal という名前のフォルダを追加します。
既にサンプルとして hello_world というアプリが入っている*2ので、それをコピペするのが楽かと思います。
中身は以下の3つのファイルになっています。
- __init__.py
- handlers.py
- urls.py
開発に入る前に、それぞれのファイルの役割を詳しく説明します。
ルーティング -> リクエストハンドラ -> テンプレート
リクエストハンドラ
handlers.py にはリクエストを受けた時の処理内容を書きます。中身はこんな感じになってるはずです。
from tipfy import RequestHandler, Response from tipfy.ext.jinja2 import render_response class HelloWorldHandler(RequestHandler): def get(self): """Simply returns a Response object with an enigmatic salutation.""" return Response('Hello, World!') class PrettyHelloWorldHandler(RequestHandler): def get(self): """Simply returns a rendered template with an enigmatic salutation.""" return render_response('hello_world.html', message='Hello, World!')
RequestHandlerを拡張したHelloWorldHandler、PrettyHelloWorldHandlerというクラスが書かれています。
リクエストを受け取ったら、〜〜する、という処理内容が
def get(self):
の中に記述されています。たとえば、HelloWorldHandler であったら、
- 中身が 'Hello, World!' となるレスポンスを返す
ようになっていて、PrettyHelloWorldHandlerであったら、
- テンプレート 'hello_world.html' を message='Hello, World!' であるコンテキストを元に解釈して返す
という感じになっています。
テンプレート
テンプレート 'hello_world.html' は templates直下にあって、
<html> <head> <title>{{ message|e }}</title> <style type="text/css"> /* 省略 */ </style> </head> <body> <h1>{{ message|e }}</h1> </body> </html>
こんなファイルになっています。ここで 「{{ }}」で囲まれた部分が、
コンテキストに設定した変数の内容を出力するようになっていて、
例えば、message='Hello, World!' のとき、{{ message }} ならば、
Hello, World!
と出力されます。
(12/10追記)
これはtipfyの機能ではなくて、jinja2 というテンプレートエンジンの機能です。
イメージ的には、tipfyが内部でjinja2を呼び出して使っている、といった感じです。
このようにテンプレートエンジンを使えば、htmlの動的生成がグッと楽になります。
jinja2の公式サイトはこちらにあります。↓
http://jinja.pocoo.org/
テンプレートのエスケープ処理
先ほどのファイル 'Hello, World!' には、
<h1>{{ message|e }}</h1>
という部分がありました。{{ message }} の横についている 「|e」とは何者なのか?
これはXSS*3対策のためのエスケープ処理を行っている部分です。
試しにテンプレートの
<h1>{{ message|e }}</h1>
この部分を
<h1>{{ message }}</h1>
として、hello_world/handlers.pyで
return render_response('hello_world.html', message='Hello, World!')
の部分を
return render_response('hello_world.html', message='Hello,<br/> World!')
で置き換えてみて、
http://localhost:8080/pretty
にアクセスしてみてください。エスケープ処理が行われず、改行が入っていることが確認できるかと思います。
ルーティング処理
説明が戻りますが、urls.pyを開いてみてください。
次のような内容になっているはずです。
from tipfy import Rule def get_rules(app): rules = [ Rule('/', endpoint='hello-world', handler='apps.hello_world.handlers.HelloWorldHandler'), Rule('/pretty', endpoint='hello-world-pretty', handler='apps.hello_world.handlers.PrettyHelloWorldHandler'), ] return rules
ここには、どのリクエストのURLが来た場合、どのリクエストハンドラを実行するか、
ということが書かれています。例えば、URLが
http://(ドメイン)/pretty
だった場合は、hello_worldモジュールのPrettyHelloWorldHandlerを実行するようになっています。
このrulesに、上記の例に倣ってRuleを追加していくことでルーティングのルールを増やせます。
管理者用アプリの作成(続き)
リクエストハンドラの作成
apps/internal/handlers.pyに以下の内容を追加します。
from tipfy import RequestHandler, Response from tipfy.ext.jinja2 import render_response from datastore.model import * class AddEntryHandler(RequestHandler): def get(self): for i in range(10): entry_model = Entry( title = "entry " + str(i), content = "content\ncontent\ncontent", ) entry_model.put() return Response('Done!')
ルーティング処理
apps/internal/urls.pyに以下の内容を追加します。
def get_rules(app): rules = [ Rule('/internal/addentry', endpoint='internal/addentry', handler='apps.internal.handlers.AddEntryHandler'), ] return rules
アプリの追加
config.pyにアプリ「internal」を追加します。
これをしないとアプリが認識されません。
'apps_installed': [ 'apps.hello_world', 'apps.internal', ],
実行
urls.pyに書いた通り、
http://localhost:8080/internal/addentry
にアクセスして実行させます。Done! が表示されたら成功!
SDK Consoleを表示させ、Datastore Viewerをのぞいてデータが追加されているか確かめてみましょう!
データストアの一括削除
SDK Consoleには残念ながらデータストアの中身をまっさらに消すツールはついてきません。
なので、これも internalアプリに追加しておくことをお勧めします。
apps/internal/handlers.pyに以下の内容を追加します。
class InitHandler(RequestHandler): def get(self): for entry_model in Entry.all(): entry_model.delete() return Response('Done!')
もちろん、ルーティング設定も忘れずに行います。
rules = [ Rule('/internal/addentry', endpoint='internal/addentry', handler='apps.internal.handlers.AddEntryHandler'), Rule('/internal/init', endpoint='internal/init', handler='apps.internal.handlers.InitHandler'), ]
実行
http://localhost:8080/internal/init
にアクセスして実行させます。Datastore Viewerを見てデータが消えていたら成功!
今回はここまで。
次回以降はエントリ一覧機能から作ります。