Rubyで小町算（その１）

# ことの始まり
先日，AtCoderの[この問題](http://abc045.contest.atcoder.jp/tasks/arc061_a)をRubyで解きました（提出したコードは[これ](http://abc045.contest.atcoder.jp/submissions/1005704)）。

ポイント（という程のものではありませんが）は，Rubyの`Array#repeated_permutation`というメソッドです。配列に対して，その要素たちからなる「重複順列」を返します。

```ruby:repeated_permutation.rb
[1,2].repeated_permutation(3).each{|i|	
	p i
}
```

```
$ ruby repeated_permutation.rb 
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 2, 2]
[2, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 2, 2]
```

AtCoderの問題では，配列`["", "+"]`に対して`repeated_permutation`を用いて生成した順列を，与えられた自然数（10進表示）の数字の間に入れ，最後に`eval`し，そうやって得られた数たちの和を求めました。

# 小町算へ

その後，「このロジックって小町算に使えるよね」と気づき，やってみました。

```ruby:komachizan1.rb
input = "123456789".chars
result = []

["", "+", "-", "*"].repeated_permutation(input.size - 1).each{|ops|
	str = input.zip(ops).join
	result.push(str)
	result.push("-" + str)
}

result.select{|i| eval(i) == 100}.each_with_index{|s, i|
		puts "#{i+1} : #{s} = 100"
}
```

>- `input.zip(ops).join`の部分で，`input`（`["1", "2", "3", "4", "5", "6", "7", "8", "9"]`）の間に演算子の並び`ops`（`["+", "-", "+", "*", "-", "", "*", "*", ""]`など）を挿入していっています。
- また，-1から始まるパターンも入れています。



```
$ ruby komachizan1.rb 
1 : 123+45-67+8-9 = 100
2 : -123+45*6-7*8+9 = 100
3 : 123+4-5+67-89 = 100
4 : 123+4*5-6*7+8-9 = 100
5 : 123-45-67+89 = 100
6 : -123-4+5*6*7+8+9 = 100
7 : 123-4-5-6-7+8-9 = 100
8 : -12+34+5-6+7+8*9 = 100
9 : 12+34+5*6+7+8+9 = 100
10 : 12+34-5+6*7+8+9 = 100
11 : 12+34-5-6+7*8+9 = 100
12 : 12+34-5-6-7+8*9 = 100
13 : 12+3+4+5-6-7+89 = 100
14 : 12+3-4+5+67+8+9 = 100
15 : 12+3*45+6*7-89 = 100
16 : 12+3*4+5+6+7*8+9 = 100
17 : 12+3*4+5+6-7+8*9 = 100
18 : 12+3*4-5-6+78+9 = 100
19 : 12-3+4*5+6+7*8+9 = 100
20 : 12-3+4*5+6-7+8*9 = 100
21 : -12-3-4+5+6*7+8*9 = 100
22 : 12-3-4+5-6+7+89 = 100
23 : 12-3-4+5*6+7*8+9 = 100
24 : 12-3-4+5*6-7+8*9 = 100
25 : 12*3-4+5-6+78-9 = 100
26 : 12*3-4-5-6+7+8*9 = 100
27 : -12*3-4*5+67+89 = 100
28 : 12*3-4*5+67+8+9 = 100
29 : 1+234-56-7-8*9 = 100
30 : 1+23-4+56+7+8+9 = 100
31 : 1+23-4+5+6+78-9 = 100
32 : 1+23-4-5+6+7+8*9 = 100
33 : -1+23*4+56-7*8+9 = 100
34 : 1+23*4+5-6+7-8+9 = 100
35 : -1+23*4+5-6-7+8+9 = 100
36 : -1+23*4-56+7*8+9 = 100
37 : -1+23*4-56-7+8*9 = 100
38 : 1+23*4-5+6+7+8-9 = 100
39 : -1+23*4-5+6+7-8+9 = 100
40 : 1+2+34-5+67-8+9 = 100
41 : 1+2+34*5+6-7-8*9 = 100
42 : -1+2+34*5-6+7-8*9 = 100
43 : -1+2+34*5-6-7*8-9 = 100
44 : 1+2+3+4+5+6+7+8*9 = 100
45 : -1+2+3+4*5-6-7+89 = 100
46 : -1+2+3+4*5*6-7-8-9 = 100
47 : 1+2+3-45+67+8*9 = 100
48 : 1+2+3-4+5+6+78+9 = 100
49 : 1+2+3-4*5+6*7+8*9 = 100
50 : 1+2+3*4-5-6+7+89 = 100
51 : -1+2-3+4+5+6+78+9 = 100
52 : 1+2-3*4+5*6+7+8*9 = 100
53 : 1+2-3*4-5+6*7+8*9 = 100
54 : 1+2*34-56+78+9 = 100
55 : -1+2*3+45+67-8-9 = 100
56 : 1+2*3+4+5+67+8+9 = 100
57 : -1+2*3+4*5+6+78-9 = 100
58 : 1+2*3+4*5-6+7+8*9 = 100
59 : -1+2*3-4+5*6+78-9 = 100
60 : 1+2*3-4-5+6+7+89 = 100
61 : -1+2*3*4+5*6+7*8-9 = 100
62 : 1-23+4*5+6+7+89 = 100
63 : 1-23-4+5*6+7+89 = 100
64 : 1-23-4-5+6*7+89 = 100
65 : -1-23*4+5*6*7-8-9 = 100
66 : 1-2+3+45+6+7*8-9 = 100
67 : 1-2+3*4+5+67+8+9 = 100
68 : 1-2+3*4*5+6*7+8-9 = 100
69 : -1-2+3*4*5+6*7-8+9 = 100
70 : 1-2+3*4*5-6+7*8-9 = 100
71 : 1-2-34+56+7+8*9 = 100
72 : 1-2-3+45+6*7+8+9 = 100
73 : 1-2-3+45-6+7*8+9 = 100
74 : 1-2-3+45-6-7+8*9 = 100
75 : 1-2-3+4*5+67+8+9 = 100
76 : -1-2*3+4+56+7*8-9 = 100
77 : 1-2*3+4*5+6+7+8*9 = 100
78 : 1-2*3-4+5*6+7+8*9 = 100
79 : 1-2*3-4-5+6*7+8*9 = 100
80 : -1-2*3*4+56+78-9 = 100
81 : 1*234+5-67-8*9 = 100
82 : -1*234+5*67+8-9 = 100
83 : 1*23+4+5+67-8+9 = 100
84 : -1*23+4+5+6*7+8*9 = 100
85 : 1*23-4+5-6-7+89 = 100
86 : 1*2+34+56+7-8+9 = 100
87 : 1*2+34+5+6*7+8+9 = 100
88 : -1*2+34+5-6+78-9 = 100
89 : 1*2+34+5-6+7*8+9 = 100
90 : 1*2+34+5-6-7+8*9 = 100
91 : -1*2+34-5-6+7+8*9 = 100
92 : -1*2+34*5-67+8-9 = 100
93 : 1*2+3+45+67-8-9 = 100
94 : -1*2+3+4+5-6+7+89 = 100
95 : -1*2+3+4+5*6+7*8+9 = 100
96 : -1*2+3+4+5*6-7+8*9 = 100
97 : 1*2+3+4*5+6+78-9 = 100
98 : -1*2+3-4+56+7*8-9 = 100
99 : 1*2+3-4+5*6+78-9 = 100
100 : -1*2+3*4+5+6+7+8*9 = 100
101 : 1*2+3*4+5-6+78+9 = 100
102 : -1*2-34+5+6*7+89 = 100
103 : 1*2-3+4-5+6+7+89 = 100
104 : -1*2-3+4*5+6+7+8*9 = 100
105 : 1*2-3+4*5-6+78+9 = 100
106 : -1*2-3-4+5*6+7+8*9 = 100
107 : -1*2-3-4-5+6*7+8*9 = 100
108 : 1*2*34+56-7-8-9 = 100
109 : 1*2*3+4+5+6+7+8*9 = 100
110 : 1*2*3-45+67+8*9 = 100
111 : 1*2*3-4+5+6+78+9 = 100
112 : 1*2*3-4*5+6*7+8*9 = 100
113 : 1*2*3*4+5+6+7*8+9 = 100
114 : 1*2*3*4+5+6-7+8*9 = 100
115 : 1*2*3*4-5-6+78+9 = 100
```

全部で115個見つかりました。

# 割り算

ただ，これでは割り算が入っていません。

```
1/2*3/4*56+7+8*9 = 100
```

のようなものもあるので，こういうものも含めて数え上げましょう。

ただ，komachizan1.rb において単純に`["", "+", "-", "*"]`の部分を`["", "+", "-", "*", "/"]`にするだけではダメです。整数の割り算では余りは切り捨てられて商のみ返すので，`1/2*3/4*56+7+8*9`は`100`ではなく`79`となってしまいます（0*0*56+7+8*9）。

```ruby:not_100_but_79.rb
p eval("1/2*3/4*56+7+8*9")
```

```
$ ruby not_100_but_79.rb
79
```

じゃあはじめから数字を`float`にキャストしておけばいいかというと，それもうまくいきません。`1`と`2`の間に演算子を入れない場合には`12`になってほしいのですが，`1.0`と`2.0`をそのままつなげても`12`にならないからです。

次回「Rubyで小町算（その２）」で，この問題を回避する方法を考えたいと思います。

# 追記１（2016年12月3日）

配列`input`の要素の間に配列`ops`を挟み込んでいく部分を

```
str = input.zip(ops).flatten.compact.join
```

と記述していましたが，この場合最後の`join`のおかげで`flatten`と`compact`は不要であると，[@scivola](http://qiita.com/scivola)さんに教えていただきました。ありがとうございます！

# 追記２（2016年12月3日）

割り算の問題は`require "mathn"`するだけで解決されると，これまた[@scivola](http://qiita.com/scivola)さんに教えていただきました。重ね重ね，ありがとうございます！

当初は

```
e = result.map{|s|
	s.gsub(/(\d)([\/\*+-])/,'\1.0\2')+".0"
}
```

としてから`eval`しようと考えていました。カッコ悪いですね…。

というわけで，「Rubyで小町算（その２）」では別のネタを考えなければならなくなりました。笑