#ProjectEuler/Python/Problem21.py
#Matthew Ellison
# Created: 03-18-19
#Modified: 07-24-21
#Evaluate the sum of all the amicable numbers under 10000
#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 NumberAlgorithms


class Problem21(Problem):
	#Variables
	__limit = 10000	#The top number that will be evaluated

	#Functions
	#Constructor
	def __init__(self) -> None:
		super().__init__("Evaluate the sum of all the amicable numbers under 10000")
		self.divisorSum = []	#Holds the sum of the divisors of the subscript number
		self.amicable = []		#Holds all amicable numbers

	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()


		#Generate the divisors of all the numbers < 10000, get their sum, and add it to the list
		self.divisorSum.append(0)	#Start with a 0 in the [0] location
		for cnt in range(1, self.__limit):
			divisors = NumberAlgorithms.getDivisors(cnt)	#Get all the divisors of a number
			if(len(divisors) > 1):
				divisors.pop()	#Remove the last entry because it will be the number itself
			self.divisorSum.append(int(sum(divisors)))
		#Check every sum of divisors in the list for a matching sum
		for cnt in range(1, len(self.divisorSum)):
			currentSum = self.divisorSum[cnt]
			#If the sum is greater than the number of divisors then it is impossible to be amicable. Skip the number and continue
			if(currentSum >= len(self.divisorSum)):
				continue
			#We know that divisorSum[cnt] == currentSum, so if divisorSum[currentSum] == cnt we found an amicable number
			if(self.divisorSum[currentSum] == cnt):
				#A number can't be amicable with itself
				if(currentSum == cnt):
					continue
				#Add the number to the amicable vector
				self.amicable.append(cnt)


		#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.divisorSum.clear()
		self.amicable.clear()

	#Gets
	#Returns the result of solving the problem
	def getResult(self) -> str:
		self.solvedCheck("result")
		result = "All amicable numbers less than 10000 are\n"
		for num in self.amicable:
			result += f"{num}\n"
		result += f"The sum of all of these amicable numbers is {sum(self.amicable)}"

		return result
	#Returns a vector with all of the amicable number calculated
	def getAmicable(self) -> list:
		self.solvedCheck("amicable numbers")
		return self.amicable
	#Returns the sum of all of the amicable numbers
	def getSum(self) -> int:
		self.solvedCheck("sum of the amicable numbers")
		return sum(self.amicable)


""" Results:
All amicable numbers less than 10000 are
220
284
1184
1210
2620
2924
5020
5564
6232
6368
The sum of all of these amicable numbers is 31626
It took an average of 54.769 milliseconds to run this problem through 100 iterations
"""