[Ryan]: Holy crap, dude! Is that for the original, four-operator problem? Oh, no. I'm talking about the latest version to handle Paul's decimal point. Which also of course includes concatenating digits, so possible operands include 9, .9, 99, 9.9, .99, etc. In the current run I'm eliminated the power operand, since that has its own increase in runtime.
My 1.5 GHz PowerBook is busy right now thanks to Paul, but on my ancient 500 MHz Dell desktop, the program for the original problem runs in about ten minutes. Aside from the speed difference, seems like there's still some room for improvement there. Oh well. I spent a little time optimizing, but once I had the answer and it would've taken more than ten minutes to optimize it further, I figured there were diminishing returns from there on.
[Jim]: It might be necessary to create (or borrow) a RationalNumber class to represent a rational number exactly.
[Ryan]: Yeah, I just wrote my own. I considered it earlier, but since I also wanted to allow power operations (including non-integer powers), I figured it would be better to just use doubles. To be fair, I suspect the non-integer powers have never led to a solution that wasn't already reachable by simpler techniques, so I could probably just drop that.
[Ryan]: What's your algorithm like? Fairly simple brute force. It's structured after RPN notation, like the traditional HP calculators - there's a stack of operands, and at every decision point, you can either push another nine on the stack, or apply an operator to the two latest elements and replace them with the result. If it leads to a new integer solution, I make a
string representation of the operators and operands and save it.
[Ryan]: And lastly... If you're going to include exponentiation, why not include log() to a given base? Because that would require a new symbol, not originally listed among the operators for this problem. To be clear, when I said exponentiation, I meant Math.pow() rather than Math.exp(). The point is that to indicate raising one number to the power of another, I don't need any additional symbol; I can just position the numbers appropriately. But for either an exponential function or a log function, I'd need additional symbols. I figure that using powers this way is
probably outside the intended scope of the problem, but not necessarily. Given nine nines, I think it's not unreasonable to take two of them and write 9 to the 9th power, with no other symbols needed.
[ March 01, 2006: Message edited by: Jim Yingst ]
