Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Not brute force algorithm

  1. Jun 27, 2017 #1
    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. jcsd
  3. Jun 27, 2017 #2

    jedishrfu

    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.
     
  4. Jun 27, 2017 #3

    Filip Larsen

    User Avatar
    Gold Member

    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.
     
  5. Jun 27, 2017 #4

    wle

    User Avatar

    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)?
     
  6. Jun 28, 2017 #5
    Thanks a lot for your answers.

    The purpose of the question was mainly for my education...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Not brute force algorithm
  1. VEGAS algorithm (Replies: 2)

  2. Ask an algorithm (Replies: 3)

  3. Knuth Algorithm (Replies: 3)

  4. Ranking Algorithm (Replies: 22)

Loading...