--luaClasses/Algorithms.lua
--Matthew Ellison
-- Created: 02-04-19
--Modified: 06-30-21
--This is a file of algorithms that I have found it useful to keep around at all times
--[[
	Copyright (C) 2021  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/>.
]]


--This function returns a list with all the primes numbers <= goalNumber
function getPrimes(goalNumber)
	local primes = {};	--Holds the prime numbers
	local foundFactor = false;

	--If the number is 0 or negative return an empty table
	if(goalNumber <= 1) then
		return primes;
	--Otherwise the number is at lease 2, therefore 2 should be added to the list
	else
		primes[#primes + 1] = 2;
	end

	--We can now start at 3 and skip all even numbers, because they cannot be prime
	for possiblePrime=3,goalNumber,2 do
		--Check all current primes, up to sqrt(possiblePrime), to see if there is a divisor
		local primesCnt = 1;
		--We can safely assume that there will be at least 1 element in the primes list because of 2 being added before the loop
		local topPossibleFactor = math.ceil(math.sqrt(possiblePrime))
		while(primes[primesCnt] <= topPossibleFactor) do
			if((possiblePrime % primes[primesCnt]) == 0) then
				foundFactor = true;
				break;
			else
				primesCnt = primesCnt + 1;
			end
			--Check if the index has gone out of range
			if(primesCnt >= #primes) then
				break;
			end
		end

		--If you didn't find a factor then the current number must be prime
			if(not foundFactor) then
				primes[#primes + 1] = possiblePrime;
			else
				foundFactor = false;
			end
	end

	--Sort the array just to be neat and safe
	table.sort(primes);

	--Return the array
	return primes;
end

--This function gets a specific number of primes
function getNumPrimes(numberOfPrimes)
	local primes = {};	--Holds the prime numbers
	local foundFactor = false;

	--If the number is 0 or negative return an empty table
	if(numberOfPrimes <= 1) then
		return primes;
	--Otherwise the number is at lease 2, therefore 2 should be added to the list
	else
		primes[#primes + 1] = 2;
	end

	--We can now start at 3 and skip all even numbers, because they cannot be prime
	local possiblePrime = 3;
	while((#primes < numberOfPrimes) and (possiblePrime >= 0)) do
		--Check all current primes, up to sqrt(possiblePrime), to see if there is a divisor
		local primesCnt = 1;
		--We can safely assume that there will be at least 1 element in the primes list because of 2 being added before the loop
		local topPossibleFactor = math.ceil(math.sqrt(possiblePrime))
		while(primes[primesCnt] <= topPossibleFactor) do
			if((possiblePrime % primes[primesCnt]) == 0) then
				foundFactor = true;
				break;
			else
				primesCnt = primesCnt + 1;
			end
			--Check if the index has gone out of range
			if(primesCnt >= #primes) then
				break;
			end
		end

		--If you didn't find a factor then the current number must be prime
		if(not foundFactor) then
			primes[#primes + 1] = possiblePrime;
		else
			foundFactor = false;
		end

		--Advance to the next possible prime number
		possiblePrime = possiblePrime + 2;
	end

	--Sort the array just to be neat and safe
	table.sort(primes);

	--Return the array
	return primes;
end

--This function determines whether the number passed into it is a prime
function isPrime(possiblePrime)
	if(possiblePrime <= 3) then
		return possiblePrime > 1;
	elseif(((possiblePrime % 2) == 0) or ((possiblePrime % 3) == 0)) then
		return false;
	end
	for cnt = 5, math.sqrt(possiblePrime) + 1, 6 do
		if(((possiblePrime % cnt) == 0) or ((possiblePrime % (cnt + 2)) == 0)) then
			return false;
		end
	end
	return true;
end

--This is a function that returns all the factors of goalNumber
function getFactors(goalNumber)
	local primes = getPrimes(math.ceil(math.sqrt(goalNumber)));	--Get all the primes up the largest possible divisor
	local factors = {};	--Holds all the factors

	--You need to step through each prime and see if it is a factor of the number
	local cnt = 1;
	while((cnt <= #primes) and (goalNumber > 1)) do
		--If the prime is a factor you need to add it to the factor list
		if((goalNumber % primes[cnt]) == 0) then
			factors[#factors + 1] = primes[cnt];
			goalNumber = goalNumber / primes[cnt];
		--Otherwise advance the location in the primes array you are looking at
		--By not advancing if the primes is a factor you allow for multiple of the same prime number as a factor
		else
			cnt = cnt + 1
		end
	end

	--If you didn't get any factors the number itself must be a prime number
	if(#factors == 0) then
		factors[#factors + 1] = goalNumber;
		goalNumber = 1
	end

	--If your some reason teh goalNumber is not 1 print an error message
	if(goalNumber > 1) then
		print("There was an error in getFactors(). A leftover of " .. goalNumber);
	end

	--Return the list of factors
	return factors;
end

--This is a function the returns all divisors of the number passed to it
function getDivisors(goalNumber)
	local divisors = {};
	--Start by checking that the number is positive
	if(goalNumber <= 0) then
		return divisors;
	--If the number is 1 return just itself
	elseif(goalNumber == 1) then
		divisors[#divisors+1] = 1;
	end

	--Start at 3 and loop through all numbers < (goalNumber / 2) looking for a number that divides it evenly
	local topPossibleDivisor = math.ceil(math.sqrt(goalNumber));
	local possibleDivisor = 1;
	while(possibleDivisor <= topPossibleDivisor) do
		--If you find one add it and the number it creates to the list
		if((goalNumber % possibleDivisor) == 0) then
			divisors[#divisors+1] = possibleDivisor;
			--Account for the possibility of sqrt(goalNumber) being a divisor
			if(possibleDivisor ~= topPossibleDivisor) then
				divisors[#divisors + 1] =(goalNumber / possibleDivisor);
			end
			--Take care of a few occations where a number was added twice
			if(divisors[#divisors] == (possibleDivisor + 1)) then
				possibleDivisor = possibleDivisor + 1;
			end
		end
		possibleDivisor = possibleDivisor + 1;
	end
	--Sort the list before returning for neatness
	table.sort(divisors);
	--Return the list
	return divisors;
end

--This function returns the numth Fibonacci number
function getFib(goalSubscript)
	--Setup the variables
	local fibNums = {1, 1, 0};	--A list to keep track of the Fibonacci Numbers. It need only be 3 long because we only need the one we are working on and the last 2

	--If the number is <= 0 return 0
	if(goalSubscript <= 0) then
		return 0;
	end

	--Loop through the list, generating Fibonacci numbers until it finds the correct subscript
	local fibLoc = 2;
	while(fibLoc <= goalSubscript) do
		fibNums[(fibLoc % 3) + 1] = fibNums[((fibLoc - 1) % 3) + 1] + fibNums[((fibLoc - 2) % 3) + 1];
		fibLoc = fibLoc + 1;
	end

	--Return the propper number
	local answerLocation = ((fibLoc - 1) % 3);
	if(answerLocation == 0) then
		answerLocation = 3;
	end
	return fibNums[answerLocation];
end

function getLargeFib(goalSubscript)
	local bigint = require "bigint";
	--Setup the variables
	local fibNums = {bigint.new(1), bigint.new(1), bigint.new(0)};

	--If the number <= 0 return 0
	if(goalSubscript <= 0) then
		return bigint.new(0);
	end

	--Loop through the list, generating Fibonacci numbers until it finds the correct subscript
	local fibLoc = 2;
	while(fibLoc <= goalSubscript) do
		fibNums[(fibLoc % 3) + 1] = bigint.add(fibNums[((fibLoc - 1) % 3) + 1], fibNums[((fibLoc - 2) % 3) + 1]);
		fibLoc = fibLoc + 1;
	end

	--Return the propper number
	local answerLocation = ((fibLoc - 1) % 3);
	if(answerLocation == 0) then
		answerLocation = 3;
	end
	return fibNums[answerLocation];
end

function getSum(ary)
	local sum = 0;	--Holds the sum of all elements. Start at 0 because num+1 = num
	--Look through every element in the array and add the number to the running sum
	for location = 1, #ary do
		sum = sum + ary[location];
	end
	--Return the sum of all elements
	return sum;
end

function getProd(ary)
	if((ary == nil) or (#ary == 0)) then
		return 0;
	end
	local prod = 1;	--Holds the product of all elements. Start at 1 because num*1 = num
	--Look through every element in the array and add the number to the running product
	for location = 1, #ary do
		prod = prod * ary[location];
	end
	--Return the product of all elements
	return prod;
end

function getPermutations(master, num)
	--If no num was given make it 0
	local num = num or 1
	local perms = {};
	--Check if the number is out of bounds
	if((num > string.len(master)) or (num <= 0)) then
		--Do nothing and return an empty list
		perms = {};
	--If this is the last possible recurse just return the current string
	elseif(num == string.len(master)) then
		perms[#perms + 1] = master;
	--If there are more possible recurses, recurse with the current permutations
	else
		local temp = getPermutations(master, num + 1);
		--Add the elements of temp to perms
		for loc = 1, #temp do
			perms[#perms + 1] = temp[loc]
		end
		--You need to swap the current letter with every possible letter after it
		--The ones needed to swap before will happen automatically when the function recurses
		for cnt = 1, (string.len(master) - num) do

			--Swap two elements
			--Turn it into byte array so you can change values
			local tempStr = {};
			for loc = 1, #master do
				tempStr[loc] = string.byte(master:sub(loc, loc));
			end

			--Swap the two elements
			local tempChar = tempStr[num];
			tempStr[num] = tempStr[num + cnt];
			tempStr[num + cnt] = tempChar;
			--Change it back to a string
			master = "";
			for loc = 1, #tempStr do
				master = master .. string.char(tempStr[loc]);
			end

			--Get the permutations after swapping two elements
			temp = getPermutations(master, num + 1);
			--Add the elements of temp to perms
			for loc = 1, #temp do
				perms[#perms + 1] = temp[loc]
			end

			--Swap the elements back
			--Turn it into byte array so you can change values
			tempStr = {};
			for loc = 1, #master do
				tempStr[loc] = string.byte(master:sub(loc, loc));
			end
			--Swap the two elements
			tempChar = tempStr[num];
			tempStr[num] = tempStr[num + cnt];
			tempStr[num + cnt] = tempChar;
			--Change it back to a string
			master = "";
			for loc = 1, #tempStr do
				master = master .. string.char(tempStr[loc]);
			end
		end
	end

	--The array is not necessarily in alpha-numeric order. So if this is the full array sort it before returning
	if(num == 1) then
		table.sort(perms);
	end

	--Return the list
	return perms;
end

function isFound(ary, key)
	for cnt = 1, #ary do
		if(ary[cnt] == key) then
			return true;
		end
	end
	return false;
end

function gcd(num1, num2)
	while((num1 ~= 0) and (num2 ~= 0)) do
		if(num1 > num2) then
			num1 = num1 % num2;
		else
			num2 = num2 % num1;
		end
	end
	return num1 | num2;
end

function factorial(num)
	local fact = 1;
	for cnt = 1, num do
		fact = fact * cnt;
	end
	return fact;
end

--Returns true if the string passed in is a palindrome
function isPalindrome(str)
	local rev = string.reverse(str);
	if(str == rev) then
		return true;
	else
		return false;
	end
end

--Converts a number to its binary equivalent
function toBin(num)
	--Convert the number to a binary string
	local binNum = "";
	while(num > 0) do
		local rest = math.fmod(num, 2);
		if(rest == 1) then
			binNum = binNum .. "1";
		else
			binNum = binNum .. "0";
		end
		num = (num - rest) / 2;
	end
	binNum = string.reverse(binNum);
	if(binNum == "") then
		binNum = "0";
	end
	return binNum;
end

--Print a table
function printTable(ary)
	local tableString = "[";
	for cnt = 1, #ary do
		tableString = tableString .. tostring(ary[cnt]);
		if(cnt < #ary) then
			tableString = tableString .. ", ";
		end
	end
	tableString = tableString .. "]";
	return tableString;
end