Pascal's triangle/Puzzle: Difference between revisions

Line 1,993:

=={{header|Phix}}==

Converts the pyramid to rules quite nicely, <del>however I will concede

--

that solving those two rules (18=2x+z and 73=5x+6z) and specifically converting them

-- demo\rosetta\Pascal_triangle_Puzzle.exw

into xrule(35=7x) and zrule(56=7z) is somewhat amateurish - suggestions welcome.</del>

-- =======================================

UPDATE: See [[Solving_coin_problems#Phix]], routine solveN()

--

<lang Phix>-- demo\rosetta\Pascal_triangle_Puzzle.exw

-- I approached this with a view to solving general pyramid puzzles, not just the one given.

sequence pyramid = {

--

{151},

-- This little ditty converts the pyramid to rules quite nicely, then uses a modified copy

{"",""},

-- of solveN() from [[Solving_coin_problems#Phix]] to solve those simultaneous equations.

{40,"",""},

--

{"","","",""},

with javascript_semantics

{"x",11,"y",4,"z"}}

sequence pyramid = {{151},

sequence rules = {}

{"",""},

{40,"",""},

-- each cell in the pyramid is either an integer final value or an equation.

{"","","",""},

-- initially the equations are strings, we substitute all with triplets of

{"x",11,"y",4,"z"}}

-- the form {k,x,z} ie k+l*x+m*z, and known values < last row become rules.

sequence rules = {}

for r=5 to 1 by -1 do

for c=1 to length(pyramid[r]) do

-- each cell in the pyramid is either an integer final value or an equation.

object prc = pyramid[r][c], equ

-- initially the equations are strings, we substitute all with triplets of

if prc="x" then prc = {0,1,0} -- ie one x

-- the form {k,x,z} ie k+l*x+m*z, and known values < last row become rules.

elsif prc="y" then prc = {0,1,1} -- ie one x plus one z

elsif prc="z" then prc = {0,0,1} -- ie one z

for r=5 to 1 by -1 do

else

for c=1 to length(pyramid[r]) do

if prc="" or r<=4 then

object prc = pyramid[r][c], equ

-- examples: x+11 is {0,1,0}+{11,0,0} -> {11,1,0},

if prc="x" then prc = {0,1,0} -- ie 0 + one x

-- 11+y is {11,0,0}+{0,1,1} -> {11,1,1},

elsif prc="y" then prc = {0,1,1} -- ie 0 + one x plus one z

-- 40=""+"" is {40,0,0}={22,2,1} ==> {18,2,1}

elsif prc="z" then prc = {0,0,1} -- ie 0 + one z

equ = sq_add(pyramid[r+1][c],pyramid[r+1][c+1])

~~end if~~

else

if prc="" or r<=4 then

if prc="" then prc = equ

~~else~~ ~~prc =~~ {~~prc~~,0,0}

-- examples: x+11 is {0,1,0}+{11,0,0} -> {11,1,0},

if ~~r<=4~~ ~~then~~

-- 11+y is {11,0,0}+{0,1,1} -> {11,1,1},

~~equ[~~1] = ~~prc[1]-equ[~~1]

-- 40=""+"" is {40,0,0}={22,2,1} ==> {18,2,1}

equ = sq_add(pyramid[r+1][c],pyramid[r+1][c+1])

rules = append(rules,equ)

~~end~~ if

end if

if prc="" then prc = equ

end if

else prc = {prc,0,0}

end if

if r<=4 then

pyramid[r][c] = prc

equ[1] = prc[1]-equ[1]

end for

rules = append(rules,equ)

end for

end if

ppOpt({pp_Nest,1,pp_StrFmt,2,pp_IntCh,false})

end if

?"equations"

pyramid[r][c] = prc

pp(pyramid)

end for

?"rules"

end for

pp(rules)

puts(1,"=====\n")

ppOpt({pp_Nest,1,pp_StrFmt,2,pp_IntCh,false})

?"equations"

if length(rules)!=2 then ?9/0 end if -- more work needed!?

pp(pyramid)

?"rules"

-- admittedly this bit is rather amateurish, and maybe problem-specific:

pp(rules) -- {18,2,1} === 18=2x+z

-- UPDATE: as above, see that solveN() routine.

-- {73,5,6} === 73=5x+6z

sequence xrule = sq_sub(sq_mul(rules[1],rules[2][3]),sq_mul(rules[2],rules[1][3])),

puts(1,"=====\n")

zrule = sq_sub(sq_mul(rules[2],rules[1][2]),sq_mul(rules[1],rules[2][2]))

assert(length(rules)==2) -- more work needed!?

?{"xrule",xrule}

?{"zrule",zrule}

-- modified copy of solveN() from Solving_coin_problems.exw as promised, a

-- bit of a sledgehammer to crack a peanut is the phrase you are looking for:

integer x = xrule[1]/xrule[2],

function solveN(sequence rules)

z = zrule[1]/zrule[3],

--

y = x+z

-- Based on https://mathcs.clarku.edu/~djoyce/ma105/simultaneous.html

-- aka the ancient Chinese Jiuzhang suanshu ~100 B.C. (!!)

printf(1,"x = %d, y=%d, z=%d\n",{x,y,z})

--

-- Example (not related to the task problem):

-- finally evaluate all the equations and print it.

-- rules = <nowiki>{{</nowiki>18,1,1},{38,1,5<nowiki>}}</nowiki>, ie 18==x+y, 38==x+5y

for r=1 to length(pyramid) do

-- ==> {13,5}, ie x=13, y=5

for c=1 to length(pyramid[r]) do

--

integer {k, l, m} = pyramid[r][c]

-- In the elimination phase, both x have multipliers of 1, ie both rii and rij are 1,

pyramid[r][c] = k+l*x+m*z

-- so we can ignore the two sq_mul and just do [sq_sub] (38=x+5y)-(18=x+y)==>(20=4y).

end for

-- Obviously therefore y is 5 and substituting backwards x is 13.

end for

--

-- Example2 (taken from the task problem):

pp(pyramid)</lang>

-- rules = <nowiki>{{</nowiki>18,2,1},{73,5,6<nowiki>}}</nowiki>, ie 18==2x+z, 73==5x+6z

-- ==> <nowiki>{{</nowiki>18,2,1},{56,0,7<nowiki>}}</nowiki>, ie rules[2]:=rules[2]*2-rules[1]*5 (eliminate)

-- ==> <nowiki>{{</nowiki>18,2,1},8}, ie rules[2]:=56/7, aka z:=8 (substitute)

-- ==> <nowiki>{{</nowiki>10,2,0},8}, ie rules[1]-=1z (substitute)

-- ==> {5,8}, ie rules[1]:=10/2, aka x:=5 (substitute)

-- ==> {5,8}, ie x=5, z=8

--

sequence ri, rj

integer l = length(rules), rii, rji

rules = deep_copy(rules)

for i=1 to l do

-- successively eliminate (grow lower left triangle of 0s)

ri = rules[i]

assert(length(ri)=l+1)

rii = ri[i+1]

assert(rii!=0) -- (see note below)

for j=i+1 to l do

rj = rules[j]

rji = rj[i+1]

if rji!=0 then

rj = sq_sub(sq_mul(rj,rii),sq_mul(ri,rji))

assert(rj[i+1]==0) -- (job done)

rules[j] = rj

end if

end for

for i=l to 1 by -1 do

-- then substitute each backwards

ri = rules[i]

rii = ri[1]/ri[i+1] -- (all else should be 0)

rules[i] = rii

for j=i-1 to 1 by -1 do

rj = rules[j]

rji = rj[i+1]

if rji!=0 then

rules[j] = 0

rj[1] -= rji*rii

rj[i+1] = 0

rules[j] = rj

end if

end for

return rules

end function

-- Obviously these next two lines directly embody knowledge from the task, and

-- would need changing for an even slightly different version of the problem:

integer {x,z} = solveN(rules),

y = x+z -- (as per task desc)

printf(1,"x=%d, y=%d, z=%d\n",{x,y,z})

-- finally evaluate all the equations and print it.

for r=1 to length(pyramid) do

for c=1 to length(pyramid[r]) do

integer {k, l, m} = pyramid[r][c]

pyramid[r][c] = k+l*x+m*z

end for

pp(pyramid)

<pre>

Line 2,080:

Line 2,142:

{73,5,6}}

=====

x=5, y=13, z=8

{"xrule",{35,7,0}}

{"zrule",{56,0,7}}

x = 5, y=13, z=8

{{151},

{81,70},

Line 2,090:

Line 2,150:

</pre>

Interestingly, this appears to match Python in that 40 is propagated up the tree, whereas Perl and Go appear to propagate 22+2x+z up, not that I can think of any case where that would make a difference.

A couple of other ways to use that solveN():

?solveN({{18,1,1,0},{73,0,5,1},{0,1,-1,1}}) -- -- {5,13,8}

ppOpt({pp_Nest,0})

-- Or, hand-coding 11 simultaneous equations for 11 unknowns:

-- (be warned I had to reorder a bit to avoid rii==0 mishaps,

-- perhaps solveN() should find or even sort rules somehow)

--sequence pyramid = <nowiki>{{</nowiki>151},

-- {"a","b"},

-- {40,"c","d"},

-- {"e","f","g","h"},

-- {"x", 11,"y", 4,"z"<nowiki>}}</nowiki>

-- a b c d e f g h x y z

pp(solveN({{151, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, -- a+b=151

{ 40, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0}, -- 40+c=a

{ 0, 0, 1,-1,-1, 0, 0, 0, 0, 0, 0, 0}, -- c+d=b

{ 0, 0, 0, 0, 1, 0, 0,-1,-1, 0, 0, 0}, -- g+h=d

{ 40, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, -- e+f=40

{ 0, 0, 0, 1, 0, 0,-1,-1, 0, 0, 0, 0}, -- f+g=c

{ 11, 0, 0, 0, 0, 1, 0, 0, 0,-1, 0, 0}, -- x+11=e

{ 4, 0, 0, 0, 0, 0, 0, 1, 0, 0,-1, 0}, -- y+4=g

{ 11, 0, 0, 0, 0, 0, 1, 0, 0, 0,-1, 0}, -- 11+y=f

{ 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,-1}, -- 4+z=h

{ 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 1,-1} -- x+z=y

-- })) -- {81,70,41,29,16,24,17,12,5,13,8}

})[-3..-1]) -- {5,13,8}

And finally, a cheeky little two-liner that does the whole job

integer Y = (151-4*(11+4))/7, X = 40-2*11-Y, Z = Y-X

printf(1,"Two-liner: x=%d, y=%d, z=%d\n",{X,Y,Z})

<pre>

Two-liner: x=5, y=13, z=8

</pre>

=={{header|PicoLisp}}==