ProjectEulerTS/Problems/Problem28.ts

//ProjectEulerTS/Problems/Problem28.ts
//Matthew Ellison
// Created: 05-26-21
//Modified: 07-14-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 non-standard includes are my own creation and available from https://bibucket.org/Mattrixwv/typescriptClasses
/*
	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/>.
*/


import { Problem } from "./Problem";


export class Problem28 extends Problem{
	//Variables
	//Static variables
	private static grid: number[][];	//Holds the grid that we will be filling and searching
	//Instance variables
	private sumOfDiagonals: number;	//Holds the sum of the diagonals of the grid

	//Functions
	//Constructor
	public constructor(){
		super(`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 diration`);
		this.sumOfDiagonals = 0;
	}
	//Operational functions
	//Sets up the grid
	private setupGrid(): void{
		Problem28.grid = [];
		//Fill the grid with 0's
		for(let cnt = 0;cnt < 1001;++cnt){
			Problem28.grid.push([]);
			for(let cnt2 = 0;cnt2 < 1001;++cnt2){
				Problem28.grid[cnt].push(0);
			}
		}

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

			//Move left until you reach a blank location above
			while(Problem28.grid[yLocation - 1][xLocation] != 0){
				Problem28.grid[yLocation][xLocation] = currentNum++;
				--xLocation;
			}

			//Move up until you reach a blank location to the right
			while(Problem28.grid[yLocation][xLocation + 1] != 0){
				Problem28.grid[yLocation][xLocation] = currentNum++;
				--yLocation;
			}

			//Move right until you reach a blank location below
			while(Problem28.grid[yLocation + 1][xLocation] != 0){
				Problem28.grid[yLocation][xLocation] = currentNum++;
				++xLocation;
				//Check if you are at the final location and break the loop if you are
				if(xLocation == Problem28.grid.length){
					finalLocation = true;
					break;
				}
			}
		}
	}
	//Finds the sum of the diagonals in the grid
	private findSum(): void{
		//Start at the top corners and work your way down moving toward the opposite side
		let leftSide: number = 0;
		let rightSide: number = Problem28.grid.length - 1;
		let row: number = 0;
		while(row < Problem28.grid.length){
			//This ensures the middle location is only counted once
			if(leftSide == rightSide){
				this.sumOfDiagonals += Problem28.grid[row][leftSide];
			}
			else{
				this.sumOfDiagonals += Problem28.grid[row][leftSide];
				this.sumOfDiagonals += Problem28.grid[row][rightSide];
			}
			++row;
			++leftSide;
			--rightSide;
		}
	}
	//Solve the problem
	public solve(): void{
		//If the problem has already been solved do nothing and end the function
		if(this.solved){
			return;
		}

		//Start the timer
		this.timer.start();


		//Setup the grid
		this.setupGrid();
		//FInd the sum of the diagonals in the grid
		this.findSum();


		//Stop the timer
		this.timer.stop();

		//Throw a flag to show the problem is solved
		this.solved = true;
	}
	//Reset the problem so it can be run again
	public reset(): void{
		super.reset();
		this.sumOfDiagonals = 0;
	}
	//Gets
	//Returns the result of solving the problem
	public getResult(): string{
		this.solvedCheck("result");
		return `The sum of the diagonals in the given grid is ${this.sumOfDiagonals}`;
	}
	//Returns the grid
	public getGrid(): number[][]{
		this.solvedCheck("grid");
		return Problem28.grid;
	}
	//Returns the sum of the diagonals
	public getSum(): number{
		this.solvedCheck("sum");
		return this.sumOfDiagonals;
	}
}


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