ウサギとカメ(循環リスト)
連結リストで循環しているかどうか、どこで循環が始まっているのかを検出する。
正式には、Floyd's cycle-finding algorithmと呼ぶらしい。
証明は省くが、だいたい↓のような手順
循環判定
・セルを2つづつ移動するのをウサギ、1つづつ移動するのをカメとして、1ステップずつシミュレートする。
・ウサギとカメが出会う(同じセルにいる)場合そのリストは循環している。
循環場所の検出
・ウサギを最初のセルにもどし、ウサギのスピードを1にする。
・再度シミュレートして、ウサギとカメが出会ったセルが循環のスタート地点。
コード
hare:ウサギ
tortoise:カメ
is_circle_listは、循環リストなら循環スタートのセルを返し、そうでなければfalseを返す。
var Cell = function(a,b){ this.car = a; this.cdr = b; } var is_circle_list = function(ls){ var hare = ls; var tortoise = ls; while (true){ if (hare.cdr == null || hare.cdr.cdr == null){ return false; } hare = hare.cdr.cdr; tortoise = tortoise.cdr; if (hare == tortoise){ break; } } hare = ls; while (true){ if (hare == tortoise){ break; } hare = hare.cdr; tortoise = tortoise.cdr; } return hare; }
schemeのパラメータオブジェクトの使い方を調べた。
r7rsでは標準。
パラメータオブジェクトは、値を束縛して動的存続期間中にその値を変更できるオブジェクト。
make-parameterで、パラメータオブジェクトを作れる。
(define foo (make-parameter 123)) (foo);123
パラメータオブジェクトに値を渡した時の挙動は処理系依存とされているが、
CHICKEN,picrinなど、値を変更するケースが多い。
(foo);123 (foo 100) (foo);100
parameterizeを使うと、その中でのパラメータオブジェクトが返す値を変更できる。
(foo);123 (parameterize ((foo 10)) (foo));10 (foo);123
make-parameterに2つ引数(init converter)を渡すと、初期化や値の変更時に
converterを通した値がセットされる。
(define boo (make-parameter 123 (lambda (x) (* x x )))) (boo);15129 (boo 3);9
python-mechanizeでログインするぞ。
mechanizeは、スクレイピングとか用のweb操作ライブラリ。
標準ではないのでpip等でinstall。
で、ためしにログイン画面をつくってmechanizeでアクセスする。
ログイン画面はこんなかんじ。
index.html
<html> <head> </head> <body> <form name="LOGIN" action="/cgi-bin/form_test.py"> USERNAME <input type="text" name="USERNAME"></input><br> PASSWORD <input type="text" name="PASSWORD"></input><br> <input type="submit"></input> </form> <div id="foo"></div> </body> </html>
cgi-bin/form_test.py
#!/usr/bin/env python import cgi print "Content-Type: text/html\n\n" print "<html><body>" form = cgi.FieldStorage() name = form["USERNAME"].value password = form["PASSWORD"].value if name == "user" and password == "pass": print "OK" else: print "ERROR" print "</body></html>"
ユーザ名がuserで、パスワードがpassだとOK、それ以外だとERRORと出力するようにした。
クライアントは以下
#coding:utf-8 import mechanize URL = "http://127.0.0.1:8000" #ブラウザオブジェクトを生成 br = mechanize.Browser() #robot.txtを無視 br.set_handle_robots(False) #アクセス br.open(URL) #form情報を作る br.select_form(name="LOGIN") br["USERNAME"] = "user" br["PASSWORD"] = "pass" #submit ret = br.submit() #帰ってきたhtmlを見る print ret.read()
以上。
schemeのdatum label
datum labelを使うとschemeの循環構造を表記できる。
(define x (list 1 2 3 )) (set-cdr! (cddr x) x) ;#0=(1 2 3 . #0#) (define y (list 4 x 6)) (set-cdr! (cddr y) y) ;#0=(4 #1=(1 2 3 . #1#) 6 . #0#) (define z (quote #0=(1 2 . #0#))) ;#0=(1 2 . #0#)
gentooにtint2をいれました。
openboxのお供にする。
インストール
ランチャー機能がある0.12以上を入れる。
emerge --ask xdotool emerge --ask "=x11-misc/tint2-0.12.3"
コンフィグを修正
~/.config/tint2/tint2rcを編集する。
初期状態では、そんざいしないアプリケーションへのリンクとかがあるので、
#Launcharの#launcher_item_app から始まるものをすべてコメントアウトする。
アプリケーションをメニュに加える
.desktopファイルを追加するだけでよい。
例えば、forefox-binだと、
.desktopファイルをapplications下において、
cp /usr/portage/www-client/firefox-bin/files/firefox-bin.desktop /usr/share/applications/
コンフィグファイルに追加する。
launcher_item_app = /usr/share/applications/firefox-bin.desktop
おしまい。
schemeのcaseについて
キーと各データをどう比較しているのか気になったので調べた。
r5rsによるとeqv?で比較しているそうだ。(4.2.1)
というわけで、
・symbol、char、symbol、空リストは見た目が同じならよい。
・数値は、正確数同士か不正確同士で数値的に等しければよい。
・文字列、リスト、ベクタはアドレスが同じならばよい。
ということですな。