Project Euler與Python：Problem 11~20與67

Project Euler針對數學和程式愛好者，設計了一系列的問題，至今已有五百多道，供大家挑戰，每一題都要求應在1分鐘內計算出答案。

我將以Python語言來解題，原始碼放在GitHub（yehnan/project_euler_python），基本上都是先採用暴力法，若運算量太大，無法在1分鐘內算出答案，才著手研究想出更快的演算法。當題目的數字很小時，隨便寫就能在1分鐘內算出答案，但是，也就只有幾題而已，大部分的題目都需要大量計算，可沒那麼好混。

我使用硬體Raspberry Pi 2與軟體Raspbian，作為執行速度的依據。

注意：不提供詳細的說明與分析。

Problem 11: Largest product in a grid，20×20格子，每格有個數字，把相鄰的四個數相乘，找出乘積最大的。所謂相鄰是指同一方向的連續四個數，方向有上下、左右、左上右下的對角線、右上左下的對角線。

把題目給的20×20格子，放進檔案裡，然後讀取放進二維串列。

from io import open
grid = []
with open('p011_data.txt', 'r', encoding='ascii') as fin:
    for line in fin:
        grid.append(list(map(int, line.split())))

給定含有數字的串列，算出乘積。

def product(li):
    result = 1
    for n in li:
        result *= n
    return result

給定串列、個數count，找出相鄰count個數字相乘後乘積最大的。

def product_max(li, count):
    max = 0
    for i in range(0, len(li)-count + 1):
        m = product(li[i:i+count])
        if m > max:
            max = m
    return max

底下函式可拿出左上右下或右上左下的對角線，由參數slant決定。

def diag(grid, row, col, slant):
    d = []
    while True:
        try:
            d.append(grid[row][col])
            row += 1
            col += slant
        except IndexError:
            break
    return d

終於到了問題本身，底下函式可找出相鄰四個數乘積最大的，但只會尋找一半：每一列、右上半部對角線為左上右下、左上半部對角線為右上左下。

def find_max(grid, count):
    max = 0
    for row in grid:
        m = product_max(row, count)
        if m > max:
            max = m
    for col in range(len(grid[0])):
        m = product_max(diag(grid, 0, col, 1), count)
        if m > max:
            max = m
    for col in range(len(grid[0])):
        m = product_max(diag(grid, 0, col, -1), count)
        if m > max:
            max = m
    return max

不過，只要把格子旋轉90度，再丟進上面的函式，便可處理另外一半。

def lpiad(grid, count):
    m = find_max(grid, count)
    grid_rotated = list(zip(*grid))
    mr = find_max(grid_rotated, count)
    return max(m, mr)

Problem 12: Highly divisible triangular number，找出第一個擁有超過500個因數的三角數（triangle number）。

暴力法太慢，應該先作質因數分解，根據質因數的次方數，便可算出因數的個數。不過此處並未作質因數分解，而是作2與奇數的分解。底下函式，給定參數n，求出n的因數個數。

def divisors_count(n):
    dc = 1
    cnt = 0
    while n % 2 == 0:
        n //= 2
        cnt += 1
    dc *= (cnt + 1)
   
    p = 3
    while n != 1:
        cnt = 0
        while n % p == 0:
            n //= p
            cnt += 1
        dc *= (cnt + 1)
        p += 2
    return dc

下面這個產生器函式，會不斷給出下一個三角數。
   
def triangle_number_gf():
    tn = 0
    i = 1
    while True:
        tn += i
        i += 1
        yield tn

最後是問題本身，傳入參數500，便可算出答案。

def hdtn(dc):
    for tn in triangle_number_gf():
        if divisors_count(tn) > dc:
            return tn

Problem 13: Large sum，給定100個數字，皆為50位數，算出總和後，取出前10個位數。

因為只要記憶體夠大，Python的整數便能不斷變大，所以這題對Python來說很簡單。把給定的東西放在檔案裡，呼叫底下函式傳入檔名，即可算出答案。

from io import open

def ls(filename):
    with open(filename, 'r', encoding='ascii') as fin:
        total = sum(int(line) for line in fin)
        return str(total)[:10]

Problem 14: Longest Collatz sequence，根據奇偶歸一猜想，每個正整數經過數次Collatz轉換後，最終會得到1。在小於一百萬的數字中，哪個數需要最多次轉換才能到1。

首先，底下函式給定參數n（起始數），回傳Collatz轉換的次數。

memo = {1: 1}
def collatz(n):
    if n not in memo:
        if n % 2 == 0:
            memo[n] = 1 + collatz(n // 2)
        else:
            memo[n] = 1 + collatz(3 * n + 1)
    return memo[n]

然後，以迴圈迭代所有起始數，找出轉換次數最多的那一個。底下函式傳入1000000即可求出答案。

def lcs(m):
    n = 1
    n_len = 1
    for i in range(2, m+1):
        i_len = collatz(i)
        if n_len < i_len:
            n = i
            n_len = i_len
    return n

Problem 15: Lattice paths，20×20的格子，從最左上走到最右下，只能向左或向下移動，請問有幾種路徑。

此題等同於：有40個位置，手上有20個紅球和20個綠球，請問共有幾種擺法。也就是40! / 20! / 20!。所以先寫階乘函式。

def factorial(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result
 
然後是問題本身，底下函式傳入20與20，即可求出答案。

def lp(row, col):
    return factorial(row+col) // factorial(row) // factorial(col)

Problem 16: Power digit sum，求2**1000的所有位數的總和。

因Python支援無限大的整數（只要記憶體足夠的話），所以這題對Python來說很簡單。底下函式傳入1000即可求出答案。

def pds(n):
    num = 2 ** n
    result = 0
    for d in str(num):
        result += int(d)
    return result

Problem 17: Number letter counts，把1到1000寫成英文，總共有幾個字母。

嗯，只能根據規則把數字轉成英文字串，底下函式只能處理1到1000的情況。

d3 = {1: 'one thousand'}
d2a = { 10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen',
        14: 'fourteen', 15: 'fifteen', 16: 'sixteen',
        17: 'seventeen', 18: 'eighteen', 19: 'nineteen' }
d2b = { 2: 'twenty', 3: 'thirty', 4: 'forty', 5: 'fifty',
        6: 'sixty', 7: 'seventy', 8: 'eighty', 9: 'ninety' }
d1 = { 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five',
       6: 'six', 7: 'seven', 8: 'eight', 9: 'nine' }

def i2s(i): # from 1 to 1000
    a4 = i // 1000
    a3 = (i % 1000) // 100
    a2 = (i % 100) // 10
    a1 = i % 10
    result = []
    if a4 == 1:
        result.append('one thousand')
        if a3 != 0 or a2 != 0 or a1 != 0:
            result.append(' and ')
    if a3 != 0:
        result.append(d1[a3])
        result.append(' hundred')
        if a2 != 0 or a1 != 0:
            result.append(' and ')
    if a2 == 1:
        result.append(d2a[a2*10 + a1])
    elif a2 >= 2:
        result.append(d2b[a2])
        if a1 != 0:
            result.append('-')
    if a2 != 1 and a1 != 0:
        result.append(d1[a1])
    return ''.join(result)

然後是問題本身，底下函式傳入1與1000，即可算出答案。
   
def nlc(n, m=None):
    if m is None:
        m = n
    result = 0
    for i in range(n, m+1):
        s = i2s(i)
        s = s.replace(' ', '').replace('-', '')
        result += len(s)
    return result

Problem 18: Maximum path sum I，Problem 67: Maximum path sum II，給定呈現三角形的數字層，從頂端開始走，往下一層走時可往左或往右，走到底部時形成一條路徑，把走過的數字加總，請問路徑加總和最大的是多少。

首先寫函式把代表三角形的資料從檔案載入，變成多維串列。

from io import open

def get_triangle(filename):
    triangle = []
    with open(filename, 'r', encoding='ascii') as fin:
        for line in fin:
            triangle.append([int(n) for n in line.split()])
    return triangle

然後是尋找最大路徑加總和的函式，屬於從上往下的遞迴形式。當你站在某一個位置時，只要算出左下三角形的最大路徑加總和、以及右下三角形的最大路徑加總和，挑出比較大的那一條，便可決定往哪走。

def max_path_sum(tri, row, col):
    if row == len(tri)-1:
        return tri[row][col]
    else:
        sub = max(max_path_sum(tri, row+1, col),
                  max_path_sum(tri, row+1, col+1))
        return tri[row][col] + sub

最後是題目本身，傳入資料檔名，即可求出答案。
       
def mpsi(filename):
    tri = get_triangle(filename)
    return max_path_sum(tri, 0, 0)

不過，當三角形層數一多（Problem 67），上述寫法就太慢了，必須由下往上，從倒數第二層開始，位置(r, c)的最大路徑加總和，會是(r, c) + (r+1, c)與(r, c) + (r+1, c+1)兩個之中較大的那一個。一層一層往上，最後便可算出頂端(0, 0)的最大路徑加總和。

def max_path_sum(tri, row, col):
    for r in range(len(tri)-1 -1, -1, -1):
        for c in range(len(tri[r])):
            tri[r][c] += max(tri[r+1][c], tri[r+1][c+1])
    return tri[row][col]

Problem 19: Counting Sundays，二十世紀每個月第一天是星期日的日子，有幾天。

我們知道1900年1月1日是星期一，定其天數為1；而1900年1月7日是星期日，天數為7，所以只要算出某日期（日月年）的天數，能被7整除的話即是星期日。

首先是判斷潤年的函式。

def is_leapyear(year):
    if year%4 == 0 and year%100 != 0 or year%400 == 0:
        return 1
    else:
        return 0

給定月份與年份，回傳該月份有幾天。
       
month = [31, 28, 31, 30, 31, 30,
         31, 31, 30, 31, 30, 31]
        
def days_of_month(m, y):
    return month[m-1] + (is_leapyear(y) if m == 2 else 0)

給定年份，回傳該年份有幾天。

def days_of_year(y):
    return sum(month) + is_leapyear(y)

給定日期（日月年），算出其天數。

def date_to_days(date):
    dy, mn, yr = date
    days = dy
    for y in range(1900, yr):
        days += days_of_year(y)
    for m in range(1, mn):
        days += days_of_month(m, yr)
    return days

能被7整除，則為星期日。

def is_sunday(days):
    return days % 7 == 0

迭代所有年份的每月第一天。
 
def cs():
    count = 0
    for y in range(1901, 2000+1):
        for m in range(1, 12+1):
            days = date_to_days((1, m, y))
            if is_sunday(days):
                count += 1
    return count

Problem 20: Factorial digit sum，加總100階乘的所有位數。

沒什麼好說的，算出階乘，然後把每個位數加起來。

def fact(n):
    result = 1
    for i in range(1, n):
        result *= i
    return result

底下函式傳入100，便可求得答案。

def fds(n):
    s = str(fact(n))
    result = 0
    for c in s:
        result += int(c)
    return result