ProjectEulerTS/Problems/Problem33.ts

//ProjectEulerTS/Problems/Problem33.ts
//Matthew Ellison
// Created: 05-28-21
//Modified: 07-14-21
/*
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s
We shall consider fractions like, 30/50 = 3/5, to be trivial examples
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator
If the product of these four fractions is given in its lowest common terms, find the value of the denominator
*/
//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 { getProd } from "../../../Typescript/typescriptClasses/ArrayAlgorithms";
import { gcd } from "../../../Typescript/typescriptClasses/NumberAlgorithms";
import { Problem } from "./Problem";


export class Problem33 extends Problem{
	//Variables
	//Static variables
	private static MIN_NUMERATOR: number = 10;	//The lowest the numerator can be
	private static MAX_NUMERATOR: number = 98;	//The highest the numerator can be
	private static MIN_DENOMINATOR: number = 11;	//The lowest the denominator can be
	private static MAX_DENOMINATOR: number = 99;	//THe highest the denominator can be
	//Instance variables
	private numerators: number[];	//Holds the numerators that were found
	private denominators: number[];	//Holds the denominators that were found
	private prodDenominator: number;	//Holds the answer to the question

	//Functions
	//Constructor
	public constructor(){
		super("If the product of these four fractions is given in its lowest common terms, find the value of the denominator");
		this.prodDenominator = 1;
		this.numerators = [];
		this.denominators = [];
	}
	//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();


		//Search every possible numerator/denominator pair
		for(let denominator = Problem33.MIN_DENOMINATOR;denominator <= Problem33.MAX_DENOMINATOR;++denominator){
			for(let numerator = Problem33.MIN_NUMERATOR;(numerator < denominator) && (numerator <= Problem33.MAX_NUMERATOR);++numerator){
				let denom = denominator.toString();
				let num = numerator.toString();
				let tempNum: number = 0;
				let tempDenom: number = 1;

				//Check that this isn't a trivial example
				if((num[1] == "0") && (denom[1] == "0")){
					continue;
				}
				//Remove the offending digits if they exist
				else if(num[0] == denom[0]){
					tempNum = parseInt(num[1]);
					tempDenom = parseInt(denom[1]);
				}
				else if(num[0] == denom[1]){
					tempNum = parseInt(num[1]);
					tempDenom = parseInt(denom[0]);
				}
				else if(num[1] == denom[0]){
					tempNum = parseInt(num[0]);
					tempDenom = parseInt(denom[1]);
				}
				else if(num[1] == denom[1]){
					tempNum = parseInt(num[0]);
					tempDenom = parseInt(denom[0]);
				}

				//Test if the new fraction is the same as the old one
				if((tempNum / tempDenom) == (numerator / denominator)){
					this.numerators.push(numerator);
					this.denominators.push(denominator);
				}
			}
		}

		//Get the product of the numbers
		let numProd: number = getProd(this.numerators);
		let denomProd: number = getProd(this.denominators);
		//Get the gcd to reduce to lowest terms
		let curGcd = gcd(numProd, denomProd);
		//Save the denominator
		this.prodDenominator = denomProd / curGcd;


		//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.numerators = [];
		this.denominators = [];
	}
	//Gets
	//Returns the reult of solving the problem
	public getResult(): string{
		this.solvedCheck("result");
		return `The denominator of the product is ${this.prodDenominator}`;
	}
	//Returns the list of numerators
	public getNumerators(): number[]{
		this.solvedCheck("list of numerators");
		return this.numerators;
	}
	//Returns the list of denominators
	public getDenominators(): number[]{
		this.solvedCheck("list of denominators");
		return this.denominators;
	}
	//Returns the answer to the question
	public getProdDenominator(){
		this.solvedCheck("denominator");
		return this.prodDenominator;
	}
}


/* Results:
The denominator of the product is 100
It took an average of 508.730 microseconds to run this problem through 100 iterations
*/