I am trying to generate a random Timetable of a University.
Following is the definition of my class "Sections",
class section:
def __init__(self):
self.id = ""
self.course = ""
self.section = ""
self.instructor = ""
And this is how my data looks like,
1
Object Oriented Programming
CS-3B
Dr Jen
,
2
Object Oriented Programming
SE-3A
Dr Bilal
,
This all data is stored in an object of sections class in array form. Now, all these courses are basically offered in different sections. For example, course id = 1, i.e. Object Oriented Programming is offered in CS-3B.
I am trying to generate a timetable based upon sections. For example, a timetable of section CS-3A which will contain all the lectures of every course offered in section CS-3A. Moreover, this section's timetable shouldn't have any overlapping courses on one slot. For example, if Lecture of 1st course of Section CS-3B is being held on Monday, 1st slot then no other lecture of any other course of Section CS-3B should be held on Monday, 1st slot. Also, every course will have two lectures per week.
Also, note that I had made a Slot class which had following definition,
class Slot:
def __init__(self,day,slot,room):
self.day = day
self.slot = slot
self.room = room
def __repr__(self) -> str:
return f'{self.day} {self.slot} {self.room}'
To make things simplier at the start, I am keeping the room of every lecture = 1. I will change it in future according to the need.
So, to solve this issue, I came up with this code.
t_sections = {}
for i in sections:
if (sections[int(i.id)-1].section[:5]) not in t_sections.keys():
t_sections[sections[int(i.id)-1].section[:5]] = [] # Make a key for new section
for x in range(2): # Because each course must have 2 lectures
lst = []
day = random.randint(1, 5)
slot = random.randint(1, 5)
while (Slot(day, slot, 1) in t_sections[sections[int(i.id)-1].section[:5]]): # check if day + slot already exist in the sections' timetable
day = random.randint(1, 5)
slot = random.randint(1, 5)
lst.append(Slot(day, slot, 1))
t_sections[sections[int(i.id)-1].section[:5]].append([sections[int(i.id)-1].id, lst])
Please don't mind the [:5], I am only doing it because some sections are further divided like CS-1A1 and CS-1A2 but I don't want a different timetable for these further divided sections and instead want their lectures to be placed in their parent section (i.e. CS-1A) which is why I have done the [:5]
What I am doing is creating a dictionary. The keys of the dictionary will contain names of all the sections and the values against every key will be a list, which will contain further lists of each lecture to be placed in that section's timetable.
Now, I used a while loop to make sure that the newly generated random values for day and slot do not exist in the already present list for that section's timetable. That is, if a lecture is already happening on [1, 1] then it shouldn't place another lecture on the same slot.
However, the results I get have some overlapping lectures, and I can't seem to find the reason why does it happen. Please note that it is ok if some lectures are overlapping IF IN CASE all the slots are booked and the lecture being appeneded has no slot at all available in the whole timetable however, I have not yet dealt this case. So, as far as my understanding is, if all lecture slots are filled (i.e. 5 * 5 = 25 slots) then the program should give error because it will never exit the While loop.
Following is the for loop I have been using to get the results of dictionary
for k, v in t_sections.items():
print(k, ": ", v)
And this is one sample result of the dictionary,
CS-3B : [['1', [4 4 1]], ['1', [1 5 1]], ['27', [4 4 1]], ['27', [3 5 1]], ['75', [4 4 1]], ['75', [3 2 1]], ['88', [3 4 1]], ['88', [5 3 1]], ['90', [5 3 1]], ['90', [5 2 1]], ['99', [2 4 1]], ['99', [1 4 1]], ['184', [1 1 1]], ['184', [5 3 1]], ['185', [5 3 1]], ['185', [5 5 1]]]
SE-3A : [['2', [2 1 1]], ['2', [4 1 1]], ['22', [2 2 1]], ['22', [5 1 1]], ['68', [4 3 1]], ['68', [1 5 1]], ['92', [3 3 1]], ['92', [2 1 1]], ['96', [2 2 1]], ['96', [4 5 1]], ['105', [2 4 1]], ['105', [2 4 1]], ['196', [2 4 1]], ['196', [4 2 1]], ['197', [2 1 1]], ['197', [4 4 1]]]
CS-7F : [['3', [3 4 1]], ['3', [5 5 1]], ['36', [5 5 1]], ['36', [2 3 1]]]
CS-1C : [['4', [1 1 1]], ['4', [2 1 1]], ['97', [1 3 1]], ['97', [2 4 1]], ['111', [5 4 1]], ['111', [4 1 1]], ['139', [2 1 1]], ['139', [3 5 1]], ['140', [2 4 1]], ['140', [5 5 1]], ['141', [1 2 1]], ['141', [3 4 1]], ['142', [1 5 1]], ['142', [2 5 1]], ['143', [4 3 1]], ['143', [3 5 1]], ['144', [4 4 1]], ['144', [5 5 1]], ['145', [3 4 1]], ['145', [2 2 1]], ['146', [1 5 1]], ['146', [3 5 1]]]
CS-1D : [['5', [2 3 1]], ['5', [1 1 1]], ['98', [2 4 1]], ['98', [5 3 1]], ['102', [5 3 1]], ['102', [3 5 1]], ['147', [5 4 1]], ['147', [2 4 1]], ['148', [5 5 1]], ['148', [2 1 1]], ['149', [5 1 1]], ['149', [3 4 1]], ['150', [1 1 1]], ['150', [2 4 1]], ['151', [2 5 1]], ['151', [4 2 1]], ['152', [2 3 1]], ['152', [1 1 1]], ['153', [4 3 1]], ['153', [2 5 1]]]
CS-7A : [['6', [1 3 1]], ['6', [1 5 1]], ['8', [5 4 1]], ['8', [1 1 1]], ['9', [3 2 1]], ['9', [4 5 1]], ['18', [3 2 1]], ['18', [3 2 1]], ['21', [2 2 1]], ['21', [4 3 1]], ['116', [4 2 1]], ['116', [1 4 1]], ['209', [4 3 1]], ['209', [4 5 1]]]
CS-7B : [['7', [1 5 1]], ['7', [3 4 1]], ['17', [3 4 1]], ['17', [5 5 1]], ['48', [2 1 1]], ['48', [1 1 1]], ['66', [5 5 1]], ['66', [2 2 1]], ['78', [5 3 1]], ['78', [1 4 1]]]
CS-1B : [['10', [2 3 1]], ['10', [4 2 1]], ['93', [1 3 1]], ['93', [5 5 1]], ['122', [5 4 1]], ['122', [3 1 1]], ['131', [3 4 1]], ['131', [5 3 1]], ['132', [2 1 1]], ['132', [5 2 1]], ['133', [1 3 1]], ['133', [3 2 1]], ['134', [4 2 1]], ['134', [5 5 1]], ['135', [4 1 1]], ['135', [4 2 1]], ['136', [4 1 1]], ['136', [2 3 1]], ['137', [2 3 1]], ['137', [1 2 1]], ['138', [1 1 1]], ['138', [2 1 1]]]
CS-1A : [['11', [1 1 1]], ['11', [1 2 1]], ['81', [4 5 1]], ['81', [5 2 1]], ['95', [3 2 1]], ['95', [5 3 1]], ['123', [2 4 1]], ['123', [4 1 1]], ['124', [4 4 1]], ['124', [5 5 1]], ['125', [1 5 1]], ['125', [5 5 1]], ['126', [2 5 1]], ['126', [1 4 1]], ['127', [1 1 1]], ['127', [3 3 1]], ['128', [1 2 1]], ['128', [1 4 1]], ['129', [2 3 1]], ['129', [1 4 1]], ['130', [3 3 1]], ['130', [3 3 1]]]
^Note, I have only listed few of the Sections result, and not all of the results.
Now, if you look clearly in the results, check CS-1A
['11', [1 1 1]
['127', [1 1 1]
['124', [5 5 1]
['125', [5 5 1]
These are overlapping lecture slots, and it shouldn't have happened. Such results can also be found in other sections timetable as well.
Can anyone help me figure out what's the problem and how can I prevent this from happening? I want unique Day + Slot combination for every lecture of one section.
EDIT: I changed my Slot Class to this,
class Slot:
def __init__(self,day,slot,room):
self.day = day
self.slot = slot
self.room = room
def __eq__(self, other):
if self.day == other.day and self.slot == other.slot:
return True
return False
def __repr__(self) -> str:
return f'{self.day} {self.slot} {self.room}'
But now I am getting this error on this function def eq,
AttributeError: 'list' object has no attribute 'day'
The error, I believe, is being called at this line,
while (Slot(day, slot, 1) in t_sections[sections[int(i.id)-1].section[:5]]): # check if day + slot already exist in the sections' timetable
When it tries to compare the Slot(day, slot, 1) with the already present slot in the timetable of that section.
Since I'm not quite sure what the problem is I'm just going to explain what your algorithm is doing.
for i in sections:
...
sections[int(i.id)-1].section[:5]
Sections is some kind of iterable which returns an object whose .id is 1 more than its index (according to your q). So what this does is:
int(i.id) - 1)Don't do this. Just do:
for section in sections: # isn't python nice?
...
if you're doing something else with this code and I've got the wrong end of the stick, it could do with explaining.
day = random.randint(1, 5)
lot = random.randint(1, 5)
while (
Slot(day, slot, 1) in
t_sections[sections[int(i.id)-1].section[:5]]
):
# check if day + slot already exist in the sections' timetable
day = random.randint(1, 5)
slot = random.randint(1, 5)
What this does is to check whether the specific object you just made exists in t_sections. Unless you defined a .__eq__() method on your Section (or inhereted from something else which provides it) python won't know how to compare your object with other objects, and will fall back to a strict identity check (x is y).
Note that there's no need to do the lookup for sections every time and it would be a good deal clearer just to do:
current_slots = section.section # or whatever
Since your while loop condition is likely never true, the while loop will never run, and so the first (random) values for day and slot will be used, hence the overlap.
P.S. you suggest than an infinite while loop will throw an error. But it won't (in any programming language I know): it will just keep going for ever. If you want it to throw an error you need to keep track of iterations, and manually throw if you go too far. Something like:
count = 0
while cond:
if count > MAX_TRIES:
raise Exception("Tried too hard")
do_stuff()
count += 1
Personally I always do this instead:
for _ in range(MAX_TRIES):
if not cond:
break
do_stuff()
I've been bitten by forgetting my manual counter variable too many times, and consider that much more readable anyhow.