Problem 33 - 変わった分数

解けたよぉ（涙

49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである.
我々は 30/50 = 3/5 のようなタイプは自明な例だとする.
1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある.
その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

オモワネェヨ。

地道なフィルタリング作戦。

10〜99までの順列を求める。
1以上になる組合せをフィルタリング
約分できないものをフィルタリング
4 9 / 9 8のようにクロスしているものを自明でない分数と考えて、フィルタリング
4個の分数を約分してみる。

以上だ。

(define (number->list n . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (acc n)
                   (let ((q (quotient n b))
                         (m (cons (modulo n b) acc)))
                        (if (zero? q)
                            m
                            (iter m q))))))
          (iter '() n)))


(define (permutations s . m)
  (letrec ((flatmap (lambda (proc s)
                      (apply append (map proc s))))
           (remove-1 (lambda (item s)
                       (cond ((null? s) '())
                             ((equal? (car s) item) (cdr s))
                             (else (cons (car s)
                                         (remove-1 item (cdr s)))))))
           (iter (lambda (s m)
                   (if (or (zero? m) (null? s))
                       (list '())
                       (flatmap (lambda (l)
                                  (map (lambda (p) (cons l p))
                                       (permutations (remove-1 l s) (- m 1))))
                                s)))))
          (iter s (if (null? m) (length s) (car m)))))


(define (problem33)
  (let ((cross? (lambda (a b)
                  (let ((sa (number->list a))
                        (sb (number->list b))
                        (cmp (/ a b)))
                    (or (and (not (zero? (car sb)))
                             (= (car sa) (cadr sb))
                             (= (/ (cadr sa) (car sb)) cmp))
                        (and (not (zero? (cadr sb)))
                             (= (cadr sa) (car sb))
                             (= (/ (car sa) (cadr sb)) cmp)))))))
  (fold (lambda (l acc)
          (let* ((a (* (car l) (car acc)))
                 (b (* (cadr l) (cdr acc)))
                 (g (gcd a b)))
            (cons (/ a g) (/ b g))))
        '(1 . 1)
        (filter (lambda (l)
                  (and (< (car l) (cadr l))
                       (not (= (gcd (car l) (cadr l)) 1))
                       (cross? (car l) (cadr l))))
                (permutations (iota 90 10) 2)))))

(problem33)
; ((16 64) (19 95) (26 65) (49 98)) fold前
; (1 . 100)

スゲーシンプルな答えなのね。