study.py

import random
from collections import deque
from enum import Enum
from functools import total_ordering
import heapq
import math
import itertools

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 print_nodes(root, discovered):
    parent = None
    cur = root
    while cur is not None and parent not in discovered:
        if parent is not None:
            discovered.add(parent)
            print(f'Node{parent.value}.next_node = Node{cur.value}')
        parent = cur
        cur = cur.next_node


def print_linked_list(nodes):
    discovered = set()

    for node in nodes:
        if node not in discovered:
            print_nodes(node, discovered)


class ComplexityClass(Enum):
    CONSTANT = (-1, '{constant}')
    LOGARITHMIC = (0, '{coefficient}nlog{constant}(n)')
    LINEAR = (1, '{coefficient}n')
    LINERARITHMIC = (2, '{coefficient}nlog{constant}(n)')
    POLYNOMIAL = (3, '{coefficient}n^{constant}')
    EXPONENTIAL = (4, '{constant}^n')
    FACTORIAL = (5, '{coefficient}n!')


CONSTANT_LESS_CLASSES = {ComplexityClass.LINEAR, ComplexityClass.FACTORIAL}


@total_ordering
class Term:
    def __init__(self, term_type, constant, coefficient=None):
        self.term_type = term_type
        self.constant = None
        if term_type not in CONSTANT_LESS_CLASSES:
            self.constant = constant

        self.coefficient = coefficient

    def __eq__(self, other):
        if self.term_type != other.term_type:
            return False
        elif self.term_type == ComplexityClass.POLYNOMIAL:
            return self.constant != other.constant

        return True

    def __gt__(self, other):
        rank, _ = self.term_type.value
        other_rank, _ = other.term_type.value
        if rank > other_rank:
            return True
        elif self.term_type == ComplexityClass.POLYNOMIAL:
            return self.constant > other.constant

        return False

    def __str__(self):
        _, fmt = self.term_type.value
        coefficient = self.coefficient if self.coefficient > 1 else ''
        return fmt.format(constant=self.constant, coefficient=coefficient)

    def as_oh(self):
        _, fmt = self.term_type.value
        constant = self.constant
        if self.term_type in {ComplexityClass.LOGARITHMIC, ComplexityClass.LINERARITHMIC}:
            constant = ''
        return fmt.format(constant=constant, coefficient='')


def random_term():
    complexity_class = random.choice(list(ComplexityClass))
    constant = random.randint(2, 10)
    coefficient = random.randint(1, 100)
    return Term(complexity_class, constant, coefficient)


def test_big_oh():
    terms = [random_term() for _ in range(random.randint(2, 5))]
    expr = ' + '.join(str(t) for t in terms)
    print(f'T(n) = {expr}')
    dominant_term = max(terms)
    answer = input('Please input the complexity class of this function: ')
    if answer == dominant_term.as_oh():
        print('Correct!')
    else:
        print(f'Incorrect, actual answer: O({dominant_term.as_oh()})')


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)
        nodea.next_node = nodeb

    print_linked_list(nodes)

    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 random_heap(lower=1, upper=100, n=10):
    heap = [random.randint(lower, upper) for _ in range(n)]
    heapq.heapify(heap)
    return heap


def test_heap_insert():
    heap = random_heap()
    item_to_insert = random.randint(1, 100)
    print(f'Heap (MinHeap): {repr(heap)}')
    print(f'What does the heap look like after inserting {item_to_insert}?')
    answer = input('Enter heap (each number followed by space): ')
    arr = [int(n) for n in answer.split(' ')]
    heapq.heappush(heap, item_to_insert)
    if arr == heap:
        print('Correct')
    else:
        print(f'Incorrect, actual heap was {heap}.')


def test_heap_remove():
    heap = random_heap()
    item_to_remove = heap[0]
    print(f'Heap (MinHeap): {repr(heap)}')
    print(f'What does the heap look like after removing {item_to_remove}?')
    answer = input('Enter heap (each number followed by space): ')
    arr = [int(n) for n in answer.split(' ')]
    heapq.heappop(heap)
    if arr == heap:
        print('Correct')
    else:
        print(f'Incorrect, actual heap was {heap}.')


def test_construct_heap():
    heap = [random.randint(1, 100) for _ in range(10)]
    print(f'Array is {arr}')
    print(f'What does the min heap of this array look like?')
    answer = input('Enter heap (each number followed by space): ')
    arr = [int(n) for n in answer.split(' ')]
    heapq.heapify(heap)
    if arr == heap:
        print('Correct')
    else:
        print(f'Incorrect, heap was {heap}.')


def erdos_graph(size):
    ''' Construct a random graph using the erdos-renyi model.
    Uses a binomial distribution to produce a set of random edges between n nodes.
    '''
    graph = {chr(i + 97): [] for i in range(size)}
    probability = 2 * math.log(size) / size

    for vert_a, vert_b in itertools.combinations(list(graph), 2):
        include_edge = random.random() < probability
        if include_edge:
            graph[vert_a].append(vert_b)
            graph[vert_b].append(vert_a)

    return graph



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


main()