SHARE
TWEET

Mystery Function (Codewars)

makispaiktis Dec 14th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2.  
  3. The mystery function is defined over the non-negative integers. The more common name of this function is concealed in order to not tempt you to search the Web for help in solving this kata, which most definitely would be a very dishonorable thing to do.
  4.  
  5. Assume num has n bits. Then mystery(num) is the number whose binary representation is the numth entry in the table T(n), where T(n) is defined recursively as follows:
  6.  
  7. T(1) = [0, 1]
  8. T(n + 1) is obtained by taking two copies of T(n), reversing the second copy, prepending each entry of the first copy with 0 and each entry of the reversed copy with 1, and then concatenating the two. For example:
  9.  
  10. T(2) = [ 00, 01, 11, 10 ]
  11. and
  12.  
  13. T(3) = [ 000, 001, 011, 010, 110, 111, 101, 100 ]
  14. mystery(6) is the 6th entry in T(3) ( with indexing starting at 0 ), i.e., 101 interpreted as a binary number. So, mystery(6) returns 5.
  15.  
  16. Your mission is to implement the function mystery, where the argument may have up to 63 bits. Note that T(63) is far too large to compute and store, so you'll have to find an alternative way of implementing mystery. You are also asked to implement mystery_inv ( or mysteryInv ), the inverse of mystery. Finally, you are asked to implement a function name_of_mystery ( or nameOfMystery ), which shall return the name that mystery is more commonly known as. After passing all tests you are free to learn more about this function on Wikipedia or another place.
  17.  
  18. Hint: If you don't know the name of mystery, remember there is information in passing as well as failing a test.
  19.  
  20. '''
  21.  
  22.  
  23. import math
  24.  
  25. # 1. Display the vector
  26. def displayVector(v):
  27.     for i in range(0, len(v)):
  28.         print(v[i])
  29.  
  30.  
  31. # 2. Decimal To Binary
  32. def decimalToBinary(num):
  33.     num = int(abs(num))
  34.     digits = []
  35.     if num == 0:
  36.         digits.append(0)
  37.         return digits
  38.  
  39.     numOfDigits = (int)(math.log2(num)) + 1
  40.     for i in range(numOfDigits-1, -1, -1):
  41.         if num >= pow(2, i):
  42.             digits.append(1)
  43.             num -= pow(2, i)
  44.         else:
  45.             digits.append(0)
  46.  
  47.     return digits
  48.  
  49.  
  50. # 3. Binary to Decimal
  51. def binaryToDecimal(v):
  52.     sum = 0
  53.     # If i have input = [1, 0, 1, 1, 0] ---->  1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 2 * 2^1 + 0 * 1^0
  54.     for i in range(0, len(v)):
  55.         sum += (v[i] * 2**(len(v)-1-i))
  56.     return sum
  57.  
  58. # 4. Create T-Map
  59. def TMap(n):
  60.     TMap1 = ['0', '1']
  61.     if n == 1:
  62.         return TMap1
  63.     elif n>1:
  64.         firstCopy = TMap(n-1)
  65.         secondCopy = firstCopy.copy()
  66.         for i in range(0, len(firstCopy)):
  67.             firstCopy[i] = '0' + firstCopy[i]
  68.             secondCopy[i] = '1' + secondCopy[i]
  69.         secondCopy.reverse()
  70.         result = firstCopy + secondCopy
  71.         return result
  72.  
  73.  
  74. # 5. Our mystery function
  75. def mystery(number):
  76.     binary = decimalToBinary(number)
  77.     n = len(binary)
  78.     tmap = TMap(n)
  79.     stringInPositionNumber = tmap[number-1]
  80.     # Convert the string into a list of integers
  81.     myList = []
  82.     for i in range(0, len(stringInPositionNumber)):
  83.         if stringInPositionNumber[i] == '0' or stringInPositionNumber[i] == '1':
  84.             myList.append((int)(stringInPositionNumber[i]))
  85.     decimal = binaryToDecimal(myList)
  86.     print()
  87.     print("mystery(" + str(number) +") = " + str(decimal) + ", because: ")
  88.     print("1:    The binary equal for " + str(number) + " is:   " + ' '.join(map(str, binary)))
  89.     print("2:    " + ' '.join(map(str, binary)) + " has " + str(n) + " digits")
  90.     print("3.    " + "So, we will create the map TMap(" + str(n) + ") = " + str(tmap))
  91.     print("4.    " + "We are going to select the element in position " + str(number) + " of TMap(" + str(n) + "), which is " + stringInPositionNumber)
  92.     print("5.    " + "Finally, we will convert " + stringInPositionNumber + " into decimal, which is: " + str(decimal))
  93.  
  94.  
  95. # **********************************************************************************************************************
  96. # **********************************************************************************************************************
  97. # **********************************************************************************************************************
  98. # **********************************************************************************************************************
  99. # MAIN FUNCTION
  100. print()
  101. print("***********************************************************************")
  102. number = int(input("Write down a number to pass it as an argument in my mystery function: "))
  103. print("***********************************************************************")
  104. mystery(number)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top