Pascal's triangle/Puzzle: Difference between revisions
Content added Content deleted
(Ada solution added) |
(→{{header|Oz}}: Add example Python code) |
||
Line 234: | Line 234: | ||
{Application.exit 0} |
{Application.exit 0} |
||
end</ocaml> |
end</ocaml> |
||
=={{header|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: |
|||
<pre>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 |
|||
</pre> |
|||
The Pyramid solver is not restricted to solving for 3 variables, or just this particular pyramid. |