目錄

1. 問題描述

2. 解題思路

3. 代碼及測驗

4. 優化

1. 問題描述

所謂字母算式，就是用字母表示的算式，規則是相同字母對應相同數字，不同字母對應不同數字，并且第一位字母的對應數字不能是 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

2. 解題思路

本題解著眼于通用的解決方案，即不僅限于以上運算式，而是任意的字串運算式（前提式的確能夠代表合法的演算法，比如說運算子不能連續出現，等等），

基本步驟如下：

Step1: 從輸入字串中提取出表示數字（即除運算子和等號外）（不重復, or unique）字符集合

Step2: 遍歷以上所有字符與數字(0~9)的映射方式，假定有k個字符，則有P(10,k)中排列，每一種排列對應一種映射方式

Step2-1將每一種映射方式代入到輸入字串得到字串算式

Step2-2 判斷所得到的字串算式是否是合法的

Step2-3 分別評估字串算式的LHS（Left-hand-side:左手邊運算式）和RHS（Right-hand-side:右手邊運算式）并判斷是否相等

在Step2中用python itertools模塊中的permutation()生成所有的組合，

在Step2-3中用pyhton內置的eval()函式進行字串形式的算式值的評估

在 Step2-2中判斷字串運算式是否合法依據的規則是多位數字的運算元的第一個字母不能為0，首先基于‘=’的位置分割得到LHS和RHS，

RHS中因為沒有運算子所以比較簡單，只要有多位數字（長度大于1）且首位為0就表示是非法運算式，

LHS的情況比較復雜，分以下三種情況考慮：

1. 第一個運算元的判斷：如果LHS[0]為0且LHS[1]仍為數字則表明肯定非法
2. 其后，搜索每個運算子，如果運算子后的第一個字符為0且第二個字符仍為數字，則為非法
3. LHS的最后一個字符不能為運算子—這個判斷，基于以下假設其實并不需要

當然以上判斷方法是基于原輸入字串運算式肯定可以表達成一個合法的算式，比如不會有兩個連續的運算子出現，等等，

3. 代碼及測驗

# -*- 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')

4. 優化

以上雖然得出的正確的結果，但是運行速度有點衰，需要考慮進一步的優化，

上一篇：Q12: 平方根數字

下一篇：

本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解