覆面算をRubyで解く - ネギのメモ帳

覆面算をプログラムで解く方法などはすでにググれば
いくらでも出てくるとは思うが, 一応自分の記録として.

あれは確か高校の頃, 友人がどっからか持ってきた問題が
なかなか印象に残っているのでそれを解くことにする.
「赤いスイカ, 種なしで美味しいです」だ.

アカイスイカ + タネナシデ = オイシイデス

出現する文字種はぴったり10種類. よくできているｗ
とりあえずRubyのソースコードを載せる.

[0,1,2,3,4,5,6,7,8,9].permutation(10) do |a,b,c,d,e,f,g,h,i,j|
  next if a == 0 or j == 0
  x = 100000*a+10000*b+1000*c+100*d+10*c+b
  y = 10000*e+1000*f+100*g+10*h+i
  z = 100000*j+10000*c+1000*h+100*c+10*i+d
  if x+y == z then
    printf("%d %d %d %d %d %d %d %d %d %d\n",a,b,c,d,e,f,g,h,i,j)
  end
end

ところでソースコードのマークアップははてダの機能なんですね.
さっき知ったんですがなんと便利な…

Array#permutation(n) は配列からn個選んだ順列を返すメソッド.
SEND MORE MONEY問題ならn = 8など.
これで「同じ文字には同じ数字が入り、違う文字には違う数字が入る」という
覆面算の基本的な条件を簡潔に表現できている.
ちなみに組み合わせconbinationや重複順列repeated_permutationなどの
メソッドも用意されているようなので
より複雑な条件の問題にも対応しやすい, かも.

next if で, 条件に一致したときはループを抜けて次の順列に移る.
自明な条件を書いておけば計算量が減るし,
多少手計算して非自明な条件を追加するともっと速くなる
(計算するより回した方が速いとか言わない).

あとは解として満たすべき条件に一致したら書き出すだけ.
…ちゃんと一意解になっているのがすごい.

ついでにもう一題. ぐぐってたら見かけたのでこちらも解いてみよう.
Business Media 誠：誠 Weekly Access Top10（2008年12月13日〜12月19日）：世界一美しい覆面算はこれだ（と思う）

割り算の筆算の問題.

          C
       ---
AB / DE
        FG
      ---
         HI

文字種が9個なのでn = 9.
2桁の上位, および商は0では無いと仮定.
割り算の筆算のルールから, AB * C = FG.
割り算の商と余りの関係から, DE = AB * C + HI.
余りが満たすべき条件から, AB > HI.

以上の条件を組み込むと,

[0,1,2,3,4,5,6,7,8,9].permutation(9) do |a,b,c,d,e,f,g,h,i|
  next if a == 0 or c == 0 or d == 0 or f == 0 or h == 0
  q = 10*a+b
  x = q*c
  r = 10*h+i
  if (x == 10*f+g) and (10*d+e == x + r) and (q>r) then
    printf("%d %d %d %d %d %d %d %d %d\n",a,b,c,d,e,f,g,h,i)
  end
end

こちらも見事一意解.