循環参照してるリストを検知する。

DeNA 
本コンテンツの一部は、業務時間内に調べた内容を含んでおり、株式会社ディー・エヌ・エーの提供でお送りしております。

フロイドの循環検出法

フロイドの循環検出法が必要になったためJSで実装。
詳細はwikipediaとか見るよろし。

/*
Floyd's cycle-finding algorithm
http://www.pierreq.kylos.pl/public/cycledetection.pdf
*/
function floyd(top) {
    var tortoise = top;
    var hare = top;

    while(true) {
        if(!hare.slice(1) || hare.length === 0) {
            return false;
        }
        hare = hare.slice(1);

        if(!hare.slice(1) || hare.length === 0) {
            return false;
        }
        hare = hare.slice(1);

        tortoise = tortoise.slice(1);

        if(hare[0] === tortoise[0]) {
            return true;
        }
    }
}

テストコード

(function testcase() {
    var assert = require("assert");
    assert.equal(false, floyd([1,2,3,4]));
    assert.equal(true, floyd([1,2,1,2,1]));
    assert.equal(true, floyd([1,2,3,1,2,3,1]));
    assert.equal(true, floyd([1,2,3,1,2,3,1,2,3,1]));
    assert.equal(true, floyd(["A","B","A","B","A"]));
})();

Python実装

実際はPythonで書いた後にJSに移植した:P

def floyd(top):
    """
    >>> floyd([1,2,3,4])
    False
    >>> floyd([1,2,1,2,1])
    True
    >>> floyd([1,2,3,1,2,3,1])
    True
    >>> floyd([1,2,3,1,2,3,1,2,3,1])
    True
    >>> floyd(["A","B","A","B","A"])
    True
    """
    tortoise = top
    hare = top

    while True:
        if not hare[1:]:
            return False
        hare = hare[1:]

        if not hare[1:]:
            return False
        hare = hare[1:]

        tortoise = tortoise[1:]

        if hare[0] == tortoise[0]:
            return True

追記

Python版がバグってたので直しました。追加したコードは下記。

        if hare[0] == tortoise[0]:
            return True