Pascal's triangle/Puzzle: Difference between revisions
(Added Haskell example) |
(Ada solution added) |
||
Line 13: | Line 13: | ||
'''Task:''' |
'''Task:''' |
||
*Find a solution of this puzzle. |
*Find a solution of this puzzle. |
||
=={{header|Ada}}== |
|||
The solution makes an upward run symbolically, though excluding Z. After that two blocks (1,1) and (3,1) being known yield a 2x2 linear system, from which X and Y are determined. Finally each block is revisited and printed. |
|||
<Ada> |
|||
with Ada.Text_IO; use Ada.Text_IO; |
|||
procedure Pyramid_of_Numbers is |
|||
B_X, B_Y, B_Z : Integer := 0; -- Unknown variables |
|||
type Block_Value is record |
|||
Known : Integer := 0; |
|||
X, Y, Z : Integer := 0; |
|||
end record; |
|||
X : constant Block_Value := (0, 1, 0, 0); |
|||
Y : constant Block_Value := (0, 0, 1, 0); |
|||
Z : constant Block_Value := (0, 0, 0, 1); |
|||
procedure Add (L : in out Block_Value; R : Block_Value) is |
|||
begin -- Symbolically adds one block to another |
|||
L.Known := L.Known + R.Known; |
|||
L.X := L.X + R.X - R.Z; -- Z is excluded as n(Y - X - Z) = 0 |
|||
L.Y := L.Y + R.Y + R.Z; |
|||
end Add; |
|||
procedure Add (L : in out Block_Value; R : Integer) is |
|||
begin -- Symbolically adds a value to the block |
|||
L.Known := L.Known + R; |
|||
end Add; |
|||
function Image (N : Block_Value) return String is |
|||
begin -- The block value, when X,Y,Z are known |
|||
return Integer'Image (N.Known + N.X * B_X + N.Y * B_Y + N.Z * B_Z); |
|||
end Image; |
|||
procedure Solve_2x2 (A11, A12, B1, A21, A22, B2 : Integer) is |
|||
begin -- Don't care about things, supposing an integer solution exists |
|||
if A22 = 0 then |
|||
B_X := B2 / A21; |
|||
B_Y := (B1 - A11*B_X) / A12; |
|||
else |
|||
B_X := (B1*A22 - B2*A12) / (A11*A22 - A21*A12); |
|||
B_Y := (B1 - A11*B_X) / A12; |
|||
end if; |
|||
B_Z := B_Y - B_X; |
|||
end Solve_2x2; |
|||
B : array (1..5, 1..5) of Block_Value; -- The lower triangle contains blocks |
|||
begin |
|||
-- The bottom blocks |
|||
Add (B(5,1),X); Add (B(5,2),11); Add (B(5,3),Y); Add (B(5,4),4); Add (B(5,5),Z); |
|||
-- Upward run |
|||
for Row in reverse 1..4 loop |
|||
for Column in 1..Row loop |
|||
Add (B (Row, Column), B (Row + 1, Column)); |
|||
Add (B (Row, Column), B (Row + 1, Column + 1)); |
|||
end loop; |
|||
end loop; |
|||
-- Now have known blocks 40=(3,1), 151=(1,1) and Y=X+Z to determine X,Y,Z |
|||
Solve_2x2 |
|||
( B(1,1).X, B(1,1).Y, 151 - B(1,1).Known, |
|||
B(3,1).X, B(3,1).Y, 40 - B(3,1).Known |
|||
); |
|||
-- Print the results |
|||
for Row in 1..5 loop |
|||
New_Line; |
|||
for Column in 1..Row loop |
|||
Put (Image (B(Row,Column))); |
|||
end loop; |
|||
end loop; |
|||
end Pyramid_of_Numbers; |
|||
</Ada> |
|||
Sample output: |
|||
<pre> |
|||
151 |
|||
81 70 |
|||
40 41 29 |
|||
16 24 17 12 |
|||
5 11 13 4 8 |
|||
</pre> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
I assume the task is to solve any such puzzle, i.e. given some data |
I assume the task is to solve any such puzzle, i.e. given some data |
Revision as of 16:34, 31 May 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.
Ada
The solution makes an upward run symbolically, though excluding Z. After that two blocks (1,1) and (3,1) being known yield a 2x2 linear system, from which X and Y are determined. Finally each block is revisited and printed. <Ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Pyramid_of_Numbers is
B_X, B_Y, B_Z : Integer := 0; -- Unknown variables
type Block_Value is record Known : Integer := 0; X, Y, Z : Integer := 0; end record; X : constant Block_Value := (0, 1, 0, 0); Y : constant Block_Value := (0, 0, 1, 0); Z : constant Block_Value := (0, 0, 0, 1); procedure Add (L : in out Block_Value; R : Block_Value) is begin -- Symbolically adds one block to another L.Known := L.Known + R.Known; L.X := L.X + R.X - R.Z; -- Z is excluded as n(Y - X - Z) = 0 L.Y := L.Y + R.Y + R.Z; end Add; procedure Add (L : in out Block_Value; R : Integer) is begin -- Symbolically adds a value to the block L.Known := L.Known + R; end Add; function Image (N : Block_Value) return String is begin -- The block value, when X,Y,Z are known return Integer'Image (N.Known + N.X * B_X + N.Y * B_Y + N.Z * B_Z); end Image;
procedure Solve_2x2 (A11, A12, B1, A21, A22, B2 : Integer) is begin -- Don't care about things, supposing an integer solution exists if A22 = 0 then B_X := B2 / A21; B_Y := (B1 - A11*B_X) / A12; else B_X := (B1*A22 - B2*A12) / (A11*A22 - A21*A12); B_Y := (B1 - A11*B_X) / A12; end if; B_Z := B_Y - B_X; end Solve_2x2; B : array (1..5, 1..5) of Block_Value; -- The lower triangle contains blocks
begin
-- The bottom blocks Add (B(5,1),X); Add (B(5,2),11); Add (B(5,3),Y); Add (B(5,4),4); Add (B(5,5),Z);
-- Upward run for Row in reverse 1..4 loop for Column in 1..Row loop Add (B (Row, Column), B (Row + 1, Column)); Add (B (Row, Column), B (Row + 1, Column + 1)); end loop; end loop; -- Now have known blocks 40=(3,1), 151=(1,1) and Y=X+Z to determine X,Y,Z Solve_2x2 ( B(1,1).X, B(1,1).Y, 151 - B(1,1).Known, B(3,1).X, B(3,1).Y, 40 - B(3,1).Known );
-- Print the results for Row in 1..5 loop New_Line; for Column in 1..Row loop Put (Image (B(Row,Column))); end loop; end loop;
end Pyramid_of_Numbers; </Ada> Sample output:
151 81 70 40 41 29 16 24 17 12 5 11 13 4 8
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>