Problem 4: Largest palindrome product
Problem 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
第一個解答
這道題目非常簡單，就是要找出最大的由兩個三位數的乘積構成的迴文數。在 Haskell 交互環境暴力破解：
Prelude> maximum [ n | a <- [100..999], b <- [a..999], let n = a*b, (\x -> x == reverse x) $ show n ]
在上述程式中：
-
假設這兩個三位數分別是 a 和 b，那麼 a 的取值範圍就是 [100..999]，由於乘法交換律，b 的取值範圍可設置為 [a..999]。
-
設置 n 為這兩個三位數的乘積，show n 將 n 轉換為字元串，reverse x 將字元串 x 倒轉，所以這個 lamda 表達式就是判斷 n 是否為迴文數。
-
最後使用 maximum 函數得到這個迴文數列表中的最大的元素。
將上述程式中的 maximum 改為 length，可以得到列表的長度為 1239，即兩個三位數的乘積可以用 1239 種方式（不計兩個三位數的次序）構成迴文數。例如，163*627 = 102201 和 209*489 = 102201 算兩種不同的方式，而 139*759 = 105501 和 759*139 = 105501 不算兩種不同的方式。
將上述程式中的 maximum 改為 length $ nub，可以得到列表的長度為 655，即兩個三位數的乘積可以構成 655 個不同的迴文數。這裡的 nub 函數的作用是刪除列表中的重複元素，只留下不相同的元素。
將上述程式的中的 [ n | 改為 [ (n,a,b) |，就不但可以知道最大的由兩個三位的乘積的構成的迴文數是什麼，同時也知道了這兩個三位數是什麼。
第二個解答
假設所求的迴文數 n 的構成形式是 xyzzyx，那麼：
- n = 100000x + 10000y + 1000z + 100z + 10y + x = 100001x + 10010y + 1100z
因此有以下的 Haskell 程式：
Prelude> maximum [ n | x <- [1..9], y <- [0..9], z <- [0..9], n <- [100001*x + 10010*y + 1100*z], not $ null [ a | a <- [100..999], mod n a == 0 && div n a < 1000 ] ]
在上述程式中：
-
x 的取值範圍是 [1..9]，y 和 z 的取值範圍都是 [0..9]。n 就是由上述公式計算的所有可能的迴文數。
-
在最右邊的列表中，a 是一個三位數，取值範圍是 [100..999]，mod n a == 0 要求 a 能夠整除 n，然後 div n a < 1000 保證了 n 的另外一個因數也是三位數。
-
not $ null 篩選出非空的列表，也就保證了 n 這個迴文數是由兩個三位數的乘積構成的。例如，迴文數 997799 = 11*90709，就不是兩個三位數的乘積。
-
最後使用 maximum 得到這個迴文數列表中的最大元素。
將上述程式中的 maximum 改為 length，可以得到列表的長度為 279，即兩個三位數的乘積可以構成 279 個不同的六位數的迴文數。前面講過：兩個三位數的乘積可以構成 655 個不同的迴文數。也就是說，這 655 個迴文數中有 279 個是六位數，其餘 376 個是五位數。
誰更快
第一個解答簡單、直接，第二個解答稍微複雜一點。不仔細分析，還不好說哪個解答運行速度更快。那麼直接使用 Haskell 編譯器 ghc 分別編譯這兩個程式，然後使用 Linux 的 time 命令計時。得到的結果是，第一個解答用時 0.161 秒，第二個解答用時 0.104 秒。
投機取巧的優化
如果我們相信兩個不小於 900 的三位數的乘積可以構成迴文數，那麼第一個解答中的 a <- [100..999] 可以改為 a <- [900..999]。這樣，只需要 0.006 秒就可以算出答案。
如果我們相信形如 9yzzy9 這樣的迴文數可以由兩個三位數的乘積構成，那麼第二個解答中的 x <- [1..9] 就可以改為 x <- [9]。這樣，只需要 0.017 秒就可以算出答案。
第二個程式的改進
Prelude> head [ n | x <- [9,8..1], y <- [9,8..0], z <- [9,8..0], n <- [100001*x + 10010*y + 1100*z], not $ null [ m | m <- [100..999], mod n m == 0 && div n m < 1000 ] ]
改變如下：
-
將 x <- [1..9], y <-[0..9], z <- [0..9] 改為 x <- [9,8..1], y <- [9,8..0], z <- [9,8..0]，即從正算改為倒算。
-
最左邊的 maximum 函數改為 head 函數。
注意，如果只做第一點改動，新程式的運行時間和舊程式相同，沒有變化。這是因為從正算改為倒算，都是要遍歷這些數，運算量沒有變化。而第二點改動是最關鍵的，Haskell 的 head 函數遇到列表中滿足條件的第一個數就停止計算，輸出結果，所以運行時間大大縮短，從 0.104 秒減少到 0.019 秒。
第一個程式的改進
Prelude> fst $ last $ takeWhile (\(n,x) -> n < x) $ scanl1 (\(z,_) (n,x) -> (max z n,x)) $ [ (n,a^2) | a <- [999,998..100], b <- [a,a-1..100], let n = a*b, (\x -> x == reverse x) $ show n ]
在上述程式中：
-
假設這兩個三位數分別是 a 和 b，將 a 設置為從 999 下降到 100，將 b 設置為從 a 下降到 100。
-
設置 n 為這兩個三位數的乘積，show n 將 n 轉換為字元串，reverse x 將字元串 x 倒轉，所以這個 lamda 表達式就是判斷 n 是否為迴文數。
-
得到的列表的元素是元組 (n,a^2)，其中 n 是所求的迴文數，a2 用於判斷何時停止計算，以節省時間。
-
scanl1 函數生成到目前為止最大的迴文數和 a2 構成的元組構成的列表。即：將列表 [ (n, a^2) ] 變換為列表 [ (max n, a^2) ]。
-
takeWhile 函數用來過濾列表，停止於列表中最後一個最大迴文數小於 a2 的元素。此時，程式將終止，不再繼續計算，這就節省了時間。
-
last 函數取得該列表的最後一個元素，該元素是一個元組。
-
fst 函數取得該元組的第一個元素，就是所求的最大的迴文數。
新程式運行時間大大縮短，從 0.161 秒減少到 0.022 秒。
改進的硬道理
如果將上述程式最左邊的 fst $ last 改為 length，可以得到列表長度為 54，這比舊程式的列表長度 1239 小多了，這就是新程式比舊程式快得多的原因。
如果將上述程式最左邊的 fst $ last $ 刪除，可以得到這個長度為 54 的列表的具體內容：
[(580085,990025),(580085,990025),(906609,986049),(906609,982081),(906609,974169),(906609,974169),(906609,964324),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,958441),(906609,956484),(906609,956484),(906609,954529),(906609,950625),(906609,948676),(906609,942841),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,937024),(906609,933156),(906609,933156),(906609,929296),(906609,927369),(906609,925444),(906609,925444),(906609,925444),(906609,925444),(906609,923521),(906609,919681),(906609,917764),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,915849),(906609,912025),(906609,908209),(906609,908209)]
可以看出，最大的迴文數在列表的第 3 項已經出現了，但是我們需要計算到第 55 項才知道以後沒有更大的迴文數了。
只保留上述程式的右半邊，並稍做修改：
Prelude> take 55 [ (n,a,b,a^2) | a <- [999,998..100], b <- [a,a-1..100], let n = a*b, (\x -> x == reverse x) $ show n ]
運行結果：
[(580085,995,583,990025),(514415,995,517,990025),(906609,993,913,986049),(119911,991,121,982081),(282282,987,286,974169),(141141,987,143,974169),(853358,982,869,964324),(650056,979,664,958441),(601106,979,614,958441),(592295,979,605,958441),(543345,979,555,958441),(485584,979,496,958441),(436634,979,446,958441),(378873,979,387,958441),(329923,979,337,958441),(408804,978,418,956484),(204402,978,209,956484),(623326,977,638,954529),(525525,975,539,950625),(299992,974,308,948676),(469964,971,484,942841),(886688,968,916,937024),(804408,968,831,937024),(698896,968,722,937024),(631136,968,652,937024),(616616,968,637,937024),(443344,968,458,937024),(428824,968,443,937024),(270072,968,279,937024),(255552,968,264,937024),(828828,966,858,933156),(414414,966,429,933156),(487784,964,506,929296),(180081,963,187,927369),(888888,962,924,925444),(666666,962,693,925444),(444444,962,462,925444),(222222,962,231,925444),(348843,961,363,923521),(770077,959,803,919681),(653356,958,682,917764),(855558,957,894,915849),(807708,957,844,915849),(696696,957,728,915849),(648846,957,678,915849),(531135,957,555,915849),(489984,957,512,915849),(372273,957,389,915849),(324423,957,339,915849),(165561,957,173,915849),(117711,957,123,915849),(577775,955,605,912025),(723327,953,759,908209),(649946,953,682,908209),(272272,952,286,906304)]
現在列表的元素是個四元組，這個四元組的第一個元素是迴文數（n），第二個元素（a）和第三個元素（b）的乘積構成第一個元素（n），第四個元素是第二個元素的平方（a2）。這個列表的第 55 項在前面的程式中就被扔掉了，因為 a2 已經小於要尋找的最大迴文數了，後面不可能出現更大迴文數了。仔細分析這個輸出結果，可以看出這個程式的運行過程，理解其工作原理。
另外還可參閱：004_overview.pdf。
