Pavel Aslanov
BAN USERPython solution
def string_ord_nums(n):
"""Generate all number less than `n` in alphabetical order
Example:
>>> from itertools import islice
>>> take = lambda n, xs: list(islice(xs, n))
>>> take(10, string_ord_nums(100))
[1, 10, 100, 11, 12, 13, 14, 15, 16, 17]
>>> take(15, string_ord_nums(1000))
[1, 10, 100, 1000, 101, 102, 103, 104, 105, 106, 107, 108, 109, 11, 110]
"""
def nums(v):
for i in range(10):
vn = v * 10 + i
if 0 < vn <= n:
yield vn
for vi in nums(vn):
yield vi
return nums(0)

Pavel Aslanov
July 19, 2014 1. Build graph of reachable stones from every stone
2. Find shortest path in graph using dijkstra algorithm.
Here is my solution
def min_rabbit_jumps(js, rs):
"""Find minimum number of jumps to cross river
js  possible jumps
rs  distance between adjacent rocks starting from first
>>> min_rabbit_jumps([3,1], [1,2,1])
2
>>> min_rabbit_jumps([3,1], [2,1,2])
3
>>> min_rabbit_jumps([3,1], [1,4])
inf
"""
ns = to_graph(js, rs) # index > children
# using dijkstra algorithm find shortest path in graph `ns`
i2d = {i: float("inf") for i in range(len(ns))}
i2d[0] = 0
q = set(range(len(ns))) # unprocessed nodes queue
while q:
# find closest elemnt
d, i = min((i2d[i], i) for i in q)
q.remove(i)
for n in ns[i]:
if i2d[n] > d + 1:
i2d[n] = d + 1
return i2d[len(rs)]
def to_graph(js, rs):
"""Convert jumps `js` and rocks `rs` to graph
Returns graph of possible positions and available jumps from them.
"""
# index to distance and vice versa
d, i2d, d2i = 0, {0: 0}, {0: 0}
for i, r in enumerate(rs):
d += r
i2d[i + 1] = d
d2i[d] = i + 1
# nodes of the graph
ns = [[] for _ in i2d]
for i, d in i2d.items():
for j in js:
ji = d2i.get(d + j) # jump index
if ji is not None:
ns[i].append(ji)
ns[ji].append(i)
return ns

Pavel Aslanov
July 15, 2014 We just need to merge from the end. Here is my python solution.
def merge(xs, xs_size, ys, ys_size):
"""Merge two arrays in the first one
Example:
>>> merge([1, 3, 5, 0, 0, 0], 3,
... [2, 4, 6], 3)
[1, 2, 3, 4, 5, 6]
>>> merge([1, 0, 0, 0], 1,
... [0, 2, 3], 3)
[0, 1, 2, 3]
>>> merge([0, 2, 3, 0], 3,
... [1], 1)
[0, 1, 2, 3]
"""
i, j = xs_size, ys_size
while i + j > 0:
if j <= 0:
i = 1
xs[i + j] = xs[i]
elif i <= 0:
j = 1
xs[i + j] = ys[j]
else:
if xs[i  1] > ys[j  1]:
i = 1
xs[i + j] = xs[i]
else:
j = 1
xs[i + j] = ys[j]
return xs
if __name__ == '__main__':
import doctest
doctest.testmod()

Pavel Aslanov
October 08, 2013 def max_three_uniq(xs):
"""Find longest sub sequence of 3 unique values
Example:
>>> max_three_uniq('123143412')
(6, 2) # (size, offset)
"""
recs = [(0, {})] # (start, {value: lastSeenIndex, ...})
for i, x in enumerate(xs):
start, vals = recs[1]
vals = vals.copy()
if len(vals) < 3 or x in vals:
vals[x] = i # update last seen property
recs.append((start, vals))
else:
# remove value with minimal last seen property
del vals[min((valLast, val) for val, valLast in vals.items())[1]]
vals[x] = i
recs.append((min(vals.values()), vals))
maxLen, maxIndex = 0, 0
for i, rec in enumerate(recs):
if i  rec[0] > maxLen:
maxLen, maxIndex = i  rec[0], rec[0]
return maxLen, maxIndex
if __name__ == '__main__':
import doctest
doctest.testmod()

Pavel Aslanov
September 27, 2013 def str2moves(cs):
"""Convet string to moves in matrix
+x
 a b c d e
 f g h i j
 k l m n o
 p q r s t
 u v w x y
 z
y
Returns string of moves encoded as follows:
R  right
L  left
D  down
U  up
O  ok
Example:
>>> str2moves('con')
'RRODDRROLO'
>>> str2moves('conz')
'RRODDRROLODDLLLDO'
>>> str2moves('conza')
'RRODDRROLODDLLLDOUUUUUO'
"""
def i2xy(i):
y, x = divmod(i, 5)
return x, y
char2xy = {chr(ord('a') + i): i2xy(i)
for i in range(ord('z')  ord('a') + 1)}
def move(cx, cy, x, y):
"""Moves required to get from (cx, cy) to (x, y)
"""
if y  cy > 0:
moves.extend('D' * (y  cy))
elif y  cy < 0:
moves.extend('U' * (cy  y))
if x  cx > 0:
moves.extend('R' * (x  cx))
elif x  cx < 0:
moves.extend('L' * (cx  x))
return x, y
moves = []
cs = cs.lower()
cx, cy, z = 0, 0, False
for c in cs:
x, y = char2xy.get(c, (None, None))
if x is None:
raise ValueError('invalid char: {}'.format(c))
if z == True:
moves.append('U')
if y == 5: # 'z'
cx, cy = move(cx, cy, x, y  1)
moves.append('D')
z = True
else:
cx, cy = move(cx, cy, x, y)
moves.append('O')
return ''.join(moves)
if __name__ == '__main__':
import doctest
doctest.testmod()

Pavel Aslanov
September 27, 2013 Indeed)
 Pavel Aslanov September 25, 2013My python solution with tests
def nums(count, digits={0,1,2,3,4,5,6,7,8,9}, zero=True):
"""Print number without repeating digits and at most count digits long
Argumetns:
count  number of digits
digits  allowed digits
zero  is all leading digits a zeroes (need to account for
numbers with most significant digit to be zero, and
not treat them as repeating)
Example:
>>> list(nums(2))[:15]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15]
# solution for problem (just use filter on nums)
>>> list(filter(lambda val: val >= 45 and val <= 4578, nums(4)))
... # doctest: +ELLIPSIS
[45, 46, ..., 4571, 4572, 4573, 4576, 4578]
"""
if not count:
yield 0
return
for digit in digits:
pos = 10 ** (count  1)
if zero and digit == 0:
for num in nums(count  1, digits, True):
yield num
else:
for num in nums(count  1, digits  {digit}, False):
yield digit * pos + num
if __name__ == '__main__':
import doctest
doctest.testmod()

Pavel Aslanov
September 25, 2013 Actually its O(n) memory because you need to allocate 2 arrays of n size for rows and columns.
 Pavel Aslanov September 25, 2013Scan matrix for zeroes and remember rows and columns containing 0,
in second path update matrix. Computational complexity O(n^2), memory complexity O(n)
def mat_zero(mat, n):
"""Zero columns and rows which contains at least one zero
Example:
>>> mat_zero([[1, 2, 3, 4],
... [5, 6, 7, 8],
... [9, 0, 1, 0],
... [3, 4, 5, 6]], 4)
[[1, 0, 3, 0], [5, 0, 7, 0], [0, 0, 0, 0], [3, 0, 5, 0]]
"""
cols, rows = [False] * n, [False] * n
for i in range(n):
for j in range(n):
if mat[i][j] == 0:
cols[i], rows[j] = True, True
for i in range(n):
for j in range(n):
if cols[i] or rows[j]:
mat[i][j] = 0
return mat

Pavel Aslanov
September 24, 2013 def permute(xs):
"""Generate all permutations of `xs`
Example:
>>> list(permute([0, 1, 2]))
[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
"""
if len(xs) <= 1:
yield xs
return
h, ts = xs[0], xs[1:]
for t in permute(ts):
for i in range(len(ts) + 1):
yield t[:i] + [h] + t[i:]

Pavel Aslanov
September 24, 2013
Repvaleriecfranks, Computer Scientist at ASAPInfosystemsPvtLtd
A strong writer with a passion for storytelling who has extensive experience of writing literary compositions, articles, reports, books and ...
Repthubmorfin, Android Engineer at ABC TECH SUPPORT
I am currently working as a safetyfocused Service Technician from Red Bank. I execute routine maintenance work while advising clients ...
Repcharlesgwitt47, Animator at ASU
By Profession, I am a Automotive service technician in Kennewick USA. My strong interest is in yoga, My yogic journey ...
Open Chat in New Window
Here are two python solutions, recursive and iterative. It is basically depth first traversal with keeping path to current node, we must be careful no to account for non leaf nodes.
 Pavel Aslanov November 26, 2014