numbers
This repo contains a solver for the "Numbers" game (as played on long-running game shows in the UK, France and Australia), as well as a tiny program to generate all possible legal games for the solver.
Brief rules for the Numbers game:
- 6 "source" numbers are chosen from a pool of 24. The pool contains two each of all the digits from 1 to 10, plus one each of 25, 50, 75 and 100.
- A three-digit "target" number is randomly selected (between 100 and 999)
- The target number must be reached using the source numbers and the basic numerical operations of addition, subtraction, multiplication and division.
- Each source number may only be used in one operation, and each intermediate result can also only be used in one later operation but it is not necessary to use all of the source numbers.
- No intermediate result may be negative
- All intermediate results must be integers
- Maximum points are scored for getting the exact target. Lower points are scored for getting up to 9 away. If the closest number attainable is 10 or more away, nothing is scored and there is considered to be no solution.
For example, with the source numbers 1 3 7 6 8 3 and target number 250 one possible solution is 8×3=24; 24+1=25; 7+3=10; 25×10=250. Note that here we had 2 3's in the source list so 3 could be used twice.
You can download an xz-compressed file containing solutions for all ~12 million possible games here: https://joat.me/all-games-solutions.xz
To build the solver:
crystal build --release numbers.cr
See https://crystal-lang.org/reference/installation/ if you don't have the Crystal compiler.
The program accepts either 7 numbers on the command line (6 source and a target) or lines of 7 space-separated numbers on standard input. To solve the example above:
numbers 1 3 7 6 8 3 250
To test using the included sample games:
numbers < samples
The algorithm is basically exhaustive search with some simple trimming of the expression space for useless or disallowed operations. (A useless operation is, for example, 6÷1 since the result is one of the operands so doesn't accomplish anything.) On relatively modern hardware this still solves over 100 games per second.
Some extra fun flags:
-q
: "quick mode": normally short solutions are checked first, this searches for a solution of any length (usually faster)-a
: "anarchy mode": source numbers are no longer restricted to the pool, target numbers can be any positive integer, and there can be any number of source numbers >=2; the algorithm is roughly O(n²) so if you add lots of source numbers it gets really slow-e
: only show exact solutions-s STEPS
: only find solutions up to STEPS steps (that is, using STEPS operators), otherwise limited only by available source numbers-m
: if many exact solutions exist then print all of them rather than just the first one found (implies-q
; if no exact solutions are found then only one inexact solution will be printed)-b
: if in anarchy mode, use arbitrary-precision integer arithmetic
If you want to feed in crazy large values use the -b
flag, otherwise all calculations are done in 64-bit integers and there's no protection against overflow.
The file all-numbers-solutions.xz was generated by first building the all-game generator:
crystal build --release all-games.cr
Then running it like this:
all-games | numbers | xz -9 > all-numbers-solutions.xz
This will take less than a day on modern hardware. The code is not multi-threaded. Although xz -9
is slow it compresses a lot faster than numbers
can generate solutions, and has by far the best compression ratio with numbers
output (more than 10:1).
numbers
- 0
- 0
- 0
- 0
- 0
- over 4 years ago
- October 8, 2019
Wed, 06 Nov 2024 22:47:17 GMT