ProjectEulerTS/Problems/Problem14.ts

//ProjectEulerTS/Problems/Problem14.ts
//Matthew Ellison
// Created: 03-26-21
//Modified: 07-14-21
/*
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Which starting number, under one million, produces the longest chain?
*/
//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 Problem14 extends Problem{
	//Variables
	//Static variables
	private static MAX_NUM: number = 1000000 - 1;	//This is the top number that you will be checking against the series
	//Instance variables
	private maxLength: number;	//This is the length of the longest chain
	private maxNum: number;		//This is the starting number of the longest chain

	//Functions
	//Constructor
	public constructor(){
		super(`Which starting number, under ${Problem14.MAX_NUM + 1}, produces the longest chain using the iterative sequence?`);
		this.maxLength = 0;
		this.maxNum = 0;
	}
	//Operational functions
	//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();


		//Loop through all numbers <= MAX_NUM and check them against the series
		for(let currentNum = 1;currentNum <= Problem14.MAX_NUM;++currentNum){
			let currentLength: number = this.checkSeries(currentNum);
			//If the current number has a longer series than the max then the current becomes the max
			if(currentLength > this.maxLength){
				this.maxLength = currentLength;
				this.maxNum = currentNum;
			}
		}


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

		//Throw a flag to show the problem is solved
		this.solved = true;
	}
	//This function follows the rules of the sequence and returns its length
	private checkSeries(num: number): number{
		let length: number = 1;	//Start at 1 because you need to count the starting number

		//Follow the series, adding 1 for each step you take
		while(num > 1){
			if((num % 2) == 0){
				num /= 2;
			}
			else{
				num = (3 * num) + 1;
			}
			++length;
		}

		//Returns the length of the series
		return length;
	}
	//Reset the problem so it can be run again
	public reset(): void{
		super.reset();
		this.maxLength = 0;
		this.maxNum = 0;
	}
	//Returns the result of solving the problem
	public getResult(): string{
		this.solvedCheck("result");
		return `The number ${this.maxNum} produced a chain of ${this.maxLength} steps`;
	}
	//Returns the length of the requested chain
	public getLength(): number{
		this.solvedCheck("length of the longest chain");
		return this.maxLength;
	}
	//Returns the starting number of the requested chain
	public getStartingNumber(): number{
		this.solvedCheck("starting number of the longest chain");
		return this.maxNum;
	}
}


/* Results:
The number 837799 produced a chain of 525 steps
It took an average of 1.178 seconds to run this problem through 100 iterations
*/