Pascal's triangle/Puzzle
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>
Python
Python 2.4, but should work with later versions as well. <Python># Pyramid solver
- [151]
- [ ] [ ]
- [ 40] [ ] [ ]
- [ ] [ ] [ ] [ ]
- [ X ] [ 11] [ Y ] [ 4 ] [ Z ]
- X -Y + Z = 0
def combine( snl, snr ):
cl = {} if type(snl ) == type(1): cl['1'] = snl elif type(snl) == type('X'): cl[snl] = 1 else: cl.update( snl)
if type(snr ) == type(1): n = cl.get('1', 0) cl['1'] = n + snr elif type(snr) == type('X'): n = cl.get(snr, 0) cl[snr] = n + 1 else: for k,v in snr.items(): n = cl.get(k, 0) cl[k] = n+v return cl
def constrain(nsum, vn ):
nn = {}
nn.update(vn)
n = nn.get('1', 0)
nn['1'] = n - nsum
return nn
def makeMatrix( constraints ): vmap = set() for c in constraints: vmap.update( c.keys()) vmap.remove('1') nvars = len(vmap) vmap = sorted(list(vmap)) # sort here so output is in sorted order mtx = [] for c in constraints: row = [] for vv in vmap: row.append(1.0* c.get(vv, 0)) row.append(-1.0*c.get('1',0)) mtx.append(row)
if len(constraints) == nvars: print 'System appears solvable' elif len(constraints) < nvars: print 'System is not solvable - needs more constraints.' return mtx, vmap
def SolvePyramid( vl, cnstr ):
vl.reverse() constraints = [cnstr] lvls = len(vl) for lvln in range(1,lvls): lvd = vl[lvln] for k in range(lvls - lvln): sn = lvd[k] ll = vl[lvln-1] vn = combine(ll[k], ll[k+1]) if sn is None: lvd[k] = vn else: constraints.append(constrain( sn, vn ))
print 'Constraint Equations:' for cstr in constraints: fset = ('%d*%s'%(v,k) for k,v in cstr.items() ) print ' + '.join(fset), ' = 0'
mtx,vmap = makeMatrix(constraints)
MtxSolve(mtx)
d = len(vmap) for j in range(d): print vmap[j],'=', mtx[j][d]
def MtxSolve(mtx):
# Simple Matrix solver...
mDim = len(mtx) # dimension--- for j in range(mDim): rw0= mtx[j] f = 1.0/rw0[j] for k in range(j, mDim+1): rw0[k] = rw0[k] * f
for l in range(1+j,mDim): rwl = mtx[l] f = -rwl[j] for k in range(j, mDim+1): rwl[k] = rwl[k] + f * rw0[k]
# backsolve part --- for j1 in range(1,mDim): j = mDim - j1 rw0= mtx[j] for l in range(0, j): rwl = mtx[l] f = -rwl[j] rwl[j] = rwl[j] + f * rw0[j] rwl[mDim] = rwl[mDim] + f * rw0[mDim]
return mtx
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)
</Python>
Output:
Constraint Equations: -1*Y + 1*X + 0*1 + 1*Z = 0 -18*1 + 1*X + 1*Y = 0 -73*1 + 5*Y + 1*Z = 0 System appears solvable X = 5.0 Y = 13.0 Z = 8.0
The Pyramid solver is not restricted to solving for 3 variables, or just this particular pyramid.