SICP P.22 両替の問題について

money.rb

def exchange x
  exchange_node x, 50
end

# proto exchange node example
def proto_exchange_node x, coin
  return 1 if x == 0
  return 1 if x < 5
  return 0 if x < 0

  sum_coin = 0
  case coin
  when 10
    sum_coin += exchange_node(x - 5, 5)
  end
  sum_coin += exchange_node(x - coin, coin) + 1
  return sum_coin
end

# bad exchange node
def bad_exchange_node x, coin
  return 1 if x == 0
  return 1 if x < 5
  return 0 if x < 0

  sum_coin =
    if coin >= 50
      exchange_node(x - 50, 50)
    else
      0
    end +
    if coin >= 25
      exchange_node(x - 25, 25)
    else
      0
    end +
    if coin >= 10
      exchange_node(x - 10, 10)
    else
      0
    end +
    if coin >= 5
      exchange_node(x -  5,  5)
    else
      0
    end
end

$caches = {}
# better refactoring
COINS = [50, 25, 10, 5]
def exchange_node x, coin
  return 1 if x == 0
  return 1 if x < 5
  return 0 if x < 0
  return COINS.inject(1) do |sum, c|
    sum + cache_exchange_coin(x, coin, c)
  end

#  return exchange_coin(x, coin, 50) +
#    exchange_coin(x, coin, 25) +
#    exchange_coin(x, coin, 10) +
#    exchange_coin(x, coin,  5) + 1
end

def exchange_coin x, n, coin
  if x - coin >= 0 && n >= coin
    exchange_node(x - coin, coin)
  else
    0
  end
end

def cache_exchange_coin x, n, coin
  caches_key = "#{x}_#{n}_#{coin}"
  if $caches[caches_key].nil?
    if x - coin >= 0 && n >= coin
      $caches[caches_key] = exchange_node(x - coin, coin)
    else
      $caches[caches_key] = 0
    end
  end
  $caches[caches_key]
end

# --------------------TestCase
require 'minitest/unit'
require 'minitest/autorun'

class TestExchange < MiniTest::Unit::TestCase
  def test_exchange_node_5
    assert_equal 3, exchange_node(10, 5)
  end

  def test_exchange_node_10
    assert_equal 4, exchange_node(10, 10)
  end

  def test_exchange_20
    assert_equal 9, exchange(20)
  end

  def test_exchange_100
    assert_equal 292, exchange(100)
  end

  def test_pef_exchange_1000
    assert_equal exchange(1000), exchange(1000)
  end
end

money.rkt

#lang racket
(require rackunit)

(define coins '(50 25 10 5))
(define (change-money x)
  (change-money-p x (car coins)))

;;   (if-check-coin-node x n 50)
;;   (if-check-coin-node x n 25)
;;   (if-check-coin-node x n 10)
;;   (if-check-coin-node x n 5)

(define (change-money-p x n)
  (if (= x 0) 1 
  (+
   (foldl + 
          0
          (map (lambda (coin) (if-check-coin-node x n coin)) coins))
   1)))

(define (if-check-coin-node x n coin)
  (if (check-coin? x n coin) (change-money-p (- x coin) coin) 0))

(define (check-coin? x n coin)
  (and (>= (- x coin) 0)
       (>= n coin)))

(check-equal? (change-money 4) 1)

(check-equal? (check-coin? 5 5 5) true)
(check-equal? (change-money 5) 2)
;; 10
;; 5 - 5
;; 5 - 1
;; 1

(check-equal? (change-money 10) 4)
;; 10 - 10
;; 10 - 5 - 5
;; 10 - 5 - 1
;; 10 - 1
;; 5 - 5 - 5 - 5
;; 5 - 5 - 5 - 1
;; 5 - 5 - 1
;; 5 - 1
;; 1
(check-equal? (change-money 20) 9)
(check-equal? (change-money 100) 292)