#ProjectEuler/Python/Problem23.py
#Matthew Ellison
# Created: 03-22-19
#Modified: 07-24-21
#Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers
#All of my 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 Problem23(Problem):
	#Variables
	__maxNum = 28123

	#Functions
	#Constructor
	def __init__(self) -> None:
		super().__init__("Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers")
		self.divisorSums = []
		self.reserveArray()
		self.sum = 0

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


		#Get the sum of the divisors of all numbers < __maxNum
		for cnt in range(1, self.__maxNum):
			div = NumberAlgorithms.getDivisors(cnt)
			if(len(div) > 1):
				div.remove(div[len(div) - 1])
			self.divisorSums[cnt] = sum(div)

		#Get the abundant numbers
		abund = []
		for cnt in range(0, len(self.divisorSums)):
			if(self.divisorSums[cnt] > cnt):
				abund.append(cnt)

		#Check if each number can be the sum of 2 abundant numbers and add to the sum if no
		self.sum = 0
		for cnt in range(1, self.__maxNum):
			if(not self.isSum(abund, cnt)):
				self.sum += cnt


		#Stop the timer
		self.timer.stop()

		#Throw a flag to show the problem is solved
		self.solved = True
	#Reserve the size of the array to speed up insertion
	def reserveArray(self) -> None:
		#Make sure every element has a 0 in it's location
		for _ in range(0, self.__maxNum):
			self.divisorSums.append(0)
	#A function that returns true if num can be created by adding two elements from abund and false if it cannot
	def isSum(self, abund: list, num: int) -> bool:
		sumOfNums = 0
		#Pick a number for the first part of the sum
		for firstNum in range(0, len(abund)):
			#Pick a number for the second part of the sum
			for secondNum in range(0, len(abund)):
				sumOfNums = abund[firstNum] + abund[secondNum]
				if(sumOfNums == num):
					return True
				elif(sumOfNums > num):
					break
		#If you have run through the entire list and did not find a sum then it is false
		return False
	#Reset the problem so it can be run again
	def reset(self) -> None:
		super().reset()
		self.divisorSums.clear()
		self.reserveArray()
		self.sum = 0

	#Gets
	#Returns the result of solving the problem
	def getResult(self) -> str:
		self.solvedCheck("result")
		return f"The answer is {self.sum}"
	#Returns the sum of the numbers asked for
	def getSum(self) -> int:
		self.solvedCheck("sum")
		return self.sum


""" Results:
The answer is 4179871
It took an average of 24.184 minutes to run this problem through 10 iterations
"""