2011-09-25

# Project Euler problem 129 - Solved

The statement of the problem can be found here.

Using the same technique as in my previous post to determine whether a number divides a repunit or not, we create a function to find the A(n) by bruteforcing it.

As A(n) can’t be greater than n we start searching for the number we are looking for from 1000001. The algorithm is really simple:

from CommonFunctions import *
from itertools import *

def A(n):
i = 2
while (mod_pow(10, i, 9 * n) != 1):
i += 1
return i

limit = 10 ** 6

if __name__ == '__main__':
for n in count(1000001, 2):
if str(n)[-1] == '5':
continue
x = A(n)
if x > limit:
break
print("The result is:", n)

2011-09-03

# Project Euler problem 132 - Solved

The statement of this problem can be found here.

In order to solve this problem the first important thing to notice is how a repunit can be represented: $R(k) = \frac{10^k - 1}{9}$

Therefore, we can express if a repunit is divisible by p like:

So if $10^k \mod 9p = 1$, then p divides $R(10^k)$. The problem now is how to calculate the remainder in an efficient way as it is impossible to calculate the remainder to a number of a thousand million digits. Here we can use Modular exponentiation as what we need to calculate is the remainder of a number than can be expressed as a power with base 10 and exponent 9.

The solution for this code in Python (problem132.py) is really simple (the CommonFunctions file can be found in my wiki):

from CommonFunctions import *
from itertools import *

if __name__ == '__main__':
primes = find_primes_less_than(10 ** 6)
base = 10
exp = 10 ** 9
result = sum(islice((p for p in primes if mod_pow(base, exp, 9 * p) == 1), 0, 40))
print("The result is:", result)

2011-07-05

# CodeJam 2009 - Qualification Round - (B)Watersheds - Solution

Today, I’m posting the solution for problem B in 2009’s Qualification Round which was called “Watersheds”.

You can find the statement of the problem in the Google CodeJam page or follow this link.

The solution is straightforward, without any tricks. For each cell in the map I throw a recursive function which checks whether that cell is already in a basin or it calls recursively with the cell where the water goes to. In case that the water can’t go any further then a new basin is set at that cell and returned so that  the rest of the recursive calls set theirs to that basin.

The python file is GCJ2009-Q-B.py and it contains the following:

last_letter = 'a'
W = 0
H = 0

def run_water(height_map, basin_map, i, j):
global last_letter, H, W
if basin_map[i][j]:
return basin_map[i][j]
min_h = height_map[i][j]
direction = 0
if i > 0 and height_map[i-1][j] < min_h:
direction = 1
min_h = height_map[i-1][j]
if j > 0 and height_map[i][j-1] < min_h:
direction = 2
min_h = height_map[i][j-1]
if j < W-1 and height_map[i][j+1] < min_h:
direction = 3
min_h = height_map[i][j+1]
if i < H-1 and height_map[i+1][j] < min_h:
direction = 4
min_h = height_map[i+1][j]
if direction == 0:
basin_map[i][j] = last_letter
last_letter = chr(ord(last_letter) + 1)
elif direction == 1:
basin_map[i][j] = run_water(height_map, basin_map, i-1, j)
elif direction == 2:
basin_map[i][j] = run_water(height_map, basin_map, i, j-1)
elif direction == 3:
basin_map[i][j] = run_water(height_map, basin_map, i, j+1)
elif direction == 4:
basin_map[i][j] = run_water(height_map, basin_map, i+1, j)
return basin_map[i][j]

def solve():
global last_letter, H, W
H, W = map(int, input().split(' '))
height_map = []
for i in range(H):
height_map.append(list(map(int, input().split(' '))))
basin_map = [[''] * W for i in range(H)]
last_letter = 'a'
for i in range(H):
for j in range(W):
run_water(height_map, basin_map, i, j)
for i in range(H):
print(' '.join(basin_map[i]))

if __name__ == '__main__':
T = int(input())
for case in range(1, T+1):
print("Case #{0}:".format(case))
solve()