Guest User

Untitled

a guest
Oct 27th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3
  2.  
  3. [d, d+1, d+2, d+3]
  4.  
  5. 1 2 3 4 5 6 7 8 9
  6.  
  7. [d, x, d+1, x]
  8.  
  9. [x,y,d,x,y,d+1]
  10.  
  11. >>> import itertools
  12. >>> g = (digit for number in itertools.count(1) for digit in map(int, str(number)))
  13. >>> digits = 2, 2, 3, 2, 4
  14. >>> i=9+(22-10)*2 + 1; list(itertools.islice(g, i, i+len(digits)))
  15. [2, 2, 3, 2, 4]
  16.  
  17. def find_min_index(number):
  18. digits = get_digits(number)
  19. # find minimal n and start,end such that
  20. # digits = get_digits(n)[start:] + get_digits(n+1) +...+ get_digits(n+m)[:end]
  21. # brute force approach
  22. for ndigits_in_n in range(1, len(digits)): # m=ceil(len(digits)/ndigits_in_n)
  23. for start in range(ndigits_in_n):
  24. i = ndigits_in_n - start # where (n+1) starts in *digits*
  25. # is10pow = (10**ndigits_in_n == (n+1))
  26. is10pow = (digits[i:i + ndigits_in_n + 1] == [1] + [0] * ndigits_in_n)
  27. # get_digits(n+1) == digits[i:i+ndigits_in_n+is10pow]
  28. n = digits2number(digits[i:i+ndigits_in_n+is10pow]) - 1
  29. if matched_n(digits, n, start):
  30. return get_index(n) + start
  31. return get_index(number) # m == 0
  32.  
  33. >>> find_min_index(22324)
  34. 34 # верно
  35.  
  36. def get_digits(number):
  37. """
  38. >>> get_digits(22324)
  39. [2, 2, 3, 2, 4]
  40. """
  41. return list(map(int, str(number))) # NOTE: O(k**2) in CPython
  42.  
  43. import functools
  44.  
  45. def digits2number(digits):
  46. """
  47. >>> digits2number([1,2,3])
  48. 123
  49. """
  50. return functools.reduce(lambda number, digit: 10 * number + digit, digits)
Add Comment
Please, Sign In to add comment