Thursday, October 17, 2013

Problem 55 - Squirrel

I have been using Squirrel a lot recently...it is a nice language, and it just happens that I seem to always use it in places where I choose to replace it very quickly. Anywhere, here is my latest squirrel problem. Problem 55 involves finding candidate lychrel numbers: A lychrel number is one which, if you repeatedly add the reverse of a number to itself, yields a palindrome. Now, no one has proved that any number is actually lychrel in base 10, however, there are many numbers which all the world's computing power has never been able to prove non-lychrel. This problem tasks one to find all such numbers under 10000, given that it will not take more than 50 iterations to reach a palindrome. Attempting to do this in Squirrel led to overflow in the 64-bit integers available....luckily, assuming that any number that could cause integer overflow was lychrel led to the correct result. Here is my code, runs in ~.166ms.
function rev(x) {
    local r = 0;
    while (x > 0) {
        r = r*10 + x%10;
        x /= 10;
    }
    return r;
}

function digits(x) {
    local arr = [];
    while (x > 0) {
        arr.append(x % 10);
        x /= 10;
    }
    return arr;
}

function isPalindrome(x) {
    local digs = digits(x);
    for (local i = 0; i < (digs.len() + 1) / 2; ++i) {
        if (digs[i] != digs[digs.len() - i - 1]) {
            return false;
        }
    }
    return true;
}

function isLycherel(x) {
    for (local i = 0; i < 50; ++i) {
        x += rev(x);
        if (x < 0) {
            return true;
        }
        if (isPalindrome(x)) {
            return false;
        }
    }
    return true;
}


local ans = 0;
for (local i = 1; i < 10000; ++i) {
    if (isLycherel(i)) {
        ++ans;
    }
}
print(ans + "\n");
    

No comments:

Post a Comment