Here’s in python, imperatively, and then in functional style without the need for loops.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def pascal(n): | |
| if n == 1: | |
| return [ 1 ] | |
| if n == 2: | |
| return [ 1, 1 ] | |
| prev = pascal(n-1) | |
| results = [] | |
| for i in range(n): | |
| if i == 0: | |
| continue | |
| if i == n-1: | |
| break | |
| results.append(prev[i] + prev[i-1]) | |
| return [1] + results + [1] | |
| # functional style, no loops | |
| def pascal_fp(n): | |
| if n == 1: | |
| return [ 1 ] | |
| prev = pascal_fp(n-1) | |
| return list(map(lambda x,y:x+y, [0] + prev, prev + [0])) |
Here’s in Haskell, I call it the gubatron’s method, explained in the comments.
Saw it by looking at a pattern while trying to solve it in paper, it just clicked.
Not sure if this is how other people code this solution.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| — Gubatron's method | |
| — n=3 [1, 2, 1] | |
| — copy the list and append a 0 on the left of the first | |
| — and append a 0 at the end of the second | |
| — [0, 1, 2, 1] | |
| — [1, 2, 1, 0] | |
| — add them up! | |
| — n=4 [1, 3, 3, 1] | |
| — | |
| — append 0s to both sides and add them up | |
| — n=4 [1, 3, 3, 1] | |
| — [0, 1, 3, 3, 1] | |
| — [1, 3, 3, 1, 0] | |
| — n=5 [1, 4, 6, 4, 1] | |
| — and so on | |
| — add two lists, for clarity | |
| addLists :: Num c => [c] -> [c] -> [c] | |
| addLists l1 l2 = zipWith (+) l1 l2 | |
| pascal :: (Eq a1, Num a1, Num a2) => a1 -> [a2] | |
| pascal 1 = [ 1 ] | |
| pascal n = | |
| let prev = pascal(n–1) | |
| zero_prev = [0] ++ prev | |
| prev_zero = prev ++ [0] | |
| in | |
| addLists zero_prev prev_zero | |
| — [1,2,3] -> "1 2 3" | |
| listToString = unwords. map show | |
| — mapM_ -> map monadic so no weird IO errors are triggered | |
| printTriangle n = mapM_ putStrLn (map listToString (map pascal [1..n])) | |
| main = do | |
| input <- getLine | |
| printTriangle . (read :: String -> Int) $ input |