SHARE
TWEET

CS3510 Final: Problem 4

apasterpastes Dec 14th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2. # coding: utf-8
  3.  
  4. # # Problem 4:
  5.  
  6. # In[143]:
  7.  
  8.  
  9. def problem_4(input_list):
  10.     # check length of list for end cases
  11.     if len(input_list) <= 4:
  12.         if len(input_list) % 2 == 0:
  13.             return None
  14.         else:
  15.             return input_list[0]
  16.     # try to split list in middle
  17.     middle = len(input_list)/2
  18.     before = int(middle)
  19.     after = before + 1
  20.     init_before = before
  21.     # account for case where we're in the middle of a string of one bit
  22.     while input_list[before] == input_list[after]:
  23.         before += 1
  24.         after += 1
  25.         if after == len(input_list):
  26.             before = 0
  27.             after = 1
  28.         # if looped all the way around, return this value
  29.         if before == init_before:
  30.             return input_list[0] if len(input_list) % 2 == 1 else None
  31.    
  32.     # recur down both sides, check for answer on way back up
  33.     res_before = problem_4(input_list[:before + 1])
  34.     res_after = problem_4(input_list[after:])
  35.     if res_before != None:
  36.         return res_before
  37.     else:
  38.         return res_after
  39.  
  40.  
  41. # In[145]:
  42.  
  43.  
  44. def problem_4_split_optim(input_list):
  45.     if len(input_list) <= 4:
  46.         if len(input_list) % 2 == 0:
  47.             return None
  48.         else:
  49.             return input_list[0]
  50.     middle = len(input_list)/2
  51.     before = int(middle)
  52.     after = before + 1
  53.     init_before = before
  54.     while input_list[before] == input_list[after]:
  55.         before += 1
  56.         after += 1
  57.         if after == len(input_list):
  58.             before = 0
  59.             after = 1
  60.         if before == init_before:
  61.             return input_list[0] if len(input_list) % 2 == 1 else None
  62.        
  63.     # THIS IS THE ONLY CHANGE, MAKES ALGORITHM LINEAR
  64.     if len(input_list[:before+1]) % 2 == 1:
  65.         return problem_4(input_list[:before + 1])
  66.    
  67.     return  problem_4(input_list[after:])    
  68.  
  69.  
  70. # In[146]:
  71.  
  72.  
  73. problem_4([0,0,0,0,1,1,0,0,1,1,1,0,0])
  74.  
  75.  
  76. # In[147]:
  77.  
  78.  
  79. problem_4([0,0,0,1,1,0,0,0,0,1,1,1,1])
  80.  
  81.  
  82. # In[148]:
  83.  
  84.  
  85. problem_4_optim([0,0,0,0,1,1,0,0,1,1,1,0,0])
  86.  
  87.  
  88. # In[149]:
  89.  
  90.  
  91. problem_4_optim([0,0,0,1,1,0,0,0,0,1,1,1,1])
  92.  
  93.  
  94. # # Generate Random Data
  95.  
  96. # In[150]:
  97.  
  98.  
  99. import random
  100.  
  101.  
  102. # In[151]:
  103.  
  104.  
  105. def generate_data(size=10):
  106.     l = []
  107.     already_added = False
  108.     answer = None
  109.     for i in range(size):
  110.         bit_type = random.random()
  111.         bit = 1 if bit_type > 0.5 else 0
  112.         bit_size = random.random()
  113.         size = 4
  114.         if not already_added and bit_size < 0.05:
  115.             size = 3
  116.             answer = bit
  117.             already_added = True
  118.         elif bit_size < 0.5:
  119.             size = 2
  120.        
  121.         l.extend([bit]*size)
  122.     # if haven't already randomly ad
  123.     if not already_added:
  124.         bit_type = random.random()
  125.         bit = 1 if bit_type > 0.5 else 0
  126.         answer = bit
  127.         l.extend([bit]*3)
  128.    
  129.     return (l, answer)
  130.  
  131.  
  132. # In[155]:
  133.  
  134.  
  135. # test against random data
  136.  
  137.  
  138. # In[154]:
  139.  
  140.  
  141. num_correct = 0
  142. num_total = 100
  143. for i in range(num_total):
  144.     size = random.randint(1, 100)
  145.     data = generate_data(size=size)
  146.     ans = problem_4(data[0])
  147.     if ans == data[1]:
  148.         num_correct += 1
  149. print(num_correct / num_total)
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