Pascal's triangle/Puzzle: Difference between revisions

{{task}}

This puzzle involves a [http://xunor.free.fr/en/riddles/auto/pyramidnb.php Pascals Triangle], also known as a [http://xunor.free.fr/en/riddles/auto/pyramidnb.php Pyramid of Numbers].

<pre>

</pre>

Each brick of the pyramid is the sum of the two bricks situated below it.<br>

 

Write a program to find a solution to this puzzle.

=={{header|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.

procedure Pyramid_of_Numbers is

end loop;

end loop;

<pre>

 

5 11 13 4 8

</pre>

=={{header|ALGOL 68}}==

{{works with|ALGOL 68|Standard - ''lu decomp'' and ''lu solve'' are from the [[ALGOL 68G]]/gsl library}}

{{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 }} -->

FIELD = REAL,

VEC = [0]REAL,

FOR var FROM 1 BY 2 TO 5 DO

printf(($5x$,$g$,puzzle[UPB puzzle][var],"=", real repr, solution[UPB puzzle][var]))

<pre>

(151.0)

=={{header|AutoHotkey}}==

The main part is this:

Z := (2*N4 - 7*N3 - 8*N2 + 6*N1) / 7

X := (N3 - 2*N1 - Z) / 2

Message box shows:

<pre>5.000000

 

The GUI shows all values in the solved state.

; Pascal's triangle.ahk

; by wolf_II

; delete status bar text

Else SB_SetText("")

 

=={{header|C}}==

This solution is based upon algebraic necessities, namely that a solution exists when (top - 4(a+b))/7 is integral. It also highlights the type difference between floating point numbers and integers in C.

 

/* Pascal's pyramid solver

*

return 0;

}

<pre>

</pre>

 

===Field equation solver===

Treating relations between cells as if they were differential equations, and apply negative feedback to each cell at every iteration step. This is how field equations with boundary conditions are solved numerically. It is, of course, not the optimal solution for this particular task.

 

for (i = 0; i < 5; i++)

for (j = 0; j <= i; j++)

}

 

{

/* enforce boundary conditions */

E(v, 0, 0) = 151;

E(diff, i, j) = 0;

if (j < i)

}

}

for (i = 0; i < 4; i++)

for (j = 0; j < i; j++)

 

E(diff, 4, 2) += E(v, 4, 0) + E(v, 4, 4) - E(v, 4, 2);

 

 

}

 

show(v);

 

return 0;

151

81 70

40 41 29

16 24 17 12

 

=={{header|Clojure}}==

 

 

(defn plus [v1 v2] (vec (map + v1 v2)))

(defn above [row] (map #(apply plus %) (partition 2 1 row)))

 

We know the integer value of cells c00 and c20 ( base-0 row then column numbers), so by subtracting these values we get two equations of the form 0=n0+n1*X+n2*Z.

(def c20 (get-in rows [2 0]))

 

(def eqn0 (minus c00 [151 0 0]))

In this case, there are only two variables, so solving the system of linear equations is simple.

(assert (<= 1 m 2))

(let [n (- 3 m)

 

(let [x (solve 1), z (solve 2), y (+ x z)]

If you want to solve the whole pyramid, just add a call ''(show-pyramid x z)'' to the previous ''let'' form:

 

(defn show-pyramid [x z]

(doseq [row rows]

 

 

 

 

 

 

 

 

 

import "fmt"

fmt.Println("y =", solveY(y))

fmt.Println("z =", solveZ(z))

<pre>

bottom row: [{1 0 0 0} {0 0 0 11} {0 1 0 0} {0 0 0 4} {0 0 1 0}]

I assume the task is to solve any such puzzle, i.e. given some data

 

 

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:

 

 

coeff xys x = maybe 0 id $ lookup x xys

eqs = eqXYZ n ++ eqPyramid n h ++ eqConst n fields

h = length puzzle

 

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

 

normalize xs = [numerator (x * v) | x <- xs] where

v = fromInteger $ foldr1 lcm $ map denominator $ xs

answer = case solve 0 lr a of

Nothing - []

 

will output one special solution and modifications that lead to more solutions, as in

 

[[151,81,70,40,41,29,16,24,17,12,5,11,13,4,8]]

*Main run [[""],["2",""],["X","Y","Z"]]

 

 

Note that the program doesn't attempt to verify that the puzzle is in correct form.

Fixed points in the pyramid are 40 and 151, which I use to check a resulting pyramid for selection:

 

 

verb for the base of the pyramid:

 

 

the height of the pyramid:

 

 

=> 'chk', 'base' and 'ord' are the knowledge rules abstracted from the problem definition.

The J-sentence that solves the puzzle is:

 

<pre> 151 0 0 0 0

81 70 0 0 0

Get rid of zeros:

or

 

<pre> +-----------+

+-----------+</pre>

 

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:

d+e==b

e+f==c

n+Y==i

n+Z==j

And we have the knowns

d->40

l->11

Giving us 10 equations with 10 unknowns; i.e. solvable. So we can do so by:

knowns={a->151,d->40,l->11,n->4};

gives back:

In pyramid form that would be:

81 70

40 41 29

16 24 17 12

 

=={{header|Oz}}==

functor

 

 

{Application.exit 0}

=={{header|PARI/GP}}==

[ 6y+x+z+4a[2]+4a[4]= 7y +4a[2]+4a[4]]

 

this helped me...

Pascals_triangle_puzzle(topvalue=151,leftsidevalue=40,bottomvalue1=11,bottomvalue2=4) = {

y=(topvalue-(4*(bottomvalue1+bottomvalue2)))/7;

z=y-x;

print(x","y","z); }

 

I'm thinking of one to solve all puzzles regardless of size and positions. but the objective was to solve this puzzle.

 

=={{header|PicoLisp}}==

(repeat)

(or

 

(be + (@A @B @Sum)

 

(be + (@A @B @Sum)

T

 

(be + (@A @B @Sum)

(number @A @Sum)

 

#{

(+ @Y 4 @G)

(+ 4 @Z @H)

<pre>: (? (puzzle @X @Y @Z))

@X=5 @Y=13 @Z=8</pre>

 

=={{header|Prolog}}==

 

puzzle(Ts, X, Y, Z) :-

% X = 5,

% Y = 13,

 

=={{header|PureBasic}}==

Brute force solution.

; A.

; [ 151]

z=SolveForZ(x)

Until z>=0

 

=={{header|Python}}==

{{works with|Python|2.4+}}

# [151]

# [ ] [ ]

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 }

<pre>Constraint Equations:

-1*Y + 1*X + 0*1 + 1*Z = 0

http://www.fantascienza.net/leonardo/so/csp.zip

 

 

p = Problem()

p.addrule("Y == X + Z")

for sol in p.xsolutions():

 

 

 

 

 

 

 

 

</pre>

 

=={{header|Ruby}}==

uses [[Reduced row echelon form#Ruby]]

 

pyramid = [

["x", 11,"y", 4,"z"]

]

equations = [[1,-1,1,0]] # y = x + z

 

for term in lhs.split("+")

case term

end

end

pyramid[row].each_index do |col|

val = pyramid[row][col]

if val.nil?

pyramid[row][col] = sum

if eqn[0] + eqn[1] + eqn[2] != 1

fail "no unique solution! #{equations.inspect} ==> #{reduced.inspect}"

end

end

 

puts "x == #{x}"

puts "y == #{y}"

answer << row.collect {|cell| eval cell.to_s}

end

x == 5

y == 13

z == 8

 

=={{header|SystemVerilog}}==

We can view this as a problem of generating a set of random numbers that satisfy the constraints. Because there is only one solution, the result isn't very random...

 

class Triangle;

 

Triangle answer = new;

<pre> [151]

[81][70]

=={{header|Tcl}}==

using code from [[Reduced row echelon form#Tcl]]

namespace path ::tcl::mathop

 

lappend solved $newrow

}

<pre>x=5.0

y=13.0

16.0 24.0 17.0 12.0

5.0 11.0 13.0 4.0 8.0</pre>