""" Copyright 2012, July 31
	Written by Pattarapol (Cheer) Iamngamsup
	E-mail:  IAM.PATTARAPOL@GMAIL.COM
	
	Largest product in a grid
	Problem 11
	
	In the 20 X 20 grid below, four numbers
	along a diagonal line have been marked in red.

	08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
	49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
	81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
	52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
	22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
	24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
	32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
	67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
	24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
	21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
	78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
	16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
	86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
	19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
	04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
	88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
	04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
	20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
	20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
	01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

	The product of these numbers is 26  63  78  14 = 1788696.

	What is the greatest product of four adjacent numbers in any direction 
	(up, down, left, right, or diagonally) in the 20 X 20 grid?
"""

#################################################
#   Importing libraries & modules
import datetime

#################################################
#   Global variables
ADJACENT_NUM = 4
ROW_NUM = 20
COL_NUM = 20

GridNumberStr =  '08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 '
GridNumberStr += '49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 '
GridNumberStr += '81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 '
GridNumberStr += '52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 '
GridNumberStr += '22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 '
GridNumberStr += '24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 '
GridNumberStr += '32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 '
GridNumberStr += '67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 '
GridNumberStr += '24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 '
GridNumberStr += '21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 '
GridNumberStr += '78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 '
GridNumberStr += '16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 '
GridNumberStr += '86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 '
GridNumberStr += '19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 '
GridNumberStr += '04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 '
GridNumberStr += '88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 '
GridNumberStr += '04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 '
GridNumberStr += '20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 '
GridNumberStr += '20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 '
GridNumberStr += '01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 '

#################################################
#   Functions

#################################################
#   Classes

#################################################
#   Main function
def main():
	numberStrList = GridNumberStr.split()
	numList = list()
	for index in range( 0, len( numberStrList ) ):
		numList.append( int( numberStrList[index] ) )

	greatestProduct = 0
	adjacentProduct = 0
	for i in range( 0, ROW_NUM ):
		for j in range( 0, COL_NUM ):
			# left to right
			if j + ( ADJACENT_NUM - 1 ) < COL_NUM:
				adjacentProduct = ( numList[ ROW_NUM * i + j ] 
									* numList[ ROW_NUM * i + j + 1 ] 
									* numList[ ROW_NUM * i + j + 2 ] 
									* numList[ ROW_NUM * i + j + 3 ] )
				if adjacentProduct > greatestProduct:
					greatestProduct = adjacentProduct
					
			########################
			# up to down
			if i + ( ADJACENT_NUM - 1 ) < ROW_NUM:
				adjacentProduct = ( numList[ ROW_NUM * i + j ] 
									* numList[ ROW_NUM * i + 1 + j ] 
									* numList[ ROW_NUM * i + 2 + j ] 
									* numList[ ROW_NUM * i + 3 + j ] )
				if adjacentProduct > greatestProduct:
					greatestProduct = adjacentProduct
			
			########################
			# diagnal left to right
			if j + ( ADJACENT_NUM - 1 ) < COL_NUM \
				and i + ( ADJACENT_NUM - 1) < ROW_NUM:
				
				adjacentProduct = ( numList[ ROW_NUM * i + j ] 
									* numList[ ROW_NUM * ( i + 1 ) + j + 1 ] 
									* numList[ ROW_NUM * ( i + 2 ) + j + 2 ] 
									* numList[ ROW_NUM * ( i + 3 ) + j + 3 ] ) 
				if adjacentProduct > greatestProduct:
					greatestProduct = adjacentProduct
					
			########################
			# diagnal right to left
			if j - ( ADJACENT_NUM - 1 ) > 0 \
				and i + ( ADJACENT_NUM - 1 ) < ROW_NUM:
				
				adjacentProduct = ( numList[ ROW_NUM * i + j ] 
									* numList[ ROW_NUM * ( i + 1 ) + j - 1 ] 
									* numList[ ROW_NUM * ( i + 2 ) + j - 2 ] 
									* numList[ ROW_NUM * ( i + 3 ) + j - 3 ] ) 
				if adjacentProduct > greatestProduct:
					greatestProduct = adjacentProduct
	
	print( 'answer = {0}'.format( greatestProduct ) )

#################################################
#   Main execution
if __name__ == '__main__':
	#   get starting date time
	startingDateTime = datetime.datetime.utcnow()
	print( 'startingDateTime = {0} UTC'.format( startingDateTime ) )

	#   call main function
	main()

	#   get ending date time
	endingdateTime = datetime.datetime.utcnow()
	print( 'endingdateTime = {0} UTC'.format( endingdateTime ) )

	#   compute delta date time
	deltaDateTime = endingdateTime - startingDateTime
	print( 'deltaDateTime = {0}'.format( deltaDateTime ) )
