Pascal's triangle/Puzzle: Difference between revisions

{{incorrect|C|Displayed result seems wrong.}}

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

<lang c>#include <stdio.h>

#define E(x, row, col) x[(row) * ((row) + 1) / 2 + col]

void show(double *x)

{

int i = 0, j = 0;

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

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

printf("%4d%c", (int)(.5 + *(x++)), j < i ? ' ':'\n');

}

void iterate(double *v, double *diff)

{

int i, j;

double sum;

redo:

/* 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);

/* do feedback, check if we are close enough */

for (i = 0, sum = 0; i < 15; i++){

v[i] += diff[i] / 4; /* 4: scale down the feedback to avoid oscillations */

sum += diff[i] * diff[i];

}

printf("dev: %g\n", sum);

if (sum < .1) return;

goto redo;

}

int main()

{

double v[15] = {0}, diff[15] = {0};

iterate(v, diff);

show(v);

return 0;

}</lang>output<lang>dev: 73410

dev: 17968.7

dev: 6388.46

dev: 2883.34

...<about a million and half iterations later>...

dev: 0.116055

dev: 0.107006

dev: 0.09866

151

81 70

40 41 29

16 24 17 12

5 11 13 4 8

</lang>