Mini-Project-CF-Coloring/testColoring.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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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)

p1 = Point(-6,-2)
p2 = Point(-5,0)
p3 = Point(-2,-1)
p4 = Point(1,-4)
p5 = Point(-3,5)
p6 = Point(0,3)
p7 = Point(2,4)
p8 = Point(4,1)
p9 = Point(5,6)
maxCol = 0
points = [p1,p2,p3,p4,p5,p6,p7,p8,p9]
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("---------------------")

    # for i in findAscendingMonotone(Ypoints):
    #     print(i)

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

    # for i in findDescendingMonotone(Ypoints):
    #     print(i)

    while len(Ypoints) != 0:
        global maxCol
        maxCol +=1
        # tempLst1 = findAscendingMonotone(Ypoints)
        # tempLst2 = findDescendingMonotone(Ypoints)

        # if len(tempLst1) >=len(tempLst2):
        #     coloringList = tempLst1
        # else:
        #     coloringList = tempLst2
        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 = compareLists(ascLst, decLst)


    for i in range(len(lst)):
        checkAscLst = findAscendingMonotone(lst[i:])
        tempLst = compareLists(tempLst, checkAscLst)

        checkDesLst = findDescendingMonotone(lst[i:])
        tempLst = compareLists(tempLst, checkDesLst)


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

    return tempLst

def compareLists(lst1, lst2):
    lst = []
    if len(lst1) >=len(lst2):
        lst = lst1
    else:
        lst = lst2

    return lst

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()