Not brute force algorithm

1. Jun 27, 2017

uzi kiko

Hi
We have a family game when we are stuck in traffic similar to https://en.wikipedia.org/wiki/Countdown_(game_show)
(I know I am a nerd )

In the game we are looking at license plate of the car in front and trying to get 120 using the 4 arithmetic operators (+-*/) and the numbers in the license plate in the same order as they appear there.
For example:
If the license plate is 212614
2+1+2*6*1*4=120.

Obviously there is no solution for all the plates, but I would like to write a small program to find the solution (if exist) to check myself.

I can write a brute force algorithm that will go through all the options, but I wonder if there is a better algorithm.

Can you suggest a better solution?

Last edited by a moderator: Jun 27, 2017
2. Jun 27, 2017

Staff: Mentor

I can't think of an algorithm off-hand other than trying all combinations which I think is 4^5 (1024) combinations for 6 digits/4 operators given that the digits are known.

Were you planning on doing this by PC or mobile?

Android has some apps like APDE (Android Processing Developers Environment) which could work well here. You'd be writing the app in Java on Android and running it on Android. For iOS there's Pythonista where you'd do the same but would be using Python. On the PC you could use the Processing IDe and write it in Java, Javascript or Python your choice.

There are other apps available but these are the ones I'm familiar with.

3. Jun 27, 2017

Filip Larsen

Better in what way? Faster?

For comparison, with 6 digits, 5 operator places and 4 operators, a simple brute force algorithm would have to check 1024 combinations which should be no problem on even very modest hardware. If you allow digits to be read as multiple digits you end up with 3125 combinations, still well within reach of brute force.

4. Jun 27, 2017

wle

I'd be surprised if there were. I'm a bit confused about the rules though given your example:
2+1+2*6*1*4 is 51. However, (2+1+2)*6*1*4 = 120. So are you counting with any possible way of putting the brackets or do you mean something more specific (e.g., keeping a sort of running total)?

5. Jun 28, 2017