2015/03/29

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 IProblem 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


No comments:

Post a Comment