Ruby is too slow for programming competitions (blog.clifreeder.com)

I'm sure if the competition was based on speed of implementation there would be different conclusions.

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.

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.

One thing that Code Jam does differently (and imho better) is that they give you an input set and you have 8 minutes (or so) to upload the solution. This is expected to give more than enough space for language speed variance.

Instead of execution time, coding time is much more precious in such competitions, and

Micro-optimizing has it's place, but it's usually not in a programming competition. that's what using ruby instead of C gives you leverage for that, as you can express more complex ideas and algorithms more easily (which should be the focus point).

This doesn't mean you shouldn't know the cost of operations.

Notice that your solution runs in O(sqrt(N)) time. If N were up to 10^14, with 10^3 test cases, then your solution could have to deal with up to 10^10 iterations... which is dangerous even for a fast language (since your CPU can only do about 10^9 things per second). As a rule of thumb, one should only ever deal with at most 10^8 things. Even just incrementing an integer 10^10 times can take some time (fortunately, not every one of the test cases were 10^14 so your Go solution took under a second).

However, Problem C of Google Code Jam qualification 2013 can be easily solved, even with a slow language, by making some observations:

1) Instead of iterating through numbers and checking if they are palindromic, you can just iterate through the numbers with half the number of digits and generate the palindrome by mirroring the half. A naive solution that uses this would run in O(N^(1/4) log(N)^1.6) instead of your O(N^(1/2) log(N)^1.6) solution. (The log(N)^1.6 is due to the time taken for multiplication, assuming the Karatsuba method).

2) With a small amount of math you can figure out that for any fair and square number N = MM, then for any digit s in M, we must have s(sum of all digits in M) < 10. Thus solutions are of the form:

case 1) Contains up to nine digits 1. (e.g. 101, 111111111)

case 2) Contains up one digit 2 and up to four digits 1. (e.g. 1002001, 2)

case 3) Contains up to two digits 2 and up to one digit 1. (e.g. 200010002, 202)

case 4) Contains one three. (i.e., just 3)

A naive solution using observation 2 may run in O(log(N)^5.6) time.

3) Use combinatorics to figure out count the ways to arrange the digits in the 4 cases shown above, rather than iterating through them. As it turns out, it is unnecessary to do this since even using an O(log(N)^6) solution I passed the 10^100 input. Since there are only about 40,000 fair and square numbers from 1 to 10^100, you can easily precompute them and find them by binary search.

Edit: as electrograv pointed out, another optimization is to generate palindromes from sqrt(start) to sqrt(end) rather than testing each number in the range for palindrome-ness. This saves you a factor of 10^3.5.

I was solving that problem with PHP and got it running reasonably fast (1s per range) for ranges up to around 10^60. PHP is probably faster than Ruby, but it's still in the same area.

The first trick you can use is that you don't have to go through all numbers between start and end, rather you can directly only traverse the palindromes (i.e. you will only have to increment one half of the integer).

The second trick is that only numbers consisting of 0s and 1s (and a 2 at the start/end or the middle) can satisfy the condition (exception: the number "3"). This further massively reduces the search space.

There are more criteria that you can use to narrow down the numbers to consider (e.g. the number of non-zero digits can't be greater than 9). But in the end, cracking the 10^100 range is probably not possible in a language like Ruby or PHP. Using something like C++ on the other hand it becomes a triviality.

  for each range (start to sqr(end))

    for each number in the range

      check if the number is fair and square

The right approach is to first compute all fair and square numbers between 0-10^14, store the result, and then simply check how many are found in each range.

It turns out there are only 39 fair and square numbers between 0 and 10^14.

I participated in Code Jam 2013 and passed the qualification round using Python; after precomputing the fair and square numbers, checking ranges was pretty much instantaneous (for large input 1).

This is one of the (many) reasons why although languages like Ruby and Python are great for rapid development, on-the-fly updates and other reasons, it can pay dividends to be fluent in a high-performance language. It wouldn't even need to be C (although this wouldn't be hard to do in C) -- a language like D would give you excellent performance and nearly as easy development as Ruby.

I was wrong.

Sure, the author is wrong, but not because Ruby is slow (it is, though). He's wrong, because he did not find the right solution for the problem. Instead, he wrote a brute-force solution with a simple optimization, and did not realize that this is the real cause of his code under-performing, blaming the Ruby's slowness for it, when he really should have blamed the Dunning-Kruger effect.

In the future, I obviously need to work on coming up with better algorithms for solving these kinds of problems, but I'll probably continue to try and use Go because it's nice to have that fallback to sheer speed when my algorithm isn't great.

Running time:

Ruby: 3180 seconds

Ruby (profiled and optimized): 342 seconds

Go (first attempt): 0.7 seconds

I know that I'll lose my fresh 100 karma points for this, but it's time to lay the dogmatic flames aside and talk about the real issues and how to solve them. For example, a JIT compiler could greatly help core PHP.

    import sys
    from math import sqrt
    
    def string_palindrome(num):
        s = str(num)
        return s == s[::-1]
    
    sys.stdin.readline() # throw away first line (number of cases)
    
    for count, line in enumerate(sys.stdin):
        found = 0
        start, finish = [int(num) for num in line.split(" ")]
        sqrt_start  = int(sqrt(start ))
        sqrt_finish = int(sqrt(finish))
    
        for x in xrange(sqrt_start, sqrt_finish+1):
            if string_palindrome(x):
                square = x * x
                if string_palindrome(square) and start <= square <= finish:
                    found += 1
    
        print("Case #%d: %d" % (count, found))

    pypy 2.0-beta2: 1.6 seconds
    pypy 1.9:       2.1 seconds
    ruby 1.9.3p194: 3.7 seconds
    python 3.3.0:   5.9 seconds
    python 2.7.1:   6.2 seconds

Edit: Even though the interger version of _palindrome is slower in pypy, there's another optimization that works there, but is slow in cpython. It brings the run time down to 0.6 seconds!

    def half_string_palindrome(num):
        num_str = str(num)
        num_len = len(num_str)
    
        for i in xrange(0, num_len // 2):
            if num_str[i] != num_str[num_len - i - 1]:
                return False
    
        return True