第14回オフラインリアルタイムどう書くの参考問題 with Python

オフラインリアルタイムどう書く
第14回(9月28日) http://atnd.org/events/43076
の、参考問題「円周上のCrossing」
http://nabetani.sakura.ne.jp/hena/ord14crosscircle/
の実装例。

慣れないpythonで。

他の言語などの解答例は
http://qiita.com/Nabetani/items/66806c9dc14a96f2fd42
から辿れます。

で。

#coding:utf-8
#tested with Python 2.7.5 and Python 3.3.2

import re

def solve( src ):
    return str(len(
            [ 0
                for a in range( 0, len(src) )
                for b in range( 0, a )              
                for c in range( 0, b ) if src[a]==src[c] 
                for d in range( 0, c ) if src[b]==src[d] ] ))

def test( samples ) :
    for line in samples.splitlines():
        a=re.split( "\s+", line ) # num, input, expected
        if len(a) <3:
            continue
        actual = solve( a[1] )
        ok=actual==a[2]
        print( [ "ok" if ok else "***NG***", a[1:3], actual ] )

test( """
0   aabbca1bcb  14  
1   111ZZZ  0   
2   v   0   
""")

いつも通り、テストデータの大半は省略。

ひどくナイーブな実装。最悪 O(N**4) という有り様だが、今回の問題にはこれで十分。

点を4つ選ぶ。最初と三番目が同じ名前で、二番目と最後が同じ名前なら交点がある。全部試せば終わり。

リスト内包表記を使うべき場面じゃないような気がするが、使いたいので迷わず使用。
使うことにはしたものの、リストの中身に興味が無いので 0 で埋めるということになり、ちょっと変な感じになった（ような気がしているが、Pythonista じゃないので本当に変なのかどうかはよくわからない）。

順序を変えると typical case は速くなるけど worst case が速くならないのでそのままにしておいた。