ISourceCode

Make the frequent cases fast and the rare case correct

Problem 81 – Project Euler – Variant of Manhattan Tourist Problem

Problem 81 – Project Euler

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold and is equal to 2427.

131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331

Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

Have a look at my article about Manhattan Tourist Problem. This problem can be solved using Dynamic Programming.

# Problem 81 of Project Euler

Manhattan = [[131,673,234,103,18],[201,96,342,965,150],[630,803,746,422,111],[537,699,497,121,956],[805,732,524,37,331]]
	
Manhattan[0][0] = 131
# Compute the Horizontal end of each block total path i.e first row
for row in range(1, 5):
	Manhattan[row][0] = Manhattan[row-1][0] + Manhattan[row][0]
# Compute the Vertical end of each block total path i.e first column	
for col in range(1, 5):
	Manhattan[0][col] = Manhattan[0][col-1] + Manhattan[0][col]

	# Then fill in the rest of the table.
for row in range(1, 5):
	for col in range(1, 5):
					
		Manhattan[row][col] = min(Manhattan[row-1][col] + Manhattan[row][col], Manhattan[row][col-1] + Manhattan[row][col])

print  "The Minumum possible path :", Manhattan[4][4]

OUTPUT:

labuser@ubuntu:~$ python manhattan.py
The Minumum possible path : 2427

Since the Algorithm run time is O( nxm) for a nxm matrix so for 80×80 input matrix this algo would take O(n2) time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: