Archive for the ‘unique’ Tag

projecteuler29

 projecteuler問題29は、2 から 100 までの自然数を 2 乗から 100乗 して、同じものを除くと何個になるかという問題。
 だから、スクリプトは単純、

(let (lst)
  (for (i 2 100)
    (for (j 2 100)
      (push (apply * (cons 1L (dup i j))) lst -1)
    )
  )
 (length (unique lst)))

 こんな感じ。1L を cons しているのは、大整数にするため。100 乗するには 64 ビット整数では足りないですからね(笑)

(let (lst)
  (for (i 2 100)
    (for (j 2 100)
      (push (apply * (map bigint (dup i j))) lst -1)
    )
  )
 (length (unique lst)))

でも同じになります。
 ここで bigint は整数を大整数に変換します。
 また、unique は同一数値を除去してくれます。
 これを実行すると

9183
> 

 と答えが求まります。

 以上、如何でしょうか?

広告

projecteuler...または、newLISP組込関数の紹介

 projecteuler.net は Lutz氏が newLISPフォーラムで紹介している、ブログラムで解く数学問題が並ぶ webサイトです。
 Lutz氏を始め、色んな人が挑戦しているので、私の出る幕ではありませんが、newLISP 固有の組込関数を紹介する良い機会だと思い、やって見ることに、、、
 まっ、どこまで続けられるか、わかりませんけどね(笑)。

 さて、早速本題です。
 最初の問題1 Multiples of 3 and 5 は 1000 未満の自然数で 3 と 5 の倍数の和を求めるというもの。
 newLISP では、こんな感じで求められます。

> (apply + (unique (append (sequence 3 999 3) (sequence 5 999 5))))
233168

 ここで使っている sequenceunique は newLISP 組込関数です。
 まず、sequence は、任意の等差数列を生成します。引数は、第一が開始数値、第二が終了数値です。第三はオプションでステップ数値、指定しなければ 1 になります。引数には全て、整数と浮動小数点数が使えます。当然、引数が整数なら整数の数列、引数が浮動小数点数なら浮動小数点数の数列になりますが、第三引数を指定した場合は、全て、浮動小数点数の数列になります。
 だから、

(sequence 3 999 3)

 は 3 から 999 間の 3 の倍数の数列を生成しますが、数列の数値は整数ではなく、浮動小数点数です。といっても、newLISP は標準で倍精度浮動小数点数ですから、今回の問題を含め、16桁くらいまでは気にする必要はありません。
 ちなみに、newLISP の整数も64ビットなので、最大値と最小値は

9,223,372,036,854,775,807
-9,223,372,036,854,775,808

 となり、これらを超える整数値が必要な時は注意が必要です。
 さて、組込関数 unique は、リスト中の同一の要素を削除してくれます。だから、3の倍数と5の倍数で重複している数値を削除するために使えます。
 以上で問題1は終了ですが、ここはちょっと汎用関数を考えてみましょう。
 引数に数列と選択する述語を与えて、必要な数列を求める

(select-numbers 数列 述語1 述語2 ...)

 こんな感じの関数。具体的には、

(define (select-numbers numbers)
; (select-numbers numbers predicate1 predicate2 ...) 
  (unique (flat 
      (let (res '()) (dolist (func (args)) (push (filter func numbers) res -1)))
  )))

 となります。
 動作は、

> (select-numbers (sequence 1 10) even?)
(2 4 6 8 10)
> (select-numbers (sequence 1 10) odd?)
(1 3 5 7 9)
> (select-numbers (sequence 1 10) odd? even?)
(1 3 5 7 9 2 4 6 8 10)

 こんな感じ。
 これで、問題1を解くと、

> [cmd]
(apply + (select-numbers (sequence 1 999)
                         (fn (x) (if (= (% x 3) 0)))
                         (fn (x) (if (= (% x 5) 0)))))
[/cmd]
233168

 となり、数列も整数値ですっきり(笑)。
 ここで fn も newLISP組込関数で lambda と等価です。

 以上、如何でしょうか?