strong-sort/main.py at main · Torumi/strong-sort · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from defaultlist import defaultlist

from colorama import Fore, Style

ALPHABET = "aābcčdeēfgģhiījkķlļmnņoprsštuūvzž"


def split_list(l: list, correct_indexes: list[int]) -> list[list[int | list]]:
    parts = []
    part = [0, []]
    for i in range(len(l)):
        if i in correct_indexes:
            if part[1]:
                parts.append(part)
            part = [i + 1, []]
            continue
        part[1].append(l[i])
    if part[1]:
        parts.append(part)
    return parts


def string_sorted(s: str | list[str]) -> bool:
    for i in range(1, len(s)):
        if ALPHABET.index(s[i - 1]) > ALPHABET.index(s[i]):
            return False
    return True


def strong_sort(l: list[str], correct_indexes: list[int] | None = None):
    if correct_indexes is None:
        correct_indexes = []
    parts = split_list(l, correct_indexes)
    strings = defaultlist(lambda: ["_"] * len(l))
    # print("Sorting of: " + " ".join(l))
    # print(f"Parts: {parts}")
    print("\t".join([f"{Fore.GREEN}{Style.BRIGHT}{l[i]}{Style.RESET_ALL}" if i in correct_indexes else l[i] for i in
                     range(len(l))]))
    for string_start, l_part in parts:
        string_index = 0
        current_index = 0
        comparing_index = len(l_part) - 1
        d = -1
        while current_index != comparing_index:
            strings[string_index][string_start + current_index] = l_part[current_index]
            strings[string_index][string_start + comparing_index] = l_part[comparing_index]
            string_index += 1
            if not ((current_index < comparing_index) ^ (
                    ALPHABET.index(l_part[current_index]) > ALPHABET.index(l_part[comparing_index]))):
                l_part[current_index], l_part[comparing_index] = l_part[comparing_index], l_part[current_index]
                current_index, comparing_index = comparing_index, current_index
                strings[string_index][string_start + current_index] = l_part[current_index]
                strings[string_index][string_start + comparing_index] = l_part[comparing_index]
                string_index += 1
                d *= -1
            comparing_index += d
        correct_indexes.append(string_start + current_index)
        if string_start + current_index + 1 < len(l) and string_start + current_index + 2 in (*correct_indexes, len(l)):
            correct_indexes.append(string_start + current_index + 1)
        if string_start + current_index - 1 >= 0 and string_start + current_index - 2 in (*correct_indexes, -1):
            correct_indexes.append(string_start + current_index - 1)
        for i in range(len(l_part)):
            l[string_start + i] = l_part[i]
    for string in strings:
        print("\t".join(string))
    print()
    print("\t".join([f"{Fore.GREEN}{Style.BRIGHT}{l[i]}{Style.RESET_ALL}" if i in correct_indexes else l[i] for i in
                     range(len(l))]))
    return l, correct_indexes


def main():
    sorting_string = list(
        input("Sorting string: ").lower().replace(" ", "").replace("\t", "")
    )
    temp = []
    for index, letter in enumerate(sorting_string):
        if letter not in sorting_string[:index]:
            temp.append(letter)
    sorting_string = temp
    expected_list = list(sorted(sorting_string, key=lambda symb: ALPHABET.index(symb)))
    print(f"Given list: {sorting_string}")
    print(f"Expected list: {expected_list}")
    i = 1
    correct_indexes = []
    while not string_sorted(sorting_string):
        print(f"{i})")
        sorting_string, correct_indexes = strong_sort(sorting_string, correct_indexes)
        i += 1
    print()
    print(f"{Style.BRIGHT}{Fore.GREEN}", end="")
    print('\t'.join(sorting_string))
    print(Style.RESET_ALL)


if __name__ == '__main__':
    main()