程序员的算法趣题Q13: 满足字母算式的解法
目录
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. 解题思路
本题解着眼于通用的解决方案,即不仅限于以上表达式,而是任意的字符串表达式(前提式的确能够代表合法的算法,比如说运算符不能连续出现,等等)。
基本步骤如下:
在Step2中用python itertools模块中的permutation()生成所有的组合。
在Step2-3中用pyhton内置的eval()函数进行字符串形式的算式值的评估
在 Step2-2中判断字符串表达式是否合法依据的规则是多位数字的操作数的第一个字母不能为0。首先基于‘=’的位置分割得到LHS和RHS。
RHS中因为没有运算符所以比较简单,只要有多位数字(长度大于1)且首位为0就表示是非法表达式。
LHS的情况比较复杂,分以下三种情况考虑:
- 第一个操作数的判断:如果LHS[0]为0且LHS[1]仍为数字则表明肯定非法
- 其后,搜索每个运算符,如果运算符后的第一个字符为0且第二个字符仍为数字,则为非法
- 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: 平方根数字
下一篇:Q14: 国名接龙
本系列总目录参见:程序员的算法趣题:详细分析和Python全解
相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- 笛卡尔积 php,PHP笛卡尔积实现算法示例
- 微软程序员的算法心得
- Topk算法_topn算法
- jvm垃圾回收算法有哪些_jvm垃圾回收过程
- 有没有可能是你的武器不够强大呢?(算法,程序员请进)
- 常见的js算法_javascript数据结构与算法
- 【分布式系统】深入理解一致性 Hash 算法
- 程序员必备的数据库知识 2:Join 算法
- 数据结构实验之图论七:驴友计划【迪杰斯特拉算法】(SDUT 3363)
- A.机器学习入门算法[七]:基于英雄联盟数据集的LightGBM的分类预测
- 【计算理论】计算复杂性 ( P 类 | 有效算法函数 | NP 直觉 | NP 简介 | NP 类严格数学定义 )
- 【数据挖掘】数据挖掘总结 ( 模式挖掘 | Apriori 算法 | 支持度 | 置信度 | 关联规则 ) ★★
- 死磕算法!35 篇算法设计实例+6 本必读书打包送你
- 数据结构和算法指南
- KNN算法详解程序员
- 常用排序算法的时间和空间复杂度及算法时间复杂度的简单计算详解程序员
- python解决八皇后算法详解编程语言
- Java程序员必须掌握的8大排序算法详解编程语言
- 必须知道的八大种排序算法【java实现】(三) 归并排序算法、堆排序算法详解编程语言
- 使用LinkedHashMap来实现一个使用LRU(Least Recently Used)算法的cache详解编程语言
- LRU算法的Java实现详解编程语言
- 想了解机器学习?你需要知道的十个基础算法
- 实现Redis集群数据共享的算法探索(redis集群中数据共享)
- C#排序算法之快速排序