What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
try:
#open the file and read in the data
#at the end, rowCount and colCount
#will contain the number of rows and columns
gridValues = []
rowCount = 0
data = open("Problem_00011.data.txt")
line = data.readline()
while line:
values = line.split()
colCount = 0
#add a new row to the grid
gridValues.append([])
for value in values:
#append the value to the current row
gridValues[rowCount].append(int(value))
colCount += 1
rowCount += 1
line = data.readline()
finally:
data.close()
maxProduct = 0
#Number of adjacent values to check
numAdjacents = 4
i = 0
j = 0
while i < rowCount:
j = 0
while j < colCount:
product = 0
#check vertical product
if i <= rowCount - numAdjacents:
product = 1
k = 0
productFactors = []
while k < numAdjacents:
product *= gridValues[i + k][j]
productFactors.append(gridValues[i + k][j])
k += 1
if product > maxProduct:
maxProduct = product
maxProductInfo = "The max product is found at %d,%d with the numbers %s in the vertical down direction." % (i,j,productFactors)
#check horizontal product
if j <= colCount - numAdjacents:
product = 1
k = 0
productFactors = []
while k < numAdjacents:
product *= gridValues[i][j+k]
productFactors.append(gridValues[i][j+k])
k += 1
if product > maxProduct:
maxProduct = product
maxProductInfo = "The max product is found at %d,%d with the numbers %s in the horizontal right direction." % (i,j,productFactors)
#check down-right diagonal
if i <= rowCount - numAdjacents and j <= colCount - numAdjacents:
product = 1
k = 0
productFactors = []
while k < numAdjacents:
product *= gridValues[i+k][j+k]
productFactors.append(gridValues[i+k][j+k])
k += 1
if product > maxProduct:
maxProduct = product
maxProductInfo = "The max product is found at %d,%d with the numbers %s in the down right diagonal direction." % (i,j,productFactors)
#check down-left diagonal
if i <= rowCount - numAdjacents and j >= numAdjacents - 1:
product = 1
k = 0
productFactors = []
while k < numAdjacents:
product *= gridValues[i+k][j-k]
productFactors.append(gridValues[i+k][j-k])
k += 1
if product > maxProduct:
maxProduct = product
maxProductInfo = "The max product is found at %d,%d with the numbers %s in the down left diagonal direction." % (i,j,productFactors)
j += 1
i += 1
print "The largest product of %d adjacent numbers is %d" % (numAdjacents,maxProduct)
print maxProductInfo
I did a lot of extra stuff in this code to ensure that it solved the more general problem. Mainly that it could read any grid of numbers regardless of the size, assuming the format was the the same, and also allow to find the sum of any number of adjacent numbers within the grid. I think that in the end, this actually made the code a little shorter, and made the code a little easier to read in some ways. Also worth pointing out that you don't need to check all directions, just vertical going down from the current position, horizontal going right, diagonal going down to the right, and diagonal going down to the left. The other products you can calculate, such as vertical going up, and already covered but the 4 necessary ones once you have checked all the values. I also added extra code to record where the value was found, and in which direction, as well as the values being evaluated to find the product.
Find the sum of all the primes below two million.
#Find the sum of all the primes below two million.
from math import sqrt
import time
#this function will determine if
# num is prime
def nextPrime(num):
isPrime = False
while not isPrime:
numSqrt = sqrt(num)
isPrime = True
i = 2
while i <= numSqrt and isPrime:
if num % i == 0:
isPrime = False
i += 1
if not isPrime:
num += 1
return num
curNum = 2
MAX_NUM = 2000000
sumOfPrimes = 0
startTime = time.time()
print "Calculating the sum of primes below %d" % (MAX_NUM,)
while True:
#Only check odd numbers that are greater than 2
curNum = nextPrime(curNum)
if curNum < MAX_NUM:
sumOfPrimes += curNum
else:
break
if curNum <= 2:
curNum +=1
else:
curNum += 2
endTime = time.time()
print 'calculation took %0.3f ms' % ((endTime-startTime)*1000.0,)
print "The sum of all primes below %d is %d" % (MAX_NUM,sumOfPrimes)
Some pretty straighforward code here. To check for primes, I'm only checking until the square root of the number. If you don't find any factors before getting to the square root, you won't find any factors. Also, I'm making sure that I'm only checking 2, and the odd numbers. I'm sure there's faster ways to find prime numbers, but this is reasonably fast. I also put in some code to time how long it took my code to run.