yuhechen2018
BAN USER'''
I/P [8, 3, 2, [5, 6, [9]], 6]
O/P 8+3+2+2*(5+6+3*(9))+6 => 95
'''
def get_next_token(tokens, cursor):
#skip whitespaces and comma
while cursor < len(tokens) and tokens[cursor] in [' ', ',']:
cursor += 1
if cursor >= len(tokens): #at the end but no token is found
return None, cursor
c = tokens[cursor]
if c in ['[', ']']:
return c, cursor+1
#invalid input
if c > '9' or c < '0':
raise Exception('unexpected charactor {} at position {}'.format(c, cursor))
#read the number
number = 0
while cursor < len(tokens):
c = tokens[cursor]
if c in ['[', ']', ',', ' ']:
break
if c > '9' or c < '0':
raise Exception('unexpected charactor {} at position {}'.format(c, cursor))
number = number*10 + int(c)
cursor += 1
return number, cursor
def calculate(equation):
stack = []
brack_depth = 0
tokens = equation
cursor = 0
while True:
token, cursor = get_next_token(tokens, cursor)
if token == None: #done. pop and return the result
return stack.pop(-1)
if token == ']': #calculate result between [ and ]
r = 0
while True:
n = stack.pop(-1)
if n == '[':
r = r*brack_depth
stack.append(r) #push it back
brack_depth = brack_depth-1
break
else:
r = r + n
else:
stack.append(token)
if token == '[':
brack_depth += 1
if __name__ == "__main__":
equation = '[8, 3, 2, [5, 6, [9]], 6]'
result = calculate(equation)
print(result)
# tokens = '[8, 3, 2, [5, 6, [9]], 6]'
# tokens = '[8, 3, 12, [5, 6, [9]], 116 ]'
# cursor = 0
# while True:
# token, cursor = get_next_token(tokens, cursor)
# print(token)
# if token == None:
# break
def r_rotate(l):
temp = l[-1]
for i in range(len(l)-1, 0, -1):
l[i] = l[i-1]
l[0] = temp
def rotate(l, k):
#if len(l) == 1:
# return
for i in range(k):
r_rotate(l)
l = [1,2,3,4,5,6]
rotate(l, 2)
print(l)
l2 = [1]
rotate(l2, 2)
print(l2)
def coin_three(a, b, c):
l = [a, b, c]
l.sort()
lout = [0]
index = 1
while True:
next_min = 2000
for i in l:
j = index-1
while True:
if j < 0 or lout[j] + i <= lout[index-1]:
break
if lout[j] + i < next_min:
next_min = lout[j] + i
j = j-1
lout.append(next_min)
print(next_min)
index += 1
if next_min >= 1000:
break
def coin_three(a, b, c):
l = [a, b, c]
l.sort()
lout = [0]
index = 1
while True:
next_min = 2000
for i in l:
j = index-1
while True:
if j < 0 or lout[j] + i <= lout[index-1]:
break
if lout[j] + i < next_min:
next_min = lout[j] + i
j = j-1
lout.append(next_min)
print(next_min)
index += 1
if next_min >= 1000:
break
class DictEntry(object):
def __init__(self, val):
self.prev = None
self.next = None
self.val = val
class DictWithLast(object):
def __init__(self):
self.dict = {}
self.latest = None
def set(self, key, value):
if key in self.dict:
self.delete(key)
new_entry = DictEntry(value)
self.dict[key] = new_entry
if self.latest == None:
self.latest = new_entry
else:
self.latest.next = new_entry
new_entry.prev = self.latest
self.latest = new_entry
def get(self, key):
if key not in self.dict:
raise KeyError
return self.dict[key].val
def delete(self, key):
if key not in self.dict:
raise KeyError
entry = self.dict[key]
if entry.prev:
entry.prev.next = entry.next
if entry.next:
entry.next.prev = entry.prev
if entry == self.latest:
self.latest = entry.prev
del self.dict[key]
def last(self):
if self.latest == None:
raise Exception('Empty dictionary no element')
return self.latest.val
if __name__ == '__main__':
mydict = DictWithLast()
mydict.set(1, 'a')
print(mydict.last())
mydict.set(2, 'b')
print(mydict.last())
mydict.set(3, 'c')
print(mydict.last())
mydict.set(2, 'x')
print(mydict.last())
mydict.set(4, 'd')
print(mydict.last())
mydict.delete(3)
print(mydict.last())
mydict.delete(4)
print(mydict.last())
mydict.delete(1)
print(mydict.last())
mydict.delete(2)
print(mydict.last())
def verify_p(s, p):
if len(s)%len(p) != 0:
return False
for i in range(len(p), len(s)):
mod = i%len(p)
if s[i] != p[mod]:
return False
return True
def find_p(s):
p = ''
k = 0
while k < len(s)-1:
p += s[k]
k += 1
ret = verify_p(s, p)
if ret:
print('found P:', s, p)
return
if __name__ == '__main__':
find_p('ababab')
find_p('abaabaabaaba')
def count_abc(n, nb, nc):
if n == 1:
return 1 + (1 if nb else 0) + (1 if nc else 0)
ret = count_abc(n-1, nb, nc)
if nb > 0:
c2 = count_abc(n-1, nb-1, nc)
ret += c2
if nc > 0:
c3 = count_abc(n-1, nb, nc-1)
ret += c3
return ret
if __name__ == '__main__':
print(count_abc(1, 1, 2))
print(count_abc(2, 1, 2))
print(count_abc(3, 1, 2))
print(count_abc(4, 1, 2))
print(count_abc(5, 1, 2))
print(count_abc(6, 1, 2))
print(count_abc(7, 1, 2))
print(count_abc(100, 1, 2))
def count_abc(n, nb, nc):
if n == 1:
return 1 + (1 if nb else 0) + (1 if nc else 0)
ret = count_abc(n-1, nb, nc)
if nb > 0:
c2 = count_abc(n-1, nb-1, nc)
ret += c2
if nc > 0:
c3 = count_abc(n-1, nb, nc-1)
ret += c3
return ret
if __name__ == '__main__':
print(count_abc(1, 1, 2))
print(count_abc(2, 1, 2))
print(count_abc(3, 1, 2))
print(count_abc(4, 1, 2))
print(count_abc(5, 1, 2))
print(count_abc(6, 1, 2))
print(count_abc(7, 1, 2))
print(count_abc(100, 1, 2))
def call_counter(func):
def helper(*args):
helper.calls += 1
return func(*args)
helper.calls = 0
return helper
@call_counter
def fill_i(l, n, i):
#print(l)
for ind in range(0, 2*n-(i+1)):
if l[ind] == 0 and l[ind+i+1] == 0:
l[ind] = i
l[ind+i+1] = i
if i == 1:
print('found:', l)
else:
fill_i(l, n, i-1)
l[ind] = 0
l[ind+i+1] = 0
def permu(n):
l = [0] * 2 * n
fill_i(l, n, n)
if __name__ == '__main__':
permu(7)
print('total attempts:', fill_i.calls)
Outputs:
found: [4, 1, 3, 1, 2, 4, 3, 2]
found: [2, 3, 4, 2, 1, 3, 1, 4]
total attempts: 18
Not all N has solution. For instance N=6 gives no answer.
found: [7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1]
found: [7, 2, 6, 3, 2, 4, 5, 3, 7, 6, 4, 1, 5, 1]
found: [7, 2, 4, 6, 2, 3, 5, 4, 7, 3, 6, 1, 5, 1]
found: [7, 3, 1, 6, 1, 3, 4, 5, 7, 2, 6, 4, 2, 5]
found: [7, 1, 4, 1, 6, 3, 5, 4, 7, 3, 2, 6, 5, 2]
found: [7, 1, 3, 1, 6, 4, 3, 5, 7, 2, 4, 6, 2, 5]
found: [7, 4, 1, 5, 1, 6, 4, 3, 7, 5, 2, 3, 6, 2]
found: [7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3, 1, 6, 1]
found: [5, 7, 2, 6, 3, 2, 5, 4, 3, 7, 6, 1, 4, 1]
found: [3, 7, 4, 6, 3, 2, 5, 4, 2, 7, 6, 1, 5, 1]
found: [5, 7, 4, 1, 6, 1, 5, 4, 3, 7, 2, 6, 3, 2]
found: [5, 7, 2, 3, 6, 2, 5, 3, 4, 7, 1, 6, 1, 4]
found: [1, 7, 1, 2, 6, 4, 2, 5, 3, 7, 4, 6, 3, 5]
found: [5, 7, 1, 4, 1, 6, 5, 3, 4, 7, 2, 3, 6, 2]
found: [1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4]
found: [2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6]
found: [6, 2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1]
found: [2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3]
found: [3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5]
found: [5, 1, 7, 1, 6, 2, 5, 4, 2, 3, 7, 6, 4, 3]
found: [2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4]
found: [4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5]
found: [5, 2, 7, 3, 2, 6, 5, 3, 4, 1, 7, 1, 6, 4]
found: [3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7, 1, 6, 1]
found: [3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4]
found: [2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5]
found: [5, 6, 1, 7, 1, 3, 5, 4, 6, 3, 2, 7, 4, 2]
found: [4, 6, 1, 7, 1, 4, 5, 2, 6, 3, 2, 7, 5, 3]
found: [1, 6, 1, 7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3]
found: [4, 6, 1, 7, 1, 4, 3, 5, 6, 2, 3, 7, 2, 5]
found: [5, 3, 6, 7, 2, 3, 5, 2, 4, 6, 1, 7, 1, 4]
found: [4, 5, 6, 7, 1, 4, 1, 5, 3, 6, 2, 7, 3, 2]
found: [3, 4, 6, 7, 3, 2, 4, 5, 2, 6, 1, 7, 1, 5]
found: [5, 2, 4, 7, 2, 6, 5, 4, 1, 3, 1, 7, 6, 3]
found: [3, 4, 5, 7, 3, 6, 4, 1, 5, 1, 2, 7, 6, 2]
found: [1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2, 6]
found: [6, 1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2]
found: [4, 6, 3, 5, 7, 4, 3, 2, 6, 5, 2, 1, 7, 1]
found: [2, 6, 3, 2, 7, 4, 3, 5, 6, 1, 4, 1, 7, 5]
found: [5, 3, 6, 4, 7, 3, 5, 2, 4, 6, 2, 1, 7, 1]
found: [4, 1, 6, 1, 7, 4, 3, 5, 2, 6, 3, 2, 7, 5]
found: [2, 3, 6, 2, 7, 3, 4, 5, 1, 6, 1, 4, 7, 5]
found: [1, 5, 1, 6, 7, 2, 4, 5, 2, 3, 6, 4, 7, 3]
found: [1, 4, 1, 6, 7, 3, 4, 5, 2, 3, 6, 2, 7, 5]
found: [1, 6, 1, 3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7]
found: [2, 6, 3, 2, 5, 7, 3, 4, 6, 1, 5, 1, 4, 7]
found: [5, 2, 6, 4, 2, 7, 5, 3, 4, 6, 1, 3, 1, 7]
found: [2, 5, 6, 2, 3, 7, 4, 5, 3, 6, 1, 4, 1, 7]
found: [5, 2, 4, 6, 2, 7, 5, 4, 3, 1, 6, 1, 3, 7]
found: [1, 5, 1, 6, 3, 7, 4, 5, 3, 2, 6, 4, 2, 7]
found: [1, 5, 1, 4, 6, 7, 3, 5, 4, 2, 3, 6, 2, 7]
found: [1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7]
total attempts: 1283
Code:
def call_counter(func):
def helper(*args):
helper.calls += 1
return func(*args)
helper.calls = 0
return helper
@call_counter
def fill_i(l, n, i):
#print(l)
for ind in range(0, 2*n-(i+1)):
if l[ind] == 0 and l[ind+i+1] == 0:
l[ind] = i
l[ind+i+1] = i
if i == 1:
print('found:', l)
else:
fill_i(l, n, i-1)
l[ind] = 0
l[ind+i+1] = 0
def permu(n):
l = [0] * 2 * n
fill_i(l, n, n)
if __name__ == '__main__':
permu(7)
print('total attempts:', fill_i.calls)
class MyIter(object):
def __init__(self, ll):
self._ll = ll
def __iter__(self):
self._list_len = len(self._ll[0])
self._list_count = len(self._ll)
self._indices = [0] * self._list_count
return self
def __next__(self):
i = 0
m = int(25535)
m_ind = None
while i < self._list_count:
index = self._indices[i]
if index < self._list_len:
temp = self._ll[i][index]
if temp < m:
m = temp
m_ind = i
i += 1
if m_ind is not None:
self._indices[m_ind] += 1
return m
else:
raise StopIteration
if __name__ == '__main__':
ll = [[1,5,7], [2,3,10],[4,6,9]]
it = MyIter(ll)
print(list(it))
class MyIter(object):
def __init__(self, ll):
self._ll = ll
def __iter__(self):
self._list_len = len(self._ll[0])
self._list_count = len(self._ll)
self._indices = [0] * self._list_count
return self
def __next__(self):
i = 0
m = int(25535)
m_ind = None
while i < self._list_count:
index = self._indices[i]
if index < self._list_len:
temp = self._ll[i][index]
if temp < m:
m = temp
m_ind = i
i += 1
if m_ind is not None:
self._indices[m_ind] += 1
return m
else:
raise StopIteration
if __name__ == '__main__':
ll = [[1,5,7], [2,3,10],[4,6,9]]
it = MyIter(ll)
print(list(it))
O(0) extra space:
class ListNode(object):
def __init__(self, v):
self._v = v
self._next = None
def reorder(l):
h = l
next = l._next
if not next or not next._next:
return l
while next._next and next._next._next:
next = next._next
h2 = h._next
h._next = next._next
next._next = None
l2 = reorder(h2)
h._next._next = l2
return h
if __name__ == '__main__':
l = ListNode('A')
l._next = ListNode('B')
l._next._next = ListNode('c')
l._next._next._next = ListNode('D')
l._next._next._next._next = ListNode('E')
#l._next._next._next._next._next = ListNode('F') #case 2
r = reorder(l)
while r:
print(r._v)
r = r._next
class MyIter(object):
def __init__(self, ll):
self._ll = ll
def __iter__(self):
self._list_len = len(self._ll[0])
self._list_count = len(self._ll)
self._indices = [0] * self._list_count
return self
def __next__(self):
i = 0
m = int(25535)
m_ind = None
while i < self._list_count:
index = self._indices[i]
if index < self._list_len:
temp = self._ll[i][index]
if temp < m:
m = temp
m_ind = i
i += 1
if m_ind is not None:
self._indices[m_ind] += 1
return m
else:
raise StopIteration
if __name__ == '__main__':
ll = [[1,5,7], [2,3,10],[4,6,9]]
it = MyIter(ll)
print(list(it))
here is the code:
- yuhechen2018 March 12, 2020