在车牌上取零

Question

当我还小的时候，我和我的堂兄弟们玩下一个游戏：

“汽车牌照中的零”：通过使用汽车牌照号码中的数字，并分别使用基本运算(和、减、积和除)，您必须找到一个等于0的顺序。

例如，如果我们有以下车牌：

2591 --> (2*5)-(9+1) = 0

2491 --> (2*4)+1 -9 = 0

我想用Haskell或Python做一个程序，让它能够玩这个游戏，并打印出结果为0的步骤。

getZero 2491 =  2*4+1-9
getZero 2591 =  2*5-9+1

也许这是不可能的，我希望你能帮助我。

Answer 1

这可能是离题的，但却是一个有趣的玩具难题。

思考这个问题的一种简单方法是分成四个独立的部分：

Pretty Pretty对参数进行枯燥的处理并打印results

• Construct给定numbers.

• Interpret的二进制操作的所有可能表达式这些表达式可获取数值文字并删除任何非零的结果。

1. 打印表达式。

我们可以执行额外的步骤，例如基于代数规则过滤重复项(a + b和b + a在道德上是相同的)，但我跳过了这一步。

无聊的管道只是获取我们的车牌号码(每个参数一个)，将这些车牌号码分解成数字，运行我们的计算，并打印解决方案。

import Data.Foldable
import Data.List
import System.Environment

main :: IO ()
main =
  do ns <- getArgs
     for_ ns $ \n -> do
        let digitList = map (read . (:[])) (n :: String) :: [Int]
        putStrLn $ "---------- " ++ show n ++ " ----------"
        putStrLn $ unlines (map render (solutions digitList))

Construction真正有趣的地方在于构建了一个包含操作和叶的二叉树。首先，我们定义表达式语言：

data Expr = Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | Lit Int
        deriving (Eq, Ord, Show)

我们可以结合使用这些表达式和Haskell列表monad来构建所有可能的表达式(假设一个非空的列表作为输入)：

operations :: [Expr -> Expr -> Expr]
operations = [Add, Sub, Mul, Div]

exprsOf :: [Expr] -> [Expr]
exprsOf [term] = [term]
exprsOf xs =
  do x <- xs
     y <- (delete x xs)
     o <- operations
     exprsOf (o x y : delete y (delete x xs))

也就是说，x是原始表达式集中的元素之一。y是另一个元素(但不是x)。o是我们的合法操作之一(加法、减法等)。我们递归地减小这个列表的大小，直到我们得到顶层表达式(变量名term)。如果你不理解操作，那就是让人困惑的特定部分，你可以提出一个很好的(关于主题的)问题。

Interpretation随着表达式的构建，我们现在可以解释它们并过滤掉任何不会导致零的结果。

当我们看到我们的Add构造函数时，解释器正在使用加法(+)，其他操作也是如此。我把所有东西都放到了“可能适用”中，因为我不想在我们的结果中显示被零除或有余数的除法。

interp :: Expr -> Maybe Int
interp (Lit n) = Just n
interp (Add a b) = (+) <$> interp a <*> interp b
interp (Sub a b) = (-) <$> interp a <*> interp b
interp (Mul a b) = (*) <$> interp a <*> interp b
interp (Div a b) | interp b == Just 0 = Nothing
                 | interp b == Nothing = Nothing
                 | otherwise          =
        case divMod <$> interp a <*> interp b of
            Nothing -> Nothing
            Just (x,0) -> Just x
            _ -> Nothing -- Ignore uneven division

应用这种解释只需要对Just 0进行过滤

solutions :: [Int] -> [Expr]
solutions xs = filter ((== Just 0) . interp) $ exprsOf (map Lit xs)

渲染最后，有一个相当丑陋的渲染函数，只是为了发出正确的括号，所以我们可以看到正确的操作顺序：

render :: Expr -> String
render (Lit n) = show n
render (Add a b) = "(" ++ render a ++ " + " ++ render b ++ ")"
render (Sub a b) = "(" ++ render a ++ " - " ++ render b ++ ")"
render (Mul a b) = "(" ++ render a ++ " * " ++ render b ++ ")"
render (Div a b) = "(" ++ render a ++ " / " ++ render b ++ ")"

示例运行

*Main> :main 2591
---------- "2591" ----------
(((2 * 5) - 9) - 1)
(1 - ((2 * 5) - 9))
(((2 * 5) - 1) - 9)
(9 - ((2 * 5) - 1))
((9 - (2 * 5)) + 1)
(1 + (9 - (2 * 5)))
((9 + 1) - (2 * 5))
((2 * 5) - (9 + 1))
((1 - (2 * 5)) + 9)
(9 + (1 - (2 * 5)))
((1 + 9) - (2 * 5))
((2 * 5) - (1 + 9))
(((5 * 2) - 9) - 1)
(1 - ((5 * 2) - 9))
(((5 * 2) - 1) - 9)
(9 - ((5 * 2) - 1))
((9 - (5 * 2)) + 1)
(1 + (9 - (5 * 2)))
((9 + 1) - (5 * 2))
((5 * 2) - (9 + 1))
((1 - (5 * 2)) + 9)
(9 + (1 - (5 * 2)))
((1 + 9) - (5 * 2))
((5 * 2) - (1 + 9))
(((9 + 1) / 2) - 5)
(5 - ((9 + 1) / 2))
(((9 + 1) / 5) - 2)
(2 - ((9 + 1) / 5))
((2 * 5) - (9 + 1))
((9 + 1) - (2 * 5))
((5 * 2) - (9 + 1))
((9 + 1) - (5 * 2))
(((1 + 9) / 2) - 5)
(5 - ((1 + 9) / 2))
(((1 + 9) / 5) - 2)
(2 - ((1 + 9) / 5))
((2 * 5) - (1 + 9))
((1 + 9) - (2 * 5))
((5 * 2) - (1 + 9))
((1 + 9) - (5 * 2))

Answer 2

这不是最好的实现，因为有相当多的重复，但确实得到了结果。

使用itertools，我生成了数字和运算可能所处的每种不同状态(排列)，例如：

[('1', '2', '3', '4'), ('1', '2', '4', '3'), ('1', '3', '2', '4'), ('1', '3', '4', '2'), ('1', '4', '2', '3'), ....... ('4', '1', '3', '2'), ('4', '2', '1', '3'), ('4', '2', '3', '1'), ('4', '3', '1', '2'), ('4', '3', '2', '1')]

[('+', '-', '*'), ('+', '*', '-') ...... ('/', '-', '*'), ('/', '*', '-')]

...then，我做了一个函数，将括号添加到计算的每种可能状态：

[1,'+',2,'-',3,'*',4]变成：

1 + 2 - 3 * 4
( 1 + 2 ) - ( 3 * 4 )
( 1 + 2 - 3 ) * 4
1 + ( 2 - 3 * 4 )
( 1 + 2 ) - 3 * 4
1 + 2 - ( 3 * 4 )
1 + ( 2 - 3 ) * 4 

..。然后，评估每种不同的可能性，如果是零，我就把它打印出来。

下面是所有的代码：

from itertools import permutations, combinations, chain
import sys

operations = ['+', '-', '*', '/'] # basic operations

# add every combination of brackets to the calculation
def addBrackets(calc):
    possibilities = []
    possibilities.append(" ".join(calc))
    possibilities.append(" ".join(str(s) for s in list(chain(["("], calc[:3], [")"], [calc[3]], ["("], calc[4:], [")"]))))
    possibilities.append(" ".join(str(s) for s in list(chain(["("], calc[:-2], [")"], calc[-2:]))))
    possibilities.append(" ".join(str(s) for s in list(chain(calc[:2], ["("], calc[2:], [")"]))))
    possibilities.append(" ".join(str(s) for s in list(chain(["("], calc[:3], [")"], calc[3:]))))
    possibilities.append(" ".join(str(s) for s in list(chain(calc[:4], ["("], calc[4:], [")"]))))
    return possibilities

def getZero(n): # 2491
    nums = [x for x in str(n)] # [2, 4, 9, 1]
    while len(nums) < 4:
        nums = ['0'] + nums # add zeroes if the input was less than 1000 e.g. [5, 3, 1] -> [0, 5, 3, 1]
    possible_number_order = list(permutations(nums)) # get every number order
    possible_op_order = list(combinations(operations, 3)) # get combinations of 3 of the operations
    possible_op_permutations = list(chain(list(permutations(p)) for p in possible_op_order)) # chain together all the permutations of each combination
    possible_op_order = []
    for perms in possible_op_permutations: 
        possible_op_order.extend(perms) # add all the lists into one
    for n in possible_number_order: # for each number order
        for op in possible_op_order: # for each operation order
            calculation = [n[0],op[0],n[1],op[1],n[2],op[2],n[3]] # create a list with the order of the operation
            for calc in addBrackets(calculation): # for each bracket position
                try:
                    result = eval(calc) # evaluate
                    if abs(result) <= 0.001: # to check for float comparison
                        print("{} = {}".format(calc, 0))
                except: # ZeroDivisionError
                    continue

if __name__ == "__main__":
    for user_input in [int(n) for n in sys.argv[1:]]:
        print("-------{0:04}-------".format(user_input)) # print 0 padded output
        getZero(user_input)

输入作为命令行参数的输入：

$ python3.6 zerogame.py 2491 2591
-------2491-------
( 2 * 4 - 9 ) + 1 = 0
( 2 * 4 ) - 9 + 1 = 0
( 2 * 4 ) + ( 1 - 9 ) = 0
( 2 * 4 + 1 ) - 9 = 0
( 2 * 4 ) + 1 - 9 = 0
2 * 4 + ( 1 - 9 ) = 0
2 + ( 1 - 9 ) / 4 = 0
( 4 * 2 - 9 ) + 1 = 0
( 4 * 2 ) - 9 + 1 = 0
( 4 * 2 ) + ( 1 - 9 ) = 0
( 4 * 2 + 1 ) - 9 = 0
( 4 * 2 ) + 1 - 9 = 0
4 * 2 + ( 1 - 9 ) = 0
4 + ( 1 - 9 ) / 2 = 0
9 - ( 2 * 4 + 1 ) = 0
9 - ( 4 * 2 + 1 ) = 0
9 - ( 1 + 2 * 4 ) = 0
9 - ( 1 + 4 * 2 ) = 0
( 1 + 2 * 4 ) - 9 = 0
1 + ( 2 * 4 - 9 ) = 0
1 + ( 2 * 4 ) - 9 = 0
( 1 + 4 * 2 ) - 9 = 0
1 + ( 4 * 2 - 9 ) = 0
1 + ( 4 * 2 ) - 9 = 0
( 1 - 9 ) + ( 2 * 4 ) = 0
( 1 - 9 ) + 2 * 4 = 0
1 - 9 + ( 2 * 4 ) = 0
( 1 - 9 ) / 2 + 4 = 0
( 1 - 9 ) + ( 4 * 2 ) = 0
( 1 - 9 ) + 4 * 2 = 0
1 - 9 + ( 4 * 2 ) = 0
( 1 - 9 ) / 4 + 2 = 0
-------2591-------
( 2 * 5 ) - ( 9 + 1 ) = 0
2 * 5 - ( 9 + 1 ) = 0
( 2 * 5 ) - ( 1 + 9 ) = 0
2 * 5 - ( 1 + 9 ) = 0
2 - ( 9 + 1 ) / 5 = 0
2 - ( 1 + 9 ) / 5 = 0
( 5 * 2 ) - ( 9 + 1 ) = 0
5 * 2 - ( 9 + 1 ) = 0
( 5 * 2 ) - ( 1 + 9 ) = 0
5 * 2 - ( 1 + 9 ) = 0
5 - ( 9 + 1 ) / 2 = 0
5 - ( 1 + 9 ) / 2 = 0
( 9 - 2 * 5 ) + 1 = 0
9 - ( 2 * 5 ) + 1 = 0
( 9 - 5 * 2 ) + 1 = 0
9 - ( 5 * 2 ) + 1 = 0
( 9 + 1 ) - ( 2 * 5 ) = 0
9 + ( 1 - 2 * 5 ) = 0
( 9 + 1 ) - 2 * 5 = 0
9 + 1 - ( 2 * 5 ) = 0
( 9 + 1 ) / 2 - 5 = 0
( 9 + 1 ) - ( 5 * 2 ) = 0
9 + ( 1 - 5 * 2 ) = 0
( 9 + 1 ) - 5 * 2 = 0
9 + 1 - ( 5 * 2 ) = 0
( 9 + 1 ) / 5 - 2 = 0
( 1 - 2 * 5 ) + 9 = 0
1 - ( 2 * 5 ) + 9 = 0
( 1 - 5 * 2 ) + 9 = 0
1 - ( 5 * 2 ) + 9 = 0
( 1 + 9 ) - ( 2 * 5 ) = 0
1 + ( 9 - 2 * 5 ) = 0
( 1 + 9 ) - 2 * 5 = 0
1 + 9 - ( 2 * 5 ) = 0
( 1 + 9 ) / 2 - 5 = 0
( 1 + 9 ) - ( 5 * 2 ) = 0
1 + ( 9 - 5 * 2 ) = 0
( 1 + 9 ) - 5 * 2 = 0
1 + 9 - ( 5 * 2 ) = 0
( 1 + 9 ) / 5 - 2 = 0