-
Notifications
You must be signed in to change notification settings - Fork 0
/
tt_generator.py
executable file
·192 lines (147 loc) · 4.73 KB
/
tt_generator.py
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
class TimetableGenerator:
def __init__(self):
self.generated = []
self.generated2 = []
self.total_combinations = 0
def store_timetable(self, tt):
self.total_combinations += 1
tt.heuristic = tt.total_time()
tt.heuristic2 = tt.total_time2()
if len(self.generated) <= 99:
self.generated.append(tt)
self.generated2.append(tt)
else:
if tt.heuristic < self.generated[99].heuristic: # tt is better
self.generated.pop(99)
self.generated.append(tt)
self.generated.sort(key=lambda tt: tt.heuristic)
if tt.heuristic2 < self.generated2[99].heuristic2: # tt is better
self.generated2.pop(99)
self.generated2.append(tt)
self.generated2.sort(key=lambda tt: tt.heuristic2)
def generate_timetables(self, lesson_blocks):
self.generate(Timetable(), lesson_blocks)
self.generated.sort(key=lambda tt: tt.heuristic)
self.generated2.sort(key=lambda tt: tt.heuristic2)
best = list(set(self.generated).intersection(set(self.generated2)))
for tt in best:
tt.score += len(self.generated) - self.generated.index(tt)
tt.score += len(self.generated2) - self.generated2.index(tt)
best.sort(key=lambda tt: tt.score, reverse=True)
return best[:100]
def generate(self, timetable, lesson_blocks):
if not lesson_blocks:
self.store_timetable(timetable)
else:
next_lesson_block = lesson_blocks[0]
for shift in next_lesson_block.shifts:
#if timetable.supports(shift):
self.generate(timetable.append_shift(shift), lesson_blocks[1:])
class Timetable:
def __init__(self):
self.lessons = []
self.score = 0
def append_shift(self, shift):
new_timetable = Timetable()
new_timetable.lessons.extend(self.lessons)
new_timetable.lessons.extend(shift.slots)
return new_timetable
def supports(self, shift):
for slot in shift.slots:
for existing in self.lessons:
if (slot.overlaps_with(existing)):
return False
return True
#def is_feasible(self):
# for slot in self.lessons:
# for other in self.lessons:
# if (slot is not other) and (slot.overlaps_with(other)):
# return False
# return True
# heuristics for selecting timetables
def total_time2(self):
result = 0
for weekday in range(Weekday.MONDAY, Weekday.SUNDAY):
daily_lessons = [slot for slot in self.lessons if slot.day == weekday]
if daily_lessons:
earliest_start = min([slot.start.minutes for slot in daily_lessons])
latest_end = max([slot.end.minutes for slot in daily_lessons])
interval = latest_end - earliest_start
result += interval
return result
def total_time(self):
result = 0
for weekday in range(Weekday.MONDAY, Weekday.SUNDAY):
daily_lessons = [slot for slot in self.lessons if slot.day == weekday]
if daily_lessons:
if len(daily_lessons) > 1:
daily_lessons.sort(key=lambda x: x.start.minutes)
prev = daily_lessons[0].end.minutes
for slot in daily_lessons[1:]:
if slot.start.minutes >= prev:
result = result + (slot.start.minutes - prev)
else:
result = result + 1000
prev = slot.end.minutes
return result
class Course(object):
def __init__(self, name):
self.name = name
self.lesson_blocks = []
def add_lesson_block(self, lesson_block):
self.lesson_blocks.append(lesson_block)
lesson_block.parent_course = self
def get_block_by_category(self, category):
for block in self.lesson_blocks:
if block.category == category:
return block
class LessonBlock:
def __init__(self, category):
self.category = category
self.shifts = []
def add_shift(self, shift):
self.shifts.append(shift)
shift.parent_lesson_block = self
class Shift:
def __init__(self, name):
self.name = name
self.slots = []
def add_lesson_slot(self, lesson_slot):
self.slots.append(lesson_slot)
lesson_slot.parent_shift = self
class LessonSlot:
def __init__(self, day, start, end, room):
self.day = day
self.start = start
self.end = end
self.room = room
def course_name(self):
return self.parent_shift.parent_lesson_block.parent_course.name
def lesson_category(self):
return self.parent_shift.parent_lesson_block.category
def overlaps_with_group(self, group):
for ss in group:
for other in ss:
if self != other:
if self.overlaps_with(other) == True:
return True
return False
def overlaps_with(self, other):
return self.day == other.day and (self.start.is_before(other.end) and self.end.is_after(other.start))
class Weekday:
MONDAY = 0
TUESDAY = 1
WEDNESDAY = 2
THURSDAY = 3
FRIDAY = 4
SATURDAY = 5
SUNDAY = 6
class Time:
def __init__(self, hour, minute):
self.minutes = hour * 60 + minute
def is_before(self, other):
return self.minutes < other.minutes
def is_after(self, other):
return self.minutes > other.minutes
def __str__(self):
return "%d:%02d" % (self.minutes/60, self.minutes%60)