Pascal's triangle/Puzzle: Difference between revisions

Content added Content deleted
No edit summary
m (Fixed lang tags.)
Line 82: Line 82:
end loop;
end loop;
end loop;
end loop;
end Pyramid_of_Numbers;
end Pyramid_of_Numbers;</lang>
</lang>
Sample output:
Sample output:
<pre>
<pre>
Line 97: Line 96:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has no FORMATted transput, and not }} -->
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has no FORMATted transput, and not }} -->
<lang algol>MODE
<lang algol68>MODE
FIELD = REAL,
FIELD = REAL,
VEC = [0]REAL,
VEC = [0]REAL,
Line 206: Line 205:
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


<lang haskell>puzzle = [["151"],["",""],["40","",""],["","","",""],["X","11","Y","4","Z"]]</lang>
<lang haskell>
puzzle = [["151"],["",""],["40","",""],["","","",""],["X","11","Y","4","Z"]]
</lang>


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:
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:


<lang haskell>
<lang haskell>triangle n = n * (n+1) `div` 2

triangle n = n * (n+1) `div` 2
coeff xys x = maybe 0 id $ lookup x xys

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
row n cs = [coeff cs k | k <- [1..n]]
a <- [1..h-1]
eqXYZ n = [(0, 1:(-1):1:replicate n 0)]
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)])
eqPyramid n h = do

a <- [1..h-1]
eqConst n fields = do
x <- [triangle (a-1) + 1 .. triangle a]
let y = x+a
(k,s) <- zip [1..] fields
guard $ not $ null s
return $ (0, 0:0:0:row n [(x,-1),(y,1),(y+1,1)])
return $ case s of
"X" - (0, 1:0:0:row n [(k,-1)])
eqConst n fields = do
(k,s) <- zip [1..] fields
"Y" - (0, 0:1:0:row n [(k,-1)])
"Z" - (0, 0:0:1:row n [(k,-1)])
guard $ not $ null s
_ - (fromInteger $ read s, 0:0:0:row n [(k,1)])
return $ case s of

"X" - (0, 1:0:0:row n [(k,-1)])
equations :: [[String]] - ([Rational], [[Rational]])
"Y" - (0, 0:1:0:row n [(k,-1)])
equations puzzle = unzip eqs where
"Z" - (0, 0:0:1:row n [(k,-1)])
fields = concat puzzle
_ - (fromInteger $ read s, 0:0:0:row n [(k,1)])
eqs = eqXYZ n ++ eqPyramid n h ++ eqConst n fields
h = length puzzle
equations :: [[String]] - ([Rational], [[Rational]])
n = length fields</lang>
equations puzzle = unzip eqs where
fields = concat puzzle
eqs = eqXYZ n ++ eqPyramid n h ++ eqConst n fields
h = length puzzle
n = length fields
</lang>


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
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


<lang haskell>
<lang haskell>normalize :: [Rational] - [Integer]
normalize :: [Rational] - [Integer]
normalize xs = [numerator (x * v) | x <- xs] where
v = fromInteger $ foldr1 lcm $ map denominator $ xs
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
run puzzle = map (normalize . drop 3) $ answer where
lr = decompose 0 m
(a, m) = equations puzzle
lr = decompose 0 m
answer = case solve 0 lr a of
Nothing - []
answer = case solve 0 lr a of
Just x - x : kernel lr</lang>
Nothing - []
Just x - x : kernel lr
</lang>


will output one special solution and modifications that lead to more solutions, as in
will output one special solution and modifications that lead to more solutions, as in


<lang haskell>
<lang haskell>*Main run puzzle
[[151,81,70,40,41,29,16,24,17,12,5,11,13,4,8]]
*Main run puzzle
*Main run [[""],["2",""],["X","Y","Z"]]
[[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]]</lang>
[[3,2,1,1,1,0],[3,0,3,-1,1,2]]
</lang>


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.
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.
Line 317: Line 308:
=={{header|Mathematica}}==
=={{header|Mathematica}}==
We assign a variable to each block starting on top with a, then on the second row b,c et cetera. k,m, and o are replaced by X, Y, and Z. We can write the following equations:
We assign a variable to each block starting on top with a, then on the second row b,c et cetera. k,m, and o are replaced by X, Y, and Z. We can write the following equations:
<lang Mathematica>
<lang Mathematica>b+c==a
b+c==a
d+e==b
d+e==b
e+f==c
e+f==c
g+h==d
g+h==d
h+i==e
h+i==e
i+j==f
i+j==f
l+X==g
l+X==g
l+Y==h
l+Y==h
n+Y==i
n+Y==i
n+Z==j
n+Z==j
X+Z==Y</lang>
X+Z==Y
</lang>
And we have the knowns
And we have the knowns
<lang Mathematica>
<lang Mathematica>a->151
a->151
d->40
d->40
l->11
n->4</lang>
l->11
n->4
</lang>
Giving us 10 equations with 10 unknowns; i.e. solvable. So we can do so by:
Giving us 10 equations with 10 unknowns; i.e. solvable. So we can do so by:
<lang Mathematica>eqs={a==b+c,d+e==b,e+f==c,g+h==d,h+i==e,i+j==f,l+X==g,l+Y==h,n+Y==i,n+Z==j,Y==X+Z};
<lang Mathematica>
knowns={a->151,d->40,l->11,n->4};
eqs={a==b+c,d+e==b,e+f==c,g+h==d,h+i==e,i+j==f,l+X==g,l+Y==h,n+Y==i,n+Z==j,Y==X+Z};
Solve[eqs/.knowns,{b,c,e,f,g,h,i,j,X,Y,Z}]</lang>
knowns={a->151,d->40,l->11,n->4};
Solve[eqs/.knowns,{b,c,e,f,g,h,i,j,X,Y,Z}]
</lang>
gives back:
gives back:
<lang Mathematica>{{b -> 81, c -> 70, e -> 41, f -> 29, g -> 16, h -> 24, i -> 17, j -> 12, X -> 5, Y -> 13, Z -> 8}}</lang>
<lang Mathematica>
{{b -> 81, c -> 70, e -> 41, f -> 29, g -> 16, h -> 24, i -> 17, j -> 12, X -> 5, Y -> 13, Z -> 8}}
</lang>
In pyramid form that would be:
In pyramid form that would be:
<lang Mathematica>
<lang Mathematica> 151
151
81 70
81 70
40 41 29
40 41 29
16 24 17 12
16 24 17 12
5 11 13 4 8
5 11 13 4 8</lang>
</lang>


=={{header|Oz}}==
=={{header|Oz}}==
<lang ocaml>%% to compile : ozc -x <file.oz>
<lang oz>%% to compile : ozc -x <file.oz>
functor
functor


Line 428: Line 409:


=={{header|Prolog}}==
=={{header|Prolog}}==
<lang prolog>
<lang prolog>:- use_module(library(clpfd)).
:- use_module(library(clpfd)).


puzzle( [[ 151],
puzzle( [[ 151],
Line 448: Line 428:
% X = 5,
% X = 5,
% Y = 13,
% Y = 13,
% Z = 8 ;
% Z = 8 ;</lang>
</lang>


=={{header|Python}}==
=={{header|Python}}==
Line 574: Line 553:
p = [ [151], [None,None], [40,None,None], [None,None,None,None], ['X', 11, 'Y', 4, 'Z'] ]
p = [ [151], [None,None], [40,None,None], [None,None,None,None], ['X', 11, 'Y', 4, 'Z'] ]
addlConstraint = { 'X':1, 'Y':-1, 'Z':1, '1':0 }
addlConstraint = { 'X':1, 'Y':-1, 'Z':1, '1':0 }
SolvePyramid( p, addlConstraint)
SolvePyramid( p, addlConstraint)</lang>
</lang>
Output:
Output:
<pre>Constraint Equations:
<pre>Constraint Equations:
Line 590: Line 568:
Alternative solution using the csp module (based on code by Gustavo Niemeyerby):
Alternative solution using the csp module (based on code by Gustavo Niemeyerby):
http://www.fantascienza.net/leonardo/so/csp.zip
http://www.fantascienza.net/leonardo/so/csp.zip
<lang python>
<lang python>from csp import Problem
from csp import Problem


p = Problem()
p = Problem()
Line 608: Line 585:
p.addrule("R2 + R3 == 151")
p.addrule("R2 + R3 == 151")
for sol in p.xsolutions():
for sol in p.xsolutions():
print [sol[k] for k in "XYZ"]
print [sol[k] for k in "XYZ"]</lang>
</lang>


All possible solutions with X,Y,Z >= 0, found in about 17 seconds, with Psyco (X, Y, Z):
All possible solutions with X,Y,Z >= 0, found in about 17 seconds, with Psyco (X, Y, Z):
<lang python>
<lang python>[4, 14, 3]
[4, 14, 3]
[5, 13, 8]
[5, 13, 8]
[6, 12, 13]
[6, 12, 13]
Line 627: Line 602:
[16, 2, 63]
[16, 2, 63]
[17, 1, 68]
[17, 1, 68]
[18, 0, 73]
[18, 0, 73]</lang>
</lang>


=={{header|Ruby}}==
=={{header|Ruby}}==
Retrieved from "https://rosettacode.org/wiki/Pascal%27s_triangle/Puzzle"