Self-hatred

Project Euler Problem #15

So, the answer was staring at me all along. No, really. Look at this picture:

On the left is a bog-standard Pascal Triangle. On the right is the example problem on the Project Euler website. I drew this diagram on paper, and what immediately leaped out of me was that the number I need (the single highest integer in the array) doesn’t change a whit if you trim out the side elements.

The only modification to my code was to add a small equation I (re)discovered: The total number of rows in the triangle I need to crunch are equal to twice the length of one side of the square, plus one:

// 20x20
long z = 20;
long a = (2 * z) +1;

Crunch a 41-line triangle and output the highest integer on the last row.

Yay!

using System;
using System.Linq;

public class Fifteen
{
	static void Main()
	{
		long z 	 = 20;
		long a 	 = (2 * z) +1;
		long[][] b = new long[a][];

		for (int i = 0; i < a; i++)
			b[i] = new long[i + 1];

		b[0][0] = 1;

		for (int i = 1; i < a; i++)
			for (int j = 0; j < b[i].Length; j++)
			{
				if (j == 0)
					b[i][j] = b[i-1][j];
				if ((j > 0) && (j < b[i].Length-1))
					b[i][j] = b[i-1][j-1] + b[i-1][j];
				if (j == (b[i].Length -1))
					b[i][j] = b[i-1][j-1];
			}

		Console.WriteLine("\n{0}\n", b[a-1].Max());
	}
}

Tagged with: 15, c, csharp, fifteen, grid, mathematics, pascal triangle, problem, project euler, projecteuler, solution

Categorised as: programming