Thread: 5 dice and a basic math game (MathDice)

Hi

i recently was introduced to a good game.
First, you need to roll the 5 dice and then someone gives you a target number.
The objective is to come up with a set of mathematical operations (+,-,x,/) that would compute the target number.
Each of the 5 dice must be used once and only once.
There's no strict rule for the mathematical operations (u can either repeatedly use any of them or not at all)

Ex.
say u roll the dice, and u get these numbers (4 3 1 6 6) and the target number is 12.
then you would probably say : 4 * 3 * 1 * (6 / 6) = 12
The game is simple and we all should have played similar ones when we were younger.


My question is... Is there an algorithm that would come up with that set of operators?

Originally Posted by glaboratory

Hi

i recently was introduced to a good game.
First, you need to roll the 5 dice and then someone gives you a target number.
The objective is to come up with a set of mathematical operations (+,-,x,/) that would compute the target number.
Each of the 5 dice must be used once and only once.
There's no strict rule for the mathematical operations (u can either repeatedly use any of them or not at all)

Ex.
say u roll the dice, and u get these numbers (4 3 1 6 6) and the target number is 12.
then you would probably say : 4 * 3 * 1 * (6 / 6) = 12
The game is simple and we all should have played similar ones when we were younger.


My question is... Is there an algorithm that would come up with that set of operators?

In fact, a brute force search is quite fast for five numbers (try all possible combinations). The operators can be chosen in 4^4 ways. The number of ways to parenthesise is given by the Catalan numbers. The overall number of possible expressions is not terribly high for modern computers. You can use Reverse Polish notation to ease the order of operations issue. You could either store the numbers as fractions, or use floating point and test whether they are integers within a certain tolerance.

A variation on the problem would be to allow concatenation of adjacent numbers.

Of interest: link 1 and link 2 -- problems from Project Euler.

Note that all Project Euler problems have solutions that can run in under one minute in a compiled language, and almost always in an interpreted language as well, on a system with standard (modest) specs.

In terms of an algorithm you could do in your head on the spot, I don't know of any general way. Obviously if you play a lot you will recognize some patterns and remember ways to get common numbers; e.g., you will recognize when the target is simply the product of all the numbers. I think that might fall more under Heuristics than an algorithm -- using "best guess" methods.