battlesort

battlesort.py

import math
from random import random
from abc import ABC

__all__ = [
    'Thing', 'battle'
]


class Thing(ABC):
    def __init__(self, name: str) -> None:
        self.name = name
        self.id = random()
        self.ties = set()

    def __repr__(self) -> str:
        return self.name

    __str__ = __repr__

    def __eq__(self, other) -> bool:
        if not isinstance(other, Thing):
            return NotImplemented
        return self.id in other.ties or other.id in self.ties


def battlesort(m: list[Thing]) -> list[Thing]:
    if len(m) <= 1:
        return m

    midpoint = math.ceil(len(m) / 2)
    left, right = m[:midpoint], m[midpoint:]

    left = battlesort(left)
    right = battlesort(right)

    return merge(left, right)


def merge(left: list[Thing], right: list[Thing]) -> list[Thing]:
    result = []

    while left and right:
        l_ = '<'  # for str formatting
        t_ = '='
        r_ = '>'

        if left[0] == right[0]:  # if already tied skip (don't think this is possible usually unless from resume data)
            ans = '='
        else:
            print(f"{str(left[0]):^25} or {str(right[0]):^25}\n"  # user input prompt
                  f"{l_:^25}{t_:^4}{r_:^25}")

            ans = input()
            while ans not in '<=>':  # prevent user input error
                print(f"{l_:^25}{t_:^4}{r_:^25}")
                ans = input()

        match ans:
            case '<':
                result.append(temp := left.pop(0))  # add left to merge list
                try:
                    while left[0] == temp:  # while next element is tied, keep adding them (skip user input)
                        result.append(temp := left.pop(0))
                        if len(left) == 0:  # prevent index error from closing the while loop
                            break
                except IndexError:  # if right was already exhausted skip the while loop entirely
                    pass
            case '>':
                result.append(temp := right.pop(0))
                try:
                    while right[0] == temp:
                        result.append(temp := right.pop(0))
                        if len(right) == 0:
                            break
                except IndexError:
                    pass
            case '=':
                left[0].ties.add(right[0].id)
                right[0].ties.add(left[0].id)

                for item in left[1:]:  # add right id to existing ties on the left
                    if item == left[0]:
                        item.ties.add(right[0].id)
                for item in right[1:]:
                    if item == right[0]:
                        item.ties.add(left[0].id)

                result.append(temp := left.pop(0))
                try:
                    while left[0] == temp:
                        result.append(temp := left.pop(0))
                        if len(left) == 0:
                            break
                except IndexError:
                    pass

                result.append(temp := right.pop(0))
                try:
                    while right[0] == temp:
                        result.append(temp := right.pop(0))
                        if len(right) == 0:
                            break
                except IndexError:
                    pass

    while left:  # if right is exhasuted, keep adding from left
        result.append(left.pop(0))

    while right:
        result.append(right.pop(0))

    return result


def fancy_print(m: list[Thing]) -> None:
    x = 1
    nxt = m.pop(0)
    print(f'{x:<4}| {str(nxt):^25}')
    while len(m) > 0:
        while m[0] == nxt:
            nxt = m.pop(0)
            print(f'    | {str(nxt):^25}')
            if len(m) == 0:
                break
        if len(m) == 0:
            break
        print('-' * 31)
        x += 1
        nxt = m.pop(0)
        print(f'{x:<4}| {str(nxt):^25}')
    print('-' * 31)


def battle(m: list[Thing]) -> None:
    fancy_print(battlesort(m))

Example script for movies:

from typing import Optional

from battlesort import *


class Watcher:
    def __init__(self, name: str):
        self.name = name

    def __repr__(self):
        return self.name

    __str__ = __repr__


# example of something you can compare
class Movie(Thing):
    def __init__(self, name: str, year: int, watchers: Optional[list[Watcher]] = None):
        super().__init__(name)
        self.year = year
        self.watchers = watchers

    def __repr__(self):
        return f'{self.name} ({self.year})'

    __str__ = __repr__


# example of how we can create extended types based on what we are comparing
class TV(Movie):
    def __init__(self, name: str, year: int, watchers: Optional[list[Watcher]] = None):
        super().__init__(name, year, watchers)

    def __repr__(self):
        return f'{self.name} ({self.year}) [TV]'

    __str__ = __repr__


def watchers(*names: str):
    x = []
    if len(names) == 1:
        names = names[0].split()
    for name in names:
        x.append(Watcher(name))
    return x


nick, austin, antonio, kyle, tarik, matt, dave, dan, tom, phil, jay, jack = watchers(
    'Nick Austin Antonio Kyle Tarik Matt Dave Dan Tom Phil Jay Jack')

all_rotten = [
    Movie('The Big Lebowski',
          1998,
          [nick, austin, antonio, kyle]),
    Movie('There Will Be Blood',
          2007,
          [nick, antonio, kyle]),
    Movie('The Big Short',
          2015,
          [nick, austin, kyle]),
    Movie('Moneyball',
          2011,
          [nick, austin, antonio, kyle, tarik]),
    TV('Chernobyl',
       2019,
       [nick, austin, antonio, kyle]),
    Movie('The Lighthouse',
          2019,
          [nick, austin, antonio, kyle]),
    Movie('In Bruges',
          2008,
          [kyle, austin, antonio]),
    Movie('Mother',
          2009,
          [nick, antonio, kyle]),
    Movie('Being John Malkovich',
          1999,
          [kyle, antonio, matt, nick]),
    Movie('Memories of Murder',
          2003,
          [antonio, kyle, nick]),
    Movie('Apocalypse Now',
          1979,
          [kyle, dan, antonio, dave]),
    Movie('Forgotten',
          2017,
          [kyle, nick]),
    Movie('Chef',
          2014,
          [nick, austin, antonio, kyle]),
    Movie('Train to Busan',
          2016,
          [austin, antonio, kyle]),
    Movie('Unforgiven',
          1992,
          [antonio, austin, kyle]),
    Movie('Minari',
          2020,
          [kyle, tarik]),
    Movie('The Lobster',
          2015,
          [nick, antonio, kyle]),
    Movie('Office Space',
          1999,
          [nick, austin, antonio, kyle, tom, phil]),
    Movie('The Deer Hunter',
          1978,
          [nick, austin, antonio, kyle, phil]),
    Movie('L.A. Confidential',
          1997,
          [nick, austin, antonio, kyle]),
    Movie('The Suicide Squad',
          2021,
          [nick, austin, matt, tom, tarik, kyle, jay]),
    Movie('Three Billboards Outside Ebbing, Missouri',
          2017,
          [nick, austin, antonio, kyle]),
    Movie('Swiss Army Man',
          2016,
          [nick, dan, antonio, kyle, jack, dave]),
    Movie('American History X',
          1998,
          [nick, austin, antonio, kyle]),
    Movie('District 9',
          2009,
          [nick, austin, antonio, kyle, tom]),
    Movie('The Gentlemen',
          2019,
          [matt, kyle]),
    Movie('The Ringer',
          2005,
          [kyle, antonio, matt, nick]),
    Movie('The Master',
          2012,
          [antonio, austin, phil, kyle]),
    Movie('12 Monkeys',
          1995,
          [nick, kyle, jack, austin, antonio, phil]),
    Movie('Run',
          2020,
          [nick, antonio, kyle]),
    Movie('One Hour Photo',
          2002,
          [kyle, austin, nick, antonio]),
    Movie('Scream',
          1996,
          [nick, kyle, dan, austin, tarik, phil]),
    Movie('Logan Lucky',
          2017,
          [nick, kyle]),
    Movie('Cars',
          2006,
          [dave, nick])
]


def battle_and(*names: Watcher):
    x = []
    for movie in all_rotten:
        if all(name in movie.watchers for name in names):
            x.append(movie)

    return battle(x)


def battle_or(*names: Watcher):
    x = []
    for movie in all_rotten:
        if any(name in movie.watchers for name in names):
            x.append(movie)

    return battle(x)

Example sorting output with ties (~60 compares for 34 items).

1   | The Suicide Squad (2021) 
    | Three Billboards Outside Ebbing, Missouri (2017)
    | American History X (1998)
    |     The Ringer (2005)    
    |     12 Monkeys (1995)    
-------------------------------
2   |     The Master (2012)    
    |        Run (2020)        
-------------------------------
3   |   The Lighthouse (2019)  
    |     In Bruges (2008)     
    |       Mother (2009)      
    |       Scream (1996)      
-------------------------------
4   |   The Big Short (2015)   
    | Being John Malkovich (1999)
    |     Forgotten (2017)     
    |        Chef (2014)       
-------------------------------
5   |       Minari (2020)      
-------------------------------
6   |   Chernobyl (2019) [TV]  
-------------------------------
7   |  The Big Lebowski (1998) 
    | Memories of Murder (2003)
    |   Train to Busan (2016)  
    |     Unforgiven (1992)    
    |    The Lobster (2015)    
-------------------------------
8   |   Swiss Army Man (2016)  
    |     District 9 (2009)    
    |   One Hour Photo (2002)  
    |        Cars (2006)       
-------------------------------
9   |   The Gentlemen (2019)   
-------------------------------
10  | There Will Be Blood (2007)
    |     Moneyball (2011)     
    |    Office Space (1999)   
    | L.A. Confidential (1997) 
-------------------------------
11  |   Apocalypse Now (1979)  
    |  The Deer Hunter (1978)  
    |    Logan Lucky (2017)    
-------------------------------