Mini-Project-CF-Coloring/testColoring copy.py at main · AsafBitan/Mini-Project-CF-Coloring · 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
98
99
100
101
102
103
104
105
106
107
108
from Point import Point
p1 = Point(-2,-6)
p2 = Point(6,-2)
p3 = Point(-5,-1)
p4 = Point(2,4)
p5 = Point(6,4)
p6 = Point(6,-3)
p7 = Point(-2,-1)
p8 = Point(3,-4)
p9 = Point(-5,-0)
p0 = Point(3,1)
maxCol = 0
points = [p1,p2,p3,p4,p5,p6,p7,p8,p9,p0]
isOnlineAlg = False  # if RectangleAlg: =False
STUDENTS_ID = "318187101_209122381"  # change IDs


def rectangleColoringAlg():
    """
    students' algorithm for "rectangle coloring"
    methodology - one-time call for method.
    use a given "points" list, color all points.
    :param: no arguments (method called once)
    :return: nothing
    """
    global isOnlineAlg
    isOnlineAlg = False

    # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Ypoints = [x for x in points]
    Ypoints.sort(key=lambda point: (point.valueX, point.valueY))


    coloringList = []

    for i in Ypoints:
        print(i)

    print("---------------------")

    while len(Ypoints) != 0:
        global maxCol
        maxCol +=1
        coloringList = findLongestMonotone(Ypoints)

        for i in range(len(coloringList)):
            if i%2 == 0:
                coloringList[i].col_num = maxCol
                Ypoints.remove(coloringList[i])

    for i in points:
        print(i)


    # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    print(f"current max col is:{maxCol}")
    print(f"finished running rectangleColoringAlg...")
    return

def findLongestMonotone(lst):
    ascLst = findAscendingMonotone(lst)
    decLst = findDescendingMonotone(lst)
    tempLst = []

    for i in range(len(lst)):
        checkAscLst = findAscendingMonotone(lst[i:])
        checkDesLst = findDescendingMonotone(lst[i:])


    if len(ascLst) >=len(decLst):
        tempLst = ascLst
    else:
        tempLst = decLst

    return tempLst


def findAscendingMonotone(lst):
    ascLst = []
    curr = lst[0]
    i = 0
    while i <= len(lst)-1:
        if (curr.valueY <= lst[i].valueY):
            ascLst.append(lst[i])
            curr = lst[i]

        i = i + 1

    return ascLst

def findDescendingMonotone(lst):
    desLst = []
    curr = lst[0]
    i = 0
    while i <= len(lst)-1:
        if (curr.valueY >= lst[i].valueY):
            desLst.append(lst[i])
            curr = lst[i]

        i = i + 1

    return desLst


rectangleColoringAlg()