naoya_t@hatenablog

いわゆるチラシノウラであります

Project EulerにGaucheで挑戦する話

Advent Calendar Project Euler Lisp Gauche Scheme

（この投稿はLisp Advent Calendar 2012の19日目の記事「Project EulerにGaucheで挑戦する話」の転載です）

Lisp Advent Calendar 19日目担当の @naoya_t です。

「昨晩@g000001さんと回転寿司屋でLispについて話した」（※実話）とかでもいいんですが、予告通りProject Eulerの話を書こうと思います。

ちょっと投稿が遅くなりましたが、インド標準時（UTC+05:30；日本時間より3時間半遅れています）でぎりぎり19日ということでお許しください。

はじめに

本記事では、特定の問題の解答や、それを導くプログラムはProject Eulerの参加規約に抵触するため掲載しません。

Project Eulerとは

http://projecteuler.net/

偉大な数学者レオンハルト・オイラーの名を冠する`Project Euler`とはいったい何なのでしょうか？

英語版WikipediaでProject Eulerを開いてみると

Project Eulerは、コンピュータプログラムで解くことを意図した計算問題とそのジャッジメントシステムを提供するウェブサイトです。

数学やコンピュータプログラムに関心のある大人や学生が世界中から集まっています。
2012年12月19日（本稿執筆時点）現在で406問が掲載されています
難易度はさまざまですが、いずれも効率的なアルゴリズムを用いればそこそこのパワーがあるマシンなら１分もかからずに解ける問題です（訳注：まじっすか）。正答にたどり着いたら、各問専用のフォーラムでの議論に参加できます。

世界中から注目を集め、2001年にColin Hughesがサイトを発足して以来、約26万人のユーザが訪れています。

参加者は、正答問題数に基づいた15段階の達成レベルで自分の能力向上を見ることができます。
新しく参加したメンバーが昔の問題を解かなくても競えるように、Eulerianレベルというのも設けられていて、これは直近の幾つかの問題を最初に解いた20人に基づいています。

Project Eulerの問題のいくつかが、APLベンダーの１つDyalogが開催したAPLプログラミングコンテストで用いられました。
整数列オンライン百科事典(the On-Line Encyclopedia of Integer Sequences(OEIS))では、現在68の数列がProject Eulerの問題を参照しています。

（naoya_t抄訳）と説明されています。

回答欄に答えの数値を入力し、それが正解かどうかしか見ていない（=回答に至るプログラムないしスクリプトの提出は不要）ので、プログラミング言語は何を使っても構いません。Pencil/Paper(鉛筆と紙)での参戦も可能です*1。

データ：Project Euler と Scheme

http://projecteuler.net/languages (要ログイン) によると…

naoya_t個人成績（2012年12月19日現在）


↑虫食い状態になっているのは212/220問まで解いた後３年半ブランクが空いた→今年の春頃に暇を持て余してた時に何問かつまみ食いしたためです。

最近時間（というか挑戦する気持ち）が割けなくて全然進んでいませんが、あと100問ぐらいは行けると思うのでそのうち何とかしたいです。

追記：Friend Keyは

4864086150836_7abbecb3db29e56be631729040879af9

です。フレンドうぇるかむです。

問題を解いてみよう

素数を生成する手段・素因数分解関数は必須

3〜4千万までの素数があれば大抵は事足ります。まずはエラトステネスのふるいを実装しましょう。
計算済みの素数データを用意しておいてmmapで読み込む、という方法も良いと思います。（heruさんの「Gaucheからmmapを使ってみる」シリーズ参照）

素数判定関数もあると良いですね。素数表がメモリにあるならそれを使うのも良いですし、Miller-Rabinテスト（SICP 1.28参照）等を実装しておくのも良いです。

素数だけでなく、与えられた整数を素因数分解する関数なども用意しておくと捗ります。
素因数分解ができたら、ついでにオイラーのφ関数(phi function, totient function)も知っていると便利です。これは、1からnまでの自然数のうち、nと互いに素なものの個数を表す関数で、と因数分解できるとき
で求めることができます。

よく使う関数
  • 整数`12345`を`(1 2 3 4 5)`のようなリストに変換する、あるいはその逆
  • 組み合わせの数 nCk を求める関数
  • ピタゴラス数を余さず生成する関数

シンプルな行列式で次々とピタゴラス数を生成する行列があるのでこれを利用すると良いです。「ピタゴラス数を生み出す行列のはなし」という本がお勧めです。

使ってるライブラリの一部を晒してみます。

繰り返し

`let`を用いて

(let loop ((l lis) (i 0))
  . . .
  )

のようなループを書くことが多いです。（末尾再帰になるように気をつけましょう！）
`fold`はちょっと遅い印象があってあまり使いません（※Gauche 0.9.3から`fold`がコアでサポートされたので改善されてるかもです。）が、やはり簡潔に書けるのでたまに使います。

forループ的な事をしたい時にはScheme純正の`do`文も使いますが、`dotimes`で済む時は`dotimes`だったりします。これはCommon Lispから導入されたマクロですね。

ハッシュテーブル

`make-hash-table` `hash-table-get` `hash-table-put!` あたりには非常にお世話になっています。
時々GCが悲鳴をあげるのを聞くことができます。

大きな整数（Bignum）をキーにする場合、比較関数には`eq?`ではなく`eqv?`を使う、という点は（言語実装を考えると自明かもしれませんが）忘れがちなので要注意です。

おわりに

１人でも多くのSchemerがProject Eulerに参加し、「黒板言語」の宿敵「鉛筆と紙」勢を打ち破ることができたら嬉しいです。

ところで、休眠中だった`Shibuya.lisp`が、運営スタッフを世代交代し動き出そうとしています。
有志運営スタッフ（naoya_t含む）によるブートストラップ・ミーティングが年明けに開かれる予定です。第2期はどんな感じになるんでしょうか。Tech TalkやLightning Talksで新しいネタが聞けるのを楽しみにしています。

*1:2012年12月19日現在、Schemerは「鉛筆と紙」勢に負けています。