Scheme:TaxiNumber

Scheme:TaxiNumber

こんなふうに言われると燃えるじゃないですか。

ラマヌジャンのタクシーナンバー: 互いに異なる正整数a, b, c, dで、 a^3+b^3 = c^3+d^3となるもの、でいいのかな。

コード:

(define (taxi-numbers n)
  (list-of (list a b c d)
    (a in (upto 1 n))       (b in (upto (+ a 1) n))
    (c in (upto (+ a 1) b)) (d in (upto (+ c 1) b))
    (= (+ (expt a 3) (expt b 3))
       (+ (expt c 3) (expt d 3)))))

実行結果:

gosh> (taxi-numbers 50)
((1 12 9 10) (2 16 9 15) (2 24 18 20) (2 34 15 33) (3 36 27 30) (4 32 18 30) (4 48 36 40) (6 48 27 45) (9 34 16 33) (10 27 19 24) (12 40 31 33) (17 39 26 36))

種明かし: Scheme:マクロの効用で定義されてるlist-ofマクロを使ってます。

追記: list-ofマクロはeagerな評価なので、あらかじめ探索するa, b, c, dの上限を 指定してやる必要があります (引数n)。 したがって、「探索上限を指定せずにcomprehensionを書いて最初から10個取る」という ような書き方は出来ません。

SRFI-40で提案されている lazy streamライブラリには、stream-ofという遅延評価版のcomprehensionが 定義されており、それを使えばHaskellと同様の感覚で書けると思います。

Tag: Puzzle


Last modified : 2013/04/26 05:19:50 UTC