所谓字母算式,就是用字母表示的算式,规则是相同字母对应相同数字,不同字母对应不同数字,并且第一位字母的对应数字不能是 0。
譬如给定算式 We * love = CodeIQ,则可以对应填上下面这些数字以使之成立。
W = 7, e = 4, l = 3, o = 8, v = 0, C = 2, d = 1, I = 9, Q = 6
这样一来,我们就能得到 74 * 3804 = 281496这样的等式。使这个字母算式成立的解法只有这一种。
求使下面这个字母算式成立的解法有多少种?
READ + WRITE + TALK = SKILL
本题解着眼于通用的解决方案,即不仅限于以上表达式,而是任意的字符串表达式(前提式的确能够代表合法的算法,比如说运算符不能连续出现,等等)。
基本步骤如下:
在Step2中用python itertools模块中的permutation()生成所有的组合。
在Step2-3中用pyhton内置的eval()函数进行字符串形式的算式值的评估
在 Step2-2中判断字符串表达式是否合法依据的规则是多位数字的操作数的第一个字母不能为0。首先基于‘=’的位置分割得到LHS和RHS。
RHS中因为没有运算符所以比较简单,只要有多位数字(长度大于1)且首位为0就表示是非法表达式。
LHS的情况比较复杂,分以下三种情况考虑:
当然以上判断方法是基于原输入字符串表达式肯定可以表达成一个合法的算式,比如不会有两个连续的运算符出现,等等。
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 5 08:39:27 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
# from collections import deque
import itertools as it
class Solution:
def stringEquation(self, strEqu:str):
"""
strEqu: Equation in the form of string with character representing digit,
assuming case insensitive.
Also it is assumed that only integer division is considered
:ret: The total number of IP satisfying the requirement
"""
# Step1: extract the alphabeta characters from the string equation
s = strEqu.upper() # Transfer to all uppercase for the convenience of processing
cLst = []
for k in range(len(s)):
if s[k].isalpha() and s[k] not in cLst:
cLst.append(s[k])
if s[k] == '=':
equalSignIndex = k
# print(cLst)
nums = 0
mapping = []
for p in it.permutations([k for k in range(10)], len(cLst)):
# print(p)
# Substitute c<->digit mapping back to the input string equation
# left-hand-side expression, before '='
lhs = s[0:equalSignIndex]
for k in range(len(cLst)):
lhs = lhs.replace(cLst[k], str(p[k]))
# right-hand-side expression, after '='
rhs = s[equalSignIndex+1:]
for k in range(len(cLst)):
rhs = rhs.replace(cLst[k], str(p[k]))
# print(lhs, rhs)
if len(rhs) > 1 and rhs[0] == '0' : # The first digit must be non-zero in multi-digit case
# print('1')
continue
if len(lhs) > 1 and lhs[0] == '0' and lhs[1].isdigit():
# print('2')
continue
if not lhs[-1].isdigit():
# print('3', lhs, lhs[-1].isdigit() )
continue
lhs_valid = True
for k in range(len(lhs)-2):
if (not lhs[k].isdigit()) and lhs[k+1]=='0' and lhs[k+2].isdigit():
# print('invalid lhs:', lhs)
lhs_valid = False
break
if not lhs_valid:
continue
# print('valid:', lhs, rhs, eval(lhs), eval(rhs))
if eval(lhs) == eval(rhs):
nums = nums + 1
mapping.append((cLst,p,lhs+'='+rhs))
return nums, mapping
if __name__ == '__main__':
sln = Solution()
tStart = time.time()
strEqu = 'A*B=C'
nums, mapping = sln.stringEquation(strEqu)
tCost = time.time() - tStart
print('nums={0}, tCost = {1:6.3f}(sec)'.format(nums,tCost))
for item in mapping:
print('\t',item)
tStart = time.time()
strEqu = 'We*love=CodeIQ'
nums, mapping = sln.stringEquation(strEqu)
tCost = time.time() - tStart
print('nums={0}, tCost = {1:6.3f}(sec)'.format(nums,tCost))
for item in mapping:
print('\t',item)
tStart = time.time()
strEqu = 'READ+WRITE+TALK=SKILL'
nums, mapping = sln.stringEquation(strEqu)
tCost = time.time() - tStart
print('nums={0}, tCost = {1:6.3f}(sec)'.format(nums,tCost))
for item in mapping:
print('\t',item)
nums=10, tCost = 46.159(sec)
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (1, 6, 3, 2, 4, 9, 7, 8, 0, 5), '1632+41976+7380=50988')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (2, 5, 4, 3, 7, 0, 6, 9, 1, 8), '2543+72065+6491=81099')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (4, 9, 0, 5, 2, 6, 8, 1, 7, 3), '4905+24689+8017=37611')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (5, 0, 9, 4, 7, 3, 1, 6, 2, 8), '5094+75310+1962=82366')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (5, 0, 9, 6, 3, 7, 1, 8, 2, 4), '5096+35710+1982=42788')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (5, 1, 8, 0, 6, 9, 2, 4, 3, 7), '5180+65921+2843=73944')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (5, 2, 7, 0, 8, 1, 3, 6, 4, 9), '5270+85132+3764=94166')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (7, 0, 9, 2, 3, 5, 1, 8, 6, 4), '7092+37510+1986=46588')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (7, 0, 9, 2, 4, 3, 1, 8, 6, 5), '7092+47310+1986=56388')
(['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S'], (9, 7, 2, 8, 1, 4, 6, 0, 5, 3), '9728+19467+6205=35400')
以上虽然得出的正确的结果,但是运行速度有点衰,需要考虑进一步的优化。