Pascal's triangle/Puzzle: Difference between revisions
(→{{header|Java}}: fixed an HTML PRE closing tag that "ate" the 1st Julia solution.) |
m (→{{header|Wren}}: Minor tidy) |
||
(27 intermediate revisions by 17 users not shown) | |||
Line 17: | Line 17: | ||
Write a program to find a solution to this puzzle. |
Write a program to find a solution to this puzzle. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="11l">F e(&x, row, col) -> & |
|||
R x[row * (row + 1) I/ 2 + col] |
|||
F iterate(&v, &diff, do_print = 1B) |
|||
V tot = 0.0 |
|||
L |
|||
e(&v, 0, 0) = 151 |
|||
e(&v, 2, 0) = 40 |
|||
e(&v, 4, 1) = 11 |
|||
e(&v, 4, 3) = 4 |
|||
L(i) 1..4 |
|||
L(j) 0..i |
|||
e(&diff, i, j) = 0 |
|||
I j < i |
|||
e(&diff, i, j) += e(&v, i - 1, j) - e(&v, i, j + 1) - e(&v, i, j) |
|||
I j != 0 |
|||
e(&diff, i, j) += e(&v, i - 1, j - 1) - e(&v, i, j - 1) - e(&v, i, j) |
|||
L(i) 1..3 |
|||
L(j) 0.<i |
|||
e(&diff, i, j) += e(&v, i + 1, j) + e(&v, i + 1, j + 1) - e(&v, i, j) |
|||
e(&diff, 4, 2) += e(&v, 4, 0) + e(&v, 4, 4) - e(&v, 4, 2) |
|||
L(i) 0 .< v.len |
|||
v[i] += diff[i] / 4 |
|||
tot = sum(diff.map(a -> a * a)) |
|||
I do_print |
|||
print(‘dev: ’tot) |
|||
I tot < 0.1 |
|||
L.break |
|||
V v = [0.0] * 15 |
|||
V diff = [0.0] * 15 |
|||
iterate(&v, &diff) |
|||
V idx = 0 |
|||
L(i) 5 |
|||
L(j) 0..i |
|||
print(‘#4’.format(Int(0.5 + v[idx])), end' I j < i {‘ ’} E "\n") |
|||
idx++</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
dev: 73410 |
|||
dev: 17968.6875 |
|||
dev: 6388.46484375 |
|||
dev: 2883.337402344 |
|||
dev: 1446.593643188 |
|||
... |
|||
dev: 0.136503592 |
|||
dev: 0.125866452 |
|||
dev: 0.116055273 |
|||
dev: 0.107006115 |
|||
dev: 0.098659977 |
|||
151 |
|||
81 70 |
|||
40 41 29 |
|||
16 24 17 12 |
|||
5 11 13 4 8 |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO; |
||
procedure Pyramid_of_Numbers is |
procedure Pyramid_of_Numbers is |
||
Line 88: | Line 155: | ||
end loop; |
end loop; |
||
end loop; |
end loop; |
||
end Pyramid_of_Numbers;</ |
end Pyramid_of_Numbers;</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 98: | Line 165: | ||
5 11 13 4 8 |
5 11 13 4 8 |
||
</pre> |
</pre> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68|Standard - ''lu decomp'' and ''lu solve'' are from the [[ALGOL 68G]]/gsl library}} |
{{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}} |
{{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 }} --> |
<!-- {{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 }} --> |
||
< |
<syntaxhighlight lang="algol68">MODE |
||
FIELD = REAL, |
FIELD = REAL, |
||
VEC = [0]REAL, |
VEC = [0]REAL, |
||
Line 197: | Line 265: | ||
FOR var FROM 1 BY 2 TO 5 DO |
FOR var FROM 1 BY 2 TO 5 DO |
||
printf(($5x$,$g$,puzzle[UPB puzzle][var],"=", real repr, solution[UPB puzzle][var])) |
printf(($5x$,$g$,puzzle[UPB puzzle][var],"=", real repr, solution[UPB puzzle][var])) |
||
OD</ |
OD</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 210: | Line 278: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
The main part is this: |
The main part is this: |
||
< |
<syntaxhighlight lang="autohotkey">N1 := 11, N2 := 4, N3 := 40, N4 := 151 |
||
Z := (2*N4 - 7*N3 - 8*N2 + 6*N1) / 7 |
Z := (2*N4 - 7*N3 - 8*N2 + 6*N1) / 7 |
||
X := (N3 - 2*N1 - Z) / 2 |
X := (N3 - 2*N1 - Z) / 2 |
||
MsgBox,, Pascal's Triangle, %X%`n%Z%</ |
MsgBox,, Pascal's Triangle, %X%`n%Z%</syntaxhighlight> |
||
Message box shows: |
Message box shows: |
||
<pre>5.000000 |
<pre>5.000000 |
||
Line 220: | Line 288: | ||
The GUI shows all values in the solved state. |
The GUI shows all values in the solved state. |
||
< |
<syntaxhighlight lang="autohotkey">;--------------------------------------------------------------------------- |
||
; Pascal's triangle.ahk |
; Pascal's triangle.ahk |
||
; by wolf_II |
; by wolf_II |
||
Line 493: | Line 561: | ||
; delete status bar text |
; delete status bar text |
||
Else SB_SetText("") |
Else SB_SetText("") |
||
}</ |
}</syntaxhighlight> |
||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> INSTALL @lib$ + "ARRAYLIB" |
||
REM Describe the puzzle as a set of simultaneous equations: |
REM Describe the puzzle as a set of simultaneous equations: |
||
Line 535: | Line 603: | ||
PRINT "X = " ; vector(8) |
PRINT "X = " ; vector(8) |
||
PRINT "Y = " ; vector(9) |
PRINT "Y = " ; vector(9) |
||
PRINT "Z = " ; vector(10)</ |
PRINT "Z = " ; vector(10)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 543: | Line 611: | ||
</pre> |
</pre> |
||
=={{header|C |
=={{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. |
|||
<lang c sharp> |
|||
<syntaxhighlight lang="c"> |
|||
/* Pascal's pyramid solver |
|||
* |
|||
* [top] |
|||
* [ ] [ ] |
|||
* [mid] [ ] [ ] |
|||
* [ ] [ ] [ ] [ ] |
|||
* [ x ] [ a ] [ y ] [ b ] [ z ] |
|||
* x + z = y |
|||
* |
|||
* This solution makes use of a little bit of mathematical observation, |
|||
* such as the fact that top = 4(a+b) + 7(x+z) and mid = 2x + 2a + z. |
|||
*/ |
|||
#include <stdio.h> |
|||
#include <math.h> |
|||
void pascal(int a, int b, int mid, int top, int* x, int* y, int* z) |
|||
{ |
|||
double ytemp = (top - 4 * (a + b)) / 7.; |
|||
if(fmod(ytemp, 1.) >= 0.0001) |
|||
{ |
|||
x = 0; |
|||
return; |
|||
} |
|||
*y = ytemp; |
|||
*x = mid - 2 * a - *y; |
|||
*z = *y - *x; |
|||
} |
|||
int main() |
|||
{ |
|||
int a = 11, b = 4, mid = 40, top = 151; |
|||
int x, y, z; |
|||
pascal(a, b, mid, top, &x, &y, &z); |
|||
if(x != 0) |
|||
printf("x: %d, y: %d, z: %d\n", x, y, z); |
|||
else printf("No solution\n"); |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<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. |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
void show(int *x) { |
|||
int i, j; |
|||
for (i = 0; i < 5; i++) |
|||
for (j = 0; j <= i; j++) |
|||
printf("%4d%c", *(x++), j < i ? ' ' : '\n'); |
|||
} |
|||
inline int sign(int i) |
|||
{ |
|||
return i < 0 ? -1 : i > 0; |
|||
} |
|||
int iter(int *v, int *diff) { |
|||
int sum, i, j, e = 0; |
|||
# define E(x, row, col) x[(row) * ((row) + 1) / 2 + (col)] |
|||
/* enforce boundary conditions */ |
|||
E(v, 0, 0) = 151; |
|||
E(v, 2, 0) = 40; |
|||
E(v, 4, 1) = 11; |
|||
E(v, 4, 3) = 4; |
|||
/* calculate difference from equilibrium */ |
|||
for (i = 1; i < 5; i++) { |
|||
for (j = 0; j <= i; j++) { |
|||
E(diff, i, j) = 0; |
|||
if (j < i) |
|||
E(diff, i, j) += E(v, i - 1, j) - |
|||
E(v, i, j + 1) - |
|||
E(v, i, j); |
|||
if (j) |
|||
E(diff, i, j) += E(v, i - 1, j - 1) - |
|||
E(v, i, j - 1) - |
|||
E(v, i, j); |
|||
} |
|||
} |
|||
for (i = 0; i < 4; i++) |
|||
for (j = 0; j < i; j++) |
|||
E(diff, i, j) += E(v, i + 1, j) + |
|||
E(v, i + 1, j + 1) - |
|||
E(v, i, j); |
|||
E(diff, 4, 2) += E(v, 4, 0) + E(v, 4, 4) - E(v, 4, 2); |
|||
# undef E |
|||
/* Do feedback, check if we are done. */ |
|||
for (i = sum = 0; i < 15; i++) { |
|||
sum += !!sign(e = diff[i]); |
|||
/* 1/5-ish feedback strength on average. These numbers are highly |
|||
magical, depending on nodes' connectivities. */ |
|||
if (e >= 4 || e <= -4) v[i] += e/5; |
|||
else if (rand() < RAND_MAX/4) v[i] += sign(e); |
|||
} |
|||
return sum; |
|||
} |
|||
int main() { |
|||
int v[15] = { 0 }, diff[15] = { 0 }, i, s; |
|||
for (i = s = 1; s; i++) { |
|||
s = iter(v, diff); |
|||
printf("pass %d: %d\n", i, s); |
|||
} |
|||
show(v); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{Out}}<pre>pass 1: 12 |
|||
pass 2: 12 |
|||
pass 3: 14 |
|||
pass 4: 14 |
|||
... |
|||
pass 113: 4 |
|||
pass 114: 7 |
|||
pass 115: 0 |
|||
151 |
|||
81 70 |
|||
40 41 29 |
|||
16 24 17 12 |
|||
5 11 13 4 8</pre> |
|||
=={{header|C sharp|C#}}== |
|||
<syntaxhighlight lang="c sharp"> |
|||
using System; |
using System; |
||
Line 731: | Line 939: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out| Program Input and Output}} |
{{out| Program Input and Output}} |
||
<pre> |
<pre> |
||
Line 798: | Line 1,006: | ||
</pre> |
</pre> |
||
=={{header|C}}== |
=={{header|C++}}== |
||
{{trans|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. |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <iomanip> |
|||
inline int sign(int i) { |
|||
<lang c> |
|||
return i < 0 ? -1 : i > 0; |
|||
/* Pascal's pyramid solver |
|||
* |
|||
* [top] |
|||
* [ ] [ ] |
|||
* [mid] [ ] [ ] |
|||
* [ ] [ ] [ ] [ ] |
|||
* [ x ] [ a ] [ y ] [ b ] [ z ] |
|||
* x + z = y |
|||
* |
|||
* This solution makes use of a little bit of mathematical observation, |
|||
* such as the fact that top = 4(a+b) + 7(x+z) and mid = 2x + 2a + z. |
|||
*/ |
|||
#include <stdio.h> |
|||
#include <math.h> |
|||
void pascal(int a, int b, int mid, int top, int* x, int* y, int* z) |
|||
{ |
|||
double ytemp = (top - 4 * (a + b)) / 7.; |
|||
if(fmod(ytemp, 1.) >= 0.0001) |
|||
{ |
|||
x = 0; |
|||
return; |
|||
} |
|||
*y = ytemp; |
|||
*x = mid - 2 * a - *y; |
|||
*z = *y - *x; |
|||
} |
} |
||
int main() |
|||
{ |
|||
int a = 11, b = 4, mid = 40, top = 151; |
|||
int x, y, z; |
|||
pascal(a, b, mid, top, &x, &y, &z); |
|||
if(x != 0) |
|||
printf("x: %d, y: %d, z: %d\n", x, y, z); |
|||
else printf("No solution\n"); |
|||
inline int& E(int *x, int row, int col) { |
|||
return 0; |
|||
return x[row * (row + 1) / 2 + col]; |
|||
} |
} |
||
</lang> |
|||
{{Out}} |
|||
<pre> |
|||
x: 5, y: 13, z: 8 |
|||
</pre> |
|||
int iter(int *v, int *diff) { |
|||
// enforce boundary conditions |
|||
E(v, 0, 0) = 151; |
|||
E(v, 2, 0) = 40; |
|||
E(v, 4, 1) = 11; |
|||
E(v, 4, 3) = 4; |
|||
// calculate difference from equilibrium |
|||
for (auto i = 1u; i < 5u; i++) |
|||
for (auto j = 0u; j <= i; j++) { |
|||
E(diff, i, j) = 0; |
|||
if (j < i) |
|||
E(diff, i, j) += E(v, i - 1, j) - E(v, i, j + 1) - E(v, i, j); |
|||
if (j) |
|||
E(diff, i, j) += E(v, i - 1, j - 1) - E(v, i, j - 1) - E(v, i, j); |
|||
} |
|||
for (auto i = 0u; i < 4u; i++) |
|||
===Field equation solver=== |
|||
for (auto j = 0u; j < i; j++) |
|||
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. |
|||
E(diff, i, j) += E(v, i + 1, j) + E(v, i + 1, j + 1) - E(v, i, j); |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
E(diff, 4, 2) += E(v, 4, 0) + E(v, 4, 4) - E(v, 4, 2); |
|||
void show(int *x) { |
|||
int i, j; |
|||
// do feedback, check if we are done |
|||
for (i = 0; i < 5; i++) |
|||
uint sum; |
|||
int e = 0; |
|||
printf("%4d%c", *(x++), j < i ? ' ' : '\n'); |
|||
for (auto i = sum = 0u; i < 15u; i++) { |
|||
} |
|||
sum += !!sign(e = diff[i]); |
|||
// 1/5-ish feedback strength on average. These numbers are highly magical, depending on nodes' connectivities |
|||
inline int sign(int i) |
|||
if (e >= 4 || e <= -4) |
|||
{ |
|||
v[i] += e / 5; |
|||
else if (rand() < RAND_MAX / 4) |
|||
v[i] += sign(e); |
|||
} |
|||
return sum; |
|||
} |
} |
||
void show(int *x) { |
|||
for (auto i = 0u; i < 5u; i++) |
|||
int sum, i, j, e = 0; |
|||
for (auto j = 0u; j <= i; j++) |
|||
std::cout << std::setw(4u) << *(x++) << (j < i ? ' ' : '\n'); |
|||
# define E(x, row, col) x[(row) * ((row) + 1) / 2 + (col)] |
|||
/* enforce boundary conditions */ |
|||
E(v, 0, 0) = 151; |
|||
E(v, 2, 0) = 40; |
|||
E(v, 4, 1) = 11; |
|||
E(v, 4, 3) = 4; |
|||
/* calculate difference from equilibrium */ |
|||
for (i = 1; i < 5; i++) { |
|||
for (j = 0; j <= i; j++) { |
|||
E(diff, i, j) = 0; |
|||
if (j < i) |
|||
E(diff, i, j) += E(v, i - 1, j) - |
|||
E(v, i, j + 1) - |
|||
E(v, i, j); |
|||
if (j) |
|||
E(diff, i, j) += E(v, i - 1, j - 1) - |
|||
E(v, i, j - 1) - |
|||
E(v, i, j); |
|||
} |
|||
} |
|||
for (i = 0; i < 4; i++) |
|||
for (j = 0; j < i; j++) |
|||
E(diff, i, j) += E(v, i + 1, j) + |
|||
E(v, i + 1, j + 1) - |
|||
E(v, i, j); |
|||
E(diff, 4, 2) += E(v, 4, 0) + E(v, 4, 4) - E(v, 4, 2); |
|||
# undef E |
|||
/* Do feedback, check if we are done. */ |
|||
for (i = sum = 0; i < 15; i++) { |
|||
sum += !!sign(e = diff[i]); |
|||
/* 1/5-ish feedback strength on average. These numbers are highly |
|||
magical, depending on nodes' connectivities. */ |
|||
if (e >= 4 || e <= -4) v[i] += e/5; |
|||
else if (rand() < RAND_MAX/4) v[i] += sign(e); |
|||
} |
|||
return sum; |
|||
} |
} |
||
int main() { |
int main() { |
||
int v[15] = { 0 }, diff[15] = { 0 }; |
|||
for (auto i = 1u, s = 1u; s; i++) { |
|||
s = iter(v, diff); |
|||
std::cout << "pass " << i << ": " << s << std::endl; |
|||
} |
|||
show(v); |
|||
return 0; |
|||
for (i = s = 1; s; i++) { |
|||
}</syntaxhighlight> |
|||
s = iter(v, diff); |
|||
printf("pass %d: %d\n", i, s); |
|||
} |
|||
show(v); |
|||
return 0; |
|||
}</lang> |
|||
{{Out}}<pre>pass 1: 12 |
|||
pass 2: 12 |
|||
pass 3: 14 |
|||
pass 4: 14 |
|||
... |
|||
pass 113: 4 |
|||
pass 114: 7 |
|||
pass 115: 0 |
|||
151 |
|||
81 70 |
|||
40 41 29 |
|||
16 24 17 12 |
|||
5 11 13 4 8</pre> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
Line 942: | Line 1,078: | ||
X and Z are the independent variables, so first work bottom up and determine the value of each cell in the form (n0 + n1*X + n2*Z). |
X and Z are the independent variables, so first work bottom up and determine the value of each cell in the form (n0 + n1*X + n2*Z). |
||
We'll use a vector [n0 n1 n2] to represent each cell. |
We'll use a vector [n0 n1 n2] to represent each cell. |
||
< |
<syntaxhighlight lang="clojure">(def bottom [ [0 1 0], [11 0 0], [0 1 1], [4 0 0], [0 0 1] ]) |
||
(defn plus [v1 v2] (vec (map + v1 v2))) |
(defn plus [v1 v2] (vec (map + v1 v2))) |
||
Line 950: | Line 1,086: | ||
(defn above [row] (map #(apply plus %) (partition 2 1 row))) |
(defn above [row] (map #(apply plus %) (partition 2 1 row))) |
||
(def rows (reverse (take 5 (iterate above bottom))))</ |
(def rows (reverse (take 5 (iterate above bottom))))</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang="clojure">(def c00 (get-in rows [0 0])) |
||
(def c20 (get-in rows [2 0])) |
(def c20 (get-in rows [2 0])) |
||
(def eqn0 (minus c00 [151 0 0])) |
(def eqn0 (minus c00 [151 0 0])) |
||
(def eqn1 (minus c20 [ 40 0 0]))</ |
(def eqn1 (minus c20 [ 40 0 0]))</syntaxhighlight> |
||
In this case, there are only two variables, so solving the system of linear equations is simple. |
In this case, there are only two variables, so solving the system of linear equations is simple. |
||
< |
<syntaxhighlight lang="clojure">(defn solve [m] |
||
(assert (<= 1 m 2)) |
(assert (<= 1 m 2)) |
||
(let [n (- 3 m) |
(let [n (- 3 m) |
||
Line 968: | Line 1,104: | ||
(let [x (solve 1), z (solve 2), y (+ x z)] |
(let [x (solve 1), z (solve 2), y (+ x z)] |
||
(println "x =" x ", y =" y ", z =" z))</ |
(println "x =" x ", y =" y ", z =" z))</syntaxhighlight> |
||
If you want to solve the whole pyramid, just add a call ''(show-pyramid x z)'' to the previous ''let'' form: |
If you want to solve the whole pyramid, just add a call ''(show-pyramid x z)'' to the previous ''let'' form: |
||
< |
<syntaxhighlight lang="clojure">(defn dot [v1 v2] (reduce + (map * v1 v2))) |
||
(defn show-pyramid [x z] |
(defn show-pyramid [x z] |
||
(doseq [row rows] |
(doseq [row rows] |
||
(println (map #(dot [1 x z] %) row)))</ |
(println (map #(dot [1 x z] %) row)))</syntaxhighlight> |
||
=={{header|Craft Basic}}== |
|||
<syntaxhighlight lang="basic">let x = -1 |
|||
do |
|||
let x = x + 1 |
|||
let z = 0 |
|||
do |
|||
let e = x + 11 |
|||
let f = 11 + (x + z) |
|||
let g = (x + z) + 4 |
|||
let h = 4 + z |
|||
if e + f = 40 then |
|||
let c = f + g |
|||
let d = g + h |
|||
let a = 40 + c |
|||
let b = c + d |
|||
let q = 0 |
|||
if a + b = 151 then |
|||
let q = 1 |
|||
endif |
|||
endif |
|||
if q = 0 then |
|||
let z = z + 1 |
|||
endif |
|||
wait |
|||
loopwhile z < 20 and q = 0 |
|||
if q = 0 then |
|||
let z = -1 |
|||
endif |
|||
wait |
|||
loopuntil z >= 0 |
|||
print "x = ", x |
|||
print "y = ", x + z |
|||
print "z = ", z</syntaxhighlight> |
|||
{{out| Output}}<pre>x = 5 |
|||
y = 13 |
|||
z = 8</pre> |
|||
=={{header|Curry}}== |
=={{header|Curry}}== |
||
{{Works with|PAKCS}} |
{{Works with|PAKCS}} |
||
< |
<syntaxhighlight lang="curry">import CLPFD |
||
import Constraint (allC, andC) |
import Constraint (allC, andC) |
||
import Findall (findall) |
import Findall (findall) |
||
Line 1,002: | Line 1,196: | ||
, [ x, 11, y, 4, z] |
, [ x, 11, y, 4, z] |
||
] |
] |
||
main = findall $ solve . test</ |
main = findall $ solve . test</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Execution time: 0 msec. / elapsed: 0 msec. |
<pre>Execution time: 0 msec. / elapsed: 0 msec. |
||
Line 1,009: | Line 1,203: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm; |
||
void iterate(bool doPrint=true)(double[] v, double[] diff) @safe { |
void iterate(bool doPrint=true)(double[] v, double[] diff) @safe { |
||
Line 1,069: | Line 1,263: | ||
iterate(v, diff); |
iterate(v, diff); |
||
show(v); |
show(v); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>dev: 73410 |
<pre>dev: 73410 |
||
Line 1,092: | Line 1,286: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
<p>In a script, using the [http://numerics.mathdotnet.com/ Math.NET Numerics] library</p> |
<p>In a script, using the [http://numerics.mathdotnet.com/ Math.NET Numerics] library</p> |
||
< |
<syntaxhighlight lang="fsharp"> |
||
#load"Packages\MathNet.Numerics.FSharp\MathNet.Numerics.fsx" |
#load"Packages\MathNet.Numerics.FSharp\MathNet.Numerics.fsx" |
||
Line 1,115: | Line 1,309: | ||
let x = A.Solve(b) |
let x = A.Solve(b) |
||
printfn "x = %f, Y = %f, Z = %f" x.[8] x.[9] x.[10]</ |
printfn "x = %f, Y = %f, Z = %f" x.[8] x.[9] x.[10]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>x = 5.000000, Y = 13.000000, Z = 8.000000</pre> |
<pre>x = 5.000000, Y = 13.000000, Z = 8.000000</pre> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.98}} |
|||
<lang factor>USING: arrays backtrack combinators.extras fry grouping.extras |
|||
<syntaxhighlight lang="factor">USING: arrays backtrack combinators.extras fry grouping.extras |
|||
interpolate io kernel math math.ranges sequences ; |
interpolate io kernel math math.ranges sequences ; |
||
IN: rosetta-code.pascals-triangle-puzzle |
|||
: base ( ?x ?z -- seq ) 2dup + swap '[ _ 11 _ 4 _ ] >array ; |
: base ( ?x ?z -- seq ) 2dup + swap '[ _ 11 _ 4 _ ] >array ; |
||
Line 1,133: | Line 1,327: | ||
up first 151 = must-be-true ; |
up first 151 = must-be-true ; |
||
find-solution [I X = ${1}, Z = ${}I] nl</ |
find-solution [I X = ${1}, Z = ${}I] nl</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
X = 5, Z = 8 |
X = 5, Z = 8 |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
{{trans|PureBasic}} |
|||
<syntaxhighlight lang="freebasic">Function SolveForZ(x As Integer) As Integer |
|||
Dim As Integer a, b, c, d, e, f, g, h, z |
|||
For z = 0 To 20 |
|||
e = x + 11 |
|||
f = 11 + (x+z) |
|||
g = (x+z) + 4 |
|||
h = 4 + z |
|||
If e + f = 40 Then |
|||
c = f + g |
|||
d = g + h |
|||
a = 40 + c |
|||
b = c + d |
|||
If a + b = 151 Then Return z |
|||
End If |
|||
Next z |
|||
Return -1 |
|||
End Function |
|||
Dim As Integer x = -1, z = 0 |
|||
Do |
|||
x = x + 1 |
|||
z = SolveForZ(x) |
|||
Loop Until z >= 0 |
|||
Print "X ="; x |
|||
Print "Y ="; x + z |
|||
Print "Z ="; z |
|||
Sleep |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>X = 5 |
|||
Y = 13 |
|||
Z = 8</pre> |
|||
=={{header|Go}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,274: | Line 1,505: | ||
fmt.Println("y =", solveY(y)) |
fmt.Println("y =", solveY(y)) |
||
fmt.Println("z =", solveZ(z)) |
fmt.Println("z =", solveZ(z)) |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,297: | Line 1,528: | ||
I assume the task is to solve any such puzzle, i.e. given some data |
I assume the task is to solve any such puzzle, i.e. given some data |
||
< |
<syntaxhighlight lang="haskell">puzzle = [["151"],["",""],["40","",""],["","","",""],["X","11","Y","4","Z"]]</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang="haskell">triangle n = n * (n+1) `div` 2 |
||
coeff xys x = maybe 0 id $ lookup x xys |
coeff xys x = maybe 0 id $ lookup x xys |
||
Line 1,329: | Line 1,560: | ||
eqs = eqXYZ n ++ eqPyramid n h ++ eqConst n fields |
eqs = eqXYZ n ++ eqPyramid n h ++ eqConst n fields |
||
h = length puzzle |
h = length puzzle |
||
n = length fields</ |
n = length fields</syntaxhighlight> |
||
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 |
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 |
||
< |
<syntaxhighlight lang="haskell">normalize :: [Rational] - [Integer] |
||
normalize xs = [numerator (x * v) | x <- xs] where |
normalize xs = [numerator (x * v) | x <- xs] where |
||
v = fromInteger $ foldr1 lcm $ map denominator $ xs |
v = fromInteger $ foldr1 lcm $ map denominator $ xs |
||
Line 1,342: | Line 1,573: | ||
answer = case solve 0 lr a of |
answer = case solve 0 lr a of |
||
Nothing - [] |
Nothing - [] |
||
Just x - x : kernel lr</ |
Just x - x : kernel lr</syntaxhighlight> |
||
will output one special solution and modifications that lead to more solutions, as in |
will output one special solution and modifications that lead to more solutions, as in |
||
< |
<syntaxhighlight lang="haskell">*Main run puzzle |
||
[[151,81,70,40,41,29,16,24,17,12,5,11,13,4,8]] |
[[151,81,70,40,41,29,16,24,17,12,5,11,13,4,8]] |
||
*Main run [[""],["2",""],["X","Y","Z"]] |
*Main run [[""],["2",""],["X","Y","Z"]] |
||
[[3,2,1,1,1,0],[3,0,3,-1,1,2]]</ |
[[3,2,1,1,1,0],[3,0,3,-1,1,2]]</syntaxhighlight> |
||
so for the second puzzle, not only X=1 Y=1 Z=0 is a solution, |
so for the second puzzle, not only X=1 Y=1 Z=0 is a solution, |
||
Line 1,360: | Line 1,591: | ||
Fixed points in the pyramid are 40 and 151, which I use to check a resulting pyramid for selection: |
Fixed points in the pyramid are 40 and 151, which I use to check a resulting pyramid for selection: |
||
< |
<syntaxhighlight lang="j">chk=:40 151&-:@(2 4{{."1)</syntaxhighlight> |
||
verb for the base of the pyramid: |
verb for the base of the pyramid: |
||
< |
<syntaxhighlight lang="j">base=: [,11,+,4,]</syntaxhighlight> |
||
the height of the pyramid: |
the height of the pyramid: |
||
< |
<syntaxhighlight lang="j">ord=:5</syntaxhighlight> |
||
=> 'chk', 'base' and 'ord' are the knowledge rules abstracted from the problem definition. |
=> 'chk', 'base' and 'ord' are the knowledge rules abstracted from the problem definition. |
||
Line 1,374: | Line 1,605: | ||
The J-sentence that solves the puzzle is: |
The J-sentence that solves the puzzle is: |
||
< |
<syntaxhighlight lang="j"> |."2(#~chk"2) 2(+/\)^:(<ord)"1 base/"1>,{ ;~i:28</syntaxhighlight> |
||
<pre> 151 0 0 0 0 |
<pre> 151 0 0 0 0 |
||
81 70 0 0 0 |
81 70 0 0 0 |
||
Line 1,383: | Line 1,614: | ||
Get rid of zeros: |
Get rid of zeros: |
||
< |
<syntaxhighlight lang="j">,.(1+i.5)<@{."0 1{.|."2(#~chk"2) 2(+/\)^:(<ord)"1 base/"1>,{ ;~i:28</syntaxhighlight> |
||
or |
or |
||
< |
<syntaxhighlight lang="j">,.(<@{."0 1~1+i.@#){.|."2(#~chk"2) 2(+/\)^:(<ord)"1 base/"1>,{ ;~i:28</syntaxhighlight> |
||
<pre> +-----------+ |
<pre> +-----------+ |
||
Line 1,403: | Line 1,634: | ||
Generate 11 equations and 11 unknowns. Reuse code from Cramer's Rule. |
Generate 11 equations and 11 unknowns. Reuse code from Cramer's Rule. |
||
< |
<syntaxhighlight lang="java"> |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.Arrays; |
import java.util.Arrays; |
||
Line 1,517: | Line 1,748: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,525: | Line 1,756: | ||
Y = 13.00 |
Y = 13.00 |
||
Z = 8.00 |
Z = 8.00 |
||
</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Also works with gojq, the Go implementation of jq, and with fq.''' |
|||
In the spirit of the simplicity of Pascal Triangle's definition, the |
|||
first solution given in this entry works up from the bottom of the triangle using the |
|||
basic Pascal Triangle equation for each brick that is above two |
|||
others. |
|||
In the following, the value of the j-th brick in the i-th row is |
|||
denoted by rij if initially known (so r11 refers to the apex), and by |
|||
$Rij if initially unknown, so the variable "X" in the puzzle |
|||
could be denoted by $R51. |
|||
It is assumed that: |
|||
* all values in the triangle must be positive integers; |
|||
* the task is to solve for any given values of r11, r31, r52, r54; |
|||
* all solutions for the triple [X, Y, Z] should be found. |
|||
<syntaxhighlight lang=jq> |
|||
def solve(r11; r31; r52; r54): |
|||
range(1;r31 - 1) as $X |
|||
| range(1; r31 - 1) as $Y |
|||
| (($Y - $X) | select(. > 0)) as $Z |
|||
| (r52 + $X) as $R41 |
|||
| (r52 + $Y) as $R42 |
|||
| select($R41 + $R42 == r31) |
|||
| ($Y + r54) as $R43 |
|||
| (r54 + $Z) as $R44 |
|||
| ($R42 + $R43) as $R32 |
|||
| ($R43 + $R44) as $R33 |
|||
| (r31 + $R32) as $R21 |
|||
| ($R32 + $R33) as $R22 |
|||
| select($R21 + $R22 == r11) |
|||
| [$X, $Y, $Z]; |
|||
solve(151; 40; 11; 4), |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
[5,13,8] |
|||
</pre> |
|||
===Algebraic solution=== |
|||
As noted elsewhere on this page, elementary considerations show that |
|||
the apex (top) value and the value in the third row (mid) can be written as: |
|||
<pre> |
|||
top = 4(a+b) + 7(x+z) |
|||
mid = 2x + 2a + z |
|||
</pre> |
|||
where a and b are the known values at the base. |
|||
Using the jq program at [[Cramer%27s_rule#jq|Cramer's rule]], with the unknown vector being [x, z]: |
|||
<syntaxhighlight lang=jq> |
|||
include "rc-cramers-rule"; |
|||
def solve(top; mid; a; b): |
|||
cramer( |
|||
[ [7, 7], |
|||
[2, 1]]; |
|||
[top - 4*(a+b), mid-2*a]); |
|||
solve(151; 40; 11; 4) |
|||
</syntaxhighlight> |
|||
This gives the solution for [x,z] as: |
|||
{{output}} |
|||
<pre> |
|||
[5,8] |
|||
</pre> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{works with|Julia|0.6}} |
|||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
<syntaxhighlight lang="julia">function pascal(a::Integer, b::Integer, mid::Integer, top::Integer) |
|||
<lang julia>function pascal(a::Integer, b::Integer, mid::Integer, top::Integer) |
|||
yd = round((top - 4 * (a + b)) / 7) |
yd = round((top - 4 * (a + b)) / 7) |
||
!isinteger(yd) && return 0, 0, 0 |
!isinteger(yd) && return 0, 0, 0 |
||
Line 1,544: | Line 1,840: | ||
else |
else |
||
println("There is no solution.") |
println("There is no solution.") |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Solution: x = 5, y = 13, z = 8.</pre> |
<pre>Solution: x = 5, y = 13, z = 8.</pre> |
||
=={{header|Julia}}== |
|||
{{trans|Kotlin}} |
|||
<lang julia>struct Solution |
|||
x::Int |
|||
y::Int |
|||
z::Int |
|||
end |
|||
isIntegral(sol, atol) = (sol - floor(sol) <= atol) || (ceil(sol) - sol <= atol) |
|||
function pascal(a, b, mid, top) |
|||
yd = (top - 4 * (a + b)) / 7.0 |
|||
!isIntegral(yd, 0.0001) && return Solution(0, 0, 0) |
|||
y = Int(round(yd)) |
|||
x = mid - 2 * a - y |
|||
return Solution(x, y, y - x) |
|||
end |
|||
function testpascalpuzzle() |
|||
p = pascal(11, 4, 40, 151) |
|||
println(p.x != 0 ? |
|||
"Solution is: x = $(p.x), y = $(p.y), z = $(p.z)" : |
|||
"There is no solution.") |
|||
end |
|||
testpascalpuzzle() |
|||
</lang>{{out}} |
|||
<pre> |
|||
Solution is: x = 5, y = 13, z = 8 |
|||
</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="scala">// version 1.1.3 |
||
data class Solution(val x: Int, val y: Int, val z: Int) |
data class Solution(val x: Int, val y: Int, val z: Int) |
||
Line 1,603: | Line 1,868: | ||
else |
else |
||
println("There is no solutuon") |
println("There is no solutuon") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,611: | Line 1,876: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
<syntaxhighlight lang="maple"> |
|||
<lang Maple> |
|||
sys := {22 + x + y = 40, 78 + 5*y + z = 151, x + z = y}: |
sys := {22 + x + y = 40, 78 + 5*y + z = 151, x + z = y}: |
||
solve(sys, {x,y,z}); |
solve(sys, {x,y,z}); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre> |
{{out}}<pre> |
||
{x = 5, y = 13, z = 8} |
{x = 5, y = 13, z = 8} |
||
</pre> |
</pre> |
||
=={{header|Mathematica}}== |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
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: |
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: |
||
< |
<syntaxhighlight lang="mathematica">b+c==a |
||
d+e==b |
d+e==b |
||
e+f==c |
e+f==c |
||
Line 1,630: | Line 1,896: | ||
n+Y==i |
n+Y==i |
||
n+Z==j |
n+Z==j |
||
X+Z==Y</ |
X+Z==Y</syntaxhighlight> |
||
And we have the knowns |
And we have the knowns |
||
< |
<syntaxhighlight lang="mathematica">a->151 |
||
d->40 |
d->40 |
||
l->11 |
l->11 |
||
n->4</ |
n->4</syntaxhighlight> |
||
Giving us 10 equations with 10 unknowns; i.e. solvable. So we can do so by: |
Giving us 10 equations with 10 unknowns; i.e. solvable. So we can do so by: |
||
< |
<syntaxhighlight lang="mathematica">eqs={a==b+c,d+e==b,e+f==c,g+h==d,h+i==e,i+j==f,l+X==g,l+Y==h,n+Y==i,n+Z==j,Y==X+Z}; |
||
knowns={a->151,d->40,l->11,n->4}; |
knowns={a->151,d->40,l->11,n->4}; |
||
Solve[eqs/.knowns,{b,c,e,f,g,h,i,j,X,Y,Z}]</ |
Solve[eqs/.knowns,{b,c,e,f,g,h,i,j,X,Y,Z}]</syntaxhighlight> |
||
gives back: |
gives back: |
||
< |
<syntaxhighlight lang="mathematica">{{b -> 81, c -> 70, e -> 41, f -> 29, g -> 16, h -> 24, i -> 17, j -> 12, X -> 5, Y -> 13, Z -> 8}}</syntaxhighlight> |
||
In pyramid form that would be: |
In pyramid form that would be: |
||
< |
<syntaxhighlight lang="mathematica"> 151 |
||
81 70 |
81 70 |
||
40 41 29 |
40 41 29 |
||
16 24 17 12 |
16 24 17 12 |
||
5 11 13 4 8</ |
5 11 13 4 8</syntaxhighlight> |
||
An alternative solution in Mathematica 10, constructing the triangle: |
An alternative solution in Mathematica 10, constructing the triangle: |
||
< |
<syntaxhighlight lang="mathematica">triangle[n_, m_] := Nest[MovingMap[Total, #, 1] &, {x, 11, y, 4, z}, n - 1][[m]] |
||
Solve[{triangle[3, 1] == 40, triangle[5, 1] == 151, y == x + z}, {x, y, z}]</ |
Solve[{triangle[3, 1] == 40, triangle[5, 1] == 151, y == x + z}, {x, y, z}]</syntaxhighlight> |
||
Three equations and three unknowns, which gives back: |
Three equations and three unknowns, which gives back: |
||
< |
<syntaxhighlight lang="mathematica">{{x -> 5, y -> 13, z -> 8}}</syntaxhighlight> |
||
=={{header|MiniZinc}}== |
|||
<syntaxhighlight lang="minizinc"> |
|||
%Pascal's Triangle Puzzle. Nigel Galloway, February 17th., 2020 |
|||
int: N11=151; constraint N11=N21+N22; |
|||
var 1..N11: N21=N31+N32; |
|||
var 1..N11: N22=N32+N33; |
|||
int: N31=40; constraint N31=N41+N42; |
|||
var 1..N11: N32=N42+N43; |
|||
var 1..N11: N33=N43+N44; |
|||
var 1..N11: N41=X+11; |
|||
var 1..N11: N42=Y+11; |
|||
var 1..N11: N43=Y+4; |
|||
var 1..N11: N44=Z+4; |
|||
var 1..N11: X; |
|||
var 1..N11: Y=X+Z; |
|||
var 1..N11: Z; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Z = 8; |
|||
X = 5; |
|||
---------- |
|||
</pre> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Ada}} |
|||
Translation of Ada solution: |
|||
<lang |
<syntaxhighlight lang="nim">import strutils |
||
var B_X, B_Y, B_Z : int = 0 |
|||
type |
|||
Block_Value = object |
|||
Known : int |
|||
X, Y, Z : int |
|||
type |
|||
let |
|||
X: Block_Value = Block_Value(Known:0, X:1, Y:0, Z:0) |
|||
Y: Block_Value = Block_Value(Known:0, X:0, Y:1, Z:0) |
|||
Z: Block_Value = Block_Value(Known:0, X:0, Y:0, Z:1) |
|||
proc Add (L : var Block_Value, R : Block_Value) = |
|||
# 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 |
|||
BlockValue = object |
|||
proc Add (L: var Block_Value, R: int) = |
|||
known: int |
|||
# Symbolically adds a value to the block |
|||
x, y, z: int |
|||
proc Image (N : Block_Value): string = |
|||
# The block value, when X,Y,Z are known |
|||
result = $(N.Known + N.X * B_X + N.Y * B_Y + N.Z * B_Z) |
|||
proc Solve_2x2 (A11: int, A12:int, B1:int, A21:int, A22:int, B2: int) = |
|||
# Don't care about things, supposing an integer solution exists |
|||
if A22 == 0: |
|||
B_X = toInt(B2 / A21) |
|||
B_Y = toInt((B1 - (A11*B_X)) / A12) |
|||
else: |
|||
B_X = toInt((B1*A22 - B2*A12) / (A11*A22 - A21*A12)) |
|||
B_Y = toInt((B1 - A11*B_X) / A12) |
|||
B_Z = B_Y - B_X |
|||
var B : array [1..5, array[1..5, Block_Value]] # The lower triangle contains blocks |
|||
Variables = tuple[x, y, z: int] |
|||
# The bottom blocks |
|||
Add(B[5][1],X) |
|||
func `+=`(left: var BlockValue; right: BlockValue) = |
|||
Add(B[5][2],11) |
|||
## Symbolically add one block to another. |
|||
Add(B[5][3],Y) |
|||
left.known += right.known |
|||
Add(B[5][4],4) |
|||
left.x += right.x - right.z # Z is excluded as n(Y - X - Z) = 0. |
|||
Add(B[5][5],Z) |
|||
left.y += right.y + right.z |
|||
# Upward run |
|||
proc toString(n: BlockValue; vars: Variables): string = |
|||
for Row in countdown(4,1): |
|||
## Return the representation of the block value, when X, Y, Z are known. |
|||
for Column in 1 .. Row: |
|||
result = $(n.known + n.x * vars.x + n.y * vars.y + n.z * vars.z) |
|||
Add (B[Row][Column], B[Row + 1][Column]) |
|||
Add (B[Row][Column], B[Row + 1][Column + 1]) |
|||
proc Solve2x2(a11, a12, b1, a21, a22, b2: int): Variables = |
|||
## Solve a puzzle, supposing an integer solution exists. |
|||
# Now have known blocks 40=[3][1], 151=[1][1] and Y=X+Z to determine X,Y,Z |
|||
if a22 == 0: |
|||
Solve_2x2( B[1][1].X, |
|||
result.x = b2 div a21 |
|||
result.y = (b1 - a11 * result.x) div a12 |
|||
151 - B[1][1].Known, |
|||
else: |
|||
B[3][1].X, |
|||
result.x = (b1 * a22 - b2 * a12) div (a11 * a22 - a21 * a12) |
|||
result.y = (b1 - a11 * result.x) div a12 |
|||
result.z = result.y - result.x |
|||
#Print the results |
|||
var blocks : array[1..5, array[1..5, BlockValue]] # The lower triangle contains blocks. |
|||
for Row in 1..5: |
|||
writeln(stdout,"") |
|||
# The bottom blocks. |
|||
for Column in 1..Row: |
|||
blocks[5][1] = BlockValue(x: 1) |
|||
write(stdout, Image(B[Row][Column]), " ")</lang> |
|||
blocks[5][2] = BlockValue(known: 11) |
|||
blocks[5][3] = BlockValue(y: 1) |
|||
blocks[5][4] = BlockValue(known: 4) |
|||
blocks[5][5] = BlockValue(z: 1) |
|||
# Upward run. |
|||
for row in countdown(4, 1): |
|||
for column in 1..row: |
|||
blocks[row][column] += blocks[row + 1][column] |
|||
blocks[row][column] += blocks[row + 1][column + 1] |
|||
# Now have known blocks 40=[3][1], 151=[1][1] and Y=X+Z to determine X,Y,Z. |
|||
let vars = Solve2x2(blocks[1][1].x, |
|||
blocks[1][1].y, |
|||
151 - blocks[1][1].known, |
|||
blocks[3][1].x, |
|||
blocks[3][1].y, |
|||
40 - blocks[3][1].known) |
|||
# Print the results. |
|||
for row in 1..5: |
|||
var line = "" |
|||
for column in 1..row: |
|||
line.addSep(" ") |
|||
line.add toString(blocks[row][column], vars) |
|||
echo line</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre>151 |
<pre>151 |
||
81 70 |
81 70 |
||
40 41 29 |
40 41 29 |
||
16 24 17 12 |
16 24 17 12 |
||
5 11 13 4 8</pre> |
5 11 13 4 8</pre> |
||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
< |
<syntaxhighlight lang="oz">%% to compile : ozc -x <file.oz> |
||
functor |
functor |
||
Line 1,799: | Line 2,083: | ||
{Application.exit 0} |
{Application.exit 0} |
||
end</ |
end</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
[ 6y+x+z+4a[2]+4a[4]= 7y +4a[2]+4a[4]] |
[ 6y+x+z+4a[2]+4a[4]= 7y +4a[2]+4a[4]] |
||
Line 1,808: | Line 2,093: | ||
this helped me... |
this helped me... |
||
< |
<syntaxhighlight lang="parigp"> |
||
Pascals_triangle_puzzle(topvalue=151,leftsidevalue=40,bottomvalue1=11,bottomvalue2=4) = { |
Pascals_triangle_puzzle(topvalue=151,leftsidevalue=40,bottomvalue1=11,bottomvalue2=4) = { |
||
y=(topvalue-(4*(bottomvalue1+bottomvalue2)))/7; |
y=(topvalue-(4*(bottomvalue1+bottomvalue2)))/7; |
||
Line 1,814: | Line 2,099: | ||
z=y-x; |
z=y-x; |
||
print(x","y","z); } |
print(x","y","z); } |
||
</syntaxhighlight> |
|||
</lang> |
|||
I'm thinking of one to solve all puzzles regardless of size and positions. but the objective was to solve this puzzle. |
I'm thinking of one to solve all puzzles regardless of size and positions. but the objective was to solve this puzzle. |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl"># set up triangle |
||
my $rows = 5; |
my $rows = 5; |
||
my @tri = map { [ map { {x=>0,z=>0,v=>0,rhs=>undef} } 1..$_ ] } 1..$rows; |
my @tri = map { [ map { {x=>0,z=>0,v=>0,rhs=>undef} } 1..$_ ] } 1..$rows; |
||
Line 1,858: | Line 2,144: | ||
my $y = $x+$z; |
my $y = $x+$z; |
||
printf "x=%d, y=%d, z=%d\n", $x, $y, $z; |
printf "x=%d, y=%d, z=%d\n", $x, $y, $z; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Equations: |
<pre>Equations: |
||
Line 1,867: | Line 2,153: | ||
x=5, y=13, z=8 |
x=5, y=13, z=8 |
||
</pre> |
</pre> |
||
=={{header|Perl 6}}== |
|||
{{trans|Perl}} |
|||
<lang perl6># set up triangle |
|||
my $rows = 5; |
|||
my @tri = (1..$rows).map: { [ { x => 0, z => 0, v => 0, rhs => Nil } xx $_ ] } |
|||
@tri[0][0]<rhs> = 151; |
|||
@tri[2][0]<rhs> = 40; |
|||
@tri[4][0]<x> = 1; |
|||
@tri[4][1]<v> = 11; |
|||
@tri[4][2]<x> = 1; |
|||
@tri[4][2]<z> = 1; |
|||
@tri[4][3]<v> = 4; |
|||
@tri[4][4]<z> = 1; |
|||
# aggregate from bottom to top |
|||
for @tri - 2 ... 0 -> $row { |
|||
for 0 ..^ @tri[$row] -> $col { |
|||
@tri[$row][$col]{$_} = @tri[$row+1][$col]{$_} + @tri[$row+1][$col+1]{$_} for 'x','z','v'; |
|||
} |
|||
} |
|||
# find equations |
|||
my @eqn = gather for @tri -> $row { |
|||
for @$row -> $cell { |
|||
take [ $cell<x>, $cell<z>, $cell<rhs> - $cell<v> ] if defined $cell<rhs>; |
|||
} |
|||
} |
|||
# print equations |
|||
say "Equations:"; |
|||
say " x + z = y"; |
|||
for @eqn -> [$x,$z,$y] { say "$x x + $z z = $y" } |
|||
# solve |
|||
my $f = @eqn[0][1] / @eqn[1][1]; |
|||
@eqn[0][$_] -= $f * @eqn[1][$_] for 0..2; |
|||
$f = @eqn[1][0] / @eqn[0][0]; |
|||
@eqn[1][$_] -= $f * @eqn[0][$_] for 0..2; |
|||
# print solution |
|||
say "Solution:"; |
|||
my $x = @eqn[0][2] / @eqn[0][0]; |
|||
my $z = @eqn[1][2] / @eqn[1][1]; |
|||
my $y = $x + $z; |
|||
say "x=$x, y=$y, z=$z";</lang> |
|||
{{out}} |
|||
<pre>Equations: |
|||
x + z = y |
|||
7 x + 7 z = 91 |
|||
2 x + 1 z = 18 |
|||
Solution: |
|||
x=5, y=13, z=8</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
Converts the pyramid to rules quite nicely, <small><del>however I will concede |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
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></small> |
|||
-- ======================================= |
|||
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,"",""}, |
|||
--</span> |
|||
{"","","",""}, |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
{"x",11,"y",4,"z"}} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pyramid</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">151</span><span style="color: #0000FF;">},</span> |
|||
sequence rules = {} |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">},</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">},</span> |
|||
-- each cell in the pyramid is either an integer final value or an equation. |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">},</span> |
|||
-- initially the equations are strings, we substitute all with triplets of |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"x"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"y"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"z"</span><span style="color: #0000FF;">}}</span> |
|||
-- the form {k,x,z} ie k+l*x+m*z, and known values < last row become rules. |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rules</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
for r=5 to 1 by -1 do |
|||
for c=1 to length(pyramid[r]) do |
|||
<span style="color: #000080;font-style:italic;">-- 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.</span> |
|||
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 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">5</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
else |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span> |
|||
if prc="" or r<=4 then |
|||
<span style="color: #004080;">object</span> <span style="color: #000000;">prc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">equ</span> |
|||
-- examples: x+11 is {0,1,0}+{11,0,0} -> {11,1,0}, |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">prc</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"x"</span> <span style="color: #008080;">then</span> <span style="color: #000000;">prc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- ie 0 + one x</span> |
|||
-- 11+y is {11,0,0}+{0,1,1} -> {11,1,1}, |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">prc</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"y"</span> <span style="color: #008080;">then</span> <span style="color: #000000;">prc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- ie 0 + one x plus one z</span> |
|||
-- 40=""+"" is {40,0,0}={22,2,1} ==> {18,2,1} |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">prc</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"z"</span> <span style="color: #008080;">then</span> <span style="color: #000000;">prc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- ie 0 + one z</span> |
|||
equ = sq_add(pyramid[r+1][c],pyramid[r+1][c+1]) |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">prc</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span> <span style="color: #008080;">or</span> <span style="color: #000000;">r</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span> |
|||
if prc="" then prc = equ |
|||
<span style="color: #000080;font-style:italic;">-- examples: x+11 is {0,1,0}+{11,0,0} -> {11,1,0}, |
|||
-- 11+y is {11,0,0}+{0,1,1} -> {11,1,1}, |
|||
-- 40=""+"" is {40,0,0}={22,2,1} ==> {18,2,1}</span> |
|||
<span style="color: #000000;">equ</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span><span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
rules = append(rules,equ) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">prc</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span> <span style="color: #008080;">then</span> <span style="color: #000000;">prc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">equ</span> |
|||
end if |
|||
<span style="color: #008080;">else</span> <span style="color: #000000;">prc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">prc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span> |
|||
pyramid[r][c] = prc |
|||
<span style="color: #000000;">equ</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">equ</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #000000;">rules</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rules</span><span style="color: #0000FF;">,</span><span style="color: #000000;">equ</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
ppOpt({pp_Nest,1,pp_StrFmt,1}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
?"equations" |
|||
<span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prc</span> |
|||
pp(pyramid) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
?"rules" |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
pp(rules) |
|||
puts(1,"=====\n") |
|||
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_StrFmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"equations"</span> |
|||
if length(rules)!=2 then ?9/0 end if -- more work needed!? |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pyramid</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"rules"</span> |
|||
-- admittedly this bit is rather amateurish, and maybe problem-specific: |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rules</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- {18,2,1} === 18=2x+z |
|||
-- UPDATE: as above, see that solveN() routine. |
|||
-- {73,5,6} === 73=5x+6z</span> |
|||
sequence xrule = sq_sub(sq_mul(rules[1],rules[2][3]),sq_mul(rules[2],rules[1][3])), |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"=====\n"</span><span style="color: #0000FF;">)</span> |
|||
zrule = sq_sub(sq_mul(rules[2],rules[1][2]),sq_mul(rules[1],rules[2][2])) |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rules</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 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:</span> |
|||
integer x = xrule[1]/xrule[2], |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">solveN</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">rules</span><span style="color: #0000FF;">)</span> |
|||
z = zrule[1]/zrule[3], |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
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 |
|||
-- </span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rj</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rules</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">rii</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rji</span> |
|||
<span style="color: #000000;">rules</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rules</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000080;font-style:italic;">-- successively eliminate (grow lower left triangle of 0s)</span> |
|||
<span style="color: #000000;">ri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">rii</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rii</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (see note below)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">rj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">rji</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rj</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">rji</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">rj</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rj</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rii</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rji</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rj</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (job done)</span> |
|||
<span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rj</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000080;font-style:italic;">-- then substitute each backwards</span> |
|||
<span style="color: #000000;">ri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">rii</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]/</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (all else should be 0)</span> |
|||
<span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rii</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">rj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">rji</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rj</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">rji</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #000000;">rj</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">rji</span><span style="color: #0000FF;">*</span><span style="color: #000000;">rii</span> |
|||
<span style="color: #000000;">rj</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #000000;">rules</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rj</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">rules</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #000080;font-style:italic;">-- Obviously these next two lines directly embody knowledge from the task, and |
|||
-- would need changing for an even slightly different version of the problem:</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solveN</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rules</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">z</span> <span style="color: #000080;font-style:italic;">-- (as per task desc)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"x=%d, y=%d, z=%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #000080;font-style:italic;">-- finally evaluate all the equations and print it.</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pyramid</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">pyramid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">m</span><span style="color: #0000FF;">*</span><span style="color: #000000;">z</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pyramid</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,008: | Line 2,304: | ||
{73,5,6}} |
{73,5,6}} |
||
===== |
===== |
||
x=5, y=13, z=8 |
|||
{"xrule",{35,7,0}} |
|||
{"zrule",{56,0,7}} |
|||
x = 5, y=13, z=8 |
|||
{{151}, |
{{151}, |
||
{81,70}, |
{81,70}, |
||
Line 2,018: | Line 2,312: | ||
</pre> |
</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. |
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(): |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">solveN</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">73</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}})</span> <span style="color: #000080;font-style:italic;">-- -- {5,13,8}</span> |
|||
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #000080;font-style:italic;">-- 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</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">solveN</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">151</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- a+b=151</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- 40+c=a</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- c+d=b</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- g+h=d</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- e+f=40</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- f+g=c</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- x+11=e</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- y+4=g</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- 11+y=f</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- 4+z=h</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- x+z=y |
|||
-- })) -- {81,70,41,29,16,24,17,12,5,13,8}</span> |
|||
<span style="color: #0000FF;">})[-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #000080;font-style:italic;">-- {5,13,8}</span> |
|||
<!--</syntaxhighlight>--> |
|||
And finally, a cheeky little two-liner that does the whole job |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">Y</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">151</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">11</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span><span style="color: #0000FF;">))/</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">X</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">40</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">11</span><span style="color: #0000FF;">-</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Z</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">X</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Two-liner: x=%d, y=%d, z=%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">X</span><span style="color: #0000FF;">,</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">Z</span><span style="color: #0000FF;">})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
Two-liner: x=5, y=13, z=8 |
|||
</pre> |
|||
=={{header|Picat}}== |
|||
Below are three different approaches using constraint modelling (cp solver). |
|||
===Using lists to represent the triangle=== |
|||
{{trans|Prolog}} |
|||
<syntaxhighlight lang="picat">import cp. |
|||
go => |
|||
puzzle(T, X, Y,Z), |
|||
foreach(TT in T) |
|||
println(TT) |
|||
end, |
|||
println([x=X,y=Y,z=Z]), |
|||
nl, |
|||
fail, % are there any more solutions? |
|||
nl. |
|||
% Port of the Prolog solution |
|||
puzzle(Ts, X, Y, Z) :- |
|||
Ts = [ [151], |
|||
[_, _], |
|||
[40, _, _], |
|||
[_, _, _, _], |
|||
[X, 11, Y, 4, Z]], |
|||
Y #= X + Z, |
|||
triangle(Ts), |
|||
Vs = vars(Ts), |
|||
Vs :: 0..10000, |
|||
solve(Vs). |
|||
triangle([T|Ts]) :- |
|||
( Ts = [N|_] -> triangle_(T, N), triangle(Ts) ; true ). |
|||
triangle_([], _). |
|||
triangle_([T|Ts],[A,B|Rest]) :- |
|||
T #= A + B, triangle_(Ts, [B|Rest]).</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[151] |
|||
[81,70] |
|||
[40,41,29] |
|||
[16,24,17,12] |
|||
[5,11,13,4,8] |
|||
[x = 5,y = 13,z = 8]</pre> |
|||
===Calculating the positions=== |
|||
Here is a constraint model which calculates the positions in the triangle that should be added together. |
|||
<syntaxhighlight lang="picat">import cp. |
|||
puzzle2 => |
|||
N = 5, % number of rows |
|||
Len = (N*(N+1)) div 2, % number of entries |
|||
% The triangle numbers for 1..N |
|||
T = [I*(I+1) div 2 : I in 1..N], |
|||
% The index of first number to use in addition |
|||
% create the indices of the numbers to add, |
|||
% i.e. Adds[I] + Adds[I+1] |
|||
Adds = new_list(T[N-1]), |
|||
Adds[1] := 2, |
|||
foreach(I in 2..T[N-1]) |
|||
% "jump" of 2 when i-1 is a triangle number |
|||
if membchk(I-1,T) then |
|||
Adds[I] := Adds[I-1] + 2 |
|||
else |
|||
Adds[I] := Adds[I-1] + 1 |
|||
end |
|||
end, |
|||
% the pyramid |
|||
MaxVal = 10_000, |
|||
L = new_list(Len), |
|||
L :: 1..MaxVal, |
|||
% The clues. |
|||
L = [ 151, |
|||
_, _, |
|||
40, _, _, |
|||
_, _,_ , _ , |
|||
X, 11, Y, 4, Z |
|||
], |
|||
% The sums |
|||
foreach(I in 1..T[N-1]) |
|||
L[I] #= L[Adds[I]]+L[Adds[I]+1] |
|||
end, |
|||
% The extra constraint |
|||
Y #= X + Z, |
|||
solve(L), |
|||
println([x=X,y=Y,z=Z]), |
|||
fail, % check if there is another solution |
|||
nl.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[x = 5,y = 13,z = 8]</pre> |
|||
===Hard coded constraints=== |
|||
<syntaxhighlight lang="picat">import cp. |
|||
puzzle3 => |
|||
% 1 |
|||
% 2 3 |
|||
% 4 5 6 |
|||
% 7 8 9 10 |
|||
%11 12 13 14 15 |
|||
X = new_list(15), |
|||
X :: 0..10_000, |
|||
X[1] #= X[2]+X[3], |
|||
X[2] #= X[4]+X[5], |
|||
X[3] #= X[5]+X[6], |
|||
X[4] #= X[7]+X[8], |
|||
X[5] #= X[8]+X[9], |
|||
X[6] #= X[9]+X[10], |
|||
X[7] #= X[11]+X[12], |
|||
X[8] #= X[12]+X[13], |
|||
X[9] #= X[13]+X[14], |
|||
X[10] #= X[14]+X[15], |
|||
X[13] #= X[11] + X[15], % Y=X+Z, |
|||
% The hints |
|||
X[1] #= 151, |
|||
X[4] #= 40, |
|||
X[12] #= 11, |
|||
X[14] #= 4, |
|||
solve(X), |
|||
println([x=X[11],y=X[13],z=X[15]]), |
|||
fail, |
|||
nl.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[x = 5,y = 13,z = 8]</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(be number (@N @Max) |
||
(^ @C (box 0)) |
(^ @C (box 0)) |
||
(repeat) |
(repeat) |
||
Line 2,063: | Line 2,533: | ||
(+ 4 @Z @H) |
(+ 4 @Z @H) |
||
(+ @X @Z @Y) |
(+ @X @Z @Y) |
||
T )</ |
T )</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>: (? (puzzle @X @Y @Z)) |
<pre>: (? (puzzle @X @Y @Z)) |
||
Line 2,069: | Line 2,539: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
< |
<syntaxhighlight lang="prolog">:- use_module(library(clpfd)). |
||
puzzle(Ts, X, Y, Z) :- |
puzzle(Ts, X, Y, Z) :- |
||
Line 2,087: | Line 2,557: | ||
% X = 5, |
% X = 5, |
||
% Y = 13, |
% Y = 13, |
||
% Z = 8 ;</ |
% Z = 8 ;</syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
Brute force solution. |
Brute force solution. |
||
< |
<syntaxhighlight lang="purebasic">; Known; |
||
; A. |
; A. |
||
; [ 151] |
; [ 151] |
||
Line 2,121: | Line 2,591: | ||
z=SolveForZ(x) |
z=SolveForZ(x) |
||
Until z>=0 |
Until z>=0 |
||
MessageRequester(title$,"X="+Str(x)+#CRLF$+"Y="+Str(x+z)+#CRLF$+"Z="+Str(z))</ |
MessageRequester(title$,"X="+Str(x)+#CRLF$+"Y="+Str(x+z)+#CRLF$+"Z="+Str(z))</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{works with|Python|2.4+}} |
{{works with|Python|2.4+}} |
||
< |
<syntaxhighlight lang="python"># Pyramid solver |
||
# [151] |
# [151] |
||
# [ ] [ ] |
# [ ] [ ] |
||
Line 2,246: | Line 2,716: | ||
p = [ [151], [None,None], [40,None,None], [None,None,None,None], ['X', 11, 'Y', 4, 'Z'] ] |
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 } |
addlConstraint = { 'X':1, 'Y':-1, 'Z':1, '1':0 } |
||
SolvePyramid( p, addlConstraint)</ |
SolvePyramid( p, addlConstraint)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Constraint Equations: |
<pre>Constraint Equations: |
||
Line 2,262: | Line 2,732: | ||
http://www.fantascienza.net/leonardo/so/csp.zip |
http://www.fantascienza.net/leonardo/so/csp.zip |
||
< |
<syntaxhighlight lang="python">from csp import Problem |
||
p = Problem() |
p = Problem() |
||
Line 2,280: | Line 2,750: | ||
p.addrule("Y == X + Z") |
p.addrule("Y == X + Z") |
||
for sol in p.xsolutions(): |
for sol in p.xsolutions(): |
||
print [sol[k] for k in "XYZ"]</ |
print [sol[k] for k in "XYZ"]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 2,291: | Line 2,761: | ||
We'll use a struct (cell v x z) to represent each cell, |
We'll use a struct (cell v x z) to represent each cell, |
||
where the value is (v + x*X + z*Z). |
where the value is (v + x*X + z*Z). |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket/base |
#lang racket/base |
||
(require racket/list) |
(require racket/list) |
||
Line 2,306: | Line 2,776: | ||
(- (cell-x cx) (cell-x cy)) |
(- (cell-x cx) (cell-x cy)) |
||
(- (cell-z cx) (cell-z cy)))) |
(- (cell-z cx) (cell-z cy)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
We first work bottom up and determine the value of each cell, starting from the bottom row. |
We first work bottom up and determine the value of each cell, starting from the bottom row. |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
(define (row-above row) (map cell-add (drop row 1) (drop-right row 1))) |
(define (row-above row) (map cell-add (drop row 1) (drop-right row 1))) |
||
Line 2,317: | Line 2,787: | ||
(define row3 (row-above row2)) |
(define row3 (row-above row2)) |
||
(define row4 (row-above row3)) |
(define row4 (row-above row3)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
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. |
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. |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
(define eqn40 (cell-sub (car row4) (cell 151 0 0))) |
(define eqn40 (cell-sub (car row4) (cell 151 0 0))) |
||
(define eqn20 (cell-sub (car row2) (cell 40 0 0))) |
(define eqn20 (cell-sub (car row2) (cell 40 0 0))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
To solve the 2 equation system, we will use the Cramer's rule. |
To solve the 2 equation system, we will use the Cramer's rule. |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
(define (det2 eqnx eqny get-one get-oth) |
(define (det2 eqnx eqny get-one get-oth) |
||
(- (* (get-one eqnx) (get-oth eqny)) (* (get-one eqny) (get-oth eqnx)))) |
(- (* (get-one eqnx) (get-oth eqny)) (* (get-one eqny) (get-oth eqnx)))) |
||
Line 2,334: | Line 2,804: | ||
(/ (det2 eqnx eqny get-val get-oth) |
(/ (det2 eqnx eqny get-val get-oth) |
||
(det2 eqnx eqny get-unk get-oth))) |
(det2 eqnx eqny get-unk get-oth))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
To get the correct values of X, Y and Z we must change their signs. |
To get the correct values of X, Y and Z we must change their signs. |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
(define x (- (cramer2 eqn20 eqn40 cell-v cell-x cell-z))) |
(define x (- (cramer2 eqn20 eqn40 cell-v cell-x cell-z))) |
||
(define z (- (cramer2 eqn20 eqn40 cell-v cell-z cell-x))) |
(define z (- (cramer2 eqn20 eqn40 cell-v cell-z cell-x))) |
||
Line 2,344: | Line 2,814: | ||
(displayln (list "Y" (+ x z))) |
(displayln (list "Y" (+ x z))) |
||
(displayln (list "Z" z)) |
(displayln (list "Z" z)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
Line 2,352: | Line 2,822: | ||
(Z 8) |
(Z 8) |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{trans|Perl}} |
|||
<syntaxhighlight lang="raku" line># set up triangle |
|||
my $rows = 5; |
|||
my @tri = (1..$rows).map: { [ { x => 0, z => 0, v => 0, rhs => Nil } xx $_ ] } |
|||
@tri[0][0]<rhs> = 151; |
|||
@tri[2][0]<rhs> = 40; |
|||
@tri[4][0]<x> = 1; |
|||
@tri[4][1]<v> = 11; |
|||
@tri[4][2]<x> = 1; |
|||
@tri[4][2]<z> = 1; |
|||
@tri[4][3]<v> = 4; |
|||
@tri[4][4]<z> = 1; |
|||
# aggregate from bottom to top |
|||
for @tri - 2 ... 0 -> $row { |
|||
for 0 ..^ @tri[$row] -> $col { |
|||
@tri[$row][$col]{$_} = @tri[$row+1][$col]{$_} + @tri[$row+1][$col+1]{$_} for 'x','z','v'; |
|||
} |
|||
} |
|||
# find equations |
|||
my @eqn = gather for @tri -> $row { |
|||
for @$row -> $cell { |
|||
take [ $cell<x>, $cell<z>, $cell<rhs> - $cell<v> ] if defined $cell<rhs>; |
|||
} |
|||
} |
|||
# print equations |
|||
say "Equations:"; |
|||
say " x + z = y"; |
|||
for @eqn -> [$x,$z,$y] { say "$x x + $z z = $y" } |
|||
# solve |
|||
my $f = @eqn[0][1] / @eqn[1][1]; |
|||
@eqn[0][$_] -= $f * @eqn[1][$_] for 0..2; |
|||
$f = @eqn[1][0] / @eqn[0][0]; |
|||
@eqn[1][$_] -= $f * @eqn[0][$_] for 0..2; |
|||
# print solution |
|||
say "Solution:"; |
|||
my $x = @eqn[0][2] / @eqn[0][0]; |
|||
my $z = @eqn[1][2] / @eqn[1][1]; |
|||
my $y = $x + $z; |
|||
say "x=$x, y=$y, z=$z";</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Equations: |
|||
x + z = y |
|||
7 x + 7 z = 91 |
|||
2 x + 1 z = 18 |
|||
Solution: |
|||
x=5, y=13, z=8</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
This REXX version also displays a diagram of the puzzle. |
This REXX version also displays a diagram of the puzzle. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program solves a (Pascal's) "Pyramid of Numbers" puzzle given four values. */ |
||
/* ╔══════════════════════════════════════════════════╗ |
/* ╔══════════════════════════════════════════════════╗ |
||
║ answer ║ |
║ answer ║ |
||
Line 2,386: | Line 2,910: | ||
end /*z*/ |
end /*z*/ |
||
end /*y*/ |
end /*y*/ |
||
end /*x*/ /*stick a fork in it, we're all done. */</ |
end /*x*/ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 2,408: | Line 2,932: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
uses [[Reduced row echelon form#Ruby]] |
uses [[Reduced row echelon form#Ruby]] |
||
< |
<syntaxhighlight lang="ruby">require 'rref' |
||
pyramid = [ |
pyramid = [ |
||
Line 2,469: | Line 2,993: | ||
end |
end |
||
puts |
puts |
||
answer.each{|row| p row}</ |
answer.each{|row| p row}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,491: | Line 3,015: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">object PascalTriangle extends App { |
||
val (x, y, z) = pascal(11, 4, 40, 151) |
val (x, y, z) = pascal(11, 4, 40, 151) |
||
Line 2,502: | Line 3,026: | ||
println(if (x != 0) s"Solution is: x = $x, y = $y, z = $z" else "There is no solution.") |
println(if (x != 0) s"Solution is: x = $x, y = $y, z = $z" else "There is no solution.") |
||
}</ |
}</syntaxhighlight> |
||
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/UJF14fw/0 (JavaScript)] |
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/UJF14fw/0 (JavaScript)] |
||
or by [https://scastie.scala-lang.org/l0AlwpSdR7i801Fq8CWHEQ Scastie (JVM)]. |
or by [https://scastie.scala-lang.org/l0AlwpSdR7i801Fq8CWHEQ Scastie (JVM)]. |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans| |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby"># set up triangle |
||
var rows = 5 |
var rows = 5 |
||
var tri = rows.of {|i| (i+1).of { Hash(x => 0, z => 0, v => 0, rhs => nil) } } |
var tri = rows.of {|i| (i+1).of { Hash(x => 0, z => 0, v => 0, rhs => nil) } } |
||
Line 2,553: | Line 3,078: | ||
var z = (eqn[1][2] / eqn[1][1]) |
var z = (eqn[1][2] / eqn[1][1]) |
||
var y = (x + z) |
var y = (x + z) |
||
say "x=#{x}, y=#{y}, z=#{z}"</ |
say "x=#{x}, y=#{y}, z=#{z}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,566: | Line 3,091: | ||
=={{header|SystemVerilog}}== |
=={{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... |
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... |
||
< |
<syntaxhighlight lang="systemverilog">program main; |
||
class Triangle; |
class Triangle; |
||
Line 2,603: | Line 3,128: | ||
Triangle answer = new; |
Triangle answer = new; |
||
endprogram</ |
endprogram</syntaxhighlight> |
||
<pre> [151] |
<pre> [151] |
||
[81][70] |
[81][70] |
||
Line 2,613: | Line 3,138: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
using code from [[Reduced row echelon form#Tcl]] |
using code from [[Reduced row echelon form#Tcl]] |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
namespace path ::tcl::mathop |
namespace path ::tcl::mathop |
||
Line 2,680: | Line 3,205: | ||
lappend solved $newrow |
lappend solved $newrow |
||
} |
} |
||
print_matrix $solved</ |
print_matrix $solved</syntaxhighlight> |
||
<pre>x=5.0 |
<pre>x=5.0 |
||
y=13.0 |
y=13.0 |
||
Line 2,689: | Line 3,214: | ||
16.0 24.0 17.0 12.0 |
16.0 24.0 17.0 12.0 |
||
5.0 11.0 13.0 4.0 8.0</pre> |
5.0 11.0 13.0 4.0 8.0</pre> |
||
=={{header|Wren}}== |
|||
{{trans|Kotlin}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
var isIntegral = Fn.new { |x, tol| x.fraction.abs <= tol } |
|||
var pascal = Fn.new { |a, b, mid, top| |
|||
var yd = (top - 4 * (a + b)) / 7 |
|||
if (!isIntegral.call(yd, 0.0001)) return [0, 0, 0] |
|||
var y = yd.truncate |
|||
var x = mid - 2*a - y |
|||
return [x, y, y - x] |
|||
} |
|||
var sol = pascal.call(11, 4, 40, 151) |
|||
if (sol[0] != 0) { |
|||
Fmt.print("Solution is: x = $d, y = $d, z = $d", sol[0], sol[1], sol[2]) |
|||
} else { |
|||
System.print("There is no solution") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Solution is: x = 5, y = 13, z = 8 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang="xpl0">proc Print; int N, A, B, C, D, E; |
|||
int I, P; |
|||
def Tab = $09; |
|||
[P:= @A; \point to first number |
|||
for I:= N to 5-1 do ChOut(0, Tab); |
|||
for I:= 0 to N-1 do |
|||
[IntOut(0, P(I)); ChOut(0, Tab); ChOut(0, Tab)]; |
|||
CrLf(0); |
|||
]; |
|||
int N, P, Q, R, S, T, U, V, W, X, Y, Z; \ 151 |
|||
[for X:= 0 to 40-11 do \ N P |
|||
for Z:= 0 to 151-4 do \ Q R S |
|||
[Y:= X+Z; \ T U V W |
|||
T:= X+11; \X 11 Y 4 Z |
|||
U:= 11+Y; |
|||
V:= Y+4; |
|||
W:= 4+Z; |
|||
if T+U = 40 then |
|||
[R:= U+V; |
|||
S:= V+W; |
|||
N:= 40+R; |
|||
P:= R+S; |
|||
if N+P = 151 then |
|||
[Print(1, 151); |
|||
Print(2, N, P); |
|||
Print(3, 40, R, S); |
|||
Print(4, T, U, V, W); |
|||
Print(5, X, 11, Y, 4, Z); |
|||
exit; |
|||
]; |
|||
]; |
|||
]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
151 |
|||
81 70 |
|||
40 41 29 |
|||
16 24 17 12 |
|||
5 11 13 4 8 |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="zkl"># Pyramid solver |
||
# [151] |
# [151] |
||
# [ ] [ ] |
# [ ] [ ] |
||
Line 2,703: | Line 3,300: | ||
L("X", 11, "Y", 4, "Z") ); |
L("X", 11, "Y", 4, "Z") ); |
||
addlConstraint:=Dictionary( "X",1, "Y",-1, "Z",1, "1",0 ); |
addlConstraint:=Dictionary( "X",1, "Y",-1, "Z",1, "1",0 ); |
||
solvePyramid(p, addlConstraint);</ |
solvePyramid(p, addlConstraint);</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">fcn solvePyramid([List]vl,[Dictionary]cnstr){ //ListOfLists,Hash-->zip |
||
vl=vl.reverse(); |
vl=vl.reverse(); |
||
constraints:=L(cnstr); |
constraints:=L(cnstr); |
||
Line 2,786: | Line 3,383: | ||
} |
} |
||
return(mtx); |
return(mtx); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 11:10, 24 January 2024
You are encouraged to solve this task according to the task description, using any language you may know.
This puzzle involves a Pascals Triangle, also known as a Pyramid of Numbers.
[ 151] [ ][ ] [40][ ][ ] [ ][ ][ ][ ] [ X][11][ Y][ 4][ Z]
Each brick of the pyramid is the sum of the two bricks situated below it.
Of the three missing numbers at the base of the pyramid,
the middle one is the sum of the other two (that is, Y = X + Z).
- Task
Write a program to find a solution to this puzzle.
11l
F e(&x, row, col) -> &
R x[row * (row + 1) I/ 2 + col]
F iterate(&v, &diff, do_print = 1B)
V tot = 0.0
L
e(&v, 0, 0) = 151
e(&v, 2, 0) = 40
e(&v, 4, 1) = 11
e(&v, 4, 3) = 4
L(i) 1..4
L(j) 0..i
e(&diff, i, j) = 0
I j < i
e(&diff, i, j) += e(&v, i - 1, j) - e(&v, i, j + 1) - e(&v, i, j)
I j != 0
e(&diff, i, j) += e(&v, i - 1, j - 1) - e(&v, i, j - 1) - e(&v, i, j)
L(i) 1..3
L(j) 0.<i
e(&diff, i, j) += e(&v, i + 1, j) + e(&v, i + 1, j + 1) - e(&v, i, j)
e(&diff, 4, 2) += e(&v, 4, 0) + e(&v, 4, 4) - e(&v, 4, 2)
L(i) 0 .< v.len
v[i] += diff[i] / 4
tot = sum(diff.map(a -> a * a))
I do_print
print(‘dev: ’tot)
I tot < 0.1
L.break
V v = [0.0] * 15
V diff = [0.0] * 15
iterate(&v, &diff)
V idx = 0
L(i) 5
L(j) 0..i
print(‘#4’.format(Int(0.5 + v[idx])), end' I j < i {‘ ’} E "\n")
idx++
- Output:
dev: 73410 dev: 17968.6875 dev: 6388.46484375 dev: 2883.337402344 dev: 1446.593643188 ... dev: 0.136503592 dev: 0.125866452 dev: 0.116055273 dev: 0.107006115 dev: 0.098659977 151 81 70 40 41 29 16 24 17 12 5 11 13 4 8
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.
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;
- Output:
151 81 70 40 41 29 16 24 17 12 5 11 13 4 8
ALGOL 68
MODE
FIELD = REAL,
VEC = [0]REAL,
MAT = [0,0]REAL;
MODE BRICK = UNION(INT, CHAR);
FLEX[][]BRICK puzzle = (
( 151),
( " ", " "),
( 40, " ", " "),
( " ", " ", " ", " "),
( "x", 11, "y", 4, "z")
);
PROC mat col = (INT row, col)INT: row*(row-1)OVER 2 + col;
INT col x = mat col(5,1),
col y = mat col(5,3),
col z = mat col(5,5);
OP INIT = (REF VEC vec)VOID: FOR elem FROM LWB vec TO UPB vec DO vec[elem]:=0 OD;
OP INIT = (REF MAT mat)VOID: FOR row FROM LWB mat TO UPB mat DO INIT mat[row,] OD;
OP / = (MAT a, MAT b)MAT:( # matrix division #
[LWB b:UPB b]INT p ;
INT sign;
[,]FIELD lu = lu decomp(b, p, sign);
[LWB a:UPB a, 1 LWB a:2 UPB a]FIELD out;
FOR col FROM 2 LWB a TO 2 UPB a DO out[,col] := lu solve(b, lu, p, a[,col]) OD;
out
);
OP / = (VEC a, MAT b)VEC: ( # vector division #
[LWB a:UPB a,1]FIELD transpose a;
transpose a[,1]:=a;
(transpose a/b)[,LWB a]
);
INT upb mat = mat col(UPB puzzle, UPB puzzle);
[upb mat, upb mat] REAL mat; INIT mat;
[upb mat] REAL vec; INIT vec;
INT mat row := LWB mat;
INT known row := UPB mat - UPB puzzle + 1;
# build the simultaneous equation to solve #
FOR row FROM LWB puzzle TO UPB puzzle DO
FOR col FROM LWB puzzle[row] TO UPB puzzle[row] DO
IF row < UPB puzzle THEN
mat[mat row, mat col(row, col)] := 1;
mat[mat row, mat col(row+1, col)] := -1;
mat[mat row, mat col(row+1, col+1)] := -1;
mat row +:= 1
FI;
CASE puzzle[row][col] IN
(INT value):(
mat[known row, mat col(row, col)] := 1;
vec[known row] := value;
known row +:= 1
),
(CHAR variable):SKIP
ESAC
OD
OD;
# finally add x - y + z = 0 #
mat[known row, col x] := 1;
mat[known row, col y] := -1;
mat[known row, col z] := 1;
FORMAT real repr = $g(-5,2)$;
CO # print details of the simultaneous equation being solved #
FORMAT
vec repr = $"("n(2 UPB mat-1)(f(real repr)", ")f(real repr)")"$,
mat repr = $"("n(1 UPB mat-1)(f(vec repr)", "lx)f(vec repr)")"$;
printf(($"Vec: "l$,vec repr, vec, $l$));
printf(($"Mat: "l$,mat repr, mat, $l$));
END CO
# finally actually solve the equation #
VEC solution vec = vec/mat;
# and wrap up by printing the solution #
FLEX[UPB puzzle]FLEX[0]REAL solution;
FOR row FROM LWB puzzle TO UPB puzzle DO
solution[row] := LOC[row]REAL;
FOR col FROM LWB puzzle[row] TO UPB puzzle[row] DO
solution[row][col] := solution vec[mat col(row, col)]
OD;
printf(($n(UPB puzzle-row)(4x)$, $x"("f(real repr)")"$, solution[row], $l$))
OD;
FOR var FROM 1 BY 2 TO 5 DO
printf(($5x$,$g$,puzzle[UPB puzzle][var],"=", real repr, solution[UPB puzzle][var]))
OD
- Output:
(151.0) (81.00) (70.00) (40.00) (41.00) (29.00) (16.00) (24.00) (17.00) (12.00) ( 5.00) (11.00) (13.00) ( 4.00) ( 8.00) x= 5.00 y=13.00 z= 8.00
AutoHotkey
The main part is this:
N1 := 11, N2 := 4, N3 := 40, N4 := 151
Z := (2*N4 - 7*N3 - 8*N2 + 6*N1) / 7
X := (N3 - 2*N1 - Z) / 2
MsgBox,, Pascal's Triangle, %X%`n%Z%
Message box shows:
5.000000 8.000000
The fun part is to create a GUI for entering different values for N1, N2, N3 and N4.
The GUI shows all values in the solved state.
;---------------------------------------------------------------------------
; Pascal's triangle.ahk
; by wolf_II
;---------------------------------------------------------------------------
; http://rosettacode.org/wiki/Pascal's_triangle/Puzzle
;---------------------------------------------------------------------------
;---------------------------------------------------------------------------
AutoExecute: ; auto-execute section of the script
;---------------------------------------------------------------------------
#SingleInstance, Force ; only one instance allowed
#NoEnv ; don't check empty variables
;-----------------------------------------------------------------------
AppName := "Pascal's triangle"
N1 := 11, N2 := 4, N3 := 40, N4 := 151
; monitor MouseMove events
OnMessage(0x0200, "WM_MOUSEMOVE")
; GUI
Gosub, GuiCreate
Gui, Show,, %AppName%
Return
;---------------------------------------------------------------------------
GuiCreate: ; create the GUI
;---------------------------------------------------------------------------
Gui, -MinimizeBox
Gui, Margin, 8, 8
; 15 edit controls
Loop, 5
Loop, % Row := A_Index {
xx := 208 + (A_Index - 5) * 50 - (Row - 5) * 25
yy := 8 + (Row - 1) * 22
vv := Row "_" A_Index
Gui, Add, Edit, x%xx% y%yy% w50 v%vv% Center ReadOnly -TabStop
}
GuiControl, -WantReturn, Edit11
GuiControl, -WantReturn, Edit15
; buttons (2 hidden)
Gui, Add, Button, x8 w78, &Restart
Gui, Add, Button, x+8 wp, &Solve
Gui, Add, Button, x+8 wp, &Check
Gui, Add, Button, x8 wp, Cle&ar
Gui, Add, Button, xp wp Hidden, &Cancel
Gui, Add, Button, x+8 wp, &New
Gui, Add, Button, xp wp Hidden, &Apply
Gui, Add, Button, x+8 wp, E&xit
; status bar
Gui, Add, StatusBar
; blue font
Gui, Font, bold cBlue
GuiControl, Font, Edit11
GuiControl, Font, Edit15
; falling through
;---------------------------------------------------------------------------
ButtonRestart: ; restart retaining the blue clues
;---------------------------------------------------------------------------
Controls(True) ; enable controls
Loop, 15
If A_Index Not In 1,4,11,12,14,15
GuiControl,, Edit%A_Index% ; clear
GuiControl,, Edit1, %N4%
GuiControl,, Edit4, %N3%
GuiControl,, Edit12, %N1%
GuiControl,, Edit14, %N2%
GuiControl,, Edit11, %X%
GuiControl,, Edit15, %Z%
GreenFont:
Gui, Font, bold cGreen
GuiControl, Font, Edit1
GuiControl, Font, Edit4
GuiControl, Font, Edit12
GuiControl, Font, Edit14
Return
;---------------------------------------------------------------------------
ButtonSolve: ; calculate solution
;---------------------------------------------------------------------------
; N1 := 11 N2 := 4 N3 := 40 N4 := 151
;-----------------------------------------------------------------------
; Y = X + Z
; 40 = (11+X) + (11+Y)
; A = (11+Y) + (Y+4)
; B = (4+Y) + (4+Z)
; 151 = (40+A) + (A+B)
;-----------------------------------------------------------------------
Gosub, GreenFont
GuiControl,, Edit15, % Z := Round( (2*N4 - 7*N3 - 8*N2 + 6*N1) / 7 )
GuiControl,, Edit11, % X := Round( (N3 - 2*N1 - Z) / 2 )
; falling through
;---------------------------------------------------------------------------
ButtonCheck: ; check the [entry|solution] for errors
;---------------------------------------------------------------------------
Controls(False) ; disable controls
Gui, Submit, NoHide
X := 5_1, Z := 5_5
Loop, 5
Loop, % Row := A_Index
If (%Row%_%A_Index% = "")
%Row%_%A_Index% := 0
GuiControl,, Edit13, % 5_3 := 5_1 + 5_5
GuiControl,, Edit10, % 4_4 := 5_4 + 5_5
GuiControl,, Edit9, % 4_3 := 5_3 + 5_4
GuiControl,, Edit8, % 4_2 := 5_2 + 5_3
GuiControl,, Edit7, % 4_1 := 5_1 + 5_2
GuiControl,, Edit6, % 3_3 := 4_4 + 4_3
GuiControl,, Edit5, % 3_2 := 4_3 + 4_2
GuiControl,, Edit4, % 3_1 := 4_2 + 4_1
GuiControl,, Edit3, % 2_2 := 3_3 + 3_2
GuiControl,, Edit2, % 2_1 := 3_2 + 3_1
GuiControl,, Edit1, % 1_1 := 2_2 + 2_1
Gui, Font, bold cRed
If Not 3_1 = N3
GuiControl, Font, Edit4
If Not 1_1 = N4
GuiControl, Font, Edit1
Return
;---------------------------------------------------------------------------
ButtonClear: ; restart without the blue clues
;---------------------------------------------------------------------------
X := Z := ""
Gosub, ButtonRestart
Return
;---------------------------------------------------------------------------
ButtonNew: ; enter new numbers for the puzzle
;---------------------------------------------------------------------------
Gosub, GreenFont
Loop, 15
If A_Index Not In 1,4,12,14
GuiControl,, Edit%A_Index% ; clear
Controls(False) ; disable controls
NewContr(True) ; enable controls for new numbers
Return
;---------------------------------------------------------------------------
ButtonApply: ; remember the new numbers
;---------------------------------------------------------------------------
Gui, Submit, NoHide
N1 := 5_2, N2 := 5_4, N3 := 3_1, N4 := 1_1
NewContr(False) ; disable controls for new numbers
Controls(True) ; enable controls
Return
;---------------------------------------------------------------------------
ButtonCancel: ; restore the old numbers
;---------------------------------------------------------------------------
GuiControl,, Edit1, %N4%
GuiControl,, Edit4, %N3%
GuiControl,, Edit12, %N1%
GuiControl,, Edit14, %N2%
NewContr(False) ; disable controls for new numbers
Controls(True) ; enable controls
Return
;---------------------------------------------------------------------------
GuiClose:
;---------------------------------------------------------------------------
GuiEscape:
;---------------------------------------------------------------------------
ButtonExit:
;---------------------------------------------------------------------------
; common action
ExitApp
Return
;---------------------------------------------------------------------------
Controls(Bool) { ; [dis|re-en]able some controls
;---------------------------------------------------------------------------
Enable := Bool ? "+" : "-"
Disable := Bool ? "-" : "+"
GuiControl, %Disable%ReadOnly, Edit11
GuiControl, %Disable%ReadOnly, Edit15
GuiControl, %Enable%TabStop, Edit11
GuiControl, %Enable%TabStop, Edit15
GuiControl, %Disable%Default, &Restart
GuiControl, %Enable%Default, &Check
GuiControl, %Disable%Disabled, &Check
GuiControl, %Enable%Disabled, &Restart
}
;---------------------------------------------------------------------------
NewContr(Bool) { ; [dis|re-en]able control for new numbers
;---------------------------------------------------------------------------
Enable := Bool ? "+" : "-"
Disable := Bool ? "-" : "+"
GuiControl, %Disable%ReadOnly, Edit1
GuiControl, %Disable%ReadOnly, Edit4
GuiControl, %Disable%ReadOnly, Edit12
GuiControl, %Disable%ReadOnly, Edit14
GuiControl, %Enable%TabStop, Edit1
GuiControl, %Enable%TabStop, Edit4
GuiControl, %Enable%TabStop, Edit12
GuiControl, %Enable%TabStop, Edit14
GuiControl, %Enable%Hidden, Button1
GuiControl, %Enable%Hidden, Button2
GuiControl, %Enable%Hidden, Button3
GuiControl, %Enable%Hidden, Button4
GuiControl, %Disable%Hidden, Button5
GuiControl, %Enable%Hidden, Button6
GuiControl, %Disable%Hidden, Button7
GuiControl, %Enable%Hidden, Button8
}
;---------------------------------------------------------------------------
WM_MOUSEMOVE() { ; monitor MouseMove events
;---------------------------------------------------------------------------
; display quick help in StatusBar
;-----------------------------------------------------------------------
global AppName
CurrControl := A_GuiControl
IfEqual True,, MsgBox ; dummy
; mouse is over buttons
Else If (CurrControl = "&Restart")
SB_SetText("restart retaining the blue clues")
Else If (CurrControl = "&Solve")
SB_SetText("calculate solution")
Else If (CurrControl = "&Check")
SB_SetText("check if the entries are correct")
Else If (CurrControl = "Cle&ar")
SB_SetText("restart without the blue clues")
Else If (CurrControl = "&New")
SB_SetText("enter new numbers for the puzzle")
Else If (CurrControl = "E&xit")
SB_SetText("exit " AppName)
; delete status bar text
Else SB_SetText("")
}
BBC BASIC
INSTALL @lib$ + "ARRAYLIB"
REM Describe the puzzle as a set of simultaneous equations:
REM a + b = 151
REM a - c = 40
REM -b + c + d = 0
REM e + f = 40
REM -c + f + g = 0
REM -d + g + h = 0
REM e - x = 11
REM f - y = 11
REM g - y = 4
REM h - z = 4
REM x - y + z = 0
REM So we have 11 equations in 11 unknowns.
REM We can represent these equations as a matrix and a vector:
DIM matrix(10,10), vector(10)
matrix() = \ a, b, c, d, e, f, g, h, x, y, z
\ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, \
\ 1, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0, \
\ 0,-1, 1, 1, 0, 0, 0, 0, 0, 0, 0, \
\ 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, \
\ 0, 0,-1, 0, 0, 1, 1, 0, 0, 0, 0, \
\ 0, 0, 0,-1, 0, 0, 1, 1, 0, 0, 0, \
\ 0, 0, 0, 0, 1, 0, 0, 0,-1, 0, 0, \
\ 0, 0, 0, 0, 0, 1, 0, 0, 0,-1, 0, \
\ 0, 0, 0, 0, 0, 0, 1, 0, 0,-1, 0, \
\ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,-1, \
\ 0, 0, 0, 0, 0, 0, 0, 0, 1,-1, 1
vector() = 151, 40, 0, 40, 0, 0, 11, 11, 4, 4, 0
REM Now solve the simultaneous equations:
PROC_invert(matrix())
vector() = matrix().vector()
PRINT "X = " ; vector(8)
PRINT "Y = " ; vector(9)
PRINT "Z = " ; vector(10)
- Output:
X = 5 Y = 13 Z = 8
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
*
* [top]
* [ ] [ ]
* [mid] [ ] [ ]
* [ ] [ ] [ ] [ ]
* [ x ] [ a ] [ y ] [ b ] [ z ]
* x + z = y
*
* This solution makes use of a little bit of mathematical observation,
* such as the fact that top = 4(a+b) + 7(x+z) and mid = 2x + 2a + z.
*/
#include <stdio.h>
#include <math.h>
void pascal(int a, int b, int mid, int top, int* x, int* y, int* z)
{
double ytemp = (top - 4 * (a + b)) / 7.;
if(fmod(ytemp, 1.) >= 0.0001)
{
x = 0;
return;
}
*y = ytemp;
*x = mid - 2 * a - *y;
*z = *y - *x;
}
int main()
{
int a = 11, b = 4, mid = 40, top = 151;
int x, y, z;
pascal(a, b, mid, top, &x, &y, &z);
if(x != 0)
printf("x: %d, y: %d, z: %d\n", x, y, z);
else printf("No solution\n");
return 0;
}
- Output:
x: 5, y: 13, z: 8
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 <stdio.h>
#include <stdlib.h>
void show(int *x) {
int i, j;
for (i = 0; i < 5; i++)
for (j = 0; j <= i; j++)
printf("%4d%c", *(x++), j < i ? ' ' : '\n');
}
inline int sign(int i)
{
return i < 0 ? -1 : i > 0;
}
int iter(int *v, int *diff) {
int sum, i, j, e = 0;
# define E(x, row, col) x[(row) * ((row) + 1) / 2 + (col)]
/* enforce boundary conditions */
E(v, 0, 0) = 151;
E(v, 2, 0) = 40;
E(v, 4, 1) = 11;
E(v, 4, 3) = 4;
/* calculate difference from equilibrium */
for (i = 1; i < 5; i++) {
for (j = 0; j <= i; j++) {
E(diff, i, j) = 0;
if (j < i)
E(diff, i, j) += E(v, i - 1, j) -
E(v, i, j + 1) -
E(v, i, j);
if (j)
E(diff, i, j) += E(v, i - 1, j - 1) -
E(v, i, j - 1) -
E(v, i, j);
}
}
for (i = 0; i < 4; i++)
for (j = 0; j < i; j++)
E(diff, i, j) += E(v, i + 1, j) +
E(v, i + 1, j + 1) -
E(v, i, j);
E(diff, 4, 2) += E(v, 4, 0) + E(v, 4, 4) - E(v, 4, 2);
# undef E
/* Do feedback, check if we are done. */
for (i = sum = 0; i < 15; i++) {
sum += !!sign(e = diff[i]);
/* 1/5-ish feedback strength on average. These numbers are highly
magical, depending on nodes' connectivities. */
if (e >= 4 || e <= -4) v[i] += e/5;
else if (rand() < RAND_MAX/4) v[i] += sign(e);
}
return sum;
}
int main() {
int v[15] = { 0 }, diff[15] = { 0 }, i, s;
for (i = s = 1; s; i++) {
s = iter(v, diff);
printf("pass %d: %d\n", i, s);
}
show(v);
return 0;
}
- Output:
pass 1: 12pass 2: 12 pass 3: 14 pass 4: 14 ... pass 113: 4 pass 114: 7 pass 115: 0
151 81 70 40 41 29 16 24 17 125 11 13 4 8
C#
using System;
namespace Pyramid_of_Numbers
{
class Program
{
public static void Main(string[] args)
{
// Set console properties
Console.Title = " Pyramid of Numbers / Pascal's triangle Puzzle";
Console.SetBufferSize(80,1000);
Console.SetWindowSize(80,60);
Console.ForegroundColor = ConsoleColor.Green;
// Main Program Loop
ConsoleKeyInfo k = new ConsoleKeyInfo('Y', ConsoleKey.Y,true,true,true);
while (k.Key == ConsoleKey.Y)
{
Console.Clear();
Console.WriteLine("----------------------------------------------");
Console.WriteLine(" Pyramid of Numbers / Pascal's triangle Puzzle");
Console.WriteLine("----------------------------------------------");
Console.WriteLine();
//
// Declare new Pyramid array
//
int r = 5;// Number of rows
int [,] Pyramid = new int[r,r];
// Set initial Pyramid values
for (int i = 0; i < r; i++)
{
for(int j = 0; j < r; j++)
{
Pyramid[i,j] = 0;
}
}
// Show info on created array
Console.WriteLine(" Pyramid has " + r + " rows");
Console.WriteLine("--------------------------------------------");
// Enter Pyramid values
for(int i = 0; i <= r-1; i++)
{
Console.WriteLine(" Enter " + (i+1).ToString() + ". row values:");
Console.WriteLine("--------------------------------------------");
for(int j = 0; j < i+1; j++)
{
Console.Write(" " + (j+1).ToString() + ". value = ");
int v = int.Parse(Console.ReadLine());
Pyramid[i,j] = v;
}
Console.WriteLine("--------------------------------------------");
}
//
// Show initial Pyramid values
//
Console.WriteLine();
Console.WriteLine(" Initial Pyramid Values ");
Console.WriteLine();
// Show Pyramid values
for(int i = 0; i <= r-1; i++)
{
for(int j = 0; j < i+1; j++)
{
Console.Write("{0,4}",Pyramid[i,j]);
}
Console.WriteLine();
}
Console.WriteLine("--------------------------------------------");
// Find solution
Solve_Pyramid(Pyramid);
Console.WriteLine();
Console.Write(" Start new calculation <Y/N> . . . ");
k = Console.ReadKey(true);
}
}
//
// Solve Function
//
public static void Solve_Pyramid(int [,] Pyramid)
{
int r = 5; // Number of rows
// Calculate Y
int a = Pyramid[r-1,1];
int b = Pyramid[r-1,3];
int c = Pyramid[0,0];
int y = (c - (4*a) - (4*b))/7;
Pyramid[r-1,2] = y;
// Create copy of Pyramid
int [,] Pyramid_Copy = new int[r,r];
Array.Copy(Pyramid,Pyramid_Copy,r*r);
int n = 0; // solution counter
for(int x = 0; x < y + 1; x++)
{
for(int z = 0; z < y + 1; z++)
{
if( (x+z) == y)
{
Pyramid[r-1,0] = x;
Pyramid[r-1,r-1] = z;
// Recalculate Pyramid values
for(int i = r-1; i > 0; i--)
{
for(int j = 0; j < i; j++)
{
Pyramid[i-1,j] = Pyramid[i,j]+Pyramid[i,j+1];
}
}
// Compare Pyramid values
bool solved = true;
for(int i = 0; i < r-1; i++)
{
for(int j = 0; j < i+1; j++)
{
if(Pyramid_Copy[i,j]>0)
{
if(Pyramid[i,j] != Pyramid_Copy[i,j])
{
solved = false;
i = r;
break;
}
}
}
}
if(solved)
{
n++;
Console.WriteLine();
Console.WriteLine(" Solved Pyramid Values no." + n);
Console.WriteLine();
// Show Pyramid values
for(int i = 0; i <= r-1; i++)
{
for(int j = 0; j < i+1; j++)
{
Console.Write("{0,4}",Pyramid[i,j]);
}
Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine(" X = " + Pyramid[r-1,0] + " " +
" Y = " + Pyramid[r-1,2] + " " +
" Z = " + Pyramid[r-1,4]);
Console.WriteLine();
Console.WriteLine("--------------------------------------------");
}
Array.Copy(Pyramid_Copy,Pyramid,r*r);
}
}
}
if(n == 0)
{
Console.WriteLine();
Console.WriteLine(" Pyramid has no solution ");
Console.WriteLine();
}
}
}
}
- Program Input and Output:
---------------------------------------------- Pyramid of Numbers / Pascal's triangle Puzzle ---------------------------------------------- Pyramid has 5 rows -------------------------------------------- Enter 1. row values: -------------------------------------------- 1. value = 151 -------------------------------------------- Enter 2. row values: -------------------------------------------- 1. value = 0 2. value = 0 -------------------------------------------- Enter 3. row values: -------------------------------------------- 1. value = 40 2. value = 0 3. value = 0 -------------------------------------------- Enter 4. row values: -------------------------------------------- 1. value = 0 2. value = 0 3. value = 0 4. value = 0 -------------------------------------------- Enter 5. row values: -------------------------------------------- 1. value = 0 2. value = 11 3. value = 0 4. value = 4 5. value = 0 -------------------------------------------- Initial Pyramid Values 151 0 0 40 0 0 0 0 0 0 0 11 0 4 0 -------------------------------------------- Solved Pyramid Values no.1 151 81 70 40 41 29 16 24 17 12 5 11 13 4 8 X = 5 Y = 13 Z = 8 -------------------------------------------- Start new calculation <Y/N> . . .
C++
#include <iostream>
#include <iomanip>
inline int sign(int i) {
return i < 0 ? -1 : i > 0;
}
inline int& E(int *x, int row, int col) {
return x[row * (row + 1) / 2 + col];
}
int iter(int *v, int *diff) {
// enforce boundary conditions
E(v, 0, 0) = 151;
E(v, 2, 0) = 40;
E(v, 4, 1) = 11;
E(v, 4, 3) = 4;
// calculate difference from equilibrium
for (auto i = 1u; i < 5u; i++)
for (auto j = 0u; j <= i; j++) {
E(diff, i, j) = 0;
if (j < i)
E(diff, i, j) += E(v, i - 1, j) - E(v, i, j + 1) - E(v, i, j);
if (j)
E(diff, i, j) += E(v, i - 1, j - 1) - E(v, i, j - 1) - E(v, i, j);
}
for (auto i = 0u; i < 4u; i++)
for (auto j = 0u; j < i; j++)
E(diff, i, j) += E(v, i + 1, j) + E(v, i + 1, j + 1) - E(v, i, j);
E(diff, 4, 2) += E(v, 4, 0) + E(v, 4, 4) - E(v, 4, 2);
// do feedback, check if we are done
uint sum;
int e = 0;
for (auto i = sum = 0u; i < 15u; i++) {
sum += !!sign(e = diff[i]);
// 1/5-ish feedback strength on average. These numbers are highly magical, depending on nodes' connectivities
if (e >= 4 || e <= -4)
v[i] += e / 5;
else if (rand() < RAND_MAX / 4)
v[i] += sign(e);
}
return sum;
}
void show(int *x) {
for (auto i = 0u; i < 5u; i++)
for (auto j = 0u; j <= i; j++)
std::cout << std::setw(4u) << *(x++) << (j < i ? ' ' : '\n');
}
int main() {
int v[15] = { 0 }, diff[15] = { 0 };
for (auto i = 1u, s = 1u; s; i++) {
s = iter(v, diff);
std::cout << "pass " << i << ": " << s << std::endl;
}
show(v);
return 0;
}
Clojure
X and Z are the independent variables, so first work bottom up and determine the value of each cell in the form (n0 + n1*X + n2*Z). We'll use a vector [n0 n1 n2] to represent each cell.
(def bottom [ [0 1 0], [11 0 0], [0 1 1], [4 0 0], [0 0 1] ])
(defn plus [v1 v2] (vec (map + v1 v2)))
(defn minus [v1 v2] (vec (map - v1 v2)))
(defn scale [n v] (vec (map #(* n %) v )))
(defn above [row] (map #(apply plus %) (partition 2 1 row)))
(def rows (reverse (take 5 (iterate above bottom))))
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 c00 (get-in rows [0 0]))
(def c20 (get-in rows [2 0]))
(def eqn0 (minus c00 [151 0 0]))
(def eqn1 (minus c20 [ 40 0 0]))
In this case, there are only two variables, so solving the system of linear equations is simple.
(defn solve [m]
(assert (<= 1 m 2))
(let [n (- 3 m)
v0 (scale (eqn1 n) eqn0)
v1 (scale (eqn0 n) eqn1)
vd (minus v0 v1)]
(assert (zero? (vd n)))
(/ (- (vd 0)) (vd m))))
(let [x (solve 1), z (solve 2), y (+ x z)]
(println "x =" x ", y =" y ", z =" z))
If you want to solve the whole pyramid, just add a call (show-pyramid x z) to the previous let form:
(defn dot [v1 v2] (reduce + (map * v1 v2)))
(defn show-pyramid [x z]
(doseq [row rows]
(println (map #(dot [1 x z] %) row)))
Craft Basic
let x = -1
do
let x = x + 1
let z = 0
do
let e = x + 11
let f = 11 + (x + z)
let g = (x + z) + 4
let h = 4 + z
if e + f = 40 then
let c = f + g
let d = g + h
let a = 40 + c
let b = c + d
let q = 0
if a + b = 151 then
let q = 1
endif
endif
if q = 0 then
let z = z + 1
endif
wait
loopwhile z < 20 and q = 0
if q = 0 then
let z = -1
endif
wait
loopuntil z >= 0
print "x = ", x
print "y = ", x + z
print "z = ", z
- Output:
x = 5y = 13
z = 8
Curry
import CLPFD
import Constraint (allC, andC)
import Findall (findall)
import List (init, last)
solve :: [[Int]] -> Success
solve body@([n]:rest) =
domain (concat body) 1 n
& andC (zipWith atop body rest)
& labeling [] (concat body)
where
xs `atop` ys = andC $ zipWith3 tri xs (init ys) (tail ys)
tri :: Int -> Int -> Int -> Success
tri x y z = x =# y +# z
test (x,y,z) | tri y x z =
[ [151]
, [ _, _]
, [40, _, _]
, [ _, _, _, _]
, [ x, 11, y, 4, z]
]
main = findall $ solve . test
- Output:
Execution time: 0 msec. / elapsed: 0 msec. [(5,13,8)]
D
import std.stdio, std.algorithm;
void iterate(bool doPrint=true)(double[] v, double[] diff) @safe {
static ref T E(T)(T[] x, in size_t row, in size_t col)
pure nothrow @safe @nogc {
return x[row * (row + 1) / 2 + col];
}
double tot = 0.0;
do {
// Enforce boundary conditions.
E(v, 0, 0) = 151;
E(v, 2, 0) = 40;
E(v, 4, 1) = 11;
E(v, 4, 3) = 4;
// Calculate difference from equilibrium.
foreach (immutable i; 1 .. 5) {
foreach (immutable j; 0 .. i + 1) {
E(diff, i, j) = 0;
if (j < i)
E(diff, i, j) += E(v, i - 1, j) - E(v, i, j + 1) - E(v, i, j);
if (j)
E(diff, i, j) += E(v, i - 1, j - 1) - E(v, i, j - 1) - E(v, i, j);
}
}
foreach (immutable i; 1 .. 4)
foreach (immutable j; 0 .. i)
E(diff, i, j) += E(v, i + 1, j) + E(v, i + 1, j + 1) - E(v, i, j);
E(diff, 4, 2) += E(v, 4, 0) + E(v, 4, 4) - E(v, 4, 2);
// Do feedback, check if we are close enough.
// 4: scale down the feedback to avoid oscillations.
v[] += diff[] / 4;
tot = diff.map!q{ a ^^ 2 }.sum;
static if (doPrint)
writeln("dev: ", tot);
// tot(dx^2) < 0.1 means each cell is no more than 0.5 away
// from equilibrium. It takes about 50 iterations. After
// 700 iterations tot is < 1e-25, but that's overkill.
} while (tot >= 0.1);
}
void main() {
static void show(in double[] x) nothrow @nogc {
int idx;
foreach (immutable i; 0 .. 5)
foreach (immutable j; 0 .. i+1) {
printf("%4d%c", cast(int)(0.5 + x[idx]), j < i ? ' ' : '\n');
idx++;
}
}
double[15] v = 0.0, diff = 0.0;
iterate(v, diff);
show(v);
}
- Output:
dev: 73410 dev: 17968.7 dev: 6388.46 dev: 2883.34 dev: 1446.59 dev: 892.753 dev: 564.678 [... several more iterations...] dev: 0.136504 dev: 0.125866 dev: 0.116055 dev: 0.107006 dev: 0.0986599 151 81 70 40 41 29 16 24 17 12 5 11 13 4 8
F#
In a script, using the Math.NET Numerics library
#load"Packages\MathNet.Numerics.FSharp\MathNet.Numerics.fsx"
open MathNet.Numerics.LinearAlgebra
let A = matrix [
[ 1.; 1.; 0.; 0.; 0.; 0.; 0.; 0.; 0.; 0.; 0. ]
[ -1.; 0.; 1.; 0.; 0.; 0.; 0.; 0.; 0.; 0.; 0. ]
[ 0.; -1.; 1.; 1.; 0.; 0.; 0.; 0.; 0.; 0.; 0. ]
[ 0.; 0.; 0.; 0.; 1.; 1.; 0.; 0.; 0.; 0.; 0. ]
[ 0.; 0.; -1.; 0.; 0.; 1.; 1.; 0.; 0.; 0.; 0. ]
[ 0.; 0.; 0.; -1.; 0.; 0.; 1.; 1.; 0.; 0.; 0. ]
[ 0.; 0.; 0.; 0.; -1.; 0.; 0.; 0.; 1.; 0.; 0. ]
[ 0.; 0.; 0.; 0.; 0.; -1.; 0.; 0.; 0.; 1.; 0. ]
[ 0.; 0.; 0.; 0.; 0.; 0.; -1.; 0.; 0.; 1.; 0. ]
[ 0.; 0.; 0.; 0.; 0.; 0.; 0.; -1.; 0.; 0.; 1. ]
[ 0.; 0.; 0.; 0.; 0.; 0.; 0.; 0.; 1.; -1.; 1. ]
]
let b = vector [151.; -40.; 0.; 40.; 0.; 0.; -11.; -11.; -4.; -4.; 0.]
let x = A.Solve(b)
printfn "x = %f, Y = %f, Z = %f" x.[8] x.[9] x.[10]
- Output:
x = 5.000000, Y = 13.000000, Z = 8.000000
Factor
USING: arrays backtrack combinators.extras fry grouping.extras
interpolate io kernel math math.ranges sequences ;
: base ( ?x ?z -- seq ) 2dup + swap '[ _ 11 _ 4 _ ] >array ;
: up ( seq -- seq' ) [ [ + ] 2clump-map ] twice ;
: find-solution ( -- x z )
10 [1,b] dup [ amb-lazy ] bi@ 2dup base
up dup first 40 = must-be-true
up first 151 = must-be-true ;
find-solution [I X = ${1}, Z = ${}I] nl
- Output:
X = 5, Z = 8
FreeBASIC
Function SolveForZ(x As Integer) As Integer
Dim As Integer a, b, c, d, e, f, g, h, z
For z = 0 To 20
e = x + 11
f = 11 + (x+z)
g = (x+z) + 4
h = 4 + z
If e + f = 40 Then
c = f + g
d = g + h
a = 40 + c
b = c + d
If a + b = 151 Then Return z
End If
Next z
Return -1
End Function
Dim As Integer x = -1, z = 0
Do
x = x + 1
z = SolveForZ(x)
Loop Until z >= 0
Print "X ="; x
Print "Y ="; x + z
Print "Z ="; z
Sleep
- Output:
X = 5 Y = 13 Z = 8
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.
package main
import "fmt"
// representation of an expression in x, y, and z
type expr struct {
x, y, z float64 // coefficients
c float64 // constant term
}
// add two expressions
func addExpr(a, b expr) expr {
return expr{a.x + b.x, a.y + b.y, a.z + b.z, a.c + b.c}
}
// subtract two expressions
func subExpr(a, b expr) expr {
return expr{a.x - b.x, a.y - b.y, a.z - b.z, a.c - b.c}
}
// multiply expression by a constant
func mulExpr(a expr, c float64) expr {
return expr{a.x * c, a.y * c, a.z * c, a.c * c}
}
// given a row of expressions, produce the next row up, by the given
// sum relation between blocks
func addRow(l []expr) []expr {
if len(l) == 0 {
panic("wrong")
}
r := make([]expr, len(l)-1)
for i := range r {
r[i] = addExpr(l[i], l[i+1])
}
return r
}
// given expression b in a variable, and expression a,
// take b == 0 and substitute to remove that variable from a.
func substX(a, b expr) expr {
if b.x == 0 {
panic("wrong")
}
return subExpr(a, mulExpr(b, a.x/b.x))
}
func substY(a, b expr) expr {
if b.y == 0 {
panic("wrong")
}
return subExpr(a, mulExpr(b, a.y/b.y))
}
func substZ(a, b expr) expr {
if b.z == 0 {
panic("wrong")
}
return subExpr(a, mulExpr(b, a.z/b.z))
}
// given an expression in a single variable, return value of that variable
func solveX(a expr) float64 {
if a.x == 0 || a.y != 0 || a.z != 0 {
panic("wrong")
}
return -a.c / a.x
}
func solveY(a expr) float64 {
if a.x != 0 || a.y == 0 || a.z != 0 {
panic("wrong")
}
return -a.c / a.y
}
func solveZ(a expr) float64 {
if a.x != 0 || a.y != 0 || a.z == 0 {
panic("wrong")
}
return -a.c / a.z
}
func main() {
// representation of given information for bottom row
r5 := []expr{{x: 1}, {c: 11}, {y: 1}, {c: 4}, {z: 1}}
fmt.Println("bottom row:", r5)
// given definition of brick sum relation
r4 := addRow(r5)
fmt.Println("next row up:", r4)
r3 := addRow(r4)
fmt.Println("middle row:", r3)
// given relation y = x + z
xyz := subExpr(expr{y: 1}, expr{x: 1, z: 1})
fmt.Println("xyz relation:", xyz)
// remove z from third cell using xyz relation
r3[2] = substZ(r3[2], xyz)
fmt.Println("middle row after substituting for z:", r3)
// given cell = 40,
b := expr{c: 40}
// this gives an xy relation
xy := subExpr(r3[0], b)
fmt.Println("xy relation:", xy)
// substitute 40 for cell
r3[0] = b
// remove x from third cell using xy relation
r3[2] = substX(r3[2], xy)
fmt.Println("middle row after substituting for x:", r3)
// continue applying brick sum relation to get top cell
r2 := addRow(r3)
fmt.Println("next row up:", r2)
r1 := addRow(r2)
fmt.Println("top row:", r1)
// given top cell = 151, we have an equation in y
y := subExpr(r1[0], expr{c: 151})
fmt.Println("y relation:", y)
// using xy relation, we get an equation in x
x := substY(xy, y)
fmt.Println("x relation:", x)
// using xyz relation, we get an equation in z
z := substX(substY(xyz, y), x)
fmt.Println("z relation:", z)
// show final answers
fmt.Println("x =", solveX(x))
fmt.Println("y =", solveY(y))
fmt.Println("z =", solveZ(z))
}
- Output:
bottom row: [{1 0 0 0} {0 0 0 11} {0 1 0 0} {0 0 0 4} {0 0 1 0}] next row up: [{1 0 0 11} {0 1 0 11} {0 1 0 4} {0 0 1 4}] middle row: [{1 1 0 22} {0 2 0 15} {0 1 1 8}] xyz relation: {-1 1 -1 0} middle row after substituting for z: [{1 1 0 22} {0 2 0 15} {-1 2 0 8}] xy relation: {1 1 0 -18} middle row after substituting for x: [{0 0 0 40} {0 2 0 15} {0 3 0 -10}] next row up: [{0 2 0 55} {0 5 0 5}] top row: [{0 7 0 60}] y relation: {0 7 0 -91} x relation: {1 0 0 -5} z relation: {0 0 -1 8} x = 5 y = 13 z = 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.
J
Fixed points in the pyramid are 40 and 151, which I use to check a resulting pyramid for selection:
chk=:40 151&-:@(2 4{{."1)
verb for the base of the pyramid:
base=: [,11,+,4,]
the height of the pyramid:
ord=:5
=> 'chk', 'base' and 'ord' are the knowledge rules abstracted from the problem definition.
The J-sentence that solves the puzzle is:
|."2(#~chk"2) 2(+/\)^:(<ord)"1 base/"1>,{ ;~i:28
151 0 0 0 0 81 70 0 0 0 40 41 29 0 0 16 24 17 12 0 5 11 13 4 8
Get rid of zeros:
,.(1+i.5)<@{."0 1{.|."2(#~chk"2) 2(+/\)^:(<ord)"1 base/"1>,{ ;~i:28
or
,.(<@{."0 1~1+i.@#){.|."2(#~chk"2) 2(+/\)^:(<ord)"1 base/"1>,{ ;~i:28
+-----------+ |151 | +-----------+ |81 70 | +-----------+ |40 41 29 | +-----------+ |16 24 17 12| +-----------+ |5 11 13 4 8| +-----------+
Java
Generate 11 equations and 11 unknowns. Reuse code from Cramer's Rule.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PascalsTrianglePuzzle {
public static void main(String[] args) {
Matrix mat = new Matrix(Arrays.asList(1d, 0d, 0d, 0d, 0d, 0d, 0d, 0d, -1d, 0d, 0d),
Arrays.asList(0d, 1d, 0d, 0d, 0d, 0d, 0d, 0d, 0d, -1d, 0d),
Arrays.asList(0d, 0d, 0d, 0d, 0d, 0d, 0d, 0d, -1d, 1d, -1d),
Arrays.asList(0d, 0d, 1d, 0d, 0d, 0d, 0d, 0d, 0d, -1d, 0d),
Arrays.asList(0d, 0d, 0d, 1d, 0d, 0d, 0d, 0d, 0d, 0d, -1d),
Arrays.asList(1d, 1d, 0d, 0d, 0d, 0d, 0d, 0d, 0d, 0d, 0d),
Arrays.asList(0d, 1d, 1d, 0d, -1d, 0d, 0d, 0d, 0d, 0d, 0d),
Arrays.asList(0d, 0d, 1d, 1d, 0d, -1d, 0d, 0d, 0d, 0d, 0d),
Arrays.asList(0d, 0d, 0d, 0d, -1d, 0d, 1d, 0d, 0d, 0d, 0d),
Arrays.asList(0d, 0d, 0d, 0d, 1d, 1d, 0d, -1d, 0d, 0d, 0d),
Arrays.asList(0d, 0d, 0d, 0d, 0d, 0d, 1d, 1d, 0d, 0d, 0d));
List<Double> b = Arrays.asList(11d, 11d, 0d, 4d, 4d, 40d, 0d, 0d, 40d, 0d, 151d);
List<Double> solution = cramersRule(mat, b);
System.out.println("Solution = " + cramersRule(mat, b));
System.out.printf("X = %.2f%n", solution.get(8));
System.out.printf("Y = %.2f%n", solution.get(9));
System.out.printf("Z = %.2f%n", solution.get(10));
}
private static List<Double> cramersRule(Matrix matrix, List<Double> b) {
double denominator = matrix.determinant();
List<Double> result = new ArrayList<>();
for ( int i = 0 ; i < b.size() ; i++ ) {
result.add(matrix.replaceColumn(b, i).determinant() / denominator);
}
return result;
}
private static class Matrix {
private List<List<Double>> matrix;
@Override
public String toString() {
return matrix.toString();
}
@SafeVarargs
public Matrix(List<Double> ... lists) {
matrix = new ArrayList<>();
for ( List<Double> list : lists) {
matrix.add(list);
}
}
public Matrix(List<List<Double>> mat) {
matrix = mat;
}
public double determinant() {
if ( matrix.size() == 1 ) {
return get(0, 0);
}
if ( matrix.size() == 2 ) {
return get(0, 0) * get(1, 1) - get(0, 1) * get(1, 0);
}
double sum = 0;
double sign = 1;
for ( int i = 0 ; i < matrix.size() ; i++ ) {
sum += sign * get(0, i) * coFactor(0, i).determinant();
sign *= -1;
}
return sum;
}
private Matrix coFactor(int row, int col) {
List<List<Double>> mat = new ArrayList<>();
for ( int i = 0 ; i < matrix.size() ; i++ ) {
if ( i == row ) {
continue;
}
List<Double> list = new ArrayList<>();
for ( int j = 0 ; j < matrix.size() ; j++ ) {
if ( j == col ) {
continue;
}
list.add(get(i, j));
}
mat.add(list);
}
return new Matrix(mat);
}
private Matrix replaceColumn(List<Double> b, int column) {
List<List<Double>> mat = new ArrayList<>();
for ( int row = 0 ; row < matrix.size() ; row++ ) {
List<Double> list = new ArrayList<>();
for ( int col = 0 ; col < matrix.size() ; col++ ) {
double value = get(row, col);
if ( col == column ) {
value = b.get(row);
}
list.add(value);
}
mat.add(list);
}
return new Matrix(mat);
}
private double get(int row, int col) {
return matrix.get(row).get(col);
}
}
}
- Output:
Solution = [16.0, 24.0, 17.0, 12.0, 41.0, 29.0, 81.0, 70.0, 5.0, 13.0, 8.0] X = 5.00 Y = 13.00 Z = 8.00
jq
Also works with gojq, the Go implementation of jq, and with fq.
In the spirit of the simplicity of Pascal Triangle's definition, the first solution given in this entry works up from the bottom of the triangle using the basic Pascal Triangle equation for each brick that is above two others.
In the following, the value of the j-th brick in the i-th row is denoted by rij if initially known (so r11 refers to the apex), and by $Rij if initially unknown, so the variable "X" in the puzzle could be denoted by $R51.
It is assumed that:
- all values in the triangle must be positive integers;
- the task is to solve for any given values of r11, r31, r52, r54;
- all solutions for the triple [X, Y, Z] should be found.
def solve(r11; r31; r52; r54):
range(1;r31 - 1) as $X
| range(1; r31 - 1) as $Y
| (($Y - $X) | select(. > 0)) as $Z
| (r52 + $X) as $R41
| (r52 + $Y) as $R42
| select($R41 + $R42 == r31)
| ($Y + r54) as $R43
| (r54 + $Z) as $R44
| ($R42 + $R43) as $R32
| ($R43 + $R44) as $R33
| (r31 + $R32) as $R21
| ($R32 + $R33) as $R22
| select($R21 + $R22 == r11)
| [$X, $Y, $Z];
solve(151; 40; 11; 4),
- Output:
[5,13,8]
Algebraic solution
As noted elsewhere on this page, elementary considerations show that the apex (top) value and the value in the third row (mid) can be written as:
top = 4(a+b) + 7(x+z) mid = 2x + 2a + z
where a and b are the known values at the base.
Using the jq program at Cramer's rule, with the unknown vector being [x, z]:
include "rc-cramers-rule";
def solve(top; mid; a; b):
cramer(
[ [7, 7],
[2, 1]];
[top - 4*(a+b), mid-2*a]);
solve(151; 40; 11; 4)
This gives the solution for [x,z] as:
- Output:
[5,8]
Julia
function pascal(a::Integer, b::Integer, mid::Integer, top::Integer)
yd = round((top - 4 * (a + b)) / 7)
!isinteger(yd) && return 0, 0, 0
y = Int(yd)
x = mid - 2a - y
return x, y, y - x
end
x, y, z = pascal(11, 4, 40, 151)
if !iszero(x)
println("Solution: x = $x, y = $y, z = $z.")
else
println("There is no solution.")
end
- Output:
Solution: x = 5, y = 13, z = 8.
Kotlin
// version 1.1.3
data class Solution(val x: Int, val y: Int, val z: Int)
fun Double.isIntegral(tolerance: Double = 0.0) =
(this - Math.floor(this)) <= tolerance || (Math.ceil(this) - this) <= tolerance
fun pascal(a: Int, b: Int, mid: Int, top: Int): Solution {
val yd = (top - 4 * (a + b)) / 7.0
if (!yd.isIntegral(0.0001)) return Solution(0, 0, 0)
val y = yd.toInt()
val x = mid - 2 * a - y
return Solution(x, y, y - x)
}
fun main(args: Array<String>) {
val (x, y, z) = pascal(11, 4, 40, 151)
if (x != 0)
println("Solution is: x = $x, y = $y, z = $z")
else
println("There is no solutuon")
}
- Output:
Solution is: x = 5, y = 13, z = 8
Maple
sys := {22 + x + y = 40, 78 + 5*y + z = 151, x + z = y}:
solve(sys, {x,y,z});
- Output:
{x = 5, y = 13, z = 8}
Mathematica/Wolfram Language
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:
b+c==a
d+e==b
e+f==c
g+h==d
h+i==e
i+j==f
l+X==g
l+Y==h
n+Y==i
n+Z==j
X+Z==Y
And we have the knowns
a->151
d->40
l->11
n->4
Giving us 10 equations with 10 unknowns; i.e. solvable. So we can do so by:
eqs={a==b+c,d+e==b,e+f==c,g+h==d,h+i==e,i+j==f,l+X==g,l+Y==h,n+Y==i,n+Z==j,Y==X+Z};
knowns={a->151,d->40,l->11,n->4};
Solve[eqs/.knowns,{b,c,e,f,g,h,i,j,X,Y,Z}]
gives back:
{{b -> 81, c -> 70, e -> 41, f -> 29, g -> 16, h -> 24, i -> 17, j -> 12, X -> 5, Y -> 13, Z -> 8}}
In pyramid form that would be:
151
81 70
40 41 29
16 24 17 12
5 11 13 4 8
An alternative solution in Mathematica 10, constructing the triangle:
triangle[n_, m_] := Nest[MovingMap[Total, #, 1] &, {x, 11, y, 4, z}, n - 1][[m]]
Solve[{triangle[3, 1] == 40, triangle[5, 1] == 151, y == x + z}, {x, y, z}]
Three equations and three unknowns, which gives back:
{{x -> 5, y -> 13, z -> 8}}
MiniZinc
%Pascal's Triangle Puzzle. Nigel Galloway, February 17th., 2020
int: N11=151; constraint N11=N21+N22;
var 1..N11: N21=N31+N32;
var 1..N11: N22=N32+N33;
int: N31=40; constraint N31=N41+N42;
var 1..N11: N32=N42+N43;
var 1..N11: N33=N43+N44;
var 1..N11: N41=X+11;
var 1..N11: N42=Y+11;
var 1..N11: N43=Y+4;
var 1..N11: N44=Z+4;
var 1..N11: X;
var 1..N11: Y=X+Z;
var 1..N11: Z;
- Output:
Z = 8; X = 5; ----------
Nim
import strutils
type
BlockValue = object
known: int
x, y, z: int
Variables = tuple[x, y, z: int]
func `+=`(left: var BlockValue; right: BlockValue) =
## Symbolically add one block to another.
left.known += right.known
left.x += right.x - right.z # Z is excluded as n(Y - X - Z) = 0.
left.y += right.y + right.z
proc toString(n: BlockValue; vars: Variables): string =
## Return the representation of the block value, when X, Y, Z are known.
result = $(n.known + n.x * vars.x + n.y * vars.y + n.z * vars.z)
proc Solve2x2(a11, a12, b1, a21, a22, b2: int): Variables =
## Solve a puzzle, supposing an integer solution exists.
if a22 == 0:
result.x = b2 div a21
result.y = (b1 - a11 * result.x) div a12
else:
result.x = (b1 * a22 - b2 * a12) div (a11 * a22 - a21 * a12)
result.y = (b1 - a11 * result.x) div a12
result.z = result.y - result.x
var blocks : array[1..5, array[1..5, BlockValue]] # The lower triangle contains blocks.
# The bottom blocks.
blocks[5][1] = BlockValue(x: 1)
blocks[5][2] = BlockValue(known: 11)
blocks[5][3] = BlockValue(y: 1)
blocks[5][4] = BlockValue(known: 4)
blocks[5][5] = BlockValue(z: 1)
# Upward run.
for row in countdown(4, 1):
for column in 1..row:
blocks[row][column] += blocks[row + 1][column]
blocks[row][column] += blocks[row + 1][column + 1]
# Now have known blocks 40=[3][1], 151=[1][1] and Y=X+Z to determine X,Y,Z.
let vars = Solve2x2(blocks[1][1].x,
blocks[1][1].y,
151 - blocks[1][1].known,
blocks[3][1].x,
blocks[3][1].y,
40 - blocks[3][1].known)
# Print the results.
for row in 1..5:
var line = ""
for column in 1..row:
line.addSep(" ")
line.add toString(blocks[row][column], vars)
echo line
- Output:
151 81 70 40 41 29 16 24 17 12 5 11 13 4 8
Oz
%% 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
PARI/GP
[ 6y+x+z+4a[2]+4a[4]= 7y +4a[2]+4a[4]] [3y+x+37 ][3y+z+23] [40=x+y+22][ 2y+15][ y+z+8 ] [ x+11 ][y+11 ][y+4 ][z+4 ] [ X][11][ Y][ 4][ Z]
this helped me...
Pascals_triangle_puzzle(topvalue=151,leftsidevalue=40,bottomvalue1=11,bottomvalue2=4) = {
y=(topvalue-(4*(bottomvalue1+bottomvalue2)))/7;
x=leftsidevalue-(y+2*bottomvalue1);
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.
Perl
# set up triangle
my $rows = 5;
my @tri = map { [ map { {x=>0,z=>0,v=>0,rhs=>undef} } 1..$_ ] } 1..$rows;
$tri[0][0]{rhs} = 151;
$tri[2][0]{rhs} = 40;
$tri[4][0]{x} = 1;
$tri[4][1]{v} = 11;
$tri[4][2]{x} = 1;
$tri[4][2]{z} = 1;
$tri[4][3]{v} = 4;
$tri[4][4]{z} = 1;
# aggregate from bottom to top
for my $row ( reverse 0..@tri-2 ) {
for my $col ( 0..@{$tri[$row]}-1 ){
$tri[$row][$col]{$_} = $tri[$row+1][$col]{$_}+$tri[$row+1][$col+1]{$_} for 'x','z','v';
}
}
# find equations
my @eqn;
for my $row ( @tri ) {
for my $col ( @$row ){
push @eqn, [ $$col{x}, $$col{z}, $$col{rhs}-$$col{v} ] if defined $$col{rhs};
}
}
# print equations
print "Equations:\n";
print " x + z = y\n";
printf "%d x + %d z = %d\n", @$_ for @eqn;
# solve
my $f = $eqn[0][1] / $eqn[1][1];
$eqn[0][$_] -= $f * $eqn[1][$_] for 0..2;
$f = $eqn[1][0] / $eqn[0][0];
$eqn[1][$_] -= $f * $eqn[0][$_] for 0..2;
# print solution
print "Solution:\n";
my $x = $eqn[0][2]/$eqn[0][0];
my $z = $eqn[1][2]/$eqn[1][1];
my $y = $x+$z;
printf "x=%d, y=%d, z=%d\n", $x, $y, $z;
- Output:
Equations: x + z = y 7 x + 7 z = 91 2 x + 1 z = 18 Solution: x=5, y=13, z=8
Phix
-- -- demo\rosetta\Pascal_triangle_Puzzle.exw -- ======================================= -- -- I approached this with a view to solving general pyramid puzzles, not just the one given. -- -- 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. -- with javascript_semantics sequence pyramid = {{151}, {"",""}, {40,"",""}, {"","","",""}, {"x",11,"y",4,"z"}} sequence rules = {} -- 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 -- the form {k,x,z} ie k+l*x+m*z, and known values < last row become rules. for r=5 to 1 by -1 do for c=1 to length(pyramid[r]) do object prc = pyramid[r][c], equ if prc="x" then prc = {0,1,0} -- ie 0 + one x elsif prc="y" then prc = {0,1,1} -- ie 0 + one x plus one z elsif prc="z" then prc = {0,0,1} -- ie 0 + one z else if prc="" or r<=4 then -- examples: x+11 is {0,1,0}+{11,0,0} -> {11,1,0}, -- 11+y is {11,0,0}+{0,1,1} -> {11,1,1}, -- 40=""+"" is {40,0,0}={22,2,1} ==> {18,2,1} equ = sq_add(pyramid[r+1][c],pyramid[r+1][c+1]) end if if prc="" then prc = equ else prc = {prc,0,0} if r<=4 then equ[1] = prc[1]-equ[1] rules = append(rules,equ) end if end if end if pyramid[r][c] = prc end for end for ppOpt({pp_Nest,1,pp_StrFmt,2,pp_IntCh,false}) ?"equations" pp(pyramid) ?"rules" pp(rules) -- {18,2,1} === 18=2x+z -- {73,5,6} === 73=5x+6z puts(1,"=====\n") assert(length(rules)==2) -- more work needed!? -- 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: function solveN(sequence rules) -- -- Based on https://mathcs.clarku.edu/~djoyce/ma105/simultaneous.html -- aka the ancient Chinese Jiuzhang suanshu ~100 B.C. (!!) -- -- Example (not related to the task problem): -- rules = {{18,1,1},{38,1,5}}, ie 18==x+y, 38==x+5y -- ==> {13,5}, ie x=13, y=5 -- -- In the elimination phase, both x have multipliers of 1, ie both rii and rij are 1, -- so we can ignore the two sq_mul and just do [sq_sub] (38=x+5y)-(18=x+y)==>(20=4y). -- Obviously therefore y is 5 and substituting backwards x is 13. -- -- Example2 (taken from the task problem): -- rules = {{18,2,1},{73,5,6}}, ie 18==2x+z, 73==5x+6z -- ==> {{18,2,1},{56,0,7}}, ie rules[2]:=rules[2]*2-rules[1]*5 (eliminate) -- ==> {{18,2,1},8}, ie rules[2]:=56/7, aka z:=8 (substitute) -- ==> {{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 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 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 end for pp(pyramid)
- Output:
"equations" {{{151,0,0}}, {{55,2,2}, {23,3,4}}, {{40,0,0}, {15,2,2}, {8,1,2}}, {{11,1,0}, {11,1,1}, {4,1,1}, {4,0,1}}, {{0,1,0}, {11,0,0}, {0,1,1}, {4,0,0}, {0,0,1}}} "rules" {{18,2,1}, {73,5,6}} ===== x=5, y=13, z=8 {{151}, {81,70}, {40,41,29}, {16,24,17,12}, {5,11,13,4,8}}
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 = {{151}, -- {"a","b"}, -- {40,"c","d"}, -- {"e","f","g","h"}, -- {"x", 11,"y", 4,"z"}} -- 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})
- Output:
Two-liner: x=5, y=13, z=8
Picat
Below are three different approaches using constraint modelling (cp solver).
Using lists to represent the triangle
import cp.
go =>
puzzle(T, X, Y,Z),
foreach(TT in T)
println(TT)
end,
println([x=X,y=Y,z=Z]),
nl,
fail, % are there any more solutions?
nl.
% Port of the Prolog solution
puzzle(Ts, X, Y, Z) :-
Ts = [ [151],
[_, _],
[40, _, _],
[_, _, _, _],
[X, 11, Y, 4, Z]],
Y #= X + Z,
triangle(Ts),
Vs = vars(Ts),
Vs :: 0..10000,
solve(Vs).
triangle([T|Ts]) :-
( Ts = [N|_] -> triangle_(T, N), triangle(Ts) ; true ).
triangle_([], _).
triangle_([T|Ts],[A,B|Rest]) :-
T #= A + B, triangle_(Ts, [B|Rest]).
- Output:
[151] [81,70] [40,41,29] [16,24,17,12] [5,11,13,4,8] [x = 5,y = 13,z = 8]
Calculating the positions
Here is a constraint model which calculates the positions in the triangle that should be added together.
import cp.
puzzle2 =>
N = 5, % number of rows
Len = (N*(N+1)) div 2, % number of entries
% The triangle numbers for 1..N
T = [I*(I+1) div 2 : I in 1..N],
% The index of first number to use in addition
% create the indices of the numbers to add,
% i.e. Adds[I] + Adds[I+1]
Adds = new_list(T[N-1]),
Adds[1] := 2,
foreach(I in 2..T[N-1])
% "jump" of 2 when i-1 is a triangle number
if membchk(I-1,T) then
Adds[I] := Adds[I-1] + 2
else
Adds[I] := Adds[I-1] + 1
end
end,
% the pyramid
MaxVal = 10_000,
L = new_list(Len),
L :: 1..MaxVal,
% The clues.
L = [ 151,
_, _,
40, _, _,
_, _,_ , _ ,
X, 11, Y, 4, Z
],
% The sums
foreach(I in 1..T[N-1])
L[I] #= L[Adds[I]]+L[Adds[I]+1]
end,
% The extra constraint
Y #= X + Z,
solve(L),
println([x=X,y=Y,z=Z]),
fail, % check if there is another solution
nl.
- Output:
[x = 5,y = 13,z = 8]
Hard coded constraints
import cp.
puzzle3 =>
% 1
% 2 3
% 4 5 6
% 7 8 9 10
%11 12 13 14 15
X = new_list(15),
X :: 0..10_000,
X[1] #= X[2]+X[3],
X[2] #= X[4]+X[5],
X[3] #= X[5]+X[6],
X[4] #= X[7]+X[8],
X[5] #= X[8]+X[9],
X[6] #= X[9]+X[10],
X[7] #= X[11]+X[12],
X[8] #= X[12]+X[13],
X[9] #= X[13]+X[14],
X[10] #= X[14]+X[15],
X[13] #= X[11] + X[15], % Y=X+Z,
% The hints
X[1] #= 151,
X[4] #= 40,
X[12] #= 11,
X[14] #= 4,
solve(X),
println([x=X[11],y=X[13],z=X[15]]),
fail,
nl.
- Output:
[x = 5,y = 13,z = 8]
PicoLisp
(be number (@N @Max)
(^ @C (box 0))
(repeat)
(or
((^ @ (>= (val (-> @C)) (-> @Max))) T (fail))
((^ @N (inc (-> @C)))) ) )
(be + (@A @B @Sum)
(^ @ (-> @A))
(^ @ (-> @B))
(^ @Sum (+ (-> @A) (-> @B))) )
(be + (@A @B @Sum)
(^ @ (-> @A))
(^ @ (-> @Sum))
(^ @B (- (-> @Sum) (-> @A)))
T
(^ @ (ge0 (-> @B))) )
(be + (@A @B @Sum)
(number @A @Sum)
(^ @B (- (-> @Sum) (-> @A))) )
#{
151
A B
40 C D
E F G H
X 11 Y 4 Z
}#
(be puzzle (@X @Y @Z)
(+ @A @B 151)
(+ 40 @C @A)
(+ @C @D @B)
(+ @E @F 40)
(+ @F @G @C)
(+ @G @H @D)
(+ @X 11 @E)
(+ 11 @Y @F)
(+ @Y 4 @G)
(+ 4 @Z @H)
(+ @X @Z @Y)
T )
- Output:
: (? (puzzle @X @Y @Z)) @X=5 @Y=13 @Z=8
Prolog
:- use_module(library(clpfd)).
puzzle(Ts, X, Y, Z) :-
Ts = [ [151],
[_, _],
[40, _, _],
[_, _, _, _],
[X, 11, Y, 4, Z]],
Y #= X + Z, triangle(Ts), append(Ts, Vs), Vs ins 0..sup, label(Vs).
triangle([T|Ts]) :- ( Ts = [N|_] -> triangle_(T, N), triangle(Ts) ; true ).
triangle_([], _).
triangle_([T|Ts], [A,B|Rest]) :- T #= A + B, triangle_(Ts, [B|Rest]).
% ?- puzzle(_,X,Y,Z).
% X = 5,
% Y = 13,
% Z = 8 ;
PureBasic
Brute force solution.
; Known;
; A.
; [ 151]
; [a ][b ]
; [40][c ][d ]
; [e ][f ][g ][h ]
; [ X][11][ Y][ 4][ Z]
;
; B.
; Y = X + Z
Procedure.i SolveForZ(x)
Protected a,b,c,d,e,f,g,h,z
For z=0 To 20
e=x+11: f=11+(x+z): g=(x+z)+4: h=4+z
If e+f=40
c=f+g : d=g+h: a=40+c: b=c+d
If a+b=151
ProcedureReturn z
EndIf
EndIf
Next z
ProcedureReturn -1
EndProcedure
Define x=-1, z=0, title$="Pascal's triangle/Puzzle in PureBasic"
Repeat
x+1
z=SolveForZ(x)
Until z>=0
MessageRequester(title$,"X="+Str(x)+#CRLF$+"Y="+Str(x+z)+#CRLF$+"Z="+Str(z))
Python
# Pyramid solver
# [151]
# [ ] [ ]
# [ 40] [ ] [ ]
# [ ] [ ] [ ] [ ]
#[ X ] [ 11] [ Y ] [ 4 ] [ Z ]
# X -Y + Z = 0
def combine( snl, snr ):
cl = {}
if isinstance(snl, int):
cl['1'] = snl
elif isinstance(snl, string):
cl[snl] = 1
else:
cl.update( snl)
if isinstance(snr, int):
n = cl.get('1', 0)
cl['1'] = n + snr
elif isinstance(snr, string):
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(vmap) # sort here so output is in sorted order
mtx = []
for c in constraints:
row = []
for vv in vmap:
row.append(float(c.get(vv, 0)))
row.append(-float(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] *= f
for l in range(1+j,mDim):
rwl = mtx[l]
f = -rwl[j]
for k in range(j, mDim+1):
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] += f * rw0[j]
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)
- 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.
Alternative solution using the csp module (based on code by Gustavo Niemeyerby): http://www.fantascienza.net/leonardo/so/csp.zip
from csp import Problem
p = Problem()
pvars = "R2 R3 R5 R6 R7 R8 R9 R10 X Y Z".split()
# 0-151 is the possible finite range of the variables
p.addvars(pvars, xrange(152))
p.addrule("R7 == X + 11")
p.addrule("R8 == Y + 11")
p.addrule("R9 == Y + 4")
p.addrule("R10 == Z + 4")
p.addrule("R7 + R8 == 40")
p.addrule("R5 == R8 + R9")
p.addrule("R6 == R9 + R10")
p.addrule("R2 == 40 + R5")
p.addrule("R3 == R5 + R6")
p.addrule("R2 + R3 == 151")
p.addrule("Y == X + Z")
for sol in p.xsolutions():
print [sol[k] for k in "XYZ"]
- Output:
[5, 13, 8]
Racket
(Based on the clojure version)
Only X and Z are independent variables. We'll use a struct (cell v x z) to represent each cell, where the value is (v + x*X + z*Z).
#lang racket/base
(require racket/list)
(struct cell (v x z) #:transparent)
(define (cell-add cx cy)
(cell (+ (cell-v cx) (cell-v cy))
(+ (cell-x cx) (cell-x cy))
(+ (cell-z cx) (cell-z cy))))
(define (cell-sub cx cy)
(cell (- (cell-v cx) (cell-v cy))
(- (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 row0 (list (cell 0 1 0) (cell 11 0 0) (cell 0 1 1) (cell 4 0 0) (cell 0 0 1)))
(define row1 (row-above row0))
(define row2 (row-above row1))
(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))))
(define (cramer2 eqnx eqny get-val get-unk get-oth)
(/ (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 "X" x))
(displayln (list "Y" (+ x z)))
(displayln (list "Z" z))
- Output:
(X 5) (Y 13) (Z 8)
Raku
(formerly Perl 6)
# set up triangle
my $rows = 5;
my @tri = (1..$rows).map: { [ { x => 0, z => 0, v => 0, rhs => Nil } xx $_ ] }
@tri[0][0]<rhs> = 151;
@tri[2][0]<rhs> = 40;
@tri[4][0]<x> = 1;
@tri[4][1]<v> = 11;
@tri[4][2]<x> = 1;
@tri[4][2]<z> = 1;
@tri[4][3]<v> = 4;
@tri[4][4]<z> = 1;
# aggregate from bottom to top
for @tri - 2 ... 0 -> $row {
for 0 ..^ @tri[$row] -> $col {
@tri[$row][$col]{$_} = @tri[$row+1][$col]{$_} + @tri[$row+1][$col+1]{$_} for 'x','z','v';
}
}
# find equations
my @eqn = gather for @tri -> $row {
for @$row -> $cell {
take [ $cell<x>, $cell<z>, $cell<rhs> - $cell<v> ] if defined $cell<rhs>;
}
}
# print equations
say "Equations:";
say " x + z = y";
for @eqn -> [$x,$z,$y] { say "$x x + $z z = $y" }
# solve
my $f = @eqn[0][1] / @eqn[1][1];
@eqn[0][$_] -= $f * @eqn[1][$_] for 0..2;
$f = @eqn[1][0] / @eqn[0][0];
@eqn[1][$_] -= $f * @eqn[0][$_] for 0..2;
# print solution
say "Solution:";
my $x = @eqn[0][2] / @eqn[0][0];
my $z = @eqn[1][2] / @eqn[1][1];
my $y = $x + $z;
say "x=$x, y=$y, z=$z";
- Output:
Equations: x + z = y 7 x + 7 z = 91 2 x + 1 z = 18 Solution: x=5, y=13, z=8
REXX
This REXX version also displays a diagram of the puzzle.
/*REXX program solves a (Pascal's) "Pyramid of Numbers" puzzle given four values. */
/* ╔══════════════════════════════════════════════════╗
║ answer ║
║ / ║
║ mid / ║
║ \ 151 ║
║ \ ααα ααα ║
║ 40 ααα ααα ║
║ ααα ααα ααα ααα ║
║ x 11 y 4 z ║
║ / \ ║
║ find: / \ ║
║ x y z b d ║
╚══════════════════════════════════════════════════╝ */
do #=2; _= sourceLine(#); n= pos('_', _) /* [↓] this DO loop shows (above) box.*/
if n\==0 then leave; say _ /*only display up to the above line. */
end /*#*/; say /* [↑] this is a way for in─line doc. */
parse arg b d mid answer . /*obtain optional variables from the CL*/
if b=='' | b=="," then b= 11 /*Not specified? Then use the default.*/
if d=='' | d=="," then d= 4 /* " " " " " " */
if mid='' | mid=="," then mid= 40 /* " " " " " " */
if answer='' | answer=="," then answer= 151 /* " " " " " " */
big= answer - 4*b - 4*d /*calculate BIG number less constants*/
do x=-big to big
do y=-big to big
if x+y\==mid - 2*b then iterate /*40 = x+2B+Y ──or── 40-2*11 = x+y */
do z=-big to big
if z \== y - x then iterate /*Z has to equal Y-X (Y= X+Z) */
if x+y*6+z==big then say right('x =', n) x right("y =",n) y right('z =',n) z
end /*z*/
end /*y*/
end /*x*/ /*stick a fork in it, we're all done. */
- output when using the default inputs:
/* ╔══════════════════════════════════════════════════╗ ║ answer ║ ║ / ║ ║ mid / ║ ║ \ 151 ║ ║ \ ααα ααα ║ ║ 40 ααα ααα ║ ║ ααα ααα ααα ααα ║ ║ x 11 y 4 z ║ ║ / \ ║ ║ find: / \ ║ ║ x y z b d ║ ╚══════════════════════════════════════════════════╝ */ x = 5 y = 13 z = 8
Ruby
uses Reduced row echelon form#Ruby
require 'rref'
pyramid = [
[ 151],
[nil,nil],
[40,nil,nil],
[nil,nil,nil,nil],
["x", 11,"y", 4,"z"]
]
pyramid.each{|row| p row}
equations = [[1,-1,1,0]] # y = x + z
def parse_equation(str)
eqn = [0] * 4
lhs, rhs = str.split("=")
eqn[3] = rhs.to_i
for term in lhs.split("+")
case term
when "x" then eqn[0] += 1
when "y" then eqn[1] += 1
when "z" then eqn[2] += 1
else eqn[3] -= term.to_i
end
end
eqn
end
-2.downto(-5) do |row|
pyramid[row].each_index do |col|
val = pyramid[row][col]
sum = "%s+%s" % [pyramid[row+1][col], pyramid[row+1][col+1]]
if val.nil?
pyramid[row][col] = sum
else
equations << parse_equation(sum + "=#{val}")
end
end
end
reduced = convert_to(reduced_row_echelon_form(equations), :to_i)
for eqn in reduced
if eqn[0] + eqn[1] + eqn[2] != 1
fail "no unique solution! #{equations.inspect} ==> #{reduced.inspect}"
elsif eqn[0] == 1 then x = eqn[3]
elsif eqn[1] == 1 then y = eqn[3]
elsif eqn[2] == 1 then z = eqn[3]
end
end
puts
puts "x == #{x}"
puts "y == #{y}"
puts "z == #{z}"
answer = []
for row in pyramid
answer << row.collect {|cell| eval cell.to_s}
end
puts
answer.each{|row| p row}
- Output:
[151] [nil, nil] [40, nil, nil] [nil, nil, nil, nil] ["x", 11, "y", 4, "z"] x == 5 y == 13 z == 8 [151] [81, 70] [40, 41, 29] [16, 24, 17, 12] [5, 11, 13, 4, 8]
Scala
object PascalTriangle extends App {
val (x, y, z) = pascal(11, 4, 40, 151)
def pascal(a: Int, b: Int, mid: Int, top: Int): (Int, Int, Int) = {
val y = (top - 4 * (a + b)) / 7
val x = mid - 2 * a - y
(x, y, y - x)
}
println(if (x != 0) s"Solution is: x = $x, y = $y, z = $z" else "There is no solution.")
}
- Output:
See it in running in your browser by (JavaScript)
or by Scastie (JVM).
Sidef
# set up triangle
var rows = 5
var tri = rows.of {|i| (i+1).of { Hash(x => 0, z => 0, v => 0, rhs => nil) } }
tri[0][0]{:rhs} = 151
tri[2][0]{:rhs} = 40
tri[4][0]{:x} = 1
tri[4][1]{:v} = 11
tri[4][2]{:x} = 1
tri[4][2]{:z} = 1
tri[4][3]{:v} = 4
tri[4][4]{:z} = 1
# aggregate from bottom to top
for row in (tri.len ^.. 1) {
for col in (^tri[row-1]) {
[:x, :z, :v].each { |key|
tri[row-1][col]{key} = (tri[row][col]{key} + tri[row][col+1]{key})
}
}
}
# find equations
var eqn = gather {
for r in tri {
for c in r {
take([c{:x}, c{:z}, c{:rhs} - c{:v}]) if defined(c{:rhs})
}
}
}
# print equations
say "Equations:"
say " x + z = y"
for x,z,y in eqn { say "#{x}x + #{z}z = #{y}" }
# solve
var f = (eqn[0][1] / eqn[1][1])
{|i| eqn[0][i] -= (f * eqn[1][i]) } << ^3
f = (eqn[1][0] / eqn[0][0])
{|i| eqn[1][i] -= (f * eqn[0][i]) } << ^3
# print solution
say "Solution:"
var x = (eqn[0][2] / eqn[0][0])
var z = (eqn[1][2] / eqn[1][1])
var y = (x + z)
say "x=#{x}, y=#{y}, z=#{z}"
- Output:
Equations: x + z = y 7x + 7z = 91 2x + 1z = 18 Solution: x=5, y=13, z=8
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...
program main;
class Triangle;
rand bit [7:0] a,b,c,d,e,f,g,h,X,Y,Z;
function new();
randomize;
$display(" [%0d]", 151);
$display(" [%0d][%0d]", a, b);
$display(" [%0d][%0d][%0d]", 40,c,d);
$display(" [%0d][%0d][%0d][%0d]", e,f,g,h);
$display(" [%0d][%0d][%0d][%0d][%0d]",X,11,Y,4,Z);
endfunction
constraint structure {
151 == a + b;
a == 40 + c;
b == c + d;
40 == e + f;
c == f + g;
d == g + h;
e == X + 11;
f == 11 + Y;
g == Y + 4;
h == 4 + Z;
};
constraint extra {
Y == X + Z;
};
endclass
Triangle answer = new;
endprogram
[151] [81][70] [40][41][29] [16][24][17][12] [5][11][13][4][8]
Tcl
using code from Reduced row echelon form#Tcl
package require Tcl 8.5
namespace path ::tcl::mathop
set pyramid {
{151.0 "" "" "" ""}
{"" "" "" "" ""}
{40.0 "" "" "" ""}
{"" "" "" "" ""}
{x 11.0 y 4.0 z}
}
set equations {{1 -1 1 0}}
proc simplify {terms val} {
set vars {0 0 0}
set x 0
set y 1
set z 2
foreach term $terms {
switch -exact -- $term {
x - y - z {
lset vars [set $term] [+ 1 [lindex $vars [set $term]]]
}
default {
set val [- $val $term]
}
}
}
return [concat $vars $val]
}
for {set row [+ [llength $pyramid] -2]} {$row >= 0} {incr row -1} {
for {set cell 0} {$cell <= $row} {incr cell } {
set sum [concat [lindex $pyramid [+ 1 $row] $cell] [lindex $pyramid [+ 1 $row] [+ 1 $cell]]]
if {[set val [lindex $pyramid $row $cell]] ne ""} {
lappend equations [simplify $sum $val]
} else {
lset pyramid $row $cell $sum
}
}
}
set solution [toRREF $equations]
foreach row $solution {
lassign $row a b c d
if {$a + $b + $c > 1} {
error "problem does not have a unique solution"
}
if {$a} {set x $d}
if {$b} {set y $d}
if {$c} {set z $d}
}
puts "x=$x"
puts "y=$y"
puts "z=$z"
foreach row $pyramid {
set newrow {}
foreach cell $row {
if {$cell eq ""} {
lappend newrow ""
} else {
lappend newrow [expr [join [string map [list x $x y $y z $z] $cell] +]]
}
}
lappend solved $newrow
}
print_matrix $solved
x=5.0 y=13.0 z=8.0 151.0 81.0 70.0 40.0 41.0 29.0 16.0 24.0 17.0 12.0 5.0 11.0 13.0 4.0 8.0
Wren
import "./fmt" for Fmt
var isIntegral = Fn.new { |x, tol| x.fraction.abs <= tol }
var pascal = Fn.new { |a, b, mid, top|
var yd = (top - 4 * (a + b)) / 7
if (!isIntegral.call(yd, 0.0001)) return [0, 0, 0]
var y = yd.truncate
var x = mid - 2*a - y
return [x, y, y - x]
}
var sol = pascal.call(11, 4, 40, 151)
if (sol[0] != 0) {
Fmt.print("Solution is: x = $d, y = $d, z = $d", sol[0], sol[1], sol[2])
} else {
System.print("There is no solution")
}
- Output:
Solution is: x = 5, y = 13, z = 8
XPL0
proc Print; int N, A, B, C, D, E;
int I, P;
def Tab = $09;
[P:= @A; \point to first number
for I:= N to 5-1 do ChOut(0, Tab);
for I:= 0 to N-1 do
[IntOut(0, P(I)); ChOut(0, Tab); ChOut(0, Tab)];
CrLf(0);
];
int N, P, Q, R, S, T, U, V, W, X, Y, Z; \ 151
[for X:= 0 to 40-11 do \ N P
for Z:= 0 to 151-4 do \ Q R S
[Y:= X+Z; \ T U V W
T:= X+11; \X 11 Y 4 Z
U:= 11+Y;
V:= Y+4;
W:= 4+Z;
if T+U = 40 then
[R:= U+V;
S:= V+W;
N:= 40+R;
P:= R+S;
if N+P = 151 then
[Print(1, 151);
Print(2, N, P);
Print(3, 40, R, S);
Print(4, T, U, V, W);
Print(5, X, 11, Y, 4, Z);
exit;
];
];
];
]
- Output:
151 81 70 40 41 29 16 24 17 12 5 11 13 4 8
zkl
# Pyramid solver
# [151]
# [ ] [ ]
# [ 40] [ ] [ ]
# [ ] [ ] [ ] [ ]
#[ X ] [ 11] [ Y ] [ 4 ] [ Z ]
# Known: X - Y + Z = 0
p:=T( L(151), L(Void,Void), L(40,Void,Void), L(Void,Void,Void,Void),
L("X", 11, "Y", 4, "Z") );
addlConstraint:=Dictionary( "X",1, "Y",-1, "Z",1, "1",0 );
solvePyramid(p, addlConstraint);
fcn solvePyramid([List]vl,[Dictionary]cnstr){ //ListOfLists,Hash-->zip
vl=vl.reverse();
constraints:=L(cnstr);
lvls:=vl.len();
foreach lvln in ([1..lvls-1]){
lvd:=vl[lvln];
foreach k in (lvls-lvln){
sn:=lvd[k];
ll:=vl[lvln-1];
vn:=combine(ll[k], ll[k+1]);
if(Void==sn) lvd[k]=vn;
else constraints.append(constrainK(sn,vn));
}
}
println("Constraint Equations:");
constraints.pump(Console.println,fcn(hash){
hash.pump(List,fcn([(k,v)]){"%d*%s".fmt(v,k)}).concat(" + ") + " = 0"
});
mtx,vmap:=makeMatrix(constraints);
mtxSolve(mtx);
d:=vmap.len();
foreach j in (d){ println(vmap[j]," = ", mtx[j][d]); }
}
fcn [mixin=Dictionary] constrainK([Int]nsum,[Dictionary]vn){ //-->new hash of old hash, sum K
nn:=vn.copy(); nn["1"]=nn.find("1",0) - nsum;
return(nn.makeReadOnly());
}
fcn combine(snl,snr){ //Int|String|Hash *2 --> new Hash
cl:=Dictionary();
if(snl.isInstanceOf(Int)) cl["1"]=snl;
else if(snl.isInstanceOf(String)) cl[snl]=1;
else cl =snl.copy();
if(snr.isInstanceOf(Int)) cl["1"]=cl.find("1",0) + snr;
else if(snr.isInstanceOf(String)) cl[snr]=cl.find(snr,0) + 1;
else{ foreach k,v in (snr){ cl[k] =cl.find(k,0) + v; } }
return(cl.makeReadOnly())
}
//-->(listMatrix(row(X,Y,Z,c),row...),List("X","Y","Z"))
fcn makeMatrix([Dictionary]constraints){
vmap:=Dictionary();// create a sorted list of the variable names in constraints
foreach c in (constraints){ vmap.extend(c) } // no duplicate names
vmap.del("1"); vmap=vmap.keys.sort(); # sort here so output is in sorted order
mtx:=constraints.pump(List,'wrap(c){ // create list of [writeable] rows
vmap.pump(List, c.find.fp1(0),"toFloat").copy()
.append(-c.find("1",0).toFloat())
}).copy();
nvars:=vmap.len();
if(constraints.len()==nvars) println("System appears solvable");
else if(constraints.len()<nvars)
println("System is not solvable - needs more constraints.");
return(mtx,vmap);
}
fcn mtxSolve([List]mtx){ //munge mtx # Simple Matrix solver...
mDim:=mtx.len(); # num rows
foreach j in (mDim){
rw0:=mtx[j];
f:=1.0/rw0[j];
foreach k in ([j..mDim]){ rw0[k]=rw0[k]*f }
foreach l in ([j+1..mDim-1]){
rwl:=mtx[l]; f:=-rwl[j];
foreach k in ([j..mDim]){ rwl[k]+=f*rw0[k] }
}
}
# backsolve part ---
foreach j1 in ([1..mDim-1]){
j:=mDim - j1; rw0:=mtx[j];
foreach l in (j){
rwl:=mtx[l]; f:=-rwl[j];
rwl[j] +=f*rw0[j];
rwl[mDim]+=f*rw0[mDim];
}
}
return(mtx);
}
- Output:
Constraint Equations: 0*1 + 1*X + -1*Y + 1*Z = 0 -18*1 + 1*X + 1*Y = 0 -73*1 + 5*Y + 1*Z = 0 System appears solvable X = 5 Y = 13 Z = 8
- Programming Tasks
- Solutions by Programming Task
- 11l
- Ada
- ALGOL 68
- AutoHotkey
- BBC BASIC
- C
- C sharp
- C++
- Clojure
- Craft Basic
- Curry
- D
- F Sharp
- Factor
- FreeBASIC
- Go
- Haskell
- J
- Java
- Jq
- Julia
- Kotlin
- Maple
- Mathematica
- Wolfram Language
- MiniZinc
- Nim
- Oz
- PARI/GP
- Perl
- Phix
- Picat
- PicoLisp
- Prolog
- PureBasic
- Python
- Racket
- Raku
- REXX
- Ruby
- Scala
- Sidef
- SystemVerilog
- Tcl
- Wren
- Wren-fmt
- XPL0
- Zkl
- Puzzles