Problems 11 20

Euler 11: What is the greatest product of four numbers in any direction (up, down, left, right, or diagonally) in the 20x20 grid?

def euler11(strmatrix, op, length):
    """What is the greatest product of four numbers on the same straight line 
    in the 20 by 20 grid?"""
    def getgroups(matrix, sx, sy, x, y, length):
        definitions = [ \
            (x <= sx-length, (0, +1)),  
            (y <= sy-length, (+1, 0)),
            (x <= sx-length and y <= sy-length, (+1, +1)),
            (x >= length-1 and y <= sy-length, (+1, -1))]
        return ([matrix[y+incy*k][x+incx*k] for k in xrange(length)] \
            for condition, (incy, incx) in definitions if condition)
    process_line = lambda s: map(int, s.split())
    matrix = map(process_line, filter(bool, strmatrix.splitlines()))
    sx, sy = len(matrix[0]), len(matrix)
    gg = lambda x, y: getgroups(matrix, sx, sy, x, y, length)
    groups = flatten(starmap(gg, icross(xrange(sx), xrange(sy))))
    return max(map(lambda it: reduce(op, it), groups))
 
euler11(data.problem11, operator.mul, 4)

Discussion: A solution that shifts rows/columns, transposes matrix and so on are not hard to implement, but extremely hard to understand (however, it would be very easily solvable if no diagonally items were involved). Thus, I prefer this simple solution, iterate over each row/column element and get a group if it can be build, considering 4 directions (right, down, down-left, down-right), which covers the whole matrix.

Euler 12: What is the first triangle number to have over five-hundred divisors?

def triangle_number(x):
    """The nth triangle number is defined as the sum of [1,n] values.
    A brute-force approach could be sum(xrange(1, x+1)), but let's
    take pencil&paper, some draws to get..."""
    return (x*(x+1))/2
 
def triangle_numbers(start=1):
    """Generate triangle numbers tn(n) = 1+2+3+....+n"""
    first = triangle_number(start-1)
    return ireduce(operator.add, count(start), first)
 
def euler12(ndivisors):
    """What is the first triangle number to have over five-hundred divisors?"""
    num_factors = lambda x: mul((exp+1) for (base, exp) in factorize(x))
    return head(x for x in triangle_numbers() if num_factors(x) > ndivisors)
 
euler12(500)

Discussion: Number of divisors (including 1 and the number itself) can be calculated taking one element from prime (and power) divisors.

Euler 13: Find the first ten digits of the sum of one-hundred 50-digit numbers

def euler13(strnums, ndigits):
    """Find the first ten digits of the sum of one-hundred 50-digit numbers"""
    value = sum(int(s) for s in strnums.splitlines() if s.isdigit())
    return value/10**(int(log10(value))-ndigits+1)
 
euler13(data.problem13, 10)

Euler 14: Find the longest sequence using a starting number under one million

def euler14(end):    
    """Find the longest sequence using a starting number under one million"""
    def next_state(x):
        return (x % 2) and (3*x+1) or (x/2)
    def get_length(n, curlen=1):
        if n <= 1:
            return curlen
        return get_length(next_state(n), curlen+1)
    return max((get_length(x), x) for x in xrange(1, end))[1]
 
euler14(1000000)

Discussion: In my computer it takes more than one minute to find the solution. We could make some optmizations (%2 -> &1, x/2 -> x»2) or taking in account short-cuts in state transitions, but it does not make sense to do that. This does not compute in time simply because Python implementation is slow for this kind of task.

Euler 15: How many routes are there through a 20x20 grid?

def combinations(n, k):
    """Combinations of k elements from a group of n"""
    return mul(xrange(n-k+1, n+1))/factorial(k)
 
def euler15(width, height):
    """How many routes are there through a 20x20 grid?"""
    def get_paths(x=0, y=0, count=0):
        if (x, y) == (width, height):
            return count/(width+height)
        elif x < width:
            px = get_paths(x+1, y, count+1)
            if y == height:
                return px   
            return px + get_path_numbers(x, y+1, count+1)
        return get_paths(x, y+1, count+1)
    #return get_paths() # brute-force (painful slow)
    return combinations(width+height, width)
 
euler15(20, 20)

Discussion: If you try a graphical solution you will see that each node accoumulator value defines the Tartaglia Triangle. Each element (we need only the last one) can be calculed simply with the combination function.

Euler 16: What is the sum of the digits of the number 2**1000?

def digits_from_num(num, base=10):
    """Get digits from num in base 'base'"""
    def recursive(num, base):
        if num < base:
            return [num]
        return [num%base] + recursive(num/base, base)
    return list(reversed(recursive(num, base)))
 
def euler16(base, exponent):
    """What is the sum of the digits of the number 2**1000?"""
    return sum(digits_from_num(pow(base, exponent)))
 
euler16(2, 1000)

Euler 17: If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

def get_cardinal_name(num):
    """Get cardinal name for number (0 to 1000 only)"""
    numbers = { 
        0: "zero", 1: "one", 2: "two", 3: "three", 4: "four", 5: "five", 
        6: "six", 7: "seven", 8: "eight", 9: "nine", 10: "ten", 
        11: "eleven", 12: "twelve", 13: "thirteen", 14: "fourteen", 
        15: "fifteen", 16: "sixteen", 17: "seventeen", 18: "eighteen", 
        19: "nineteen", 20: "twenty", 30: "thirty", 40: "forty", 
        50: "fifty", 60: "sixty", 70: "seventy", 80: "eighty", 90: "ninety"}
    def _get_tens(num, withand=False):
        header = (withand and num) and "and" or None
        if num == 0 and withand:
            return
        elif num <= 20:
            s = numbers[num]
        else: 
            a, b = digits_from_num(num)
            s = b and "%s-%s"%(numbers[10*a], numbers[b]) or "%s"%numbers[10*a]
        return " ".join(nonvoid([header, s]))
    if num < 100:
        return _get_tens(num)
    elif num < 1000:
        a, b, c = digits_from_num(num)
        return " ".join(nonvoid([numbers[a], "hundred", _get_tens(10*b+c, True)]))
    elif num == 1000:
        return "one thousand"
    raise ValueError, "not supported"
 
def euler17(end):
    """If all the numbers from 1 to 1000 (one thousand) inclusive were 
    written out in words, how many letters would be used?"""
    inwords = imap(get_cardinal_name, xrange(1, end+1))
    return len([c for c in "".join(inwords) if c in string.letters])
 
euler17(1000)

Euler 18: Find the maximum sum travelling from the top of the triangle to the base

def euler18(data):
    """Find the maximum sum travelling from the top of the triangle 
    to the base"""
    process_line = lambda s: map(int, s.split())
    triangle = map(process_line, filter(bool, data.splitlines()))
    def _process_row(data, row):
        get = lambda n: (n < 0 or n >= len(data)) and -1 or data[n]
        return [max([k+value for k in (get(column-1), get(column))]) \
            for column, value in enumerate(row)]
    return max(reduce(_process_row, triangle))
 
euler18(data.problem18)

Euler 19: How many Sundays fell on the first of the month during the twentieth century?

def euler19(dayweekname, years):
    """How many Sundays fell on the first of the month during the 
    twentieth century?"""
    from calendar import monthrange
    dayweek = ["monday", "tuesday", "wednesday", "thursday", "friday", \
        "saturday", "sunday"].index(dayweekname.lower())
    getfirstday = lambda year, month: monthrange(year, month)[0]
    condition = lambda d: (d == dayweek)
    pairs = icross(years, xrange(1, 13))
    return iterlen(ifilter(condition, starmap(getfirstday, pairs)))
 
euler19("Sunday", range(1901, 2001))

Euler 20: Find the sum of the digits in the number 100!

def euler20(num):
    """Find the sum of the digits in the number 100!"""
    return sum(digits_from_num(factorial(num)))
 
euler20(100)