《24点》APP——提示功能的实现

更新：《24点》APP——提示功能实现

背景

商店里所有24点 APP 的一个付费功能是提示的获取，会通过限制提示次数，超出次数后观看广告或者购买来解锁额外次数。比如：

这里就来分享一下，类似24点的提示功能是怎么实现的，其实现步骤如下：

步骤一：判断结果能不能等于24；

步骤二：如果能等于24，显示出能得到24的表达式。

下面详细记录一下实现的过程：

解法原理

步骤一，判断能不能等于24

有[a, b, c, d] 四个数字，任取两个数字，通过遍历运算符得到运算结果 e，然后把运算结果和剩余的数字放入新的数组中，重复上面的计算过程，直到数组中有一个元素为止；最后判断数组中唯一的数字是否等于24即可。

这里需要注意几点，一是遍历运算符的时候，加和乘符合交换律，所以不需要重复计算；二是除法会有小数，所以最终判断是否等于24的时候，需要通过设置误差范围来判断；再有就是除法的除数不能为零。

所以最终解法描述如下：

1. 定义误差范围，定义要对比的值，定义运算符数组；
2. 定义判断是否相等的判断方法，传入值和要对比的值的绝对值小于误差范围，即视作相等；
3. 数据转换，由于传入的数字是Int，所以通过 map 转为 Double 类型；
4. 实现计算方法
   1. 数组为空，不合法；
   2. 数组中只有一个数字，即停止，调用判断相等方法判断是否相等
   3. 从数组中依次取两个数字，两个数字不能相等
   4. 把余下的数字放入新的数组中
   5. 遍历运算符数组
      1. 运算符为”+”或”*”时，注意交换律，刚开始 i < j，所以到 i > j 时，就不需要重复计算了
      2. 运算符为”-“时，除数不能为0
      3. 把取出的两个数字通过运算符计算出结果，放入余下数字的新数组中，新数组中即有3个数字
      4. 再从这个新数组中取出两个数字重复上面的计算过程，递归调用，得到返回结果
      5. 如果返回结果不为真，则从3个数字的新数组中，移除最后一个元素即此次通过运算符运算后的数字；然后再继续遍历下一个运算符
   6. 如果所有运算符已遍历完成，结果还不为真，则继续遍历原始数组，取出后面的数字。

流程图如下：

代码实现如下：

// 1. 定义误差范围，定义要对比的值，定义运算符数组；
let elipson = 0.001
let TargetReuslt = 24
let OperationList = ["+", "-", "*", "/"]

class Solution {
    // 2. 定义判断是否相等的判断方法，传入值和要对比的值的绝对值小于误差范围，即视作相等；
    func isEqual24(_ value: Double) -> Bool {
        return abs(value - Double(TargetReuslt)) < elipson
    }

    func judgePoint24(_ list: [Int]) -> Bool {
        // 3. 数据转换，由于传入的数字是Int，所以通过 map 转为 Double 类型；
        let resultList: [Double] = list.map({ Double($0) })
        return find24(resultList)
    }

    // 每次都是选取两张牌
    func find24(_ cards: [Double]) -> Bool {
        // 4.1 数组为空，不合法；
        if cards.count == 0 {
            return false
        }

        // 4.2 数组中只有一个数字，即停止，调用判断相等方法判断是否相等
        if cards.count == 1 {
            let result = isEqual24(cards[0])
            return result
        }

        let count = cards.count
        // 4.3 从数组中依次取两个数字，两个数字不能相等
        for i in 0..<count {
            for j in 0..<count {
                if i != j {
                    let a = cards[i]
                    let b = cards[j]

                    // 4.4 把余下的数字放入新的数组中
                    var restCards: [Double] = []
                    for k in 0..<count {
                        if k != i && k != j {
                            restCards.append(cards[k])
                        }
                    }

                    // 4.5 遍历运算符数组
                    for op in OperationList {
                        // 4.5.1 运算符为"+"或"*"时，注意交换律，刚开始 i < j，所以到 i > j 时，就不需要重复计算了
                        if ((op == "+" || op == "*") && (i > j)) {
                            // "+"、"*", a + b = b + a, no need to recalculate
                            continue
                        }

                        // 4.5.2 运算符为"-"时，除数不能为0
                        if (op == "/") && b < elipson {
                            // "/" dividend can not equal to zero
                            continue
                        }

                        // 4.5.3 把取出的两个数字通过运算符计算出结果，放入余下数字的新数组中，新数组中即有3个数字
                        switch op {
                            case "+":
                                restCards.append(a+b)
                            case "-":
                                restCards.append(a-b)
                            case "*":
                                restCards.append(a*b)
                            case "/":
                                restCards.append(a/b)
                            default:
                                break
                        }

                        // 4.5.4 再从这个新数组中取出两个数字重复上面的计算过程，递归调用，得到返回结果
                        let result = find24(restCards)
                        if result == true {
                            return true
                        }

                        // 4.5.5 如果返回结果不为真，则从3个数字的新数组中，移除最后一个元素即此次通过运算符运算后的数字；然后再继续遍历下一个运算符
                        restCards.removeLast()
                    }
                }
            }
        }
        return false
    }
}

步骤二，获得等于24时的表达式

上面的逻辑计算出能否等于24，那在计算出24的情况下，如何把得到这个结果的表达式显示出来？

回过头来看上面的代码，在步骤4.5.3时，进行了表达式和运算符计算的操作，所以如果想要得到计算的表达式的话，需要在这个计算地方把表达式也存储一下。

然后问题是，计算过程是一个递归的过程，如何在递归的过程中保证前面步骤的表达式不丢失，从而得到递归过程中所有计算的表达式，最终在得到结果时，得到一个表达式数组。

修改func find24(_ cards: [Double]) -> Bool方法，传入参数中增加resultExpressList参数，类型为数组，用于保存每次递归的表达式；传出参数改为增加数组，用于获取最终计算出结果时的表达式。

需要注意：

• func find24(_ cards: [Double]) -> Bool返回类型为元组
• 传入表达式数组不可变，故而需要转为可变的
• 表达式的中数字使用 NSNumber转换，避免浮点精度问题

代码如下：

// 1. 定义误差范围，定义要对比的值，定义运算符数组；
let elipson = 0.001
let TargetReuslt = 24
let OperationList = ["+", "-", "*", "/"]

class Solution {
    // 2. 定义判断是否相等的判断方法，传入值和要对比的值的绝对值小于误差范围，即视作相等；
    func isEqual24(_ value: Double) -> Bool {
        return abs(value - Double(TargetReuslt)) < elipson
    }

    func judgePoint24(_ list: [Int]) -> Bool {
        // 3. 数据转换，由于传入的数字是Int，所以通过 map 转为 Double 类型；
        let resultList: [Double] = list.map({ Double($0) })
        let value: (result: Bool, expressList: [String]) = find24(resultList, resultExpressList: [])
        return value.result
    }

    // 每次都是选取两张牌
    func find24(_ cards: [Double], resultExpressList: [String]) -> (Bool, [String]) {
        // 4.1 数组为空，不合法；
        if cards.count == 0 {
            return (false, resultExpressList)
        }

        // 4.2 数组中只有一个数字，即停止，调用判断相等方法判断是否相等
        if cards.count == 1 {
            let result = isEqual24(cards[0])
            return (result, resultExpressList)
        }
        
        // 将传入数据变为可变数组
        var expressionList: [String] = []
        expressionList.append(contentsOf: resultExpressList)

        let count = cards.count
        // 4.3 从数组中依次取两个数字，两个数字不能相等
        for i in 0..<count {
            for j in 0..<count {
                if i != j {
                    let a = cards[i]
                    let b = cards[j]

                    // 4.4 把余下的数字放入新的数组中
                    var restCards: [Double] = []
                    for k in 0..<count {
                        if k != i && k != j {
                            restCards.append(cards[k])
                        }
                    }

                    // 4.5 遍历运算符数组
                    for op in OperationList {
                        // 4.5.1 运算符为"+"或"*"时，注意交换律，刚开始 i < j，所以到 i > j 时，就不需要重复计算了
                        if ((op == "+" || op == "*") && (i > j)) {
                            // "+"、"*", a + b = b + a, no need to recalculate
                            continue
                        }

                        // 4.5.2 运算符为"-"时，除数不能为0
                        if (op == "/") && b < elipson {
                            // "/" dividend can not equal to zero
                            continue
                        }

                        // 4.5.3 把取出的两个数字通过运算符计算出结果，放入余下数字的新数组中，新数组中即有3个数字
                        // 计算后，将表达式保存到 expressionList 中，并作为下次递归的参数
                        // 注意：表达式的中数字使用 NSNumber，避免浮点精度问题
                        switch op {
                            case "+":
                                restCards.append(a+b)
                                expressionList.append(String(format: "(%@ + %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a + b)))
                            case "-":
                                restCards.append(a-b)
                                expressionList.append(String(format: "(%@ - %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a - b)))
                            case "*":
                                restCards.append(a*b)
                                expressionList.append(String(format: "(%@ * %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a * b)))
                            case "/":
                                restCards.append(a/b)
                                expressionList.append(String(format: "(%@ / %@) = %@", NSNumber(value: a), NSNumber(value: b), NSNumber(value: a / b)))
                            default:
                                break
                        }

                        // 4.5.4 再从这个新数组中取出两个数字重复上面的计算过程，递归调用，得到返回结果
                        let resultValue: (result: Bool, list: [String]) = find24(tempList, resultExpressList: expressionList, level: level)
                        if resultValue.result {
                            return (true, resultValue.list)
                        }

                        // 4.5.5 如果返回结果不为真，则从3个数字的新数组中，移除最后一个元素即此次通过运算符运算后的数字；然后再继续遍历下一个运算符
                        restCards.removeLast()
                    }
                }
            }
        }
        return false
    }
}

测试上面的代码：

给定[6, 8, 5, 8]四个数字，判断能否等于24，如果能，打印表达式，最终打印出的表达式数组如下：

["(6 - 8) = -2", "(5 + -2) = 3", "(8 * 3) = 24"]

从上面打印出的日志可以看到，确实可以计算出24，且把计算出24过程保存下来了，但是跟想象中的不一样，因为同类型《24点》APP的提示功能中，提示的表达式是把步骤合一，最后是一个整体的表达式，而不是分步骤的，所以要怎么把这个步骤合一呢？

再看一遍上面的数字和表达式数组：

数字：              [6, 8, 5, 8]
表达式数组：  ["(6 - 8) = -2", "(5 + -2) = 3", "(8 * 3) = 24"]

要做的就是把表达式数组换成一个完整的表达式：

• 把5+ -2中的-2替换为(6 - 8)
• 把8 * 3中的3替换为(5 + (6- 8))，从而得到最终的(8 * (5 + (6 - 8)))

这个转换需要注意两点：

1. 每个数组只能用一遍
2. 每个表达式只能用一次

笔者这里转换的步骤如下：

• 定义一个字典数组，用于存储每一步转换的字典
• 遍历上面的表达式数组
  • 定义一个字典，三个 key，表达式，表达式结果，表达式是否使用过，{“expressionStr”: “a + b”, “expressionValue”: “c”, “expressionUsed”: “0”}
  • 将表达式和结果分开，存储到字典里，默认没使用过，并且存储到字典数组中
  • 遍历非第一个元素时
    • 遍历字典数组，判断是否使用过，元素是否包含字典表达式元素的值，
      • 包含则把元素中对应的值替换为字典表达式元素的表达式，且标记字典表达式为使用过，且把新的字典存储到字典数组中
      • 不包含，则把新的字典存储到字典数组中
• 最后返回字典数组最后一个元素的表达式，即是所需结果

流程图如下：

代码如下：

func generateExpressStr(from list: [String]) -> String {
        var resultStrList: [NSMutableDictionary] = []
        let strKey = "expressionStr"
        let valueKey = "expressionValue"
        let statusKey = "expressionUsed"

        var newResultStrList: [NSMutableDictionary] = []
        for index in 0..<list.count {
            let itemStr = list[index]
            
            let componentList = itemStr.components(separatedBy: " = ")
            var expressionStr = componentList[0]
            let expressionValue = componentList[1]
            
            if index == 0 {
                let tempDic = NSMutableDictionary()
                tempDic.setValue(expressionStr, forKey: strKey)
                tempDic.setValue(expressionValue, forKey: valueKey)
                tempDic.setValue("0", forKey: statusKey)
                newResultStrList.append(tempDic)
            }
            else {
                for itemDic in resultStrList {
                    print(itemDic)
                    if let previousExpressionStr = itemDic.value(forKey: strKey) as? String,
                       let previousExpressionValueStr = itemDic.value(forKey: valueKey) as? String,
                       let previousStatusValue = itemDic.value(forKey: statusKey) as? String,
                       previousStatusValue == "0" {
                        let tempDic = NSMutableDictionary()
                        if expressionStr.contains(previousExpressionValueStr) {
                            let range = (expressionStr as NSString).range(of: previousExpressionValueStr)
                            let newExpressionStr = (expressionStr as NSString).replacingCharacters(in: range, with: previousExpressionStr)
                            expressionStr = newExpressionStr
                            let newExpressionValue = expressionValue
                            tempDic.setValue(newExpressionStr, forKey: strKey)
                            tempDic.setValue(newExpressionValue, forKey: valueKey)
                            tempDic.setValue("0", forKey: statusKey)
                            newResultStrList.append(tempDic)
                            
                            itemDic.setValue("1", forKey: statusKey)
                        }
                        else {
                            let newExpressionStr = expressionStr
                            let newExpressionValue = expressionValue
                            let tempDic = NSMutableDictionary()
                            tempDic.setValue(newExpressionStr, forKey: strKey)
                            tempDic.setValue(newExpressionValue, forKey: valueKey)
                            tempDic.setValue("0", forKey: statusKey)
                            newResultStrList.append(tempDic)
                        }
                    }
                }
            }
            resultStrList = newResultStrList
        }
        let resultStr = resultStrList.last?.value(forKey: strKey) as? String ?? ""
        print(resultStr)
        return resultStr
    }

完整代码

本篇的完整代码已整理放在Github，链接如下：
https://github.com/mokong/game24HintDemo

最终效果如下：

结语

通过Swift 后缀表达式和24点提示功能的实现两篇文章，介绍了做一个《24点 APP》所需的主要功能，感兴趣的可以自己设计 UI、动效，加上自己独有的功能实现，比如换肤、闯关、内购等等，可以做出自己的独特的《24点 APP》，欢迎大家尝试。