combinatorics - How to design an algorithm to calculate countdown style maths number puzzle

Question

I have always wanted to do this but every time I start thinking about the problem it blows my mind because of its exponential nature.

The problem solver I want to be able to understand and code is for the countdown maths problem:

Given set of number X1 to X5 calculate how they can be combined using mathematical operations to make Y. You can apply multiplication, division, addition and subtraction.

So how does 1,3,7,6,8,3 make 348?

Answer: (((8 * 7) + 3) -1) *6 = 348.

How to write an algorithm that can solve this problem? Where do you begin when trying to solve a problem like this? What important considerations do you have to think about when designing such an algorithm?

Answer 1

Sure it's exponential but it's tiny so a good (enough) naive implementation would be a good start. I suggest you drop the usual infix notation with bracketing, and use postfix, it's easier to program. You can always prettify the outputs as a separate stage.

Start by listing and evaluating all the (valid) sequences of numbers and operators. For example (in postfix):

1 3 7 6 8 3 + + + + + -> 28
1 3 7 6 8 3 + + + + - -> 26

My Java is laughable, I don't come here to be laughed at so I'll leave coding this up to you.

To all the smart people reading this: yes, I know that for even a small problem like this there are smarter approaches which are likely to be faster, I'm just pointing OP towards an initial working solution. Someone else can write the answer with the smarter solution(s).

So, to answer your questions:

• I begin with an algorithm that I think will lead me quickly to a working solution. In this case the obvious (to me) choice is exhaustive enumeration and testing of all possible calculations.
• If the obvious algorithm looks unappealing for performance reasons I'll start thinking more deeply about it, recalling other algorithms that I know about which are likely to deliver better performance. I may start coding one of those first instead.
• If I stick with the exhaustive algorithm and find that the run-time is, in practice, too long, then I might go back to the previous step and code again. But it has to be worth my while, there's a cost/benefit assessment to be made -- as long as my code can outperform Rachel Riley I'd be satisfied.
• Important considerations include my time vs computer time, mine costs a helluva lot more.