mirror of
https://bitbucket.org/Mattrixwv/projecteulerts.git
synced 2025-12-06 17:43:59 -05:00
215 lines
7.2 KiB
TypeScript
215 lines
7.2 KiB
TypeScript
//ProjectEulerTS/Problems/Problem18.ts
|
|
//Matthew Ellison
|
|
// Created: 04-05-21
|
|
//Modified: 07-14-21
|
|
//Find the maximum total from top to bottom
|
|
/*
|
|
75
|
|
95 64
|
|
17 47 82
|
|
18 35 87 10
|
|
20 04 82 47 65
|
|
19 01 23 75 03 34
|
|
88 02 77 73 07 63 67
|
|
99 65 04 28 06 16 70 92
|
|
41 41 26 56 83 40 80 70 33
|
|
41 48 72 33 47 32 37 16 94 29
|
|
53 71 44 65 25 43 91 52 97 51 14
|
|
70 11 33 28 77 73 17 78 39 68 17 57
|
|
91 71 52 38 17 14 91 43 58 50 27 29 48
|
|
63 66 04 68 89 53 67 30 73 16 69 87 40 31
|
|
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
|
|
*/
|
|
//This is done using a breadth first search
|
|
//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 Problem18 extends Problem{
|
|
//Variables
|
|
//Static variables
|
|
protected static list: number[][] = [[75],
|
|
[95, 64],
|
|
[17, 47, 82],
|
|
[18, 35, 87, 10],
|
|
[20, 4, 82, 47, 65],
|
|
[19, 1, 23, 75, 3, 34],
|
|
[88, 2, 77, 73, 7, 63, 67],
|
|
[99, 65, 4, 28, 6, 16, 70, 92],
|
|
[41, 41, 26, 56, 83, 40, 80, 70, 33],
|
|
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
|
|
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
|
|
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
|
|
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
|
|
[63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
|
|
[ 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]];
|
|
//Instance variables
|
|
protected foundPoints: location[]; //For the points that you have already found the shortest distance to
|
|
protected possiblePoints: location[]; //For the locations you am checking this round
|
|
protected actualTotal: number; //The true total of the path from the top to the bottom
|
|
|
|
//Functions
|
|
//Constructor
|
|
public constructor(){
|
|
super("Find the maximum total from top to bottom");
|
|
this.foundPoints = [];
|
|
this.possiblePoints = [];
|
|
this.actualTotal = 0;
|
|
}
|
|
//Operational functions
|
|
//This function turns every number in the array into (100 - num) to allow you to find the largest numbers rather than the smallest
|
|
protected invert(list: number[][]): void{
|
|
//Loop through every row in the list
|
|
for(let rowCnt = 0;rowCnt < list.length;++rowCnt){
|
|
//Loop through every column in the list
|
|
for(let colCnt = 0;colCnt < list[rowCnt].length;++colCnt){
|
|
//The current element gets the value of 100 - value
|
|
list[rowCnt][colCnt] = 100 - list[rowCnt][colCnt];
|
|
}
|
|
}
|
|
}
|
|
//This function helps by removing the element that is the same as the minumum location
|
|
protected removeHelper(possiblePoints: location[], minLoc: location): location[]{
|
|
return possiblePoints.filter(loc => ((loc.xLocation != minLoc.xLocation) || (loc.yLocation != minLoc.yLocation)));
|
|
}
|
|
//Solve the problem
|
|
public solve(): void{
|
|
//If the problem has already been solved do nothing and end the function
|
|
if(this.solved){
|
|
return;
|
|
}
|
|
|
|
let workingList = JSON.parse(JSON.stringify((this.constructor as any).list));
|
|
|
|
//Start the timer
|
|
this.timer.start();
|
|
|
|
|
|
//Invert the list
|
|
this.invert(workingList);
|
|
|
|
//Add the first row as a found point because you have to go through the top element
|
|
this.foundPoints.push(new location(0, 0, workingList[0][0], false));
|
|
//Add the scond row as possible points
|
|
this.possiblePoints.push(new location(0, 1, (workingList[0][0] + workingList[1][0]), true));
|
|
this.possiblePoints.push(new location(1, 1, (workingList[0][0] + workingList[1][1]), false));
|
|
let foundBottom: boolean = false; //Used when you find a point at the bottom of the list
|
|
|
|
//Loop through the algorithm until you find the bottom of the list
|
|
while(!foundBottom){
|
|
//Check which possible point gives us the lowest number. If more than one has the same number simple keep the first one
|
|
let minLoc: location = this.possiblePoints[0];
|
|
for(let loc of this.possiblePoints){
|
|
if(loc.total < minLoc.total){
|
|
minLoc = loc;
|
|
}
|
|
}
|
|
|
|
//Remove it from the list of possible points
|
|
this.possiblePoints = this.removeHelper(this.possiblePoints, minLoc);
|
|
|
|
//Add that point to the list of found points
|
|
this.foundPoints.push(minLoc);
|
|
|
|
//Add to the list of possible pionts from the point we just found and
|
|
//If you are at the bottom raise the flag to end the program
|
|
let xLoc: number = minLoc.xLocation;
|
|
let yLoc: number = minLoc.yLocation + 1; //Add one because you will always be moving to the next row
|
|
if(yLoc >= workingList.length){
|
|
foundBottom = true;
|
|
}
|
|
else{
|
|
this.possiblePoints.push(new location(xLoc, yLoc, minLoc.total + workingList[yLoc][xLoc], true));
|
|
//Advance the x location to simulate going right
|
|
++xLoc;
|
|
//Check if x is out of bounds
|
|
if(xLoc < workingList[yLoc].length){
|
|
this.possiblePoints.push(new location(xLoc, yLoc, minLoc.total + workingList[yLoc][xLoc], true));
|
|
}
|
|
}
|
|
}
|
|
|
|
//Invert the list again so it is correct
|
|
this.invert(workingList);
|
|
|
|
//Save the results
|
|
//Get the correct total which wil be the inversion of the current one
|
|
this.actualTotal = ((100 * workingList.length) - this.foundPoints[this.foundPoints.length - 1].total);
|
|
|
|
|
|
//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.foundPoints = [];
|
|
this.possiblePoints = [];
|
|
this.actualTotal = 0;
|
|
}
|
|
//Gets
|
|
//Returns the result of solving the problem
|
|
public getResult(): string{
|
|
this.solvedCheck("result");
|
|
return `The value of the longest path is ${this.actualTotal}`;
|
|
}
|
|
//Returns the pyramid that was traversed as a string
|
|
public getPyramid(): string{
|
|
this.solvedCheck("pyramid of numbers");
|
|
return Problem18.list.toString();
|
|
}
|
|
//Returns the trail the algorithm took as a string
|
|
public getTrail(): string{
|
|
this.solvedCheck("trail of the shortest path");
|
|
//TODO:
|
|
return "";
|
|
}
|
|
//Returns the total that was asked for
|
|
public getTotal(): number{
|
|
this.solvedCheck("total");
|
|
return this.actualTotal;
|
|
}
|
|
}
|
|
|
|
//Used to keep track of where the best location came from
|
|
class location{
|
|
public xLocation: number;
|
|
public yLocation: number;
|
|
public total: number;
|
|
//Used originally for debugging so I could trace the path backwards
|
|
public fromRight: boolean;
|
|
public constructor(x: number, y: number, t: number, r: boolean){
|
|
this.xLocation = x;
|
|
this.yLocation = y;
|
|
this.total = t;
|
|
this.fromRight = r;
|
|
}
|
|
}
|
|
|
|
|
|
/* Results:
|
|
The value of the longest path is 1074
|
|
It took an average of 134.407 microseconds to run this problem through 100 iterations
|
|
*/
|