Pascal's triangle/Puzzle: Difference between revisions
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}}== |
Revision as of 14:14, 26 March 2008
You are encouraged to solve this task according to the task description, using any language you may know.
Here is a puzzle of Pyramid of numbers.
[ 151] [ ][ ] [40][ ][ ] [ ][ ][ ][ ] [ X][11][ Y][ 4][ Z]
Each brick of the pyramid is the sum of the two bricks situated below this brick.
For the three missing numbers at the base of the pyramid : the one of the middle is the sum of the two other (that is, Y = X + Z).
Task:
- Find a solution of this puzzle.
Haskell
I assume the task is to solve any such puzzle, i.e. given some data
puzzle = [["151"],["",""],["40","",""],["","","",""],["X","11","Y","4","Z"]]
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:
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
To solve the system, any linear algebra library will do (e.g 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
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
will output one special solution and modifications that lead to more solutions, as in
*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]]
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.
Oz
<ocaml>%% to compile : ozc -x <file.oz> functor
import
System Application FD Search
define
proc{Quest Root Rules}
proc{Limit Rc Ls} case Ls of nil then skip [] X|Xs then {Limit Rc Xs} case X of N#V then Rc.N =: V [] N1#N2#N3 then Rc.N1 =: Rc.N2 + Rc.N3 end end end
proc {Pyramid R} {FD.tuple solution 15 0#FD.sup R} %% non-negative integers domain %% 01 , pyramid format %% 02 03 %% 04 05 06 %% 07 08 09 10 %% 11 12 13 14 15 R.1 =: R.2 + R.3 %% constraints of Pyramid of numbers R.2 =: R.4 + R.5 R.3 =: R.5 + R.6 R.4 =: R.7 + R.8 R.5 =: R.8 + R.9 R.6 =: R.9 + R.10 R.7 =: R.11 + R.12 R.8 =: R.12 + R.13 R.9 =: R.13 + R.14 R.10 =: R.14 + R.15 {Limit R Rules} %% additional constraints {FD.distribute ff R} end in {Search.base.one Pyramid Root} %% search for solution end
local Root R in {Quest Root [1#151 4#40 12#11 14#4 13#11#15]} %% supply additional constraint rules if {Length Root} >= 1 then R = Root.1 {For 1 15 1 proc{$ I} if {Member I [1 3 6 10]} then {System.printInfo R.I#'\n'} else {System.printInfo R.I#' '} end end } else {System.showInfo 'No solution found.'} end end
{Application.exit 0}
end</ocaml>