study.py

import random
from collections import deque

with open('words.txt') as infile:
    WORDS = [l.strip() for l in infile]

def nice_hash(val):
    value = ord(val[0]) << 7
    for char in val:
        value = ((1000003 * value) & 0xFFFFFFFF) ^ ord(char)
    value = value ^ len(val)
    if value == -1:
        value = -2
    return value


def insert_value(hashtable, hash_type, value):

    cur = nice_hash(value) % len(hashtable)
    collisions = 0
    while hashtable[cur] is not None:
        collisions += 1
        if hash_type == 'quadratic':
            cur += collisions ** 2
            cur = cur % len(hashtable)
        else:
            cur = (cur + 1) % len(hashtable)

    hashtable[cur] = value
    return collisions


def print_hashtable(hashtable):
    for index, val in enumerate(hashtable):
        print(f'{index}: {val}')


def test_probing():
    hash_type = random.choice(['linear', 'quadratic'])
    collisions_required = random.randint(1, 4)
    hashtable_length = random.randint(5, 15)
    hashtable = [None] * hashtable_length
    collisions_met = False
    last_value = None
    last_hashtable = None
    inserted_items = []
    while collisions_met is False:
        value_to_store = random.choice(WORDS)
        load_factor = (len(inserted_items) + 1) / len(hashtable)
        cycle_danger = False
        if hash_type == 'quadratic' and load_factor > 0.5:
            # This is the last attempt we can make before possibility
            # of infinite cycles, so we'll instead insert an already inserted element.
            # This will force at least one collision.
            value_to_store = random.choice(inserted_items)
            cycle_danger = True
        elif load_factor > 1:
            # This is the last attempt we can make before possibility
            # (in a LINEAR probing hashtable)
            # of infinite cycles, so we'll instead insert an already inserted element.
            # This will force at least one collision.
            value_to_store = random.choice(inserted_items)
            cycle_danger = True

        inserted_items.append(value_to_store)
        last_hashtable = hashtable[:]
        collisions = insert_value(hashtable, hash_type, value_to_store)
        inserted_items.append(value_to_store)
        collisions_met = cycle_danger or collisions >= collisions_required
    last_value = inserted_items[-1]
    inserted_place = nice_hash(value_to_store) % len(hashtable)
    print(f'The value {last_value} hashes to {inserted_place}')
    print(f'The current state of the {hash_type} probing hashtable (length: {hashtable_length}) is:')
    print_hashtable(last_hashtable)
    location = int(input('Where does the new value go? '))
    if hashtable[location] == last_value:
        print('Correct!')
    else:
        print('Nope. Take a look at the new hashtable:')
        print_hashtable(hashtable)



def shellSort(alist, gaplist):
    comparisons = 0
    for gap in gaplist:
        for startposition in range(gap):
            comparisons += gapInsertionSort(alist, startposition, gap)

    return comparisons


def gapInsertionSort(alist,start,gap):
    comparisons = 0
    for i in range(start+gap,len(alist),gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position-gap] > currentvalue:
            comparisons += 1
            alist[position] = alist[position - gap]
            position -= gap

        if position >= gap:
            comparisons += 1

        alist[position] = currentvalue
    return comparisons


def test_shellsort():
    lst_length = random.randint(8, 16)
    lst = random.choices(list(range(lst_length)), k=random.randint(5, lst_length))
    conditions = [lambda l: None, lambda l: sorted(l, reverse=True), lambda l: random.shuffle(l)]

    lst = random.choice(conditions)(lst) or lst

    gap = random.randint(1, (len(lst) // 2))
    print(f'Please show the list {lst} after applying a {gap}-sort to it.')
    print('Separate each value with a space')
    comparisons = shellSort(lst, [gap])
    new_lst = [int(el) for el in input('New List: ').split()]
    if new_lst != lst:
        print(f'You said {new_lst}, when actually it was {lst}')
    else:
        print('Correct!')

    user_comparisons = int(input('How many comparisons did would that take? '))
    if comparisons == user_comparisons:
        print('That\'s correct too!')
    else:
        print(f'Oops, maybe not, the actual answer is {comparisons}')

PRECENDENCE = {'+': 0, '-': 0, '*': 1, '/': 1}

def infix_to_postfix(infix):
    ''' Convert an infix expression to a postfix expression. '''
    stack = []
    output = []
    for token in infix:
        if type(token) == int:
            output.append(token)
        elif token == ')':
            while len(stack) and stack[-1] != '(':
                output.append(stack.pop())
            if stack != []:
                stack.pop()
        elif token == '(':
            stack.append(token)
        else:
            # token is an operator
            # look up token operator in precedence array
            precedence = PRECENDENCE[token]
            while len(stack) and PRECENDENCE.get(stack[-1], -1) >= precedence:
                output.append(stack.pop())
            stack.append(token)
    output += stack
    return output


def gen_infix(term_count):
    '''generate random infix expression'''
    output = [random.randint(1, 10)]
    open_brackets = 0
    terms_counted = 1
    while terms_counted < term_count:
        last_is_number = type(output[-1]) == int
        if output[-1] in PRECENDENCE and random.random() < 0.2:
            output.append('(')
            open_brackets += 1
        elif output[-1] == '(' or output[-1] in PRECENDENCE:
            output.append(random.randint(1, 10))
            terms_counted += 1
        elif last_is_number and open_brackets > 0 and random.random() < 0.2:
            output.append(')')
            open_brackets -= 1
        elif last_is_number or output[-1] == ')':
            output.append(random.choice(list(PRECENDENCE)))

    output += open_brackets * [')']
    return output


OP_MAP = {'+': lambda a, b: a + b, '-': lambda a, b: a - b, '*': lambda a, b: a * b, '/': lambda a, b: a / b}

def evaluate_postfix(expr):
    stack = []
    for token in expr:
        if type(token) == int:
            stack.append(token)
        else:
            a, b = tuple(stack[-2:])
            stack = stack[:-2]
            stack.append(OP_MAP[token](a, b))
    return stack[-1]

def test_infix_to_postfix():
    infix = gen_infix(random.randint(5, 10))
    infix_str = ' '.join(str(e) for e in infix)
    print(f'Convert this infix expression to postfix notation: {infix_str}')
    print('Leave spaces around every term.')
    postfix = [str(e) for e in infix_to_postfix(infix)]
    answer = input('Postfix: ').split()
    if postfix == answer:
        print('Correct')
    else:
        print('That is incorrect.')
        postfix_str = ' '.join(postfix)
        print(f'The correct postfix expression is: {postfix_str}')

def test_postfix_evaluate():
    postfix = infix_to_postfix(gen_infix(random.randint(5, 10)))
    print('Please evaluate this postfix expression, use ERR if divide by zero occurs: ')
    postfix_str = ' '.join(str(e) for e in postfix)
    print('(round to 4dp)')
    print(postfix_str)
    answer = None
    try:
        answer = evaluate_postfix(postfix)
    except ArithmeticError:
        pass

    user_answer = input('Answer: ')
    if answer is None and answer == 'ERR':
        print('This was a malformed expresssion, you are correct!')
    elif round(answer, 4) == user_answer:
        print('Correct!')
    else:
        print(f'Sorry, the actual answer was {round(answer, 4)}')


def test_queue_inserts():
    statements = random.randint(5, 10)
    queue = deque()
    var_table = {}
    print('Given that the following code manipulating a queue has run:')
    for i in range(statements):
        statement_choices = [('enqueue_front', deque.append),
                             ('enqueue_rear', deque.appendleft)]
        if len(queue) > 0:
            statement_choices += [('dequeue_front', deque.pop),
                                  ('dequeue_rear', deque.popleft)]

        stmt_type, stmt_func = random.choice(statement_choices)
        val = random.randint(1, 10)
        if stmt_type in {'enqueue_front', 'enqueue_rear'}:
            stmt_func(queue, val)
            print(f'd.{stmt_type}({val})')
        else:
            var = chr(random.randint(97, 122))
            print(f'{var} = d.{stmt_type}()')
            var_table[var] = stmt_func(queue)

    chosen_var = random.choice(list(var_table))
    print(f'What is the value of {chosen_var}?')
    user_response = int(input(f'{chosen_var} = '))
    if user_response == var_table[chosen_var]:
        print('Correct!')
    else:
        print(f'Incorrect, {chosen_var} actually was {var_table[chosen_var]}')


class Node:
    def __init__(self, value, next_node):
        self.value = value
        self.next_node = next_node


def test_linked_list():
    nodes = []
    node_count = random.randint(4, 8)
    for index in range(node_count):
        print(f'node{index} = Node({index})')
        nodes.append(Node(index, None))

    assignments = random.randint(5, 8)
    for i in range(assignments):
        nodea = random.choice(nodes)
        nodeb = random.choice(nodes)
        print(f'node{nodea.value}.next_node = node{nodeb.value}')
        nodea.next_node = nodeb

    paths_travelled = random.randint(2, 5)
    cur = 0
    cur_node = random.choice([node for node in nodes if node.next_node])
    next_nodes = f'print(node{cur_node.value}'
    while cur_node.next_node is not None and paths_travelled > cur:
        cur_node = cur_node.next_node
        cur += 1
        next_nodes += '.next_node'
    next_nodes += ')'
    print(next_nodes)
    print('What is printed?')
    val = int(input('Printed: '))
    if val == cur_node.value:
        print('Correct!')
    else:
        print(f'Incorrect, correct answer was {cur_node.value}')





def main():
    for i in range(20):
        test = random.choice([test_shellsort,
                              test_probing,
                              test_infix_to_postfix,
                              test_linked_list,
                              test_queue_inserts,
                              test_postfix_evaluate])
        test()
main()