hackathon2017/SortingAlgorithm.py at master · HackathonAnyway/hackathon2017 · 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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
import time

class obj:
    """unsorted list objects, obtain from back-end database"""
    def __init__(self,id,begin,last):
        self.id = id
        self.begin = begin
        self.last = last

class Sorting:
    """
    TimeVec: n*n vector for storing the distance from server
    TimeDiff: pre-regulated time between different actions
    sequence: the arranged time provided to the user
    UnsortedList: the waiting list to be sorted
    [
        id:
        begin:
        last:
        location:
    ]
    """
    def __init__(self,TimeVec,TimeDiff,UnSortedList,beginTime = 0,endTime = 86400):
        self.TimeVec = TimeVec #attain from database
        self.TimeDiff = TimeDiff #attain from database
        self.UnSortedList = UnSortedList
        self.sequence = []
        # self.currentTime = time.time()
        self.currentTime = 0
        self.beginTime = beginTime
        self.endTime=endTime

    def GetTravellingTime(self, begin_id,end_id):
        return TimeVec[begin_id][end_id]

    def GreedyRoute(self):
        ''' rrange the marked schedule'''
        cnt1 = 0
        for i in self.UnSortedList:
            if i.begin != -1:
                i.last += self.TimeDiff #the lasting Time has been prolonged for "Timediff" sec
                self.sequence.append(i)
                self.UnSortedList.remove(i) #remove the user-defined ones
                # print("self.sequence=",self.sequence[:])
                cnt1+=1
        #consider the problem for "no sorted list"

        '''arrange the unmarked schedule'''
        # 1. search for min-time-range
        TimeInterval = [] #record the time intervals between two different positioned works
        # ScheduleInsertion = [] #record the inserted schedule between diff intervals
        newTime = [] #[time interval,beginid,[schedule in between]]
        newTime.append(self.sequence[0].begin-self.currentTime-self.TimeDiff)
        newTime.append(0);
        newTime.append([]);
        TimeInterval.append(newTime)
        # ScheduleInsertion.append([])
        # TimeInterval.append(sequence[0].begin-self.currentTime)
        for i in range(0,len(self.sequence)-1):
            print("i",i)
            # newSchedule = []
            # ScheduleInsertion.append(newSchedule)
            newTime = []
            newTime.append(self.sequence[i+1].begin-(self.sequence[i].begin+self.sequence[i].last))
            newTime.append(self.sequence[i].id)
            newTime.append([])
            TimeInterval.append(newTime)
        TimeInterval.append([self.endTime-(self.sequence[len(self.sequence)-1].begin+self.sequence[len(self.sequence)-1].last),self.sequence[len(self.sequence)-1].id,[]])
        # newSchedule = []
        # ScheduleInsertion.append(newSchedule)
        # print("schedule insertion", ScheduleInsertion)
        TimeInterval.sort(cmp = None,key = lambda x:x[0],reverse=False)
        #2. insert objects according to a greedy schedule
        SortedSequence = self.UnSortedList
        begin_id = 0 # from current place
        for i in SortedSequence:
            i.last += self.GetTravellingTime(begin_id,i.id)
            print i.last
        SortedSequence = sorted(self.sequence,key = lambda x :x.last,reverse=False)#sorted schemes to be planned
        cnt = 0
        valid = True
        while len(SortedSequence):
            """
            for insertion into every single piece
            try
            """
            if cnt == len(TimeInterval)-1:
                if  TimeInterval[cnt][0]- cur.last < self.TimeDiff:
                    print("No appropriate solution.")
                    valid = False
                    break
                else:
                    cur.begin = self.endTime - (TimeInterval[cnt][0]-self.TimeDiff)
                    # cur.begin = self.sequence(TimeInterval[cnt][1])+TimeInterval[cnt][0]+self.TimeDiff
                    TimeInterval[cnt][2].append(cur)
                    TimeInterval[cnt][0] -= (cur.last + self.TimeDiff)
                    SortedSequence.remove(SortedSequence[0])
                    begin_id = cur.id
                    for i in SortedSequence:
                        i.last += self.GetTravellingTime(begin_id,i.id)
                    cnt = 0
                    # SortedSequence = self.UnSortedList
                    continue

            cur = SortedSequence[0]
            if TimeInterval[cnt][0] - cur.last < self.TimeDiff:
                cnt+=1
                continue
            cur.begin = TimeInterval[cnt+1][0] - (TimeInterval[cnt][0]-self.TimeDiff)
            TimeInterval[cnt][2].append(cur)
            # ScheduleInsertion[TimeInterval[cnt][1]+1].append(cur)
            TimeInterval[cnt][0] -= (cur.last + self.TimeDiff)
            """between schedule insertion, the scheule marked 0 means from current status to the 1st scheme, and so on and so on.."""
            SortedSequence.remove(SortedSequence[0])
            begin_id = cur.id
            for i in SortedSequence:
                i.last += self.GetTravellingTime(begin_id,i.id)
            cnt = 0
            # SortedSequence = self.UnSortedList
        if valid:
            for i in TimeInterval:
                print i


TimeVec = [[0,3,2,6],[3,0,4,2],[2,4,0,5],[6,2,5,0]]
TimeDiff = 0.05
A = obj(0,1,0.5)
B = obj(1,-1,3)
C = obj(2,1.5,3)
D = obj(3,-1,2)

UnSortedList = []
UnSortedList.append(A)
UnSortedList.append(B)
UnSortedList.append(C)
UnSortedList.append(D)

res = Sorting(TimeVec,TimeDiff,UnSortedList)
res.GreedyRoute()