# peijunz/game24

24 Puzzle Game: A simple arithmetic game with a solver and a pyqt graphical front end.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
Dist
img
numgame
.gitignore
Makefile
TODO.md
game24
game24.desktop
numsolver
setup.py

# 24 Game

24 game is an arithmetic game with a simple rule: Given 4 numbers and use `+ - * /` to get 24.

• A simple example is `1,2,3,4`, and you find `1*2*3*4=24`
• A more difficult one is `5 5 5 1`, the answer is `5*(5-(1/5))=24`, which includes fractions.

The project provides a powerful solver for the 24 game. And you can play with the PyQt5 based graphical front end.

## Graphical PyQt5 front end

Run the python3 script `game24` to play the game:

There is also a `solver` to solve number puzzles:

### Dependency and Packaging

• Depends on `pyqt5`
• Packaging for rpm: `Dist/24game.spec`

## Generalized 24 Game Solver in CLI

The generalized 24 game is able to handle lists of moderate length as well as any aim.

No dependency except `python3` for the solve.

### Usage

Use `getanswer` to get answer in arithmetic expression

```from Game24.Solver import getanswer

You will get `'5*(5-(1/5))'` returned.

Use `solve()` to get answer in step by step manner. It is fast enough even for a long list and strange aiming number:

```from Game24.Solver import solve
solve([1,5,5,5], 24)```

You will get

``````[
[Fraction(1, 1), Fraction(5, 1), Fraction(5, 1), Fraction(5, 1)],
[Fraction(5, 1), Fraction(5, 1), Fraction(1, 5)],
[Fraction(5, 1), Fraction(24, 5)],
[Fraction(24, 1)]
]
``````

## Use C++ solver extension

Default solver written in python is slow, which makes is hard to handle long list. To use the C++ extension, you need to compile the shared library on your own computer using `make` at the `Game24/Solver` directory.

### Example

The C++ solver is fast enough even for a long list and strange aiming number:

```from Game24.Solver import solve
for i in range(100):
solve([1,2,3,4,5,6,7,8,9,10,11,12],i)  # Get result in about 1 second```

If the compiled C++ shared library `solver.so` is not available, or not setup properly, the program will use python solver as a fallback, at the expense of runtime speed.

## Complexity

If the aim is too large, there may well be only few solutions or even no solution. In this case, the time cost will be very LARGE because the program must enumerate all possibilities.

In the worst case for a list of length L, it will consume time propotional to \$3^{L-1}L!(L-1)!\$:

L Time(L)
2 6
3 108
4 3888
5 233280
6 20995200
7 2645395200
8 444426393600
9 95996101017600

From \$L>6\$, the worst case time become unbearable.

Hint: In the example for C++ extension above, the list length is 12 and the worst time is `3387088029864591360000`. But we definitely get all the answers in 1 second for 100 test cases. The reason is that the input has various numbers and a small aim. So the actual time is far less than worst case.