function [] = Problem26()
%ProjectEuler/Octave/Problem26.m
%Matthew Ellison
% Created: 08-02-19
%Modified: 08-02-19
%Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
%{
	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/>.
%}


TOP_NUMBER = 999;	%The largest denominator to the checked


%Setup variables
longestCycle = 0;	%
longestNumber = 1;

%Start the timer
startTime = clock();

%Start with 1/2 and find out how long the longest cycle is by checking the remainders
%Loop through every number from 2-999 and use it for the denominator
for denominator = 2 : TOP_NUMBER
	remainderList = [];	%Holds the list of remainders
	endFound = false;	%Holds whether we have found an end ot the number (either a cycle or a 0 for a remainder)
	cycleFound = false;	%Holds whether a cycle was detected
	numerator = 1;	%The numerator that will be divided
	while(~endFound)
		%Get the remainder after the division
		remainder = mod(numerator, denominator);
		%Check if the remainder is 0
		%If it is, set the flag
		if(remainder == 0)
			endFound = true;
		%Check if the remainder is in the list
		%If it is in the list, set the appropriate flags
		elseif(isFound(remainderList, remainder))
			endFound = true;
			cycleFound = true;
		%Else add it to the list
		else
			remainderList(end + 1) = remainder;
		end
		%Multiply the remainder by 10 to continue finding the next remainder
		numerator = remainder * 10;
	end
	%If a cycle was found check the size of the list against the largest cycle
	if(cycleFound)
		%If it is larger than the largest, set it as the new largest
		if(size(remainderList)(2) > longestCycle)
			longestCycle = size(remainderList)(2);
			longestNumber = denominator;
		end
	end
end

%End the timer
endTime = clock();

%Print the results
printf("The longest cycle is %d digits long\n", longestCycle);
printf("It is started with the number %d\n", longestNumber);
printf("It took %f seconds to run this algorithm\n", etime(endTime, startTime));

end

function [found] = isFound(array, key)
	found = false;	%Start with a false. It only turns true if you find key in array
	for location = 1 : size(array)(2)
		if(key == array(location))
			found = true;
			return;
		end
	end
end

%{
Results:
The longest cycle is 982 digits long
It is started with the number 983
It took 49.173325 seconds to run this algorithm
%}