# [PYTHON] Solve the verbal arithmetic

Solve the verbal arithmetic of addition. Outputs all possible solutions. It is not a brute force algorithm.

Written in python, but I think there is better coding. The algorithm is based on "The latest algorithm encyclopedia in C language" by Haruhiko Okumura.

Give the code execute permission, and specify each character string of the verbal arithmetic on the command line, for example, `./fukumen.py SEND MORE MONEY`.

#### `fukumen.py`

``````
#!/usr/bin/python3
import sys

N = 128
s = "0123456789ABCDEFGHIJKLMNOPQRTSUVWXYZ"
word = [['' for i in range(N)] for j in range(128)]
digit = [0 for i in range(len(s))]
l = [0 for i in range(len(s))]
ok = [False for i in range(10)]
ii = 0
jj = 0
carry = 0
solution = 0

def found():
global solution
solution += 1
print("\n solution%d" % solution)
for i in range(imax):
if (i == imax-1):
print("-"*jmax)
for j in range(jmax):
k = jmax-1-j
c = word[i][k]
if (c == ''):
print(" ", end="")
else:
print("%d" % digit[s.index(c)], end='')
print("")

def tr(sum):
global ii, jj
w = word[ii][jj]
c = 0 if w == '' else s.index(w)
if (ii < imax-1):
ii += 1
d = digit[c]
if (d < 0):
d = l[c]
while(d <= 9):
if (ok[d]):
digit[c] = d
ok[d] = False
tr(sum+d)
ok[d] = True
d += 1
digit[c] = -1
else:
tr(sum+d)
ii -= 1
else:
jj += 1
ii = 0
carry, d = divmod(sum, 10)
if (digit[c] == d):
if (jj < jmax):
tr(carry)
elif (carry == 0):
found()
else:
if (digit[c] < 0 and ok[d] and d >= l[c]):
digit[c] = d
ok[d] = False
if (jj < jmax):
tr(carry)
elif (carry == 0):
found()
digit[c] = -1
ok[d] = True
jj -= 1
ii = imax-1

argv = sys.argv
argv.pop(0)
imax = len(argv)
jmax = max(map(len, argv))

for i in range(imax):
argv[i] = argv[i].upper()
l[s.index(argv[i][0])] = 1
a = argv[i][-1::-1]
for j in range(len(a)):
word[i][j] = a[j]
c = word[i][j]
if (c.isalpha()):
digit[s.index(c)] = -1
elif (c.isdigit()):
digit[s.index(c)] = int(c)
else:
print("Invalid parameter.")
exit(1)

for i in range(10):
ok[i] = True
tr(0)
if (solution == 0):
print("There is no solution.")
exit(0)

``````

# Execution example

``````\$ ./fukumen.py send more money

Solution 1
9567
1085
-----
10652

\$ ./fukumen.py send much money

Solution 1
8932
1465
-----
10397

Solution 2
9482
1365
-----
10847

Solution 3
8935
1462
-----
10397

Solution 4
9485
1362
-----
10847

Solution 5
9475
1268
-----
10743

Solution 6
8635
1729
-----
10364

Solution 7
9478
1265
-----
10743

Solution 8
8639
1725
-----
10364

\$ ./fukumen.py five seven eleven twelve fifteen twenty seventy

Solution 1
3209
59094
969094
819609
3238994
819487
-------
5909487
``````