CS3510 Final: Problem 4

#!/usr/bin/env python
# coding: utf-8

# # Problem 4:

# In[143]:


def problem_4(input_list):
    # check length of list for end cases
    if len(input_list) <= 4:
        if len(input_list) % 2 == 0:
            return None
        else:
            return input_list[0]
    # try to split list in middle
    middle = len(input_list)/2
    before = int(middle)
    after = before + 1
    init_before = before
    # account for case where we're in the middle of a string of one bit
    while input_list[before] == input_list[after]:
        before += 1
        after += 1
        if after == len(input_list):
            before = 0
            after = 1
        # if looped all the way around, return this value
        if before == init_before:
            return input_list[0] if len(input_list) % 2 == 1 else None

    # recur down both sides, check for answer on way back up
    res_before = problem_4(input_list[:before + 1])
    res_after = problem_4(input_list[after:])
    if res_before != None:
        return res_before
    else:
        return res_after


# In[145]:


def problem_4_split_optim(input_list):
    if len(input_list) <= 4:
        if len(input_list) % 2 == 0:
            return None
        else:
            return input_list[0]
    middle = len(input_list)/2
    before = int(middle)
    after = before + 1
    init_before = before
    while input_list[before] == input_list[after]:
        before += 1
        after += 1
        if after == len(input_list):
            before = 0
            after = 1
        if before == init_before:
            return input_list[0] if len(input_list) % 2 == 1 else None

    # THIS IS THE ONLY CHANGE, MAKES ALGORITHM LINEAR
    if len(input_list[:before+1]) % 2 == 1:
        return problem_4(input_list[:before + 1])

    return  problem_4(input_list[after:])


# In[146]:


problem_4([0,0,0,0,1,1,0,0,1,1,1,0,0])


# In[147]:


problem_4([0,0,0,1,1,0,0,0,0,1,1,1,1])


# In[148]:


problem_4_optim([0,0,0,0,1,1,0,0,1,1,1,0,0])


# In[149]:


problem_4_optim([0,0,0,1,1,0,0,0,0,1,1,1,1])


# # Generate Random Data

# In[150]:


import random


# In[151]:


def generate_data(size=10):
    l = []
    already_added = False
    answer = None
    for i in range(size):
        bit_type = random.random()
        bit = 1 if bit_type > 0.5 else 0
        bit_size = random.random()
        size = 4
        if not already_added and bit_size < 0.05:
            size = 3
            answer = bit
            already_added = True
        elif bit_size < 0.5:
            size = 2

        l.extend([bit]*size)
    # if haven't already randomly ad
    if not already_added:
        bit_type = random.random()
        bit = 1 if bit_type > 0.5 else 0
        answer = bit
        l.extend([bit]*3)

    return (l, answer)


# In[155]:


# test against random data


# In[154]:


num_correct = 0
num_total = 100
for i in range(num_total):
    size = random.randint(1, 100)
    data = generate_data(size=size)
    ans = problem_4(data[0])
    if ans == data[1]:
        num_correct += 1
print(num_correct / num_total)