'''
April Math Puzzler Solution
Dave Vogel - dvogel003@monroecc.edu
5/2/16
http://web.monroecc.edu/MathPuzzler/May16puzzle
Consider the grid shown in the figure below. How many different ways
are there to get from point A (the bottom left corner) to point B
(the top right corner) if you must move along the gridlines in
combinations of only upward and rightward moves?
(7,0) ----------------------------- B
| | | | | | | |
(6,0) ----------------------------- (6,7)
| | | | | | | |
-----------------------------
| | | | | |
--------- . . ---------
| | | | | |
--------- . . ---------
| | | | | |
-----------------------------
| | | | | | | |
---------------------------- (1,7)
| | | | | | | |
A ---------------------------- (0,7)
(0,0)
'''
import random #For the random walk solution
import itertools as it #For the test all possibilities solution
class Point:
'''
A Point is a vertice in the puzzle grid. Each point has a row, column,
pointer to the Point at the vertex to the right and a pointer to the
Point at the vertex above, if they exist. If either contiguous point
does not exist, the pointer is set to ''.
'''
def __init__(self, r, c, rLink, uLink):
self.row = r
self.col = c
self.rightLink = rLink
self.upLink = uLink
def __repr__(self):
'''
Text representation of a Point showing is row and column
'''
return "(" + str(self.row) + ", " + str(self.col) +")"
###End class Point
def findPoint(r, c, list):
'''
Find the Point at (R, C) in the list of Points. Return the Point
or '' if point doesn't exist.
'''
for point in list:
if point.row == r and point.col == c:
return point
return ''
def rectanglePaths(rows, columns):
'''
Create a list of the up/right step possibilities in a grid of shape
(rows x columns) to transverse the rectangle diagonally. First create a
larger list of all combinations of 0's and 1's where 0 represents
an UP step and a 1 represents a RIGHT step. Then whittle the list
by keeping only the ones that have (rows) UPs and (columns) RIGHTs.
Returns a list of the valid paths
'''
direction = ['r','u'] #Direction right (0), up (1)
paths = [] #List of valid paths
#Create the set of all possible combinations of a list of zeros
# and ones.
allCombinations = it.product([0,1], repeat=(rows+columns))
#We are only interested in the entries that have row zeros and
# column ones
for path in allCombinations:
if sum(path) == rows:
#Convert the list of ones and zeros to a string of r's and u's
pathString = ''.join(direction[e] for e in path)
paths.append(pathString)
return paths
def findValidPaths():
'''
Creates a list of all possible paths through a 7x7 grid (without
the central obstruction) then test each to see if it is a valid
path for this puzzle grid.
Returns a list of the valid paths through the puzzle grid.
'''
validPathsList = []
#Get all paths if there is no center obstruction
allPaths = rectanglePaths(7,7)
#Find the ones that are valid for this puzzle
for pathString in allPaths:
#Test if the path is valid and if so, add to validPathsList
if testPath(pathString):
validPathsList.append(pathString)
return validPathsList
def testPath(string):
'''
Test the path represented by string to see if it is a valid path.
Return True if valid, otherwise False.
'''
point = findPoint(0, 0, listOfPoints)
for n in string:
#If point doesn't exist in the direction, return false and exit
if (n == "u" and point.upLink == "") or\
(n == "r" and point.rightLink == ""):
return False
#Else make point the next point and continue testing
elif n == "u":
point = point.upLink
else:
point = point.rightLink
return True
def makePoints():
'''
Create the list of the vertices in the puzzle grid.
Return the list.
'''
listOfPoints = []
#Create a list of all vertices in a 7x7 grid
for r in range(8):
for c in range(8):
listOfPoints.append(Point(r, c, 0, 0))
#Remove the ones in the center
listOfPoints.remove(findPoint(3, 3, listOfPoints))
listOfPoints.remove(findPoint(3, 4, listOfPoints))
listOfPoints.remove(findPoint(4, 3, listOfPoints))
listOfPoints.remove(findPoint(4, 4, listOfPoints))
#Create links for each Point. Link each Point to the Point to the right
# and the Point above. If the linking Point doesn't exist the link is
# set to ''
for n in listOfPoints:
n.upLink = findPoint(n.row+1, n.col, listOfPoints)
n.rightLink = findPoint(n.row, n.col+1, listOfPoints)
return listOfPoints
def randomPaths(listOfPoints, tries):
'''
Start at (0, 0) and take 14 random steps toward B. If the path was valid
add to the set of valid paths (routes). Since it is a set, there will be
no duplicates. If run for a sufficient number of times, all valid paths
will eventually be included and the length will give the number of
possible paths.
Returns the list of valid paths found
'''
routes = set() #The SET of valid paths (no dups)
for iterations in range(tries):
point = findPoint(0, 0, listOfPoints) #Start at A
pathString = ""
for step in range(14): #Each path is 14 steps
upPoint = point.upLink #Point above
rightPoint = point.rightLink #Point to the right
#Randomly choose the step, either UP or RIGHT
if random.randint(0,1) == 1:
#Try to step UP
if upPoint != "": #If upPoint is not "", step up
point = upPoint # make current point the new upper point
pathString += "u" # indicate we went UP
else: #If no upper point
point = rightPoint # then step right
pathString += "r"
else: #Otherwise, try to step RIGHT
if rightPoint != "": # ditto, as above...
point = rightPoint # ...
pathString += "r"
else:
point = upPoint
pathString += "u"
routes.add(pathString) #Add to the set
return routes
##MAIN PROGRAM STARTS HERE#################################
if __name__ == "__main__":
listOfPoints = makePoints() #Create the list of vertices
iterations = 100000 #Number of times to run the random walk
#Get the number of paths with a random walk sequence
print("1) Doing a random walk through the puzzle for " + str(iterations) +\
"\ntrips. This takes a while, please be patient.")
routes = randomPaths(listOfPoints, iterations)
print("\nFound: " + str(len(routes)) + " valid paths.")
#Get the number of paths by generating the completely list of paths and testing
# for valid paths.
testSolution = findValidPaths()
print("\n\n2) Make a list of possible paths ignoring center obstruction\n" +
"and test each for validity.\n\nFound: " + str(len(testSolution)) +\
" valid paths.")
print("\nThe above two sets are equal? " + str(routes == set(testSolution)))
#Get the number of paths by counting the total number of paths without
# the central obstruction and then subtracting the invalid paths (the
# ones that path through Point(3,4) or Point(4,3).
totalPaths = str(len(rectanglePaths(7,7)))
pathAto34 = str(len(rectanglePaths(3,4)))
pathAto43 = str(len(rectanglePaths(4,3)))
print("\n\n3) Using combinations:")
print("\nNumber of paths A to Point(3,4) and\n" +\
"(from Point(3,4) to B): " + pathAto34)
print("\nNumber of paths A to Point(4,3) and\n" +\
"(from Point(4,3) to B): " + pathAto43)
print("\n\nNumber of total paths A to B without center the obstruction: " +\
totalPaths)
print('''\n Number of valid puzzle paths is equal to the total number of
paths without the obstructions minus the number of paths
that pass through Points(3,4) and (4,3). The paths through
Point(3,4) is the number of paths from A to Point(3,4) times
the number of paths from Point(3,4) to B (ditto for Point(4,3)).
''')
print ("\nNumber of valid paths = " + totalPaths + " - 2 * (" +\
pathAto34 + " * " + pathAto34 + ") = " +\
str(int(totalPaths) - 2 * int(pathAto34) * int(pathAto43)))