mirror of
https://bitbucket.org/Mattrixwv/projecteulerpython.git
synced 2025-12-06 17:43:58 -05:00
186 lines
6.1 KiB
Python
186 lines
6.1 KiB
Python
#ProjectEuler/Python/Problem18.py
|
|
#Matthew Ellison
|
|
# Created: 03-12-19
|
|
#Modified: 07-24-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
|
|
"""
|
|
#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
|
|
from collections import namedtuple
|
|
|
|
|
|
class Problem18(Problem):
|
|
#Structures
|
|
location = namedtuple("location", "xLocation yLocation total fromRight")
|
|
|
|
#Variables
|
|
__numRows = 15
|
|
__listNum = [[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]]
|
|
|
|
#Functions
|
|
#Constructor
|
|
def __init__(self) -> None:
|
|
super().__init__("Find the maximum total from top to bottom")
|
|
self.foundPoints = [] #For the points that I have already found the shortest distance to
|
|
self.possiblePoints = [] #For the locations you are checking this round
|
|
self.actualTotal = 0 #The true total of the path from the top to the bottom
|
|
|
|
#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()
|
|
|
|
|
|
#Invert the list so that each element = 100 - element
|
|
self.invert()
|
|
|
|
#Add the tip of the pyramid because everything has to go through that
|
|
self.foundPoints.append(self.location(0, 0, self.__listNum[0][0], True))
|
|
#Add the second row as possible points because everything must pass through the second row
|
|
self.possiblePoints.append(self.location(0, 1, (self.__listNum[0][0] + self.__listNum[1][0]), True))
|
|
self.possiblePoints.append(self.location(1, 1, (self.__listNum[0][0] + self.__listNum[1][1]), False))
|
|
foundBottom = False
|
|
|
|
#Loop until you find the bottom
|
|
while(not foundBottom):
|
|
#Check which possible point gives us the lowest number. If more than one has the same number simply keep the first one
|
|
minLoc = self.possiblePoints[0]
|
|
for loc in self.possiblePoints:
|
|
if(loc.total < minLoc.total):
|
|
minLoc = loc
|
|
|
|
#Remove it from the list of possible points
|
|
self.removeIf(self.possiblePoints, minLoc)
|
|
|
|
self.foundPoints.append(minLoc)
|
|
|
|
#Add to the list of possible points from the point we just found and
|
|
#If you are at the bottom raise the flag to end the program
|
|
xLoc = minLoc.xLocation
|
|
yLoc = minLoc.yLocation + 1
|
|
if(yLoc >= self.__numRows):
|
|
foundBottom = True
|
|
else:
|
|
self.possiblePoints.append(self.location(xLoc, yLoc, minLoc.total + self.__listNum[yLoc][xLoc], True))
|
|
xLoc += 1
|
|
self.possiblePoints.append(self.location(xLoc, yLoc, minLoc.total + self.__listNum[yLoc][xLoc], False))
|
|
|
|
#Get the real total of the journey
|
|
self.actualTotal = ((100 * self.__numRows) - self.foundPoints[len(self.foundPoints) - 1].total)
|
|
|
|
#Invert the list so it can be read again
|
|
self.invert()
|
|
|
|
|
|
#Stop the timer
|
|
self.timer.stop()
|
|
|
|
#Throw a flag to show the problem is solved
|
|
self.solved = True
|
|
|
|
#This function turns every number in the array into (100 - num) to allow you to find the largest numbers rather than the smallest
|
|
def invert(self) -> None:
|
|
for rowCnt in range(0, self.__numRows):
|
|
for colCnt in range(0, len(self.__listNum[rowCnt])):
|
|
self.__listNum[rowCnt][colCnt] = 100 - self.__listNum[rowCnt][colCnt]
|
|
|
|
#This function removes every element in listNum that is equal to loc
|
|
def removeIf(self, listNum: list, loc: tuple) -> None:
|
|
location = 0
|
|
while(location < len(listNum)):
|
|
if((listNum[location].xLocation == loc.xLocation) and (listNum[location].yLocation == loc.yLocation)):
|
|
del listNum[location]
|
|
else:
|
|
location += 1
|
|
|
|
#Reset the problem so it can be run again
|
|
def reset(self) -> None:
|
|
super().reset()
|
|
self.foundPoints.clear()
|
|
self.possiblePoints.clear()
|
|
self.actualTotal = 0
|
|
|
|
#Gets
|
|
#Returns the result of solving the problem
|
|
def getResult(self) -> str:
|
|
self.solvedCheck("result")
|
|
return f"The value of the longest path is {self.actualTotal}"
|
|
#Returns the pyramid that was traversed as a string
|
|
def getPyramid(self) -> str:
|
|
self.solvedCheck("pyramid of numbers")
|
|
pyramidString = ""
|
|
#Loop through all elements of the list and print them
|
|
for row in self.__listNum:
|
|
for column in row:
|
|
pyramidString += "{:02d}".format(column)
|
|
pyramidString += '\n'
|
|
return pyramidString
|
|
#Returns the trail the algorithm took as a string
|
|
def getTrail(self) -> str:
|
|
self.solvedCheck("trail of the shortest path")
|
|
#TODO: Implement this
|
|
return ""
|
|
#Returns the total that was asked for
|
|
def getTotal(self) -> int:
|
|
self.solvedCheck("total")
|
|
return self.actualTotal
|
|
|
|
|
|
""" Results:
|
|
The value of the longest path is 1074
|
|
It took an average of 422.974 microseconds to run this problem through 100 iterations
|
|
"""
|