Can i somehow see what pattern haskell tries to use? It works on the smaller example, but crashes on the larger one, and I have a hard time finding what case it could be.
euler18 :: [[Integer]]
euler18 = pathPyr minipyr
pathPyr xss = path [(head xss)] (tail xss)
minipyr = [[3],[7,4],[2,4,6]]
pyramid = [[75], [95,64], [17,47,82], [18,35,87,10], [20,4,82,47,65], [19,1,23,75,3,34], [88,2,77,73,7,63,67], [99,65,4,28,6,16,70,92], [41,41,26,56,83,40,80,70,33], [41,48,72,33,47,32,37,16,94,29], [53,71,44,65,25,43,91,52,97,51,14], [70,11,33,28,77,73,17,78,39,68,17,57], [91,71,52,38,17,14,91,43,58,50,27,29,48], [63,66,4,68,89,53,67,30,73,16,69,87,40,31], [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
path :: [[Integer]] -> [[Integer]] -> [[Integer]]
path xss (ys:[]) = extendpath xss ys
path xss (ys:yss) = path (extendpath xss ys) yss
extendpath :: [[Integer]] -> [Integer] -> [[Integer]]
extendpath (xs:[]) (y1:y2:[]) = [y1:xs,y2:xs]
extendpath (xs:xss) (y1:y2:ys) = [y1:xs,y2:xs] ++ extendpath xss (y2:ys)
the output:
*Main> pathPyr pyramid
[[4,63,91,70,53,41,41,99,88,19,20,18,17,95,75],[62,63,91,70,53,41,41,99,88,19,20,18,17,95,75],[62,66,91,70,53,41,41,99,88,19,20,18,17,95,75],[98,66,91,70,53,41,41,99,88,19,20,18,17,95,75],[98,66,71,70,53,41,41,99,88,19,20,18,17,95,75],[27,66,71,70,53,41,41,99,88,19,20,18,17,95,75],[27,4,71,70,53,41,41,99,88,19,20,18,17,95,75],[23,4,71,70,53,41,41,99,88,19,20,18,17,95,75],[23,4,71,11,53,41,41,99,88,19,20,18,17,95,75],[9,4,71,11,53,41,41,99,88,19,20,18,17,95,75],[9,68,71,11,53,41,41,99,88,19,20,18,17,95,75],[70,68,71,11,53,41,41,99,88,19,20,18,17,95,75],[70,68,52,11,53,41,41,99,88,19,20,18,17,95,75],[98,68,52,11,53,41,41,99,88,19,20,18,17,95,75],[98,89,52,11,53,41,41,99,88,19,20,18,17,95,75],[73,89,52,11,53,41,41,99,88,19,20,18,17,95,75],[73,89,52,11,71,41,41,99,88,19,20,18,17,95,75],[93,89,52,11,71,41,41,99,88,19,20,18,17,95,75],[93,53,52,11,71,41,41,99,88,19,20,18,17,95,75],[38,53,52,11,71,41,41,99,88,19,20,18,17,95,75],[38,53,38,11,71,41,41,99,88,19,20,18,17,95,75],[53,53,38,11,71,41,41,99,88,19,20,18,17,95,75],[53,67,38,11,71,41,41,99,88,19,20,18,17,95,75],[60,67,38,11,71,41,41,99,88,19,20,18,17,95,75],[60,67,38,33,71,41,41,99,88,19,20,18,17,95,75],[4,67,38,33,71,41,41,99,88,19,20,18,17,95,75],[4,30,38,33,71,41,41,99,88,19,20,18,17,95,75],[23,30,38,33,71,41,41,99,88,19,20,18,17,95,75]*** Exception: euler18.hs:(16,1)-(17,72): Non-exhaustive patterns in function Main.extendpath
extendpath :: [[Integer]] -> [Integer] -> [[Integer]]
extendpath (xs:[]) (y1:y2:[]) = [y1:xs,y2:xs]
extendpath (xs:xss) (y1:y2:ys) = [y1:xs,y2:xs] ++ extendpath xss (y2:ys)
While it works, extendpath
doubles the number of paths each time it's called. But the length of the rows increases only by 1. So as soon as you have a triangle with more than three rows, you get a pattern-match failure when processing the fourth (and every later) row.
After the second (zero-based, so the row with three elements) row, you have
-- LL LR RL RR
extendpath [p_1, p_2, p_3, p_4] [v_1, v_2, v_3, v_4]
~> [v_1:p_1, v_2:p_1] ++ extendpath [p_2, p_3, p_4] [v_2, v_3, v_4]
~> [v_1:p_1, v_2:p_1] ++ [v_2:p_2, v_3:p_2] ++ extendpath [p_3, p_4] [v_3, v_4]
~> [v_1:p_1, v_2:p_1] ++ [v_2:p_2, v_3:p_2] ++ [v_3:p_3, v_4:p_3] ++ extendpath [p_4] [v_4]
and the last call has no matching pattern.
Now, the paths p_2
and p_3
end in the same place, so the two can be extended by the same two values in the next row, but extendpath
doesn't take into account where a path ends. Generally, on the n
-th row there are
n `choose` k
paths ending in the k
-th spot [that's why I chose zero-based counting here]. When extending paths, the possible extensions depend on the current end point of the path.
You need a different approach. Especially for problem 67.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With