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 |
<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] |
|||
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] |
|||
(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 |
|||
( |
"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 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 |
|||
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]] |
|||
[[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 |
||
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 |
|||
X+Z==Y</lang> |
|||
X+Z==Y |
|||
</lang> |
|||
And we have the knowns |
And we have the knowns |
||
<lang Mathematica> |
<lang Mathematica>a->151 |
||
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 |
<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}}== |