Scheme の permutations-for-each が役に立つ
Problem 43 のように、このへんで pandigital number が頻出するようになる。
そんな問題たちを解くのに役に立ってくれるのが Scheme の permutations-for-each.
例えば Problem 43 では俺はこう解いた。おもいっきり brute force だけど、これ以外に思いつかない。
MacBook (Intel Core 2 Duo 2.4GHz) では
$ time ./43.scm 16695334890 ./43.scm 291.17s user 2.71s system 99% cpu 4:54.67 total
と、かなり時間は掛かった。
#!/usr/bin/env gosh (use srfi-1) (use util.combinations) (use gauche.sequence) (define (list->integer xs) (fold (lambda (x p) (+ (* 10 p) x)) 0 xs)) (define sum 0) (permutations-for-each (lambda (x) (let ((a (list->integer (subseq x 1 4))) (b (list->integer (subseq x 2 5))) (c (list->integer (subseq x 3 6))) (d (list->integer (subseq x 4 7))) (e (list->integer (subseq x 5 8))) (f (list->integer (subseq x 6 9))) (g (list->integer (subseq x 7 10)))) (if (and (= 0 (modulo a 2)) (= 0 (modulo b 3)) (= 0 (modulo c 5)) (= 0 (modulo d 7)) (= 0 (modulo e 11)) (= 0 (modulo f 13)) (= 0 (modulo g 17))) (set! sum (+ sum (list->integer x)))))) (iota 10)) (print sum)
正直、Scheme は全然使い慣れていないから不自然な部分もあるかもしれないけど。。。