# Triple-six puzzle

Consider the following puzzle:

  * $0 \, 0 \, 0 = 6$
  * $1 \, 1 \, 1 = 6$
  * $2 \, 2 \, 2 = 6$
  * ...
  * $10 \, 10 \, 10 = 6$

Insert operators `+`, `-`, `*`, `/`, square root and factorial such that the equations hold, e.g., $(1 + 1 + 1)! = 6$.  For most, multiplle solutions are possible, e.g., trivially, $(\sqrt{1} + \sqrt{1} + \sqrt{1})! = 6$.  A few less trivial examples would be $3! + 3 - 3 = 6$, $3!*3/3 = 6$, or $3*3 - 3 = 6$.

We will use the sympy library to tackle the puzzle.


```python
import itertools
import sympy
```

## Representing expressions

We start by defining the binary operators `+`, `-`, `*` and `/` based on sympy primitives `sympy.Add`, `sympy.Mul`, and `sympy.Pow`.  For each operator, we set `evaluate` to `False` to ensure that we can create an expression that isn't symplified automatically, i.e., $x + x$ should not be simplified to $2x$.


```python
def Add(x, y):
    return sympy.Add(x, y, evaluate=False)
```


```python
def Sub(x, y):
    return Add(x, -y)
```


```python
def Mul(x, y):
    return sympy.Mul(x, y, evaluate=False)
```


```python
def Div(x, y):
    return Mul(x, sympy.Pow(y, -1))
```


```python
binary_operators = [Add, Sub, Mul, Div]
```

Next, we define the unary operators square root and factorial, again based on their sympy implementation.


```python
def Sqrt(x):
    return sympy.sqrt(x, evaluate=False)
```


```python
def Fac(x):
    return sympy.factorial(x, evaluate=False)
```


```python
unary_operators = [Sqrt, Fac]
```

Using these operators, we can build experssions in a symbol `x`.


```python
x = sympy.Symbol('x')
```


```python
expr = Sub(Mul(x, x), x)
expr
```




    -x + x*x



Substituing 3 for `x` yields 6.


```python
expr.subs(x, 3)
```




    6



We can construct more elaborate expressions as well.  This one will evalutate to 6 for `x` is 3.


```python
expr = Mul(Fac(x), Div(x, x))
expr
```




    (x/x)*factorial(x)




```python
expr.subs(x, 3) == 6
```




    True



## Counting expressions

Now that we have a way to represent expressions, we need a way to generate all relevant expressions systematically.

Unfortunately, the number of mathematical expressions satifying the equations is infinite.  This is easy to proof since, e.g.,$1! = 1$, so $(1 + 1 + 1)! = (1! + 1! + 1!)! = (1!! + 1!! + 1!!)! = \cdots = 6$.

This problem can be circumvented by limiting the number of consecutive unary operations to some number, say 2.  This would yield $x$, $x!$, $\sqrt{x}$, $x!!$, $\sqrt{x}!$, $\sqrt{x!}$, $\sqrt{\sqrt{x}}$.  In general, if the number of consecutive uniary opreations is $d_{unary}$, then the number of combinations is $c_{unary} = 2^{d_{unary} + 1} - 1$, so 7 for $n = 2$.

If we consider only a single binary operator, the number of such expression would be $7 \times 4 \times 7 \times 7$.  Now we can add the second binary operator.  The first expression will be either the first, or the second operated, so that gives rise to a factor of 2.  For the other operand, there are again 7 possibilities, and we can apply 7 combinations of unary operators.  In total, there are $7 \times 7 \times 4 \times 7 \times 2 \times 7 \times 4 \times 7$ expressions.


```python
d_unary = sympy.Symbol('d_unary')
n_unary = sympy.Symbol('n_unary')
c_unary = n_unary**(d_unary + 1) - 1
n_binary = sympy.Symbol('n_binary')
```


```python
nr_expressions = c_unary*c_unary*n_binary*c_unary*2*c_unary*n_binary*c_unary
nr_expressions.subs(((n_unary, 2), (n_binary, 4), (d_unary, 2)))
```




    537824



These expressions need to be evaluated for each number from 0 to 10 which gives a quite impressive number of evaluations.


```python
nr_evaluations = 11*nr_expressions
nr_evaluations
```




    22*n_binary**2*(n_unary**(d_unary + 1) - 1)**5



Obviously, many expressions will be equivalent due to the properties of the mathematical operations, e.g., associativity, $a + (b + c) = (a + b) + c = a + b + c$.

It is also worth pointing out that this will not (reasonably) work.  One of the expressions that will be generated is $((10!! \times 10!!)!! \times 10!!)!!$, and you don't even want to think about the number of digits required to represent that number, given that $100!$ has 158 digits!


```python
sympy.factorial(100)
```




    93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000



Since $x!!$ will not yield any solutions that are non-trial, we will exclude this case.  That means that the total number of expressinos is reduced to $6 \times 6 \times 4 \times 6 \times 2 \times 6 \times 4 \times 6$ expressions.


```python
print(f'The total number of expressions is {6*6*4*6*2*6*4*6}')
```

    The total number of expressions is 248832


## Generating expressions

Now we have all ingredients to construct expressions.  We can write a generator for that purpose.  We define a helper function to apply a list of function, e.g., `[f, g]` to an argument `x` to result in `f(g(x))`.


```python
def compose(func_list, x):
    expr = x
    for func in func_list:
        expr = func(expr)
    return expr
```

We need a function that will generate all expressions, and we implement it as a generator using `yield`.


```python
def expression_trees():
    u_ops = [[], [Sqrt], [Fac], [Sqrt, Sqrt], [Sqrt, Fac], [Fac, Sqrt]]
    x = sympy.Symbol('x')
    for u_ops_1 in u_ops:
        operand_11 = compose(u_ops_1, x)
        for u_ops_2 in u_ops:
            operand_12 = compose(u_ops_2, x)
            for b_op_1 in binary_operators:
                for u_ops_3 in u_ops:
                    operand_21 = compose(u_ops_3, b_op_1(operand_11, operand_12))
                    for u_ops_4 in u_ops:
                        operand_22 = compose(u_ops_4, x)
                        for b_op_2 in binary_operators:
                            for u_ops_5 in u_ops:
                                yield compose(u_ops_5, b_op_2(operand_21, operand_22))
                                yield compose(u_ops_5, b_op_2(operand_22, operand_21))
```

Let's verify that we really generate the expected number of expressions.


```python
counter = 0
for _ in expression_trees():
    counter += 1
print(f'{counter} expression generated')
```

    248832 expression generated


Finally, the following function will solve the puzzle for a given value of $x$.  It will print all expressions that evaluate to 6, and return the total number of such expressions.


```python
def solve_puzzle(value):
    counter = 0
    for i, expr in enumerate(expression_trees()):
        try:
            if expr.subs(x, value) == 6:
                counter += 1
                print(str(expr).replace('x', str(value)))
        except ValueError:
            pass
    print(f'{counter} solutions for {value:d}')
    return counter
```


```python
solve_puzzle(0)
```

Since it takes considerable time to generate all expressions, it is more efficient to do that only once, and evaluate it for all $x$ values at once.


```python
def solve_puzzle_all_values(max_value=10):
    counter = 0
    for i, expr in enumerate(expression_trees()):
        for value in range(max_value + 1):
            try:
                if expr.subs(x, value) == 6:
                    counter += 1
                    print(str(expr).replace('x', str(value)))
            except ValueError:
                pass
    print(f'{counter} solutions for 0 up to {max_value:d}')
    return counter
```

ae4eed913e1b1336e911fbabc633683a146c5731
ipynb
Jupyter Notebook
Python/Sympy/triple_six_puzzle.ipynb
Gjacquenot/training-material
16b29962bf5683f97a1072d961dd9f31e7468b8d
CC-BY-4.0
2015-03-23T13:34:42.000Z
2022-03-21T00:27:21.000Z
Python/Sympy/triple_six_puzzle.ipynb
Gjacquenot/training-material
16b29962bf5683f97a1072d961dd9f31e7468b8d
CC-BY-4.0
2015-02-25T15:04:26.000Z
2022-01-03T07:42:48.000Z
Python/Sympy/triple_six_puzzle.ipynb
Gjacquenot/training-material
16b29962bf5683f97a1072d961dd9f31e7468b8d
CC-BY-4.0
2015-11-26T11:44:51.000Z
2022-03-21T00:27:22.000Z
Qwen/Qwen-72B
1. YES
2. YES