In [2]:
import math
import logging
import random
logging.basicConfig()
log = logging.getLogger('leetcode')
In [1]:
class Solution:
def combine(self, n, k):
L = []
self.go(1, n, k, [], L)
return L
def go(self, st, n, k, l, L):
for i in range(st, n - k + 2):
l0 = [*l, i]
if k == 1:
L.append(l0)
else:
self.go(i+1, n, k-1, l0, L)
def superPow(self, a, b):
sum([1,2])
In [29]:
def power_loop(mod, n=None):
lmap = {}
def make_unique_set(mod, i):
s, i1 = set(), i
while i1 not in s:
s.add(i1)
i1 = (i1 * i) % mod
lmap[i] = s
if n is None:
for i in range(2, mod):
make_unique_set(mod, i)
else:
make_unique_set(mod, n)
return lmap
In [38]:
sm = power_loop(1337, 2)
# len(sm[2])
# 1336 / 285, 1336 % 285
sm
Out[38]:
In [40]:
power_loop(13)
115*10 % 285
Out[40]:
In [44]:
def superPow(self, a: 'int', b: 'List[int]') -> 'int':
a = a % 1337
if a == 1 or a == 0:
return a
b.reverse()
s = powerCycle(a, 1337)
powmod = len(s)
tens = powerCycle(10, powmod)
tenmod = len(tens)
p = 0
for i, v in enumerate(b):
if i == 0:
pp = v
else:
pp = (v * tens[(i-1)%tenmod]) % powmod
p += pp
p = p % powmod
return pow(a, p) % 1337
def powerCycle(a, mod):
i, cycle = a**2, [a]
while i != a:
cycle.append(i)
i = (i*a) % mod
return cycle
In [45]:
a = 2139430
b = [2,7,1,6,6,6,3,9,9,3,1,1,7,7,4,4,7,3,4,0,3,5,5,6,5,6,0,9,5,1,2,5,8,3,3,6,9,8,8,0,1,1,3,8,0,9,5,8,2,9,0,6,6,5,4,2,3,5,3,9,8,5,6,7,1,1,5,2,0,5,5,3,6,8,4,7,8,9,7,2,0,9,8,8,4,5,2,7,2,6,8,0,3,6,9,6,8,7,9,0,2,4,3,9,4,7,8,4,8,7,7,0,6,7,9,2,2,1,9,4,9,0,7,5,6,6,1,4,3,2,6,8,8,0,7,3,9,7,9,8,6,6,8,2,4,9,4,8,1,5,5,0,7,2,7,4,0,1,0,6,3,7,4,4,9,3,7,8,0,8,6,6,5,7,0,1,6,6,9,9,3,4,2,1,8,9,7,9,0,9,5,6,6,9,0,7,4,9,6,4,7,4,2,4,1,4,5,0,2,7,9,5,1,1,6,2,1,3,1,3,3,8,9,1,9,9,9,3,0,7,9,8,1,3,2,5,7,0,5,9,7,6,4,0,8,3,2,1,8,3,6,3,3,8,5,2,9,6,5,0,5,6,0,6,9,2,3,6,4,0,7,1,7,4,2,7,9,4,0,7,0,8,1,5,6,8,8,6,6,5,6,1,2,6,9,1,0,3,0,5,3,9,8,2,3,0,1,2,7,1,2,9,0,3,4,8,3,4,4,9,0,2,2,2,0,1,5,3,6,5,8,2,5,8,4,0,9,6,5,8,9,7,7,1,2,3,0,7,8,6,6,8,1,0,2,1,1,7,4,8,5,4,2,2,3,6,4,4,4,9,2,6,8,1,9,2,6,1,9,4,8,7,4,9,9,8,2,1,6,7,1,3,3,3,5,6,1,1,0,8,3,4,4,3,7,3,6,4,5,7,0,5,7,5,6,8,3,8,9,1,7,2,6,1,7,1,7,9,5,0,7,8,6,3,1,4,8,9,0,5,9,0,0,8,7,8,6,3,9,8,4,6,0,1,9,0,4,9,1,9,9,8,9,7,3,3,3,1,2,3,7,3,4,9,3,3,0,0,6,9,0,1,5,2,4,7,2,0,6,3,2,5,3,1,4,6,4,8,0,9,1,9,4,7,8,8,1,8,0,7,9,0,0,7,2,6,4,5,7,0,0,9,7,4,2,1,2,9,9,2,8,1,1,4,0,2,2,1,2,2,1,2,4,3,9,7,0,3,4,7,3,4,6,2,0,0,3,3,9,3,5,9,6,9,4,8,1,8,0,3,3,3,5,7,6,4,6,6,9,0,5,4,7,3,6,7,4,0,0,3,5,6,3,3,5,9,1,8,7,3,1,0,8,7,8,5,3,4,3,5,7,9,1,4,4,8,1,8,0,2,4,7,0,9,0,7,8,3,5,7,7,6,8,5,5,8,2,1,2,8,8,9,9,9,5,3,9,7,4,9,1,0,8,1,9,0,8,9,4,5,6,3,1,6,0,9,4,3,2,7,1,0,8,0,1,4,5,1,3,9,2,4,9,1,5,0,1,5,1,7,0,0,0,3,6,1,4,1,4,8,0,7,8,8,9,2,4,4,5,7,6,7,3,7,0,8,0,4,5,1,1,5,1,4,1,0,5,5,1,1,4,1,0,4,1,9,8,6,5,3,5,1,3,9,1,3,9,1,7,5,4,1,2,6,5,5,8,2,3,9,3,7,2,5,3,3,4,4,1,9,7,9,3,0,0,4,6,9,7,5,6,1,6,1,7,3,6,7,5,9,6,0,8,8,5,4,4,1,8,7,3,7,6,6,8,6,2,4,8,9,9,6,0,8,7,0,1,6,7,9,7,6,9,8,4,7,2,0,8,2,8,1,9,6,7,7,3,1,3,3,0,3,9,3,3,9,3,4,7,2,3,4,8,5,2,5,2,6,5,0,8,5,4,8,2,1,7,7,5,1,2,5,6,3,0,9,2,5,5,1,8,1,8,6,8,2,3,0,9,1,2,7,6,6,7,0,0,5,7,5,8,9,2,4,3,3,5,7,8,0,1,8,3,9,7,1,1,0,3,2,1,6,2,0,4,9,0,4,6,8,1,4,9,4,0,4,9,5,4,9,8,5,0,1,6,7,5,9,7,8,2,9,4,4,9,9,3,1,5,2,1,7,6,1,3,7,7,4,4,1,5,4,8,5,8,4,2,3,4,2,3,8,3,0,2,4,1,7,5,6,9,7,5,8,8,0,7,7,4,3,1]
In [50]:
a = a % 1337
print(a)
s = powerCycle(a, 1337)
len(s)
Out[50]:
In [6]:
def change(amount, coins):
if len(coins) == 0: return 1 if amount == 0 else 0
sc = sorted(coins, reverse=True)
coin = coins[0]
return countCoins(amount, coin, coins[1:])
def countCoins(amount, coin, rem):
num = 0
for cc in range(amount // coin, -1, -1):
left = amount - cc*coin
if left == 0:
num += 1
elif len(rem) > 0:
ncoin = rem[0]
num += countCoins(left, ncoin, rem[1:])
else:
return num
return num
In [9]:
def changeDynamic(amount, coins):
sc = sorted(coins, reverse=False)
combos = [0]*amount
combos.insert(0, 1)
for coin in sc:
for i in range(len(combos)):
if i >= coin:
combos[i] += combos[i-coin]
return combos[amount]
In [7]:
change(500, [3,5,7,9,10,11])
Out[7]:
In [11]:
changeDynamic(500, [3,5,7,9,10,11])
Out[11]:
In [ ]:
# def pacificAtlantic(matrix):
# m, n = len(matrix), len(matrix[0])
# P = [[None]*n for _ in range(m)]
# for i in range(m):
# for j in range(n):
# if P[i][j] is None:
# val = matrix[i][j]
# decision = None
# if i == 0 or j == 0:
# decision = True
# else:
# s = set()
# if i < m and matrix[i+1][j] <= val and P[i+1][j] is not False:
# if P[i+1][j] is True:
# decision = True
# else:
# s.add([i+1, j])
# if decision is None matrix[i-1][j] <= val and P[i-1][j] is not False:
# if P[i-1][j] is True:
# decision = True
# else:
# s.add([i-1, j])
# if j < n and matrix[i][j+1] <= val and P[i][j+1] is not False:
# if P[]
# s.add([i, j+1])
# if i < m and matrix[i+1][j] <= val and P[i+1][j] is not False:
# s.add([i+1, j])
# return P
In [196]:
class PATree:
def __init__(self, matrix):
self.m, self.n = len(matrix), len(matrix[0])
m, n = self.m, self.n
self.P = [PANode(self, x, y, matrix[y][x]) for y in range(m) for x in range(n)]
P = self.P
self.equalNodes = {}
for node in P:
r = node.getRight()
node.compareNodes(r)
b = node.getBelow()
node.compareNodes(b)
for node in self.P:
# assign references
if node.equalTo is not None:
end = node
while end.equalTo is not None:
end = end.equalTo
end.nodes.extend(node.nodes)
node.nodes = end.nodes
for i in range(len(end.reach)):
end.reach[i] = end.reach[i] or node.reach[i]
node.reach = end.reach
for node in self.P:
node.canReach(0)
node.canReach(1)
def __repr__(self):
return '\n'.join([str(p) for p in self.P])
def prettyPrint(self):
strs = [x.flag() for x in self.P]
return '\n'.join([''.join(['{:02d}:'.format(x), *strs[x*self.n:(x+1)*self.n]]) for x in range(self.m)])
class PANode:
def __init__(self, tree, x, y, val):
self.x, self.y = x, y
self.nodes = []
self.val = val
self.pos = y*tree.n + x
self.tree = tree
self.reach = [None, None]
self.reach[0] = True if x == 0 or y == 0 else None
self.reach[1] = True if x+1 == tree.n or y+1 == tree.m else None
self.equalTo = None
def __str__(self):
return '{}:{}, {} nodes. Can reach both? {}. Equal to: {}'\
.format(self.pos, self.val, len(self.nodes),
sum(self.reach) == 2, self.equalTo.pos if self.equalTo is not None else None)
def __repr__(self):
return self.__str__()
def addNode(self, node):
self.nodes.append(node)
def getBelow(self):
return None if self.y + 1 == self.tree.m else self.tree.P[self.pos+self.tree.n]
def getRight(self):
return None if self.x + 1 == self.tree.n else self.tree.P[self.pos+1]
def compareNodes(self, other):
if other is not None and self.pos != other.pos:
if other.val < self.val:
self.addNode(other)
elif self.val < other.val:
other.addNode(self)
else:
end = self
while other.equalTo is not None:
other = other.equalTo
alreadyEqual = self is other
while end.equalTo is not None:
end = end.equalTo
alreadyEqual = alreadyEqual or end is other
if not alreadyEqual:
print('setting', end.pos, 'equal to', other.pos)
end.equalTo = other
def canReach(self, ind):
if self.reach[ind] is None:
cr = sum([n.canReach(ind) for n in self.nodes])
self.reach[ind] = cr > 0
return self.reach[ind]
def reachAll(self):
return sum(self.reach) == len(self.reach)
def flag(self):
return '({:02d})'.format(self.val)\
if self.reachAll()\
else ' {:02d} '.format(self.val)
In [197]:
testcase = [[1,2,2,3,5],
[3,2,3,4,4],
[2,4,5,3,1],
[6,7,1,4,5],
[5,1,1,2,4]]
testcase2 = [[1,2,2,3,5],
[3,2,3,4,4],
[2,4,5,3,1],
[6,7,1,4,5]]
testcase3 = [[1,1],
[1,1]]
tc4 = [[9,10,14,9,2,6,16],
[0,0,4,5,16,16,15],
[10,8,16,10,12,8,11],
[3,13,15,0,19,16,5],
[13,17,1,12,11,8,14],
[14,9,11,10,5,19,11],
[15,3,14,3,9,11,5],
[9,17,5,15,5,15,7],
[12,11,10,0,9,14,19],
[9,1,4,5,8,18,18],
[1,4,17,16,5,12,18],
[18,2,0,0,2,11,5],
[1,15,8,18,13,15,13],
[11,14,4,13,3,1,1],
[4,2,11,19,17,8,11],
[4,11,10,0,1,18,11],
[11,7,14,4,7,8,9],
[12,0,0,3,6,2,12],
[0,16,3,3,5,6,6],
[6,11,17,12,18,5,15],
[16,14,8,4,10,16,6],
[9,7,2,13,5,5,5],
[14,17,19,4,7,2,5],
[11,16,18,14,8,10,12],
[5,11,10,17,2,2,13],
[7,6,12,3,5,3,12],
[12,10,0,19,3,15,12],
[13,2,12,1,1,15,19],
[11,15,10,8,14,19,8],
[16,2,2,16,5,15,16],
[9,8,2,17,15,14,16],
[17,2,17,17,0,6,3],
[3,4,13,9,1,4,0],
[1,3,13,10,14,9,4]]
tc5 = [[11,15,10,8,14,19,8],
[16,2,2,16,5,15,16],
[9,8,2,17,15,14,16],
[17,2,17,17,0,6,3]]
tc6 = [[10,10,10],
[10,1,10],
[10,10,10]]
In [188]:
tree = PATree(tc4)
print(tree.prettyPrint())
tree
Out[188]:
In [191]:
tree = PATree(testcase3)
print(tree.prettyPrint())
tree
Out[191]:
In [198]:
tree = PATree(tc6)
print(tree.prettyPrint())
tree
Out[198]:
In [27]:
def medianSortedArrays(nums1=[0], nums2=[], version=2):
if len(nums1) == 0:
return median(nums2, -1, len(nums2))
elif len(nums2) == 0:
return median(nums1, -1, len(nums1))
vers = {
1: medianSortedArrays1,
2: medianSortedArrays2
}
return vers[version](nums1, nums2)
def medianSortedArrays1(nums1=[0], nums2=[]):
log.debug('*********')
log.debug('Arrays: %s, %s', nums1, nums2)
s1, e1 = -1, len(nums1)
s2, e2 = -1, len(nums2)
if nums1[-1] <= nums2[0]:
return median(nums1 + nums2, s1, e1 + e2)
elif nums2[-1] <= nums1[0]:
return median(nums2 + nums1, s1, e1 + e2)
while e1 - s1 > 2 and e2 - s2 > 2:
med1 = median(nums1, s1, e1)
med2 = median(nums2, s2, e2)
log.debug('med1: %d, med2: %d', med1, med2)
if med1 == med2:
return med1
jump = min(e1 - s1, e2 - s2)//2
if med1 < med2:
e2 -= jump
s1 += jump
else:
e1 -= jump
s2 += jump
log.debug('arrived. num1 bounds: [%d, %d], num2 bounds: [%d, %d]',
s1, e1, s2, e2)
cands1 = getCandidates(nums1, s1, e1)
cands2 = getCandidates(nums2, s2, e2)
if len(cands1) == 1 and len(cands2) == 1:
if nums1[cands1[0]] < nums2[cands2[0]] and\
cands1[0] < (len(nums1) - 1) and\
cands2[0] > 0:
cands1.append(cands1[0] + 1)
cands2.append(cands2[0] - 1)
elif nums1[cands1[0]] > nums2[cands2[0]] and\
cands2[0] < (len(nums2) - 1) and\
cands1[0] > 0:
cands1.append(cands1[0] - 1)
cands2.append(cands2[0] + 1)
# allcands = getCandidates(nums1, s1, e1, nums2, s2, e2)
allcands = sorted([nums1[i] for i in cands1] + [nums2[i] for i in cands2])
log.debug('all candidates: %s', allcands)
finalval = median(allcands, -1, len(allcands))
log.debug('final val: %f', finalval)
return finalval
def getCandidates(nums, s, e):
cands = []
ms = (s+e)//2
if (s + e) % 2 == 1:
me = ms + 1
if ms >= 0:
cands.append(ms)
if me < len(nums):
cands.append(me)
else:
cands.append(ms)
return cands
def median(nums, l, r):
if (l+r) % 2 == 1:
# odd
fl = (l+r)//2
return (nums[fl] + nums[fl+1])/2
else:
return nums[(l+r)//2]
Ok so the above approach is getting too complicated. I think I want to try again where instead of two pointers each to the ends of the range, just one pointer each to a point in each list, and then a number which is like the distance of the next jump, which will be cut in half every jump. Initialized to a quarter the length of the smaller list, rounded up.
In [24]:
def medianSortedArrays2(nums1, nums2):
l1, l2 = len(nums1), len(nums2)
In [26]:
log.setLevel(logging.DEBUG)
def test(asrt=False):
med1 = medianSortedArrays(nums1 = [1, 2], nums2 = [3, 4])
med2 = medianSortedArrays(nums1 = [1, 4], nums2 = [2])
med3 = medianSortedArrays(
[4, 5, 10, 21, 41, 54, 63, 71, 78, 90, 90, 94, 96, 100],
[4, 10, 17, 26, 30, 31, 36, 48, 48, 58, 59, 62, 75, 77, 81, 88, 93, 94]
)
med4 = medianSortedArrays([1,2], [-1,3])
med5 = medianSortedArrays([1], [2,3,4])
med6 = medianSortedArrays([2], [1,3,4, 5, 6])
def assertEq(act, exp):
assert exp == act, "Expected {}, received: {}".format(exp, act)
if asrt:
assertEq(med1, 2.5)
assertEq(med2, 2)
assertEq(med3, 58.5)
assertEq(med4, 1.5)
assertEq(med5, 2.5)
assertEq(med6, 3.5)
for _ in range(5):
rand1 = sorted([random.randint(0,100) for _ in range(random.randint(10,50))])
rand2 = sorted([random.randint(0,100) for _ in range(random.randint(10,50))])
log.debug('random arrays: %s, %s', rand1, rand2)
medr = medianSortedArrays(rand1, rand2)
if asrt:
expmedr = median(sorted(rand1 + rand2), -1, len(rand1) + len(rand2))
assert medr == expmedr, "Expected {}, got {}".format(expmedr, medr)
test(True)
In [17]:
log.setLevel(logging.DEBUG)
# medianSortedArrays([1,2], [-1,3])
medianSortedArrays([1], [2,3,4])
Out[17]:
In [20]:
obj = lambda: 0