ウサギとカメ(循環リスト)

連結リストで循環しているかどうか、どこで循環が始まっているのかを検出する。
正式には、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))
(make-parameter);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);123
(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#)

openboxにターミナル起動キーバインドを追加しました。

ctrl+alt+tでターミナルエミュレータを起動するようにする。
~/.config/openbox/rc.xmlキーバインド関係の設定がある。

<keybord>内に以下のような感じで書き加える。
こちらの環境では、lilytermを使っている。

    <keybind key="C-A-t">
        <action name="Execute">
            <command>lilyterm</command>
        </action>
    </keybind>

修飾キーの略語は、
C:Control
A:Alt
S:Shift
W:windows key
のような感じ。

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


おしまい。
f:id:niyarin-man:20160921171606j:plain

schemeのcaseについて

キーと各データをどう比較しているのか気になったので調べた。
r5rsによるとeqv?で比較しているそうだ。(4.2.1)
というわけで、
・symbol、char、symbol、空リストは見た目が同じならよい。
・数値は、正確数同士か不正確同士で数値的に等しければよい。
・文字列、リスト、ベクタはアドレスが同じならばよい。
ということですな。