My solutions of beatmycode.com challenges. "Digit sum", "Circular primes" and "Turtle pyramid" - most interesting of those challenges.

circular_primes.py

"""
A number is called a circular prime if all of its rotations (rotations of their digits) are primes themselves.

For example the prime number 197 has two rotations: 971, and 719. Both of them are prime, so all of them are circular primes.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below N if 1 <= N <= 1000000?
"""
from math import sqrt

N = 1000000 # let's take the worst case


def is_prime(number):
    """returns True if number has no divisors except 1 and itself"""
    if number <= 1:
        return False
    if number <= 3:
        return True
    for i in xrange(2, int(sqrt(number))+1):
        if number % i == 0:
            return False
    return True
    

BAD_DIGITS = set(['0','2','4','5','6','8'])
# as chars just because I was too lazy on line 46 to turn number into list of digits
# BTW, it works a bit faster (saves about 15%)


def circulate(number):
    digits = []
    while number >= 10:
        digits.insert(0, number % 10)
        number /= 10
    digits.insert(0, number % 10)
    for i in xrange(1, len(digits)):
        candidate = digits[i:]+digits[:i]
        yield sum([candidate[-i-1]* (10**i) for i in xrange(len(digits))])


def base_filter_check(number):
    if not is_prime(number):
        return False
    digits = set(str(number))
    if len(digits) > 1 and BAD_DIGITS.intersection(digits):
        return False
    return all([is_prime(derivative) for derivative in circulate(number)])


if __name__ == '__main__':
    primes = set([])
    if N > 2:
        primes.add(2)
    for i in xrange(3, N, 2): # important detail: step = 2 saves time by half
        if base_filter_check(i):
            primes.add(i)
            # we're not afraid to waste space, 'cause there are actually a very small count of circular primes
            # but on the other hand we could see actual set of primes, not only the count of them
    print len(primes)

digit_sum.py

"""
Find the sum of the digits of all the numbers from 1 to N (both ends included).

For N = 10 the sum is 1+2+3+4+5+6+7+8+9+(1+0) = 46
"""
# Shortest solution. Looks pretty nice, but it's not scalable. So it sucks.
# print sum([sum(map(int, str(i))) for i in xrange(1, N+1)])


def digits(number):
    """returns the sum of number's digits
    Helper function for the dumb solution
    """
    total = 0
    while number >= 10:
        total += number % 10
        number /= 10
    total += number
    return total


def solution_N(number):
    """The dumb solution itself."""
    total = 0
    for i in xrange(number+1):
        add = digits(i)
        total += add
    return total


def solution_logN(number):
    """Nice solution. 
    It's better than monkey cause it knows how to multiply :-)
    """
    i = 0
    total_sum = 0l
    while number >= 10**(i):
        current_digit = (number % 10**(i+1)) /10**i
        total_sum += number / 10**(i+1) * 45 * 10**i
        total_sum += sum(xrange(current_digit))*10**i
        total_sum += (current_digit) * ((number % 10**i)+1)
        i += 1
    return total_sum


if __name__ == '__main__':
    # print solution_N(19421942)
    print solution_logN(900219421942194219421942194219421942)
    # I've tested it on numbers of length 3500 and more and it worked as fast as goddamned hurricane

turtle_pyramid.py

"""
Turtles would like to create a pyramid, where every turtle in the pile can only be on top of a larger turtle. The only move they can make is crawling out and then crawling on top. Since they're having a problem achieving this configuration, they ask you to write a program that can tell them in which order to move. You have to advise them, so that it takes the least amount of moves to rearrange.

There are N turtles, represented by their size as numbers in the interval [1, N] (1 and N included). For example: N=3 means there are 3 turtles, and their sizes are: 1, 2, 3.
"""

# Test data
# data = "5\n6\n7\n1\n3\n2\n4"
# data = data.splitlines()

def build_random_data(n):
    import random
    stack = range(1, n+1)
    random.shuffle(stack)
    return stack

data = build_random_data(30)


def solution(data):
    if not data:
        return ""
    stack = []
    should_be_first = len(data)
    i = data.index(should_be_first)
    while i > 0:
        while i > 0 and data[i-1] != data[i]-1:
            stack.append(data.pop(i-1))
            i -= 1
        i -= 1
    i = 0
    while i < len(data) - 1:
        while i < len(data)-1 and data[i] > data[i+1]:
            stack.append(data.pop(i+1))
        i += 1
    stack.sort(reverse=True)
    return '\n'.join(map(str, stack))

if __name__ == '__main__':
    print solution(data)