再帰に対する考え方を教えてくれた練習問題

確か『LISP I』だったと思うけど、次のような練習問題があった。

2 つの引数をとり、その 2 つの値の合計を返す関数を書け。ただし + は使わずに 1+ と 1- を使って。
なお、2 つの引数は正の整数と仮定してよい。

答えをみたら「なあんだ」と思えるが、その当時は自力でこの問題を解くことができなかった。 再帰に対する考え方を教えてくれた関数のひとつとして、その影響は大きい。

(defun add (x y)
  (if (zerop x)
      y
    (add (1- x) (1+ y))))

; Emacs の *scratch* バッファでの実行結果
(add 1 2)
; 3
(add 100 2)
; 102

数値文字参照を文字に変換するPythonスクリプト

import re


def conv(s):
    cs = []
    for e in re.findall("&#x([0-9a-fA-F]+);", s):
        cs.append(chr(int(e, 16)))
    return "".join(cs)


def main():
    s = "ファイルまたはアセンブリ"
    print(conv(s)) # ファイルまたはアセンブリ


if __name__ == "__main__":
    main()

リンク

文字参照 - Wikipedia

自然数から平方数を取り除いた数列の N 番目を求める

A000037 - OEIS の式を使って求めます。

; https://oeis.org/A000037

(define (f n)
  (+ n (exact-integer-sqrt (+ n (exact-integer-sqrt n)))))

実行結果です。

% gosh -l ./not-square-numbers.scm
gosh> (map f (iota 100 1))
(2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 28 29 30 
 31 32 33 34 35 37 38 39 40 41 42 43 44 45 46 47 48 50 51 52 53 54 
 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 
 78 79 80 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 
 101 102 103 104 105 106 107 108 109 110)

バットとボールの問題を SageMath で解く

問題:バットとボールはセットで1ドル10セントします。バットはボールより1ドル高いです。ボールはいくらですか?

http://karapaia.com/archives/52047106.html

$ sage                                                             
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.2, Release Date: 2016-05-15                     │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: var('bat ball')
(bat, ball)
sage: f = [bat + ball == 110, bat == ball + 100]
sage: solve(f, bat, ball)
[[bat == 105, ball == 5]]

Gaucheで小町算にチャレンジ

Makoto HiroiさんのMemorandum(2013年1月5日)で小町算の問題が紹介されていました。

●パズルでプログラミング

パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。
たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、
たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。

[問題] 小町算

1 から 9 までの数字を順番に並べ、間に + と - を補って三桁の値 (100 - 999) になる式を作ることにします。
100 になる式の一例を示します。

例:1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

100 になる式は全部で 11 通りあります。それでは問題です。

1. 式の総数が最大になる値をすべて求めてください。
2. 解のない値で最小のものを求めてください。
3. 解のある値で最大のものを求めてください。 

Gauche(Scheme)でチャレンジしてみたいと思います。

はじめに、100になる式は全部で11通りあるとのことですので、それを確かめるプログラムを作成します。

(use util.match)

(define (komachi)
  (let loop ((expr '(1)) ; 計算式
             (rest '(2 3 4 5 6 7 8 9))) ; 残りの数字
    (cond ((null? rest)
           (when (and (integer? (car expr))
                      (= 100 (eval (reverse expr))))
             (print (reverse expr))))
          ((integer? (car expr))
           (loop (cons (+ (* 10 (car expr)) (car rest))
                       (cdr expr))
                 (cdr rest))
           (loop (cons '+ expr) rest)
           (loop (cons '- expr) rest))
          (else
           (loop (cons (car rest) expr) (cdr rest))))))

;;; 式を評価
(define (eval expr)
  (let loop ((expr (cdr expr))
             (acc  (car expr)))
    (match expr
      (() acc)
      (('+ x . z) (loop z (+ acc x)))
      (('- x . z) (loop z (- acc x))))))

実行結果です。

gosh> (komachi)
(123 + 45 - 67 + 8 - 9)
(123 + 4 - 5 + 67 - 89)
(123 - 45 - 67 + 89)
(123 - 4 - 5 - 6 - 7 + 8 - 9)
(12 + 3 + 4 + 5 - 6 - 7 + 89)
(12 + 3 - 4 + 5 + 67 + 8 + 9)
(12 - 3 - 4 + 5 - 6 + 7 + 89)
(1 + 23 - 4 + 56 + 7 + 8 + 9)
(1 + 23 - 4 + 5 + 6 + 78 - 9)
(1 + 2 + 34 - 5 + 67 - 8 + 9)
(1 + 2 + 3 - 4 + 5 + 6 + 78 + 9)
#<undef>

100になる式は全部で11通りありました。上のプログラムを元に以下の3つの問題を解いていきます。

  1. 式の総数が最大になる値をすべて求めてください。
  2. 解のない値で最小のものを求めてください。
  3. 解のある値で最大のものを求めてください。
(use util.match)
(use gauche.collection)
(use srfi-1) ; lset-difference

(define (komachi)
  (let ((ht (make-hash-table)))
    (let loop ((expr '(1)) ; 計算式
               (rest '(2 3 4 5 6 7 8 9))) ; 残りの数字
      (cond ((null? rest)
             (when (integer? (car expr))
               (let ((x (eval (reverse expr))))
                 (when (<= 100 x 999)
                   (hash-table-put! ht x (+ 1 (hash-table-get ht x 0)))))))
            ((integer? (car expr))
             (loop (cons (+ (* 10 (car expr)) (car rest))
                         (cdr expr))
                   (cdr rest))
             (loop (cons '+ expr) rest)
             (loop (cons '- expr) rest))
            (else
             (loop (cons (car rest) expr) (cdr rest)))))
    ht))

;;; 式を評価
(define (eval expr)
  (let loop ((expr (cdr expr))
             (acc  (car expr)))
    (match expr
      (() acc)
      (('+ x . z) (loop z (+ acc x)))
      (('- x . z) (loop z (- acc x))))))

(define (solve1) ; 問題1
  (let* ((alist (hash-table->alist (komachi)))
         (nmax (cdr (find-max alist :key cdr))))
    (map car (filter (^x (= nmax (cdr x))) alist))))

(define (solve2) ; 問題2
  (let ((alist (hash-table->alist (komachi))))
    (find-min (lset-difference = (iota 900 100) (map car alist)))))

(define (solve3) ; 問題3
  (let ((alist (hash-table->alist (komachi))))
    (car (find-max alist :key car))))

問題 1 の「全て求める」というのが結構くせ者ですね……。上のプログラムでは、まず最大値を見つけてから、再度その値を持つ要素を検索しています。1度きりの探索で答えを出せたら良いのですがうまく書けませんでした。

問題 2 は、存在しない値を求めるのにlset-differenceを使っています。最小値だけでなく、存在しない値を全て求めてしまっているのはあまり良くないかも知れません。

問題 3 は、単純にfind-maxで最も大きい値を求めています。

実行結果です。

gosh> (solve1)
(117 108 126)
gosh> (solve2)
160
gosh> (solve3)
972

参考

プログラミングGauche

プログラミングGauche

追記

  • 2013年1月12日のMemorandumに解答編が掲載されていました(2013-01-14)。

RubyのBinDataが便利!

これはすごい。。忘れないようにメモ。Rubyだとこんな書き方が出来るんですね。