Rubyて10パズル

友人の結婚式や台風などなどで正直あまり時間の確保ができず、チュートリアルも1章飛ばしてしまったせいでエラーが発生してしまい
なんともなーと思って惰性で体を動かしていました。

友人とのドライブ中、対向車や前の車のナンバープレートで10を作って遊んでいたのですが、
ふと、4桁の数字で10を作るプログラムとか作ってみよう、と思い立ちました。
簡単に作ってみるまでをまとめておきます。

1.調査

この10を作る遊びが何なのかと調べてみたところ、10パズルというそうです。
（参考 Wikipedia https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%B3%E3%83%91%E3%82%BA%E3%83%AB）
日常的に３桁や４桁の番号って結構溢れていて、マックの整理券なんかも３桁だった気がします。
普段はパット見で１０を作れるか否かを判断して遊んでいたのですが、
１０を作れるパターンをプログラムで総洗いできるんじゃないかと思いました。

2.プログラム
色々調べる前にどういうアプローチでやろうかなと自分だけで考えてみました。
単純な方法では4桁と四則演算の組み合わせ全てで計算して、その結果を評価することでできるかなと思います。
あとは自分なりのアプローチとして次のような感じで考えたりしました。
4桁の数字を1：3、２：２，３：１といったふうに区切って10が作れる簡単な組み合わせにできないかと考えて遊んでいます。
例えば「1234」という数字だった場合、
1.「123」と「4」に分割
2.「4」が10となる簡単な組み合わせは「6」を足すこと
3.「123」で6を作れないか確認する
4.「1+2+3」で6となる
5.「1+2+3+4」で10の完成
というふうに考えていたので、これを形にしてみるとどうなるかと考えてみました。

ex.自己流ルール

1.利用できる計算式は四則演算のみ
2.数字の順番は入れ替えられない
3.原則数字は4桁（1000～9999）

3.自己流アルゴリズム

入力された4桁の数字「abcd」を
1.X「a」とY「bcd」
2.X「ab」とY「cd」
3.X「abc」とY「d」
に分解し、それぞれの組み合わせで10になるように計算を行う。
XとYこの2つの組み合わせで10になるパターンは
1.1+9,2+8...,9+1
2.11-1,12-2,...,19-9
2.1*10,2*5（入れ替え含む）
3.90/9,...,10/1
上記パターンに当てはまる組み合わせを洗い出し、答えに格納。
最後に溜まった組み合わせを吐き出す。
といったふうに考えて見ました。

4.逆ポーランド記法

プログラム上で「演算子」を一時的に「文字列」とし格納して最後に「文字列」から「演算子」になおして計算する方法、
というのを調べているうちに「逆ポーランド記法」というものが見つかりました。
（参考　https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95）
細かい詳細はWikipediaに投げるとして、計算式を文字表現に直しかつプログラムで処理しやすい形に変換されていました。
そして、残念なことにこちらを調べていく過程で10パズルの回答も見つけてしまいました。
上記のアルゴリズムの実装は一時的においておいて、逆ポーランド記法を使ったプログラムの処理を簡単に見てみました。
（参考　http://sekai.hateblo.jp/entry/2013/09/15/203432）
参考元のプログラムを見たところ、難しそうな逆ポーランド記法があっさりと処理に落とし込まれていて勉強になりました。
数字の入れ替えがあるので明確には自己流ルールから外れてしまうのですが、
そこは柔軟にルールを考え直すことで、正解としました。（自分を曲げました）

5.今回勉強したもの

逆ポーランド記法という概念
こちらは、プログラムで計算式を処理する際に一度文字列に直すことができるので個人的には非常に式の分岐がやりやすく便利な方法だと思いました。

6.得られたもの

モチベーションがちょっと上がりました。

7.発展

こちらをベースに、発展的なものとしては「自己流ルール厳守」「四則演算だけでなく累乗などを含める」などルールの追加でより高度なプログラムが作れそうです。
世の中の役に立つかどうかで言えば、アプリにして自分で楽しむ範囲に収まるかなと思います。

プロを目指す人のためのRuby入門 言語仕様からテスト駆動開発・デバッグ技法まで (Software Design plusシリーズ)