Pascal's triangle/Puzzle: Difference between revisions
Content added Content deleted
m (Biggified header) |
(Added Haskell example) |
||
Line 1: | Line 1: | ||
{{task}}{{puzzle}} |
|||
Here is a puzzle of [http://xunor.free.fr/en/riddles/auto/pyramidnb.php Pyramid of numbers]. |
|||
<pre> |
<pre> |
||
[ 151] |
[ 151] |
||
Line 12: | Line 13: | ||
'''Task:''' |
'''Task:''' |
||
*Find a solution of this puzzle. |
*Find a solution of this puzzle. |
||
=={{header|Haskell}}== |
|||
I assume the task is to solve any such puzzle, i.e. given some data |
|||
<pre> |
|||
puzzle = [["151"],["",""],["40","",""],["","","",""],["X","11","Y","4","Z"]] |
|||
</pre> |
|||
one should calculate all possible values that fit. That just means solving a linear system of equations. We use the first three variables as placeholders for ''X'', ''Y'' and ''Z''. Then we can produce the matrix of equations: |
|||
<pre> |
|||
triangle n = n * (n+1) `div` 2 |
|||
coeff xys x = maybe 0 id $ lookup x xys |
|||
row n cs = [coeff cs k | k <- [1..n]] |
|||
eqXYZ n = [(0, 1:(-1):1:replicate n 0)] |
|||
eqPyramid n h = do |
|||
a <- [1..h-1] |
|||
x <- [triangle (a-1) + 1 .. triangle a] |
|||
let y = x+a |
|||
return $ (0, 0:0:0:row n [(x,-1),(y,1),(y+1,1)]) |
|||
eqConst n fields = do |
|||
(k,s) <- zip [1..] fields |
|||
guard $ not $ null s |
|||
return $ case s of |
|||
"X" - (0, 1:0:0:row n [(k,-1)]) |
|||
"Y" - (0, 0:1:0:row n [(k,-1)]) |
|||
"Z" - (0, 0:0:1:row n [(k,-1)]) |
|||
_ - (fromInteger $ read s, 0:0:0:row n [(k,1)]) |
|||
equations :: [[String]] - ([Rational], [[Rational]]) |
|||
equations puzzle = unzip eqs where |
|||
fields = concat puzzle |
|||
eqs = eqXYZ n ++ eqPyramid n h ++ eqConst n fields |
|||
h = length puzzle |
|||
n = length fields |
|||
</pre> |
|||
To solve the system, any linear algebra library will do (e.g [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmatrix-0.2.0.0 hmatrix]). For this example, we assume there are functions ''decompose'' for LR-decomposition, ''kernel'' to solve the homogenous system and ''solve'' to find a special solution for an imhomogenous system. Then |
|||
<pre> |
|||
normalize :: [Rational] - [Integer] |
|||
normalize xs = [numerator (x * v) | x <- xs] where |
|||
v = fromInteger $ foldr1 lcm $ map denominator $ xs |
|||
run puzzle = map (normalize . drop 3) $ answer where |
|||
(a, m) = equations puzzle |
|||
lr = decompose 0 m |
|||
answer = case solve 0 lr a of |
|||
Nothing - [] |
|||
Just x - x : kernel lr |
|||
</pre> |
|||
will output one special solution and modifications that lead to more solutions, as in |
|||
<pre> |
|||
*Main run puzzle |
|||
[[151,81,70,40,41,29,16,24,17,12,5,11,13,4,8]] |
|||
*Main run [[""],["2",""],["X","Y","Z"]] |
|||
[[3,2,1,1,1,0],[3,0,3,-1,1,2]] |
|||
</pre> |
|||
so for the second puzzle, not only X=1 Y=1 Z=0 is a solution, but also X=1-1=0, Y=1+1=2 Z=0+2=2 etc. |
|||
Note that the program doesn't attempt to verify that the puzzle is in correct form. |
|||
=={{header|Oz}}== |
=={{header|Oz}}== |