お題
これをjsで解けと会社の上司に言われたんですが全然わからん。
誰かわかります?笑 pic.twitter.com/ZM6VmigaVQ— gonta@Webエンジニア (@keisei_otsuka) February 2, 2020
Facebookで上の問題が流れてきたので、スレ(解答)を見ないようにしてRubyでやってみました。答えはたった1つというのがヒント。
なお、問題文は1から9までの数字を「1回だけ使う」のかどうか微妙にはっきりしませんでしたが、1回だけの前提で突っ走りました。
Array#permutation
まともにやれば9!
(9x8x7...x2)回の実行回数が必要になることぐらいは見当が付きました。
帰りの電車の中で書き始めましたが、組み合わせを網羅するための順列アルゴリズムをスクラッチで書くのは思ったより面倒そう...😅。
帰宅後きっとあるだろうと思ってググると、やはりArray#permutation
がありました。
[2, 3, 11, 16].permutation.to_a
#=> [[2, 3, 11, 16], [2, 3, 16, 11], [2, 11, 3, 16],
# [2, 11, 16, 3], [2, 16, 3, 11], [2, 16, 11, 3],
# [3, 2, 11, 16], [3, 2, 16, 11], [3, 11, 2, 16],
# [3, 11, 16, 2], [3, 16, 2, 11], [3, 16, 11, 2],
# [11, 2, 3, 16], [11, 2, 16, 3], [11, 3, 2, 16],
# [11, 3, 16, 2], [11, 16, 2, 3], [11, 16, 3, 2],
# [16, 2, 3, 11], [16, 2, 11, 3], [16, 3, 2, 11],
# [16, 3, 11, 2], [16, 11, 2, 3], [16, 11, 3, 2]]
欲しかったのはこれです😋。なお、to_a
しないとEnumeratorオブジェクトを返します。
[2, 6, 9, 12].permutation
#=> #<Enumerator: [2, 6, 9, 12]:permutation>
最初に書いたコード
とりあえず様子見で雑に書いてみました。問題文の式を事前に通分しておくことで除算を回避するという手もありますが、Rubyにある大好きなRational
で楽に書きました❤️。
def calc(a, b, c, d, e, f, g, h, i)
tn1 = a.to_r
td1 = (10 * b.to_r) + c.to_r
tn2 = d.to_r
td2 = (10 * e.to_r) + f.to_r
tn3 = g.to_r
td3 = (10 * h.to_r) + i.to_r
tn1/td1 + tn2/td2 + tn3/td3
end
[1, 2, 3, 4, 5, 6, 7, 8, 9].permutation.each do |i|
if calc(*i) == 1r
puts i.to_s
end
end
[5, 3, 4, 7, 6, 8, 9, 1, 2]
[5, 3, 4, 9, 1, 2, 7, 6, 8]
[7, 6, 8, 5, 3, 4, 9, 1, 2]
[7, 6, 8, 9, 1, 2, 5, 3, 4]
[9, 1, 2, 5, 3, 4, 7, 6, 8]
[9, 1, 2, 7, 6, 8, 5, 3, 4]
それっぽいものが出ました。
その2
- 配列を
[1, 2, 3, 4, 5, 6, 7, 8, 9]
と書いてあるのが素朴すぎかなと思ったので(1..9).to_a
に変えてみました。 - 一応通分する形に変えてRationalを外しました。
- 一時変数を減らしました。
result
の初期化を処理の直前に移動しました。- 処理の途中に
puts
やto_s
を挟むのもイケてない気がしたので、処理中に配列を変換しないようにし、puts
やto_s
は最後の最後に回しました。
def calc(a, b, c, d, e, f, g, h, i)
if a*(10*h + i)*(10*e + f) +
d*(10*b + c)*(10*h + i) +
g*(10*b + c)*(10*e + f) == (10*b + c)*(10*e + f)*(10*h + i)
[[a, b, c], [d, e, f], [g, h, i]]
end
end
result = []
(1..9).to_a.permutation.each do |i|
ans = calc *i
result << ans unless ans.nil?
end
puts result.to_s
[[[5, 3, 4], [7, 6, 8], [9, 1, 2]], [[5, 3, 4], [9, 1, 2], [7, 6, 8]], [[7, 6, 8], [5, 3, 4], [9, 1, 2]], [[7, 6, 8], [9, 1, 2], [5, 3, 4]], [[9, 1, 2], [5, 3, 4], [7, 6, 8]], [[9, 1, 2], [7, 6, 8], [5, 3, 4]]]
nil
対応のためにeach
ブロックの行数がちょい増えてしまいましたが、しょうがないか。
その3
最初に「答えは1つ」と書いたことからおわかりかと思いますが、実は6つの配列は順序だけ異なった、同じ解であることにこのあたりで気づきました。上の結果を整形しました。
[
[[5, 3, 4], [7, 6, 8], [9, 1, 2]],
[[5, 3, 4], [9, 1, 2], [7, 6, 8]],
[[7, 6, 8], [5, 3, 4], [9, 1, 2]],
[[7, 6, 8], [9, 1, 2], [5, 3, 4]],
[[9, 1, 2], [5, 3, 4], [7, 6, 8]],
[[9, 1, 2], [7, 6, 8], [5, 3, 4]]
]
この重複をどうやって解消しよう?🤔
当初は「重複なしといえば集合」とばかりRubyのSet
でやろうとしてじたばたしましたが、翌日になってsort
してuniq
するというシェル芸でありがちなテクニックを思い出したので、そっちでやってみました。
def calc(a, b, c, d, e, f, g, h, i)
if a*(10*h + i)*(10*e + f) +
d*(10*b + c)*(10*h + i) +
g*(10*b + c)*(10*e + f) == (10*b + c)*(10*e + f)*(10*h + i)
[[a, b, c], [d, e, f], [g, h, i]].sort
end
end
result = []
(1..9).to_a.permutation.each do |i|
ans = calc *i
result << ans unless ans.nil?
end
puts result.uniq.to_s
[[[5, 3, 4], [7, 6, 8], [9, 1, 2]]]
できました😋。
最後はお楽しみの書式設定です。変数名を表示用に短くし、flatten
でつぶして楽しました(答えがひとつと知ってしまっているので)。
r = result.uniq.flatten
puts "#{r[0]}/(#{r[1]}#{r[2]}) + #{r[3]}/(#{r[4]}#{r[5]}) + #{r[6]}/(#{r[7]}#{r[8]}) = 1"
5/(34) + 7/(68) + 9/(12) = 1
少々大げさですが、最後にrubocop -a
をかけました。「calc()
の引数多すぎ👮」は自動では修正できないので、配列をまとめて渡すように変えました。
# frozen_string_literal: true
def calc(ary)
a, b, c, d, e, f, g, h, i = *ary
if a * (10 * h + i) * (10 * e + f) +
d * (10 * b + c) * (10 * h + i) +
g * (10 * b + c) * (10 * e + f) == (10 * b + c) * (10 * e + f) * (10 * h + i)
[[a, b, c], [d, e, f], [g, h, i]].sort
end
end
result = []
(1..9).to_a.permutation.each do |i|
ans = calc i
result << ans unless ans.nil?
end
r = result.uniq.flatten
puts "#{r[0]}/(#{r[1]}#{r[2]}) + #{r[3]}/(#{r[4]}#{r[5]}) + #{r[6]}/(#{r[7]}#{r[8]}) = 1"
5/(34) + 7/(68) + 9/(12) = 1
おまけ
その後いつもお世話になっているkazzさんに軽くツッコんでいただきました。
select
的なメソッド使えば一時変数要らなくなるかなresult
よりresults
にしよう
というわけでselect
で書き直しました(整形は省略)。このままだとRuboCopに怒られそう👮🏼♀️。
# frozen_string_literal: true
def calc(ary)
a, b, c, d, e, f, g, h, i = *ary
a * (10 * h + i) * (10 * e + f) + d * (10 * b + c) * (10 * h + i) + g * (10 * b + c) * (10 * e + f) == (10 * b + c) * (10 * e + f) * (10 * h + i)
end
results = (1..9).to_a.permutation.select do |i|
calc i
end
results
#=> [[5, 3, 4, 7, 6, 8, 9, 1, 2], [5, 3, 4, 9, 1, 2, 7, 6, 8], [7, 6, 8, 5, 3, 4, 9, 1, 2], [7, 6, 8, 9, 1, 2, 5, 3, 4], [9, 1, 2, 5, 3, 4, 7, 6, 8], [9, 1, 2, 7, 6, 8, 5, 3, 4]]
おまけ
強い人がJuliaでワンライナーでやってました😳。
本質的に1行でお終い。ただし #Julia言語
using Combinatorics
[k for k in permutations(1:9)
if ((a, b, c) = (10k[2]+k[3], 10k[5]+k[6], 10k[8]+k[9]);
k[1] < k[4] < k[7] && k[1]*b*c + k[4]*a*c + k[7]*a*b == a*b*c)]https://t.co/IMxBAXHVOk pic.twitter.com/Sn4gYR90ux— 黒木玄 Gen Kuroki (@genkuroki) February 3, 2020
おたより発掘
面白い!
Ruby: Array#permutationでクイズを解いてみた https://t.co/ZediaQQXnh
— あっきー🍺 (@kuronekopunk) February 22, 2020