#ProjectEuler/Python/Problem33.py
#Matthew Ellison
# Created: 02-07-21
#Modified: 07-24-21
"""
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s
We shall consider fractions like, 30/50 = 3/5, to be trivial examples
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator
If the product of these four fractions is given in its lowest common terms, find the value of the denominator
"""
#Unless otherwise listed, all of my non-standard imports can be gotten from my pyClasses repository at https://bitbucket.org/Mattrixwv/pyClasses
"""
	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/>.
"""


from Problems.Problem import Problem
import ArrayAlgorithms


class Problem33(Problem):
	#Variables
	#Static variables
	__minNumerator = 10
	__maxNumerator = 98
	__minDenominator = 11
	__maxDenominator = 99
	#Instance variables
	__numerators = []
	__denominators = []
	prodDenominator = 1

	#Functions
	#Constructor
	def __init__(self) -> None:
		super().__init__("If the product of these four fractions is given in its lowest common terms, find the value of the denominator")

	#Operational Functions
	#Solve the problem
	def solve(self) -> None:
		#If the problem has already been solved do nothing and end the function
		if(self.solved):
			return

		#Start the timer
		self.timer.start()


		#Search every possible numerator/denominator pair
		for denominator in range(self.__minDenominator, self.__maxDenominator + 1):
			for numerator in range(self.__minNumerator, denominator):
				denom = str(denominator)
				num  = str(numerator)
				tempNum = 0
				tempDenom = 1

				#Check that this isn't a trivial example
				if((num[1] == '0') and (denom[1] == '0')):
					continue
				#Remove the offending digits if they exist
				elif(num[0] == denom[0]):
					tempNum = int(num[1])
					tempDenom = int(denom[1])
				elif(num[0] == denom[1]):
					tempNum = int(num[1])
					tempDenom = int(denom[0])
				elif(num[1] == denom[0]):
					tempNum = int(num[0])
					tempDenom = int(denom[1])
				elif(num[1] == denom[1]):
					tempNum = int(num[0])
					tempDenom = int(denom[0])
				if(tempDenom == 0):
					continue

				#Test if the new fraction is the same as the old one
				if((float(tempNum) / float(tempDenom)) == (float(numerator) / float(denominator))):
					self.__numerators.append(numerator)
					self.__denominators.append(denominator)

		#Get the product of the numbers
		numProd = ArrayAlgorithms.prod(self.__numerators)
		denomProd = ArrayAlgorithms.prod(self.__denominators)
		#Get the gcd to reduce to lowest terms
		gcd = ArrayAlgorithms.gcd(numProd, denomProd)
		#Save the denominator
		self.prodDenominator = int(denomProd / gcd)


		#Stop the timer
		self.timer.stop()

		#Throw a flag to show the problem is solved
		self.solved = True

	#Reset the problem so it can be run again
	def reset(self) -> None:
		super().reset()
		self.__numerators.clear()
		self.__denominators.clear()

	#Gets
	#Returns the result of solving the problem
	def getResult(self) -> str:
		self.solvedCheck("result")
		return f"The denominator of the product is {self.prodDenominator}"

	#Returns the list of numerators
	def getNumerators(self) -> list:
		self.solvedCheck("list of numerators")
		return self.__numerators

	#Returns the list of denominators
	def getDenominators(self) -> list:
		self.solvedCheck("list of denominators")
		return self.__denominator

	#Returns the answer to the question
	def getProdDenominator(self) -> int:
		self.solvedCheck("denominator")
		return self.prodDenominator


"""Results:
The denominator of the product is 100
It took an average of 5.130 milliseconds to run this problem through 100 iterations
"""