Rosetta Code

Pascal's triangle/Puzzle: Difference between revisions

Page Discussion

Pascal's triangle/Puzzle (view source)

Revision as of 18:46, 21 November 2009

91 bytes removed ,  14 years ago
m
Fixed lang tags.
No edit summary
m (Fixed lang tags.)
Line 82:
end loop;
end loop;
end Pyramid_of_Numbers;</lang>
</lang>
Sample output:
<pre>
Line 97 ⟶ 96:
{{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 }} -->
<lang algolalgol68>MODE
FIELD = REAL,
VEC = [0]REAL,
Line 206 ⟶ 205:
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:
 
<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 =x <- [(0,triangle 1:(a-1): + 1:replicate n.. 0)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]
(k,s) let<- yzip =[1..] x+afields
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
"Y" - (k0,s) <-0:1:0:row zipn [(k,-1..)] fields)
"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
 
<lang haskell>normalize :: [Rational] - [Integer]
normalize ::xs = [Rational]numerator (x * v) | x <- [Integerxs] 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
lranswer = decomposecase solve 0 mlr 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
 
<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 [[""]3,["2",""1,1,1,0],["X"3,"Y"0,"Z"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.
Line 317 ⟶ 308:
=={{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:
<lang Mathematica>b+c==a
bd+ce==ab
d+e+f==bc
eg+fh==cd
g+h+i==de
h+i+j==ef
il+jX==fg
l+XY==gh
ln+Y==hi
n+YZ==ij
nX+Z==jY</lang>
X+Z==Y
</lang>
And we have the knowns
<lang Mathematica>a->151
ad->15140
dl->4011
n->4</lang>
l->11
n->4
</lang>
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:
<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:
<lang Mathematica> 151
151
81 70
40 41 29
16 24 17 12
5 11 13 4 8</lang>
</lang>
 
=={{header|Oz}}==
<lang ocamloz>%% to compile : ozc -x <file.oz>
functor
 
Line 428 ⟶ 409:
 
=={{header|Prolog}}==
<lang prolog>:- use_module(library(clpfd)).
:- use_module(library(clpfd)).
 
puzzle( [[ 151],
Line 448 ⟶ 428:
% X = 5,
% Y = 13,
% Z = 8 ;</lang>
</lang>
 
=={{header|Python}}==
Line 574 ⟶ 553:
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 }
SolvePyramid( p, addlConstraint)</lang>
</lang>
Output:
<pre>Constraint Equations:
Line 590 ⟶ 568:
Alternative solution using the csp module (based on code by Gustavo Niemeyerby):
http://www.fantascienza.net/leonardo/so/csp.zip
<lang python>from csp import Problem
from csp import Problem
 
p = Problem()
Line 608 ⟶ 585:
p.addrule("R2 + R3 == 151")
for sol in p.xsolutions():
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):
<lang python>[4, 14, 3]
[4, 14, 3]
[5, 13, 8]
[6, 12, 13]
Line 627 ⟶ 602:
[16, 2, 63]
[17, 1, 68]
[18, 0, 73]</lang>
</lang>
 
=={{header|Ruby}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/64699"