Euler 18

gistfile1.txt

#!/usr/local/bin/node

// put the text string into an array

triangle = new Array (); 
triangle[0] = [75]
triangle[1] = [95,64] 
triangle[2] = [17,47,82]
triangle[3] = [18,35,87,10]
triangle[4] = [20,04,82,47,65] 
triangle[5] = [19,01,23,75,03,34]
triangle[6] = [88,02,77,73,07,63,67]
triangle[7] = [99,65,04,28,06,16,70,92] 
triangle[8] = [41,41,26,56,83,40,80,70,33] 
triangle[9] = [41,48,72,33,47,32,37,16,94,29] 
triangle[10] = [53,71,44,65,25,43,91,52,97,51,14] 
triangle[11] = [70,11,33,28,77,73,17,78,39,68,17,57]
triangle[12] = [91,71,52,38,17,14,91,43,58,50,27,29,48] 
triangle[13] = [63,66,04,68,89,53,67,30,73,16,69,87,40,31] 
triangle[14] = [04,62,98,27,23,09,70,98,73,93,38,53,60,04,23]

// the officially endorsed method from the internet is to work from the bottom up
// adding the greater of the two cells below to your current value
// this is equivalent to searching every possible chain, and max value ends up in [0][0]
// doing this exercise three ways taught me about writing functions and using arrays

Array.prototype.max = function() {
var max = 0;
var len = this.length;
for (var i = len; i >=0; i--) 
	{
	if (this[i] > max) 
		{
		max = this[i]; 
		}
	}	
return max
}

for (r=13;r>=0;r--)
	{
	for (k=0;k<=r;k++)
		{
		comparison_array = [triangle[r+1][k],triangle[r+1][k+1]];
		triangle[r][k] = triangle[r][k]+comparison_array.max();
//		console.log("triangle" + r + " " + k + " is " + triangle[r][k]);
		}
	} 

console.log("largest chain in this triangle is " + triangle[0][0]);
			

i also did a variation where i took the values from right to left (in the case where there were two max values in the row, i wanted to make sure i got both chains:

!/usr/local/bin/node

// first we need to extract this stupid text string:

triangle = new Array ();
triangle[0] = [75]
triangle[1] = [95,64]
triangle[2] = [17,47,82]
triangle[3] = [18,35,87,10]
triangle[4] = [20,04,82,47,65]
triangle[5] = [19,01,23,75,03,34]
triangle[6] = [88,02,77,73,07,63,67]
triangle[7] = [99,65,04,28,06,16,70,92]
triangle[8] = [41,41,26,56,83,40,80,70,33]
triangle[9] = [41,48,72,33,47,32,37,16,94,29]
triangle[10] = [53,71,44,65,25,43,91,52,97,51,14]
triangle[11] = [70,11,33,28,77,73,17,78,39,68,17,57]
triangle[12] = [91,71,52,38,17,14,91,43,58,50,27,29,48]
triangle[13] = [63,66,04,68,89,53,67,30,73,16,69,87,40,31]
triangle[14] = [04,62,98,27,23,09,70,98,73,93,38,53,60,04,23]

// then jake's algorithm is start at row 0, pick largest number, then pick the larger of the two
// adjacent numbers, and repeat until you have 15 numbers in the sum
// we'll use this max function to find max value and position
// this variation, we're going to read the max of the line from the right, instead of the left

Array.prototype.max = function() {
var max = 0;
var len = this.length;
for (var i = len; i >=0; i--)
{
if (this[i] > max)
{
max = this[i];
max_i=i;
}
}
return [max,max_i]
}

// our approach is to find the biggest value in each row, then build a chain around it
// each link of the chain being the larger of the two values
// if the complete chain is > biggest one we've tested so far, save it

biggest=0;
item_location = 0;
sum = 75;

for(k=0; k<=14;k++)
{
downsum = 0;
upsum = 0;
item_location = triangle[k].max()[1];
console.log("----------------k is " + k);

// first let's sum down the chain- this works good
for (j=k; j<=14; j++)
{
testArray = [triangle[j][item_location], triangle[j][item_location+1]];
test = testArray.max()[1];
console.log("down " + j + "term is " + testArray.max()[0]);
if (test==0) { downsum+=testArray.max()[0]; }
if (test==1) { item_location+=1; downsum+=testArray.max()[0];}
}
console.log("down sum is" + downsum);

// then let's sum up the chain if k > 0- reset initial position- this doesn't work k=13 or k=14

item_location = triangle[k].max()[1];
for (l=k; l>0; l--)
    {
    testArray = [triangle[l-1][item_location], triangle[l-1][item_location-1]];
    test = testArray.max()[1];
    console.log("up " + l + "term is " + testArray.max()[0]);
    if (test==0) { upsum+=testArray.max()[0]; }
    if (test==1) { item_location-=1; upsum+=testArray.max()[0];}
    }   
console.log("up sum is" + upsum);
console.log("total sum is" + (downsum+upsum));  
if ((downsum+upsum)>biggest) { biggest=(downsum+upsum);}
}

console.log(biggest);