ProjectEulerPython/Problems/Problem28.py

#ProjectEuler/Python/Problem28.py
#Matthew Ellison
# Created: 09-22-19
#Modified: 07-24-21
#What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed by starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral
#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


class Problem28(Problem):
	#Variables
	grid = []
	#Functions
	#Constructor
	def __init__(self) -> None:
		super().__init__("What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed by starting with the number 1 and moving to the right in a clockwise direction?")
		self.sumOfDiagonals = 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()


		#Setup the grid
		self.grid = self.setupGrid()
		#Find the sum of the diagonals in the grid
		self.sumOfDiagonals = self.findSum()


		#Stop the timer
		self.timer.stop()

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

	#Sets up the grid
	def setupGrid(self) -> list:
		#Setup the grid to be the right size and fill it with 0's
		self.grid = [[0 for x in range(1001)] for y in range(1001)]

		finalLocation = False	#A flag to indicate if the final location to be filled has been reached
		currentNum = 1	#Set the number that is going to be put at each location
		#Start with the middle location and set it correctly and advance the tracker to the next number
		xLocation = 500
		yLocation = 500
		self.grid[yLocation][xLocation] = currentNum
		currentNum += 1
		#Move right the first time
		xLocation += 1
		#Move in a circular pattern until you reach the final location
		while(not finalLocation):
			#Move down until you reach a blank location on the left
			while(self.grid[yLocation][xLocation - 1] != 0):
				self.grid[yLocation][xLocation] = currentNum
				currentNum += 1
				yLocation += 1

			#Move left until you reach a blank location above
			while(self.grid[yLocation - 1][xLocation] != 0):
				self.grid[yLocation][xLocation] = currentNum
				currentNum += 1
				xLocation -= 1

			#Move up until you reach a blank location to the right
			while(self.grid[yLocation][xLocation + 1] != 0):
				self.grid[yLocation][xLocation] = currentNum
				currentNum += 1
				yLocation -= 1

			#Move right until you reach a blank location below
			while(self.grid[yLocation + 1][xLocation] != 0):
				self.grid[yLocation][xLocation] = currentNum
				currentNum += 1
				xLocation += 1
				#Check if you are at the final location and break the loop if you are
				if(xLocation == len(self.grid)):
					finalLocation = True
					break
		return self.grid

	#Finds the sum of the diagonals in the grid
	def findSum(self) -> int:
		sumOfDiagonals = 0
		leftSide = 0
		rightSide = len(self.grid) - 1
		row = 0
		while(row < len(self.grid)):
			#This ensure the middle location is only counted once
			if(leftSide == rightSide):
				sumOfDiagonals += self.grid[row][leftSide]
			else:
				sumOfDiagonals += self.grid[row][leftSide]
				sumOfDiagonals += self.grid[row][rightSide]
			row += 1
			leftSide += 1
			rightSide -= 1
		return sumOfDiagonals

	#Reset the problem so it can be run again
	def reset(self) -> None:
		super().reset()
		self.sumOfDiagonals = 0

	#Gets
	#Returns the result of solving the problem
	def getResult(self) -> str:
		self.solvedCheck("result")
		return f"The sum of the diagonals in the given grid is {self.sumOfDiagonals}"
	#Returns the grid
	def getGrid(self) -> list:
		return self.grid
	#Returns the sum of the diagonals
	def getSum(self) -> int:
		self.solvedCheck("sum")
		return self.sumOfDiagonals


""" Results:
The sum of the diagonals in the given grid is 669171001
It took an average of 212.747 milliseconds to run this problem through 100 iterations
"""