CodeWars Kata —— Twice Linear
Consider a sequence
uwhere u is defined as follows:
- The number
u(0) = 1is the first one in
- For each
y = 2 * x + 1and
z = 3 * x + 1must be in
- There are no other numbers in
u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]
1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on…
dbl_linear(or dblLinear…) returns the element
u(n)of the ordered (with <) sequence
dbl_linear(10) should return 22
Focus attention on efficiency
This kata is only
5kyu however costs me days.
My finnal solution:
def dbl_linear(n): u =  def isInU(q): low = 0 high = len(u)-1 while low <= high: mid = int((low+high)/2) if u[mid] == q: return True if u[mid] > q: high = mid-1 else: low = mid+1 if q > u[mid]: return False, mid + 1 elif q < u[mid]: return False, mid else: print('sth. wrong') for index, num in enumerate(u): jx = isInU(2*num+1) if jx != True: u.insert(jx, 2*num+1) jy = isInU(3*num+1) if jy != True: u.insert(jy, 3*num+1) if index == int(n*3/5): break return u[n]
The key point was that
3/5。Be more that
3/5 will only result in Timeout. But this number was only gained through tests but not provements. It is a shame.
The author of this kata provide a solution from which I learned a lot.
from collections import deque def dbl_linear(n): h = 1; cnt = 0; q2, q3 = deque(), deque() while True: if (cnt >= n): return h q2.append(2 * h + 1) q3.append(3 * h + 1) h = min(q2, q3) if h == q2: h = q2.popleft() if h == q3: h = q3.popleft() cnt += 1
deques guarantee that
h comes out in order.