Thought you guys might like a challenge. This is not a question that I need answered, as I have already answered it myself, but I saw it posted as a "hard" question during a programming job interview. I've modified it a bit:

Question

Thought you guys might like a challenge.  This is not a question that I need answered, as I have already answered it myself, but I saw it posted as a "hard" question during a programming job interview.  I've modified it a bit:

anonymous · Answer

You have the string of numbers 123456789 in order.  You may place a *,+,-, or / (or nothing at all) between any digits that you wish to create a valid mathematical expression that follows the rules of order of operations.  For example, for the year of my birth:

12/3+45*6*7+89 = 1983
123*4*5-6*78-9 = 1983

Write a program that prints out all solutions for the year 2012.
Bonus question (and if you can solve the first question, I'm sure you can solve the last question): What was the last year that has no solutions?

I have a solution in Python which could stand to be improved...it takes about 8.5 seconds to run for any one number. Bleh.  Can you do better?

anonymous · Answer

And before anyone asks, no, I'm not in a class and you are neither doing my homework, doing a project, or taking a test for me.

anonymous · Answer

(I'm a beginner) You can write a computer to solve that in 8.5 seconds? The number of permutations in mind boggling...

anonymous · Answer

Not *too* mindboggling.  There are 8 spaces between the numbers to either put *,+,-,/, or nothing at all.  So there are 5^8, or 390625, possibilities.