Tech Racho エンジニアの「?」を「!」に。
  • Ruby / Rails関連

Ruby: Array#permutationでクイズを解いてみた

お題

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の初期化を処理の直前に移動しました。
  • 処理の途中にputsto_sを挟むのもイケてない気がしたので、処理中に配列を変換しないようにし、putsto_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でワンライナーでやってました😳。

おたより発掘

関連記事

Haskell: ピーターからの問題を解いてみた

Rubyの式展開(string interpolation)についてまとめ: `#{}`、`%`、Railsの`?`

Railsでnil? blank? empty? present?を使いこなそう


CONTACT

TechRachoでは、パートナーシップをご検討いただける方からの
ご連絡をお待ちしております。ぜひお気軽にご意見・ご相談ください。