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|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

REM Describe the puzzle as a set of simultaneous equations:

PRINT "X = " ; vector(8)

PRINT "Y = " ; vector(9)

<pre>

X = 5

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>

x: 5, y: 13, z: 8

</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.

#include <stdlib.h>

 

 

return 0;

pass 2: 12

pass 3: 14

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]

 

 

=={{header|D}}==

{{trans|C}}

 

static ref T E(T)(T[] x, in size_t row, in size_t col)

return x[row * (row + 1) / 2 + col];

}

 

do {

E(v, 0, 0) = 151;

E(v, 2, 0) = 40;

E(v, 4, 3) = 4;

 

E(diff, i, j) = 0;

if (j < i)

if (j)

}

}

 

 

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

 

v[] += diff[] / 4;

 

static if (doPrint)

 

// from equilibrium. It takes about 50 iterations. After

}

 

void main() {

int idx;

idx++;

}

}

 

iterate(v, diff);

show(v);

dev: 17968.7

dev: 6388.46

16 24 17 12

5 11 13 4 8</pre>

 

=={{header|Go}}==

This solution follows the way the problem might be solved with pencil and paper. It shows a possible data representation of the problem, uses the computer to do some arithmetic, and displays intermediate and final results.

 

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

 

 

 

 

{{out}}

5 11 13 4 8</pre>

 

=={{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():

 

 

=={{header|Racket}}==

(Based on the clojure version)

 

#lang racket/base

(require racket/list)

(- (cell-x cx) (cell-x cy))

(- (cell-z cx) (cell-z cy))))

 

We first work bottom up and determine the value of each cell, starting from the bottom row.

(define (row-above row) (map cell-add (drop row 1) (drop-right row 1)))

 

(define row3 (row-above row2))

(define row4 (row-above row3))

 

We know the value of two additional cells, so by subtracting these values we get two equations of the form 0=v+x*X+z*Z. In the usual notation we get x*X+z*Z=-v, so v has the wrong sign.

 

(define eqn40 (cell-sub (car row4) (cell 151 0 0)))

(define eqn20 (cell-sub (car row2) (cell 40 0 0)))

 

To solve the 2 equation system, we will use the Cramer's rule.

(define (det2 eqnx eqny get-one get-oth)

(- (* (get-one eqnx) (get-oth eqny)) (* (get-one eqny) (get-oth eqnx))))

(/ (det2 eqnx eqny get-val get-oth)

(det2 eqnx eqny get-unk get-oth)))

 

To get the correct values of X, Y and Z we must change their signs.

(define x (- (cramer2 eqn20 eqn40 cell-v cell-x cell-z)))

(define z (- (cramer2 eqn20 eqn40 cell-v cell-z cell-x)))

(displayln (list "Y" (+ x z)))

(displayln (list "Z" z))

 

<pre>

(X 5)

(Z 8)

</pre>

 

=={{header|REXX}}==

 

</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>

 

[[Category:Puzzles]]