ronzhin-dmitry

#Good old worst-case for naive algorithm. Let's run Rabin-Karp on it.
import time
needle = 'a'*1000 + 'b'
haystack = 'a'*10000 + 'b'
result = []

start = time.time()
for i in range(50):
    result = search_Rabin_Karp(needle, haystack)
end = time.time()

ronzhin-dmitry

def string_hash(input_string, p): 
    #here we implement a simple hash function. It is made in such a way that
    #this hash function is easy to recalc when moving right on the string (see search function)
    #p is some modulo, usually large prime for good hashing
    result = ord(input_string[0])
    for i in range(1,len(input_string)):
        result *= p
        result += ord(input_string[i])
    return result % (2**64)

ronzhin-dmitry

#Just the same worst-case test as for naive case. But now we will have a much better time complexity
import time
needle = 'a'*1000 + 'b'
haystack = 'a'*10000 + 'b'
result = []

start = time.time()
buf_memory = [0] * (len(needle) + len(haystack) + 1)
start2 = time.time()
for i in range(50):

ronzhin-dmitry

def z_function(input_string, result): #memory pre-allocated
    n = len(input_string)
    left,right = 0,0 #we have two pointers which will slide through array, right will always show the border of now-known prefix
    for i in range(1,len(input_string)):
        result[i] = max(0, min(right-i, result[i-left])) #init with known prefix info
        while i + result[i] < n and input_string[result[i]] == input_string[i + result[i]]:
            result[i] += 1 #run to the right to check prefix-equality
        if i + result[i] > right: #if border moved - update left and right
            left = i
            right = i + result[i]

ronzhin-dmitry

#Worst case test of naive substring search    
import time
needle = 'a'*1000 + 'b' #so we search for a string with 1000 times letter 'a' and one letter 'b' at the end
haystack = 'a'*10000 + 'b' #and the haystack is almost like this, but longer
result = []

start = time.time()
for i in range(50): #we repeat 50 times just to better track time
    result = search_naive(needle, haystack)
end = time.time()

ronzhin-dmitry

#Naive algorithm to search all the appearences of a substring inside string
def search_naive(needle, haystack): #Search for a needle (i.e. search request) inside a haystack (i.e. text where we search)
    n = len(haystack)
    k = len(needle)
    result = []
    for i in range(n-k+1): #this is actually just a sliding window approach
        are_equal = True
        for j in range(k):
            are_equal = (haystack[i+j] == needle[j])
            if not are_equal:

ronzhin-dmitry

def rotate_with_cycles(arr,k): #inputs are array and number of steps to rotate k
    if k == 0:
        return arr #corner case
    n = len(arr)
    moved_counter = 0 #additional memory (total O(1))
    cur_start = 0
    pointer = k
    prev_element = arr[0]
    while moved_counter <n:
        buf = arr[pointer] #one more variable O(1) memory

ronzhin-dmitry

def rotate_with_reflections(arr,k): #inputs are array and number of steps to move k
    n = len(arr)
    for i in range(n//2): #make the first reflection - line from the first element of the array
        buf = arr[i] #additional memory O(1)
        arr[i] = arr[n-1-i]
        arr[n-1-i] = buf
    for i in range(k//2): #second reflection is made by parts to ease up code:
        buf = arr[i] #additional memory O(1)
        arr[i] = arr[k-1-i]
        arr[k-1-i] = buf

ronzhin-dmitry

def rotate_slow_cheap(arr, k): #inputs are array and the number of steps to rotate to the right k
    n = len(arr)
    for i in range(k): #k times repeat 1-step rotation
        last_element = arr[-1] #the only additional memory - О(1)
        for j  in range(n-1,0,-1):#move the values, traversing from the end of the array
            arr[j] = arr[j-1]
        arr[0] = last_element
    #time complexity is O(n*k)
    return arr

ronzhin-dmitry

import random

wins_random_search = 0
wins_permutation_search = 0
prisoners = 100 #num of prisoners
allowed_boxes = prisoners // 2 #how many boxes each of them checks
N = 10000 #number of experiments to run

for _ in range(N):
    numbers_in_boxes = [i for i in range(prisoners)]