テンパズルを解いてみました

はじめに

これまでRubyでちょこちょこプログラムを書いてきましたが，今年はLispを学ぼうということで，Schemeの本を読んでいます．
そんな訳で，基礎的な練習としてテンパズルをやってみることにしました．

テンパズルとは

wikipedia:テンパズルにずばり書いてあるので，ご覧下さい．(笑)
ただし，数字の並べ替えは面倒なので行わないことにしました．並べ替えを許すと表示も美しくなさそうですし...

実際にやってみた

処理系はGaucheを使いました．
Lispは括弧が多く見づらいのだけど，書いてるうちに気にならなくなってくるのが不思議．
以下，ソースです．

(use srfi-1)
(use srfi-13)
(use util.combinations)

;; 定数設定
(define *start* 1234)
(define *count* 50)
(define *operators* '(+ - * /))
(define *figure* (string-length (number->string (+ *start* *count*))))

;; 切符番号を数値が並んだリストに変換する
(define (trans-to-list num)
  (map digit->integer (string->list (string-pad (number->string num) *figure* #\0))))

;; 演算子リストからn個の重複組合せを得る (もっとうまいやり方がありそうだけど...)
(define (repeated-combination ops n)
  (define (mul-list lis n)
    (if (zero? n)
	()
	(append lis (mul-list lis (- n 1)))))
  (delete-duplicates (combinations (mul-list ops n) n)))

;; 与えられた演算子と数をLisp式に変換する
(define (make-expr num-list ops)
  (define (make-expr-iter nums ops expr)
    (if (null? nums)
	expr
	(make-expr-iter (cdr nums) (cdr ops) (list (car ops) expr (car nums)))))
  (make-expr-iter (cdr num-list) ops (car num-list)))

;; 与えられた演算子と数で10になる場合に式を返す
(define (expr-if-10 num-list ops)
  (let ((expr (make-expr num-list ops)))
    (if (= (eval expr (interaction-environment)) 10)
	expr
	#f)))

;; 全ての演算をためして，10になる組合せを見つける
(define (find-10 num-list)
  (filter-map (cut expr-if-10 num-list <>) (repeated-combination *operators* (- *figure* 1))))

;; メインループ
(for-each print (filter pair? (map find-10 (map trans-to-list (iota *count* *start*)))))

動作確認

1234から1284まで計算してみた結果です．
前置記法なのでピンとこないかもしれないですが10になっています．

((+ (+ (+ 1 2) 3) 4) (+ (* (* 1 2) 3) 4))
((* (+ (- 1 2) 3) 5) (+ (+ (* 1 2) 3) 5))
((+ (+ (- 1 2) 3) 8))
((+ (/ (+ 1 2) 3) 9))
((- (* (+ 1 2) 4) 2) (+ (* (* 1 2) 4) 2))
((+ (+ (+ 1 2) 4) 3))
((+ (+ (* 1 2) 4) 4))
((* (* (/ 1 2) 4) 5))
((+ (+ (- 1 2) 4) 7))
((+ (* (/ 1 2) 4) 8))
((+ (* (* 1 2) 5) 0) (- (* (* 1 2) 5) 0))
((/ (* (* 1 2) 5) 1) (* (* (* 1 2) 5) 1))
((+ (+ (+ 1 2) 5) 2))
((+ (+ (* 1 2) 5) 3))
((* (* (/ 1 2) 5) 4))
((- (* (+ 1 2) 5) 5))
((+ (+ (- 1 2) 5) 6))
((+ (+ (+ 1 2) 6) 1))
((* (+ (- 1 2) 6) 2) (+ (+ (* 1 2) 6) 2) (- (* (* 1 2) 6) 2))
((+ (+ (- 1 2) 6) 5))
((+ (* (/ 1 2) 6) 7))
((- (* (+ 1 2) 6) 8))
((- (+ (+ 1 2) 7) 0) (+ (+ (+ 1 2) 7) 0))
((* (+ (+ 1 2) 7) 1) (/ (+ (+ 1 2) 7) 1) (+ (+ (* 1 2) 7) 1))
((+ (+ (- 1 2) 7) 4) (- (* (* 1 2) 7) 4))
((- (+ (* 1 2) 8) 0) (+ (+ (* 1 2) 8) 0))
((- (+ (+ 1 2) 8) 1) (* (+ (* 1 2) 8) 1) (/ (+ (* 1 2) 8) 1))
((+ (+ (- 1 2) 8) 3))

ちなみに，上記のコードでは*start*を1234として4桁で計算していましたが，任意の桁が扱えるので値を変えてみます．

(define *start* 235711)
(define *count* 1)

実行すると...

((+ (+ (+ (/ (+ 2 3) 5) 7) 1) 1) (* (- (+ (+ (- 2 3) 5) 7) 1) 1) (/ (- (+ (+ (- 2 3) 5) 7) 1) 1)
(- (* (+ (+ (- 2 3) 5) 7) 1) 1) (- (/ (+ (+ (- 2 3) 5) 7) 1) 1) (+ (+ (+ (- (* 2 3) 5) 7) 1) 1))

10になっているのが分かりますか?