Ruby is too slow for programming competitions

Maybe the result would vary with JRuby or Rubinius (I'd be interested in benchmarks) because not only is Ruby itself not the fastest language, but its main implementation (MRI) is also not the best for speed.

Duh, Captain Obvious is on duty.

nope, iterating up to the square root of finish covers that

Wow, 5 minutes in Ruby, and less than a second in Go? I know scripting languages are slow, but it's easy to forget just how much slower. (EDIT: Corrected misread number thanks to dljsjr).

I don't want to detract from the article's main point with a cliche "algorithmic optimization beats fine tuning", but I think it's worth mentioning. Unless I'm mistaken, this particular problem can be solved about 10,000,000x more efficiently.

    > Given two numbers X and Y, return how many numbers in that range
    > (inclusive) are palindromes, and also the square of a palindrome.

I would just count the digits of X and Y, then ranging between those counts, apply the following algorithm: For N digits, enumerate all numbers of N/2 digits satisfying the bounds X and Y. If N is even then simply mirror the first N/2 digits. If N is odd, mirror the first N/2-1. Finally, check the bounds of the resulting number against X and Y to filter out edge cases.

If the original algorithm runs in 10^N time, this would be 10^(N/2). For N=14 as mentioned, that's roughly a speedup of 10,000,000.

Edit: It seems I misinterpreted the question (which sounds like you're supposed to enumerate all palindrome numbers X>=N>=Y, and also print out the squares of those numbers). This is actually asking for a particular type of palindromes -- those which are palindromic squares of palindromes. As macobo helpfully points out, you can drastically optimize mathematically from this additional filter.

The article doesn't actually say that performance was one of the judging criteria, and I'm unable to find anything in the code jam rules about this. Can anyone here clarify?