Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.
Sample Input
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
In [31]:
## memoization cache decorator
def memcache(f):
cache = {}
def _helper(arg):
if arg not in cache:
cache[arg] = f(arg)
return cache[arg]
return _helper
## test it
@memcache
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-1) + fib(n-2)
assert fib(10) == 55
%timeit fib(30)
In [32]:
## get the cycle-length
@memcache
def cycle_len(n):
if n == 1:
return 1
elif n % 2 == 0:
return 1 + cycle_len(n / 2)
else:
return 1 + cycle_len(3 * n + 1)
assert cycle_len(22) == 16
In [33]:
def max_cycle_len(lower, upper):
return max(map(cycle_len, xrange(lower, upper+1)))
assert max_cycle_len(1, 10) == 20
assert max_cycle_len(100, 200) == 125
assert max_cycle_len(201, 210) == 89
assert max_cycle_len(900, 1000) == 174
Have you ever played Minesweeper? This cute little game comes with a certain op- erating system whose name we can’t remember. The goal of the game is to find where all the mines are located within a M × N field. The game shows a number in a square which tells you how many mines there are adjacent to that square. Each square has at most eight adjacent squares. The 4 × 4 field on the left contains two mines, each represented by a “*” character. If we represent the same field by the hint numbers described above, we end up with the field on the right:
Sample Input
44
*...
....
.*..
....
35
**...
.....
.*...
00
Sample Output
Field #1:
*100
2210
1*10
1110
Field #2:
**100
33200
1*100
In [52]:
def wrap(grid, ROWS, COLS):
return (['.' * (COLS+2)] +
['.'+r+'.' for r in grid] +
['.' * (COLS+2)])
def neighbor(r, c, grid):
if grid[r][c] == '*':
return '*'
else:
neighbors = [(-1,-1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0)]
#print [n for n in map(lambda (dr,dc): grid[r+dr][c+dc], neighbors)]
return str(len([n for n in map(lambda (dr,dc): grid[r+dr][c+dc], neighbors) if n == '*']))
def mines_counter(grid):
grid = [r.strip() for r in grid.split("\n") if len(r) > 0]
ROWS, COLS = len(grid), len(grid[0])
wrapped_grid = wrap(grid, ROWS, COLS)
#print wrapped_grid
#print neighbor(1, 2, wrapped_grid)
return ([''.join([neighbor(r+1, c+1, wrapped_grid)
for c in xrange(COLS)])
for r in xrange(ROWS)])
print mines_counter("""
*...
....
.*..
....""")
print mines_counter("""
**...
.....
.*...
""")
In [ ]: