Egisonで三角形の組み合わせ問題を解く
はじめに
なんかいいパターンマッチな問題ないかな，って色々考えてたら，競技プログラミングの三角形の組み合わせ問題があった．
三角形の組み合わせ問題とは，x-y軸のある整数のグラフに任意の点を好きなだけ置き，その点から何種類の三角形を生み出せるか調べる問題．この問題のキモは，重複のない順列と，三角形が成立するかどうかの判定をどう入れるかどうか．
競技プログラミングとは縁もゆかりもない感じだったけれども，紆余曲折を経てやっとEgisonで書くことができた．満足満足．
実装コード
(define $point-list {
{3 1} {4 5} {7 7} {8 1} {1 9} {3 8} {3 1}})
(define $point-size (length point-list))
(define $getx (lambda [$point] (car point)))
(define $gety (lambda [$point] (car (cdr point))))
(define $getp1 (lambda [$pt] (car pt)))
(define $getp2 (lambda [$pt] (car (cdr pt))))
(define $getp3 (lambda [$pt] (car (cdr (cdr pt)))))
(define $to-vec
(lambda [$a $b]
{(- (getx b) (getx a)) (- (gety b) (gety a))}))
(define $vector-length
(lambda [$v]
(sqrt
(+
(* (getx v) (getx v))
(* (gety v) (gety v))))))
(define $reciprocal-length
(lambda [$v]
(/ 1 (vector-length v))))
(define $normalize
(lambda [$v]
{
(* (reciprocal-length v) (getx v))
(* (reciprocal-length v) (gety v))
}))
(define $dot
(lambda [$v1 $v2]
(+
(*
(getx (normalize v1))
(getx (normalize v2)))
(*
(gety (normalize v1))
(gety (normalize v2))))))
(define $calculate-degree
(lambda [$a $b $c]
(dot
(normalize (to-vec a b))
(normalize (to-vec a c)))))
(define $is-triangle
(lambda [$triangle]
(if
(gt? (calculate-degree
(getp1 triangle)
(getp2 triangle)
(getp3 triangle)
) 0.0)
1 0)))
(define $listing-match
(match-all point-list
(multiset integer)
[<cons $x <cons $y <cons $z _>>>(is-triangle {x y z})]))
(define $test-match
(match-all point-list
(multiset integer)
[<cons $x <cons $y <cons $z _>>>{x y z}]))
(define $main
(lambda [$args]
;(write (show (length test-match)))))
(write (show (foldl + 0 listing-match)))))
問題に挑戦した感想
要約すると，パターンマッチした結果をfoldlして足し合わせることで，簡単に問題を解くことができた．括弧がたくさんあるので，括弧間の対応がうまく取れないと，すぐにクソース化するような気がしたので，なるべくネストが深くならないように関数をいくつも作った．とにかく，複数の処理を1行で行わない，なるべくLisp固有の難しいことはしない．やってることは手続き型言語と一緒だから，Lispな利点を活かせていないかもしれない……．
Lispでは，こんな常識的な関数とか，こういう機能あって当然とか，そういうことはよくわからないので，知ってる範囲の機能だけで解いた．そう考えると，Egisonのパターンマッチはかなり強力なのでは？ と思った．この問題だと，ループが必要なのでどうしても再帰を作らなければならず，Lispの再帰に限って戻らなくなるのでつらい．そう考えると，EgisonはLispにおけるループとパターンマッチの両方を解放してくれるいい機能なのかもしれない．
とにかく，Lispの学習は一筋縄にはいかない．Gaucheもそうだったけれども，Lispはこれで何ができるのかさっぱり理解できない地獄が多かったので，そう考えるとEgisonのパターンマッチは，Lisp初心者にとって（ある程度）わかりやすい仕組みで，なおかつ例題がいくつか提示されているので，あとはどのようにして書けばいいのか，考えればいいのかとか，チートシートの充実などのドキュメントを整理できるかどうかとか．Lispは入門サイトでいきなりリストだとか，タプルだとか，データ構造とか，再帰定義とか，わからん地獄が多い．最近は経験値も高くなったので，概ね予測できるようにはなったけれども，それでもわからんことが多い．もっと初心者になるとさらにわからんはず．
Lispに対する愚痴は置いといて，こういう問題が解けたということは，他の類似する組み合わせに関する問題も解けるということなので，自分なりに関数型言語を学習するモチベーションが高まった．RubyでもEgisonのパターンマッチを使えるようになっているらしいので，もしかするとEgisonにお世話になるパターンも多くなるんじゃないかなと思う．
ということで，いい加減たくさん書いてきたのでこれで終わりにします．
