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)
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
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()
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()
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()
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()
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
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:]
Repvaleriecfranks, Computer Scientist at ASAPInfosystemsPvtLtd
A strong writer with a passion for story-telling 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 safety-focused 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 ...
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