【ruby】有名アルゴリズム問題「いまだに現金払い？」を解いてみた

久々のアルゴリズム問題
有名アルゴリズム問題の「いまだに現金払い？」を解きました。

参考：第40回「今週のアルゴリズム：いまだに現金払い？」正解者発表

アルゴリズムの問題集の本にも載っているような有名問題で、比較的楽しく頭をつかって解ける問題でした！

問題の概要

1000円払いたい
もっている硬貨は10円50円100円500円
つっこめる硬貨は15枚まで

何パターンの払い方があるか？

ざっくりかいつまむとこんな感じの問題。

これを見た瞬間の私。

再帰だ（゜Д゜）

文系プログラマの敵だ（゜Д゜）

あっちいけ（゜Д゜）

コード
ただいつまでも「再帰あっちいけ（゜Д゜）!!」とか言っていられないのでコード書きました。

#coding: utf-8

#お題の条件
target = 1000
wallet = [10, 50, 100, 500]
count = 0
max_count = 15

#計算
(target/wallet.max..max_count).each{|i|
	wallet.repeated_combination(i).each{|coins|
		if coins.inject(:+) == target
			count += 1 
		end
	}
}

#答え
puts count

お題で与えられた条件を定数として定義して渡せたのはなかなか良いのではないかと自負しています。プログラミングを仕事にしていると、度重なる仕様変更の辛さがわかるようになり、辛さを覚える事で辛さを軽減する実装ができるようになるのは良い事だなと。

ループのところは何かもっと良い書き方があったのかもしれませんが、せっかくrubyで書いたのでrepeated_combinationを使いました。

repeated_combinationメソッドは、配列の要素から引数n個を選んだときの重複組合せ（順序なし、重複を許す組合せ）を数え上げます。組合せの数だけブロックを繰り返し実行し、ブロック引数arrに組合せを配列で入れます。戻り値はレシーバ自身です。

出典：http://ref.xaio.jp/ruby/classes/array/repeated_combination

~~明らかに無駄がある糞コードだ・・・。~~

まとめ

再帰なんて嫌いだ（゜Д゜）!!

[500, 500]
[100, 100, 100, 100, 100, 500]
[50, 50, 100, 100, 100, 100, 500]
[50, 50, 50, 50, 100, 100, 100, 500]
[50, 50, 50, 50, 50, 50, 100, 100, 500]
[50, 50, 50, 50, 50, 50, 50, 50, 100, 500]
[100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
[10, 10, 10, 10, 10, 50, 100, 100, 100, 100, 500]
[50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 500]
[50, 50, 100, 100, 100, 100, 100, 100, 100, 100, 100]
[10, 10, 10, 10, 10, 50, 50, 50, 100, 100, 100, 500]
[50, 50, 50, 50, 100, 100, 100, 100, 100, 100, 100, 100]
[10, 10, 10, 10, 10, 50, 50, 50, 50, 50, 100, 100, 500]
[50, 50, 50, 50, 50, 50, 100, 100, 100, 100, 100, 100, 100]
[10, 10, 10, 10, 10, 50, 50, 50, 50, 50, 50, 50, 100, 500]
[50, 50, 50, 50, 50, 50, 50, 50, 100, 100, 100, 100, 100, 100]
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 100, 100, 100, 100, 500]
[10, 10, 10, 10, 10, 50, 50, 50, 50, 50, 50, 50, 50, 50, 500]
[10, 10, 10, 10, 10, 50, 100, 100, 100, 100, 100, 100, 100, 100, 100]
[50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 100, 100, 100, 100, 100]
20