• API
• FAQ
• Tools
• Archive
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 = []
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
115.             size = 3
118.         elif bit_size < 0.5:
119.             size = 2
120.
121.         l.extend([bit]*size)
124.         bit_type = random.random()
125.         bit = 1 if bit_type > 0.5 else 0
127.         l.extend([bit]*3)
128.
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.

Top