Pythonで虫食い算の自動生成
平成教育委員会を見てみて、ふと虫食い算を自動生成してみたくなる。
さて、3桁の整数どうしの掛け算で、筆算に出てくる数字の種類が一番少ないのは…
ABA
x AAB
-------
B
ABA
ABA
-------
AAAAB
う、0を使うのは禁止しよう。
AAA
x AAA
-------
AAA
AAA
AAA
-------
ABCBA
1を使うのも禁止！
AAA
x BBB
-------
CBBA
CBBA
CBBA
-------
AACCCA (問題1)
ふむふむ。これなら多少は頭を使う。問題の3桁の中で同じ数字を使わない制約を入れてもいいかも。
ABC
x DEA
-------
EDC
BEBC
BBDC
-------
BCDDBC (問題2)
うむ。それなりの問題ができた。 でもこれ筆算の1行目を解くのに一番労力がかかって、それが解けるとコーヒーに入れた角砂糖みたいにあっさりとけてしまう。出てくる数字の種類が少なくなれば難しくなると思ったけども、逆に制約が強くなりすぎて一つ目のピースがはまった瞬間すべてが解けてしまう。制約はほどほどのほうがいいのか…。
難しさの定義は難しい。やっぱり虫食い算を解くプログラムを作って、余詰めがない条件の上で説くのに必要なステップの数が最長になるような問題を探すのがいいのだろうか。
ソースコードは虫食い算を解くアルゴリズムが出来てからでいいかとも思ったのだけど、今度いつ続きを作る気になるやらわかったものじゃないので筆算を表示する部分だけでも公開しておくことにします。
def eachDigit(v):
return (v/100, v/10%10, v%10)
def hissan(x, y):
result = ""
result += " %3d\n" % x
result += "x %3d\n" % y
(y1, y2, y3) = eachDigit(y)
result += "-"*7 + "\n"
result += " %4d\n" % (x * y3)
result += " %4d\n" % (x * y2)
result += " %4d\n" % (x * y1)
result += "-"*7 + "\n"
result += " %6d\n" % (x * y)
return result
def mushikuize(s):
mapping = []
for i in range(10):
c = str(i)
start = s.find(c)
if start != -1:
mapping.append((start, c))
mapping.sort()
code = ord("A")
for i in range(len(mapping)):
c = mapping[i][1]
c2 = chr(code + i)
s = s.replace(c, c2)
return len(mapping), s
虫食い算を解くアルゴリズムは結構難しいな。 単に解くだけなら簡単で、可能性のある数字を手当たり次第にチェックすればいいわけなんだが、それは非人間的な解き方だ。
自分がどうやって解くかを観察してみる。
問題1。 うむ、筆算の2桁目と3桁目を見ると、B+A=CでB+B+A=Cと足しているものが異なるのにBが一個余計についている。ということはBは繰り上がりを受けて0に変わるような数字で、2桁目は2つの足し算なので繰り上がりは1。Bは9。次、1桁目を見るとA×9がA。そうなるのは1、5。Aが1の場合、2桁目での足し算でCが0になり、Cは数字の頭にも来ているので矛盾。よってAは5。計算してCは4。
問題2。筆算の1列目に注目すると、A×Aが1桁になることがわかる。そういうAは1,2,3のどれか。1ならば数字の並びが変わらないはずなので2か3。2または3で、Cとかけて1の位がCになるような対は…と2の段と3の段を唱える。三 五 十五。Aが3でCは5とわかる。3×3が9なので1段目の頭のEは9。繰上りがあると四桁になってしまうから繰り上がりがないと断定できるから。そのまま2行目を計算すると、一番上の桁Bは2。はめ込んで計算するとDは7。
うー。こんなのそう簡単に実装できないぞ…。
桁数非依存にして桁の多い計算にしてみた。
def eachDigit(v):
result = []
while v != 0:
r = v % 10
result.insert(0, r)
v /= 10
return result
def hissan(x, y):
sx = str(x)
sy = str(y)
ketaX = len(sx)
ketaY = len(sy)
keta = ketaX + ketaY + 1
result = ""
result += sx.rjust(keta) + "\n"
result += "x" + sy.rjust(keta - 1) + "\n"
result += "-" * keta + "\n"
ds = eachDigit(y)
ds.reverse()
for (i, d) in enumerate(ds):
result += str(x * d).rjust(keta - i) + "\n"
result += "-" * keta + "\n"
result += str(x * y).rjust(keta)
return result
問3 8 種
ABCA
x BCDB
---------
BDEB
DFBD
CEFC
BDEB
---------
BGGCHHB
問4 7 種
ABCA
x BCDC
---------
CEFC
DFBD
CEFC
BDEB
---------
BGGDBCC
問5 6 種
ABCA
x CBDC
---------
CEFC
DFBD
BDEB
CEFC
---------
CFFBACC
問6 5 種
ABCA
x ADBD
---------
AAABE
DEEE
AAABE
BDBB
---------
CAEDDAE