"""
In-class coding

Bogosort is a stupidly-inefficient sort with runtime O(n * n!).
Write a program that accepts user input of three types:

1. If the input contains 1 or more integers, sort the list with bogosort
2. If the input starts with an L, list the completed sorts
3. If the input starts with a Q, stop the program

Because bogosort can take a long time (especially with lists of 10 or more integers),
sorting should happen in a separate thread from the one handling user input.

This implementation uses one worker thread per task,
trusting that list appending will synchronize properly.
To be more correct, the completed.append and enumerate(completed) lines should be in critical sections.
"""

from threading import Thread

def bogosort(nums : list[int]) -> tuple[list[int], int]:
    import random
    steps = 0
    while not all(nums[i-1] <= nums[i] for i in range(1, len(nums))):
        random.shuffle(nums)
        steps += 1
    return nums, steps

completed : list[tuple[list[int], int]] = []

def ui():
    import re
    while True:
        entry = input("Integers, L, or Q: ").strip().upper()
        nums = [int(num) for num in re.findall('[0-9]+', entry)]
        if entry.startswith('L'):
            for i,(lst,cnt) in enumerate(completed):
                print(f'{i+1:2d}: {cnt:8d} steps to get {lst}')
        elif entry.startswith('Q'):
            break
        elif len(nums) > 0:
            t = Thread(target=worker, args=[nums])
            t.daemon = True
            t.start()

def worker(nums):
    completed.append(bogosort(nums))

ui()