function [] = Problem18()
%ProjectEuler/Octave/Problem18.m
%Matthew Ellison
% Created: 03-12-19
%Modified: 03-28-19
%Find the maximun total from top to bottom
%{
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
%}
%This is done using a breadth first search
%{
	Copyright (C) 2019  Matthew Ellison

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
%}


%Start the timer
startTime = clock();

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


%Invert the list so that each element will be 100 - element
list = invert(list);

%Keeps track of the points that we know they are at their minumum total (Maximum after inversion)
foundPoints = [];
%Add the tip to the list because we have to come through that
foundPoints(end + 1).xLocation = 1;
foundPoints(end).yLocation = 1;
foundPoints(end).total = list{1}(1);
foundPoints(end).fromRight = false;
%Keeps track of points that could be at their maximum
possiblePoints = [];
%Add the second row to the list of possibles
possiblePoints(end + 1).xLocation = 1;
possiblePoints(end).yLocation = 2;
possiblePoints(end).total = (list{1}(1) + list{2}(1));
possiblePoints(end).fromRight = true;
possiblePoints(end + 1).xLocation = 2;
possiblePoints(end).yLocation = 2;
possiblePoints(end).total = (list{1}(1) + list{2}(2));
possiblePoints(end).fromRight = false;
foundBottom = false;	%Used when you find a point at the bottom of the list

%Loop until you find the bottom
while(~foundBottom)
	%Check which possible point gives us the lowest number. If more than one has the same number simply keep the first one
	minLoc = possiblePoints(1);
	for loc = 1 : size(possiblePoints)(2)
		if(possiblePoints(loc).total < minLoc.total)
			minLoc.xLocation = possiblePoints(loc).xLocation;
			minLoc.yLocation = possiblePoints(loc).yLocation;
			minLoc.total = possiblePoints(loc).total;
			minLoc.fromRight = possiblePoints(loc).fromRight;
		end
	end
	%disp(minLoc)
	possiblePoints = remove_if(possiblePoints, minLoc);

	%Add the current minimum to the found points
	foundPoints(end + 1) = minLoc;

	%Add to the list of possible points from the point we just found and
	%If you are at the bottom raise the flag to end the program
	xLoc = minLoc.xLocation;
	yLoc = minLoc.yLocation + 1;	%Add one because you will always be moving down a row
	if(yLoc > NUM_ROWS)
		foundBottom = true;
	else
		%Add the next 2 possible points
		possiblePoints(end + 1).xLocation = xLoc;
		possiblePoints(end).yLocation = yLoc;
		possiblePoints(end).total = (minLoc.total + list{yLoc}(xLoc));
		possiblePoints(end).fromRight = true;

		xLoc = xLoc + 1;	%Advance the x location to simulate going right instead of left

		possiblePoints(end + 1).xLocation = xLoc;
		possiblePoints(end).yLocation = yLoc;
		possiblePoints(end).total = (minLoc.total + list{yLoc}(xLoc));
		possiblePoints(end).fromRight = false;
	end
end

actualTotal = ((100 * NUM_ROWS) - foundPoints(end).total);

%Stop the timer
endTime = clock();

%Reinvert the list so it will print propperly
invert(list);

%Print the results
printf("The value of the longest path is %d\n", actualTotal)
printf("It took %f seconds to run this algorithm\n", etime(endTime, startTime))

end %End of Problem18()


%This function changes each element in the list to 100 - element
function [temp] = invert(list)
	temp = list;
	for rowCnt = 1 : size(temp)(2)
		for colCnt = 1 : size(temp{rowCnt})(2)
			temp{rowCnt}(colCnt) = 100 - temp{rowCnt}(colCnt);
		end
	end
end

function [temp] = remove_if(list, loc)
	location = 1;
	while(location <= size(list)(2))
		if((list(location).xLocation == loc.xLocation) && (list(location).yLocation == loc.yLocation))
			list(location) = [];
		else
			location = location + 1;
		end
	end
	temp = list;
end

%{
Results:
The value of the longest path is 1074
It took 0.098862 seconds to run this algorithm
%}