3
\$\begingroup\$

This is an extended question to the following question I posted Class scheduling tool with image output

Context of previous question:

I have a multilayered dictionary that contains information about classes. I am using this to code an automatic schedule builder that I will eventually add to a separate Tkinter application I made that contains similar programs.

I used multiprocessing and itertools to speed up the process, taking the time needed to find overlaps from an hour to around 30 seconds, but it is still a but slow. When working with a lot of possibilities, usually in the hundreds of thousands, the following code takes 20-40 seconds to go through.

    cores = mp.cpu_count()

    splitSchedules = chunkify(PossibleSchedules, cores)

    pool = mp.Pool(processes=cores)
    result = pool.map(removeOverlaps, splitSchedules)

    TruePossibleSchedules = []
    for x in range(cores):
        TruePossibleSchedules = TruePossibleSchedules + result[x]

    TruePossibleSchedules.sort()
    sortedTruePossibleSchedules = list(TruePossibleSchedules for TruePossibleSchedules,_ in itertools.groupby(TruePossibleSchedules))

def removeOverlaps(PossibleSchedules):

    try:
        first = False
        if PossibleSchedules[-1] == "First":
            cores = mp.cpu_count()
            print "Commandeering your %s cores..."%(cores)
            del PossibleSchedules[-1]
            first = True

        listSize = len(PossibleSchedules)
        TruePossibleSchedules = []
        if first:
            for schedule in range(0,listSize):
                overlapping = [[s,e] for s in PossibleSchedules[schedule] for x in s for e in PossibleSchedules[schedule] for y in e  if s is not e and x[2]==y[2] and (int(x[0])<=int(y[1]) and int(x[1])>=int(y[0]))]

                if not overlapping:
                    TruePossibleSchedules.append(PossibleSchedules[schedule])

                sys.stdout.write("\rCalculating real schedules: " + str( float("{0:.2f}".format(( float(schedule+1)/float(listSize)) *100) )) + "%    ")
                sys.stdout.flush()

            sys.stdout.write("\rThanks for letting me borrow those      ")
            sys.stdout.flush()
        else:
            for schedule in range(0,listSize):
                overlapping = [[s,e] for s in PossibleSchedules[schedule] for x in s for e in PossibleSchedules[schedule] for y in e  if s is not e and x[2]==y[2] and (int(x[0])<=int(y[1]) and int(x[1])>=int(y[0]))]

                if not overlapping:
                    TruePossibleSchedules.append(PossibleSchedules[schedule])

        return TruePossibleSchedules  
    except KeyboardInterrupt:
        pass 

To clarify this is the old code that I am trying to get rid of by finding a faster way to do the same thing. My thought is that since I first make a huge list of possible schedules that then need to be iterated over and checked for overlaps, wouldn't it save a butt load of time if I checked for overlaps as I build the list of schedules.

Current extended question:

I am currently attempting to create a method that will create the objectively best schedules based on how close the classes are to mid-day. I believe it works fine, but it takes so long to run I cant get an output. So I am attempting to bypass the code above all together by creating my own itertool product that will check for overlaps as it builds in the hopes that it will be faster. Here is what I have so far:

def product(*args):
    pools = map(tuple, args)
    result = [[]]
    for pool in pools:
        result = [x+[y] 
                  for x in result 
                  for y in pool
                  for time in x
                  for classTx in time
                  for classTy in y
                  if not (int(classTx[0])<=int(classTy[1]) and int(classTx[1])>=int(classTy[0]))
                  and classTx[2]!=classTy[2]
                  ]
    for prod in result:
        yield tuple(prod)

This isn't working but the general idea is there, as it adds classes to the end of the results it checks if the time in y does not overlap with any times in x, and if they do not overlap it adds to the results. Anyone know how to get this code block to work?

Runnable code (Not full code but has enough to debug):

Referenced picture used: Schedule Grid.png

Database used to pull information

# coding: utf-8
'''
Created on Jul 31, 2017

@author: Jake
This is a bit sloppy and unorganized, I am still working on it and it is not going to be stand alone, it will be put into a Tkinter application I made.

'''

from bs4 import BeautifulSoup
from HTMLParser import HTMLParser
import urllib
import shlex
import re
import time
#import logging
from PIL import Image, ImageDraw, ImageFont
import itertools
import os
import shutil
import colorsys
import copy
import random
import multiprocessing as mp
import sys
import signal

class Vars():

    global vari
    vari = {}

    def GetVars(self, var):

        return vari.get(str(var))

    def SendVars(self, var, val):

        vari[str(var)] = val

def signal_handler(signal, frame):
    print 'You pressed Ctrl+C!'
    sys.exit(0)

signal.signal(signal.SIGINT, signal_handler)

def product(*args):
    pools = map(tuple, args)
    result = [[]]
    for pool in pools:
        result = [x+[y] 
                  for x in result 
                  for y in pool
                  for time in x
                  for classTx in time
                  for classTy in y
                  if not (int(classTx[0])<=int(classTy[1]) and int(classTx[1])>=int(classTy[0]))
                  and classTx[2]!=classTy[2]
                  ]
    for prod in result:
        yield tuple(prod)

runStart = time.time()

# Fluid Dynamics is a little fudged, it has multiple different section numbers, so if you want CHE, CE, or ME Fluid Mechanics then do not add it as this will not produce a correct result.

designators = {
    "CC": "Co-Req required ",
    "CS": "Freshman quiz/ Next Class ",
    "CA": "Activity needed ",
    "RQ": "Pre-Req required ",
    "R&": "Pre-Req required ",
    "RQM": "Pre-Req course reqd w/ min grade ",
    "RM&": "(cont.) Pre-Req reqd w/ min grade ",
    "RQT": "Pre-Req test required ",
    "RT&": "(cont.) Pre-Req test required ",
    "NQ": "Pre-Req course required ",
    "N&": "Pre-Req course required ",
    "NQM": "Concur Pre-Req reqd w/ min grade ",
    "NM&": "(cont.) Concur Pre-Req w/ min grade ",
    "MB": "By Application Only ",
    "MP": "Pre-Req Required ",
    "MC": "Co-Req Required ",
    "ML": "Lab Fee Required ",
    "MA": "Permission of Advisor Required ",
    "MI": "Permission of Instructor Required ",
    "MH": "Department Head Approval Required ",
    "MN": "No Credit Course for Departmental Majors ",
    "MS": "Studio course; No general Humanities credit ",
    "PAU": "Auditors need instructor permission ",
    "PCG": "Permission needed from Continuing ED ",
    "PDP": "Permission needed from department ",
    "PIN": "Permission needed from instructor ",
    "PUN": "Undergrads need instructor permission ",
    "PUA": "UGs need permission of Dean of UG Academics ",    
    "LEC": "lecture",
    "L/L": "lecture/lab",
    "LAB": "laboratory",
    "PSI": "personalized self-paced instruction",
    "QUZ": "quiz",
    "RCT": "recitation",
    "SEM": "seminar",
    "PRA": "practicum",
    "HSG": "housing (dorm)",
    "MCE": "Multiple Course Entry base course",
    "WSP": "Work Shop"
}
if os.path.exists((os.path.dirname(os.path.realpath(__file__)) + "/Schedules")):
    shutil.rmtree((os.path.dirname(os.path.realpath(__file__)) + "/Schedules"))

if not os.path.exists((os.path.dirname(os.path.realpath(__file__)) + "/Schedules")): 
    os.makedirs(os.path.dirname(os.path.realpath(__file__)) + "/Schedules")

ScheduleGrid = Image.open('Schedule Grid.png').convert('RGBA')
ClassBlocks = Image.new('RGBA', ScheduleGrid.size, (255,255,255,0))
out = Image.alpha_composite(ScheduleGrid, ClassBlocks)
out.save("Schedule.png")

h = HTMLParser()
page = urllib.urlopen('https://web.stevens.edu/scheduler/core/2017F/2017F.xml').read() # Get to database
soup = BeautifulSoup(page, "lxml")

while True:
    try:
        RawClassData = soup.contents[10].contents[0].contents[0].contents
        break
    except:
        print 'Trying again'

classes = {}
backupClasses = {}
selectedClasses = {}
var = Vars()
var.SendVars("color", 30)
def makeDatabase():


    for i in range(0, len(RawClassData)): # Parse through each class

        sys.stdout.write("\rLoading classes: " + str( float("{0:.2f}".format(( float(i)/float(len(RawClassData))) *100) )) + "%      ")
        sys.stdout.flush()

        try:
            ClassDict = {}
            MeetingsDict = {}
            RequirementsDict = {}


            #For meetings
            numMeetings = str(RawClassData[i]).split().count("<meeting")
            seper = str(RawClassData[i]).split("meeting") # Split string by meeting to get subject name and value
            try:
                for line in range(0, len(seper)):
                    if seper[line] == ">\n<":
                        del seper[line]
            except:
                pass
            for x in range(0, numMeetings):
                subMeetingsDict = {}
                MeetingInfo = shlex.split(h.unescape(str(seper[x+1]).replace(">", " "))) # sort into a list grouping string in quotes and getting rid of unnecessary symbols 

                for item in MeetingInfo: # Go through list of meeting info
                    try:

                        thing = item.split("=") # Split string by = to get subject name and value
                        name = thing[0]
                        if any(char.isdigit() for char in thing[1]): # Get rid of annoying Z at the end of numbers
                            for char in thing[1]:
                                if "-" == char:
                                    thing[1] = re.sub("[Z]","",thing[1])
                                    break

                        value = re.sub(' +',' ', thing[1])
                        if value:   # If subject has a value, store it
                            try:
                                subMeetingsDict[str(name)] = str(designators[str(value)])  # Store value converted to designator in a dictionary with the subject as the key
                            except KeyError:
                                subMeetingsDict[str(name)] = str(value)  # Store value in a dictionary with the subject as the key
                    except:
                        pass

                MeetingsDict["meeting" + str(x)] = subMeetingsDict
            ClassDict["meetings"] = MeetingsDict

            #For requirements
            numRequirements = str(RawClassData[i]).split().count("<requirement")
            seper = str(RawClassData[i]).split("requirement") # Split string by requirements to get subject name and value
            try:
                for line in range(0, len(seper) - 1):
                    if seper[line] == ">\n<":
                        del seper[line]
            except:
                pass
            for x in range(0, numRequirements):
                subRequirementsDict = {}
                RequirementsInfo = shlex.split(h.unescape(str(seper[-2 - x]).replace(">", " "))) # sort into a list grouping string in quotes and getting rid of unnecessary symbols 

                for item in RequirementsInfo: # Go through list of meeting info
                    try:

                        thing = item.split("=") # Split string by = to get subject name and value
                        name = thing[0]
                        if any(char.isdigit() for char in thing[1]): # Get rid of annoying Z at the end of numbers
                            for char in thing[1]:
                                if "-" == char:
                                    thing[1] = re.sub("[Z]","",thing[1])
                                    break

                        value = re.sub(' +',' ', thing[1])
                        if value:   # If subject has a value, store it
                            try:
                                subRequirementsDict[str(name)] = str(designators[str(value)])  # Store value converted to designator in a dictionary with the subject as the key
                            except KeyError:
                                subRequirementsDict[str(name)] = str(value)  # Store value in a dictionary with the subject as the key
                    except:
                        pass

                RequirementsDict["requirement" + str(x)] = subRequirementsDict
            ClassDict["requirements"] = RequirementsDict


            AllCourseInfo = shlex.split(h.unescape(str(RawClassData[i]).replace(">", " "))) # sort into a list grouping string in quotes and getting rid of unnecessary symbols 


            for item in AllCourseInfo: # Go through list of class info
                try:

                    thing = item.split("=") # Split string by = to get subject name and value
                    name = thing[0]
                    if any(char.isdigit() for char in thing[1]): # Get rid of annoying Z at the end of numbers
                        for char in thing[1]:
                            if "-" == char:
                                thing[1] = re.sub("[Z]","",thing[1])
                                break

                    value = re.sub(' +',' ', thing[1])
                    if value:   # If subject has a value, store it
                        try:
                            ClassDict[str(name)] = str(designators[str(value)])  # Store value converted to designator in a dictionary with the subject as the key
                        except KeyError:
                            ClassDict[str(name)] = str(value)  # Store value in a dictionary with the subject as the key
                except:
                    pass

            classes[str(ClassDict["section"])] = ClassDict
        except Exception:
            #logging.exception("message")
            pass
    sys.stdout.write("\rLoading classes: Done   ")
    sys.stdout.flush()
def pickClass(selection):

    oneSel = True
    classToSort = {}
    var = Vars()
    colorStep = var.GetVars("color")

    for key in classes:
        ClassDict = {}
        if classes[key]["title"] == selection:
            repeat = False
            oneSel = False
            for classkey in classes[key]:
                ClassDict[str(classkey)] = classes[key][classkey]
            for selectedClass in selectedClasses:
                for section in selectedClasses[selectedClass]:
                    if ClassDict["activity"] == selectedClasses[selectedClass][section]["activity"] and ClassDict["title"] == selectedClasses[selectedClass][section]["title"]:
                        repeat = True

            if  repeat == False:
                ClassDict["variable"] = "True"
                h, l, s = colorStep, 50, 100
                r, g, b = colorsys.hls_to_rgb(h/360.0, l/100.0, s/100.0)
                r, g, b = [x*255 for x in r, g, b]
                ClassDict["color"] = int(r),int(g),int(b)  # Changing color
                classToSort[str(ClassDict["section"])] = ClassDict    #Put selected class in a dictionary
                classes[str(ClassDict["section"])] = ClassDict


    if oneSel:
        classToSort[str(classes[selection]["section"])] = classes[selection]    #Put selected section in a dictionary
        classToSort[str(classes[selection]["section"])]["variable"] = "False"  #Not changing

        # Add activities
        activityHeads = ["LEC", "PRA", "L/L", "SEM", "PSI", "WSP"]
        for activityType in activityHeads:
            if str(classes[selection]["activity"]) == designators[str(activityType)]:
                Quiz = False
                Activity = False
                for requirement in classes[selection]["requirements"]:
                    for requirementInfo in classes[selection]["requirements"][requirement]:
                        # Add required activities
                        if str(classes[selection]["requirements"][requirement][requirementInfo]) == "Activity needed ":
                                Activity = True
                        # Add Recitation
                        if Activity == True and ("recitation" in str(classes[selection]["requirements"][requirement][requirementInfo])):
                            isRecIn = False
                            RecDic = {}
                            for recitSection in classes:
                                if classes[recitSection]["title"] == classes[selection]["title"]:
                                    if classes[recitSection]["activity"] == "recitation":
                                        RecDic[str(classes[recitSection]["section"])] = classes[recitSection]
                                        RecDic[str(classes[recitSection]["section"])]["variable"] = "True"  # Changing
                                        h, l, s = colorStep, 50, 100
                                        r, g, b = colorsys.hls_to_rgb(h/360.0, l/100.0, s/100.0)
                                        r, g, b = [x*255 for x in r, g, b]
                                        RecDic[str(classes[recitSection]["section"])]["color"] = int(r),int(g),int(b)  # Changing color
                            for selectedClassTitle in selectedClasses:
                                for selectedClass in selectedClasses[selectedClassTitle]:
                                    for selectedRec in RecDic:
                                        if selectedClasses[selectedClassTitle][selectedClass] == RecDic[selectedRec]:
                                            isRecIn = True
                            if isRecIn == False: # Only adds recitation if a recitation not is already given.
                                classToSort.update(RecDic)    
                                ''' Add this functionality for when a title is given'''
                        # Add Lab
                        if Activity == True and ("laboratory" in str(classes[selection]["requirements"][requirement][requirementInfo])):
                            isLabIn = False
                            LabDic = {}
                            for labSection in classes:
                                if classes[labSection]["title"] == classes[selection]["title"]:
                                    if classes[labSection]["activity"] == "laboratory":
                                        LabDic[str(classes[labSection]["section"])] = classes[labSection]
                                        LabDic[str(classes[labSection]["section"])]["variable"] = "True"  # Changing
                                        h, l, s = colorStep, 50, 100
                                        r, g, b = colorsys.hls_to_rgb(h/360.0, l/100.0, s/100.0)
                                        r, g, b = [x*255 for x in r, g, b]
                                        LabDic[str(classes[labSection]["section"])]["color"] = int(r),int(g),int(b)  # Changing color
                            for selectedClassTitle in selectedClasses:
                                for selectedClass in selectedClasses[selectedClassTitle]:
                                    for selectedRec in LabDic:
                                        if selectedClasses[selectedClassTitle][selectedClass] == LabDic[selectedRec]:
                                            isLabIn = True
                            if isLabIn == False: # Only adds recitation if a recitation not is already given.
                                classToSort.update(LabDic)    # Add this functionality for when a title is given

        #Backup classes if section closed
        for key in classes:  
            ClassDict = {}
            if (classes[key]["title"] == classes[selection]["title"]) and (classes[key] != classes[selection]):
                for classkey in classes[key]:
                    ClassDict[str(classkey)] = classes[key][classkey]
                backupClasses[str(ClassDict["section"])] = ClassDict    #Put extra sections with the same title in a dictionary

    if classToSort:
        var.SendVars("color", colorStep + 30)
        activities = ["LEC", "L/L", "LAB", "PSI", "QUZ", "RCT", "SEM", "PRA", "HSG", "MCE", "WSP"]
        activitiesDict = {"LEC": {}, "L/L": {}, "LAB": {}, "PSI": {}, "QUZ": {}, "RCT": {}, "SEM": {}, "PRA": {}, "HSG": {}, "MCE": {}, "WSP": {}}

        for activity in activities:
            for key in classToSort:
                ClassDict = {}
                if classToSort[key]["activity"] == designators[str(activity)]:
                    for classkey in classToSort[key]:
                        ClassDict[str(classkey)] = classToSort[key][classkey]
                    activitiesDict[activity][str(ClassDict["section"])] = ClassDict    #Put selected class section in a dictionary

        #"CS": "Freshman quiz/ Next Class "
        #"CA": "Activity needed ",   
        # LEC, PRA, L/L, SEM, PSI, WSP are the only ones that need to look for CS and CA
        activityHeads = ["LEC", "PRA", "L/L", "SEM", "PSI", "WSP"]

        # Build dictionary to add to selectedClasses
        for actClass in activitiesDict:
            if actClass:
                for classSec in activitiesDict[actClass]:
                    selectedClasses[ str(activitiesDict[actClass][classSec]["title"]) + " " + str(activitiesDict[actClass][classSec]["activity"])] = activitiesDict[actClass] # Add all activities of each class

                    # Add Freshman Quiz's
                    for key in activityHeads:
                        Quiz = False
                        for requirement in activitiesDict[actClass][classSec]["requirements"]:
                            for requirementInfo in activitiesDict[actClass][classSec]["requirements"][requirement]:
                                if str(activitiesDict[actClass][classSec]["requirements"][requirement][requirementInfo]) == "Freshman quiz/ Next Class ":
                                    Quiz = True
                                if Quiz == True and ("D 110" in str(activitiesDict[actClass][classSec]["requirements"][requirement][requirementInfo])):
                                    quiz = {}
                                    quiz[ str(activitiesDict[actClass][classSec]["requirements"][requirement][requirementInfo]) ] = classes[str(activitiesDict[actClass][classSec]["requirements"][requirement][requirementInfo])]
                                    quiz[ str(activitiesDict[actClass][classSec]["requirements"][requirement][requirementInfo]) ]["variable"] = "False"  #Not changing
                                    selectedClasses[ str(activitiesDict[actClass][classSec]["title"]) + " Quiz " + str(activitiesDict[actClass][classSec]["requirements"][requirement][requirementInfo])[-1] ] = quiz # Add freshman quiz


def CreateScheduleImage(possibleSchedules):

    startTest = time.time() # Start timeing the test
    scheduleNum = 0
    if len(possibleSchedules) > 3:
        for x in range(2):
            schedule = possibleSchedules[0]
            ScheduleGrid = Image.open('Schedule.png').convert('RGBA')
            ClassBlocks = Image.new('RGBA', ScheduleGrid.size, (255,255,255,0))
            fnt = ImageFont.truetype('Library/Fonts/Tahoma.ttf', 8*2)
            fnt2 = ImageFont.truetype('Library/Fonts/Tahoma.ttf', 7*2)
            d = ImageDraw.Draw(ClassBlocks)
            for section in schedule:
                meetings = schedule[section]["meetings"]
                for meeting in meetings:
                    days = schedule[str(section)]["meetings"][str(meeting)]["day"]
                    for day in days:
                        cltimeS = schedule[section]["meetings"][meeting]["starttime"]
                        cltimeF = schedule[section]["meetings"][meeting]["endtime"]
                        classStart = (cltimeS.split(":"))
                        del classStart[-1]
                        starttime = ( (int(classStart[0]) - 8)*60 + int(classStart[1]))/15 *19
                        classEnd = (cltimeF.split(":"))
                        del classEnd[-1]
                        endtime = ( (int(classEnd[0]) - 8)*60 + int(classEnd[1]))/15 *19 - starttime
                        if day == "M":
                            dayNum = 0
                        elif day == "T":
                            dayNum = 1
                        elif day == "W":
                            dayNum = 2
                        elif day == "R":
                            dayNum = 3
                        elif day == "F":
                            dayNum = 4
                        x1 = 80 + (190 + 1)*dayNum
                        y1 = 32 + starttime + (16*19) #Add 4 hours because weird bug
                        x2 = x1 + 190
                        y2 = y1 + endtime
                        BoxPosition = [((x1 +2)*2, (y1 +2)*2), ((x2)*2), ((y2 -1)*2)]
                        BoxOutlinePosition1 = [((x1 +1.5)*2, (y1 +1.5)*2), ((x2+0.5)*2), ((y2 - 0.5)*2)]
                        BoxOutlinePosition2 = [((x1 +1)*2, (y1 +1)*2), ((x2+1)*2), ((y2)*2)]
                        d.rectangle(BoxOutlinePosition2, fill=(90,190,120,0), outline="darkred")
                        d.rectangle(BoxOutlinePosition1, fill=(90,190,120,0), outline="grey")
                        if schedule[section]["variable"] == "False":
                            d.rectangle(BoxPosition, fill=(90,190,120,180), outline="darkred")
                        else:
                            d.rectangle(BoxPosition, fill=(schedule[section]["color"] + (180,)), outline="darkred")
                        d.text([(x1 + 5)*2, (y1 + 1 +9*1)*2], schedule[section]["title"], font=fnt, fill=(0,0,0,255))
                        d.text([(x1 + 5)*2, (y1 + 1)*2], schedule[section]["section"], font=fnt, fill=(0,0,0,255))
                        d.text([(x1 + 5)*2, (y1 + 1 +9*2)*2], schedule[section]["instructor1"], font=fnt, fill=(0,0,0,255))
                        d.text([(x1 + 5)*2, (y1 + 1 +9*3)*2], schedule[section]["callnumber"], font=fnt, fill=(0,0,0,255))
                        requirements = schedule[section]["requirements"]
                        count = 1
                        for requirement in requirements:
                            control = str(schedule[section]["requirements"][requirement]["control"])
                            values = []
                            for x in range(0, str(schedule[section]["requirements"][requirement]).count("value")):
                                values.append(str(schedule[section]["requirements"][requirement]["value" + str(x + 1)]))
                            if values:
                                msg = control + ": " + str(values)
                            else:
                                msg = control
                            width, height = d.textsize(msg)
                            y2 = y2 -5
                            d.text([(x2)*2 - width-10, (y2 -(height-5)*count)*2], msg, font=fnt2, fill=(200,0,0,255))
                            count = count + 0.5
            out = Image.alpha_composite(ScheduleGrid, ClassBlocks)
            out.save((os.path.dirname(os.path.realpath(__file__)) + "/Schedules/Schedule" + str(scheduleNum) + ".png") )
            print "Preparing..."
            scheduleNum = scheduleNum + 1     #
        endTest = time.time()   # End timing the test

        if os.path.exists((os.path.dirname(os.path.realpath(__file__)) + "/Schedules")):
            shutil.rmtree((os.path.dirname(os.path.realpath(__file__)) + "/Schedules"))
        if not os.path.exists((os.path.dirname(os.path.realpath(__file__)) + "/Schedules")): 
            os.makedirs(os.path.dirname(os.path.realpath(__file__)) + "/Schedules")
        photoTime = (endTest - startTest)/2
    else:
        photoTime = 1.4

    scheduleNum = 0
    estimate = str( (len(possibleSchedules)*photoTime) / 60).split(".")


    print "\n\nEstimated time to load %s images: %s minutes and %s seconds"%(len(possibleSchedules), int(estimate[0]), float("." + estimate[1])*60 )
    sys.stdout.write("\rTime left " + str( float("{0:.2f}".format((len(possibleSchedules))*photoTime - scheduleNum*photoTime)) ) + " seconds     ")
    sys.stdout.flush()

    startPhotos = time.time()
    for schedule in possibleSchedules:
        ScheduleGrid = Image.open('Schedule.png').convert('RGBA')
        ClassBlocks = Image.new('RGBA', ScheduleGrid.size, (255,255,255,0))
        fnt = ImageFont.truetype('Library/Fonts/Tahoma.ttf', 8*2)
        fnt2 = ImageFont.truetype('Library/Fonts/Tahoma.ttf', 7*2)
        d = ImageDraw.Draw(ClassBlocks)

        for section in schedule:
            meetings = schedule[section]["meetings"]
            for meeting in meetings:
                days = schedule[str(section)]["meetings"][str(meeting)]["day"]
                for day in days:

                    cltimeS = schedule[section]["meetings"][meeting]["starttime"]
                    cltimeF = schedule[section]["meetings"][meeting]["endtime"]

                    classStart = (cltimeS.split(":"))
                    del classStart[-1]
                    starttime = ( (int(classStart[0]) - 8)*60 + int(classStart[1]))/15 *19


                    classEnd = (cltimeF.split(":"))
                    del classEnd[-1]
                    endtime = ( (int(classEnd[0]) - 8)*60 + int(classEnd[1]))/15 *19 - starttime

                    if day == "M":
                        dayNum = 0
                    elif day == "T":
                        dayNum = 1
                    elif day == "W":
                        dayNum = 2
                    elif day == "R":
                        dayNum = 3
                    elif day == "F":
                        dayNum = 4

                    x1 = 80 + (190 + 1)*dayNum
                    y1 = 32 + starttime + (16*19) #Add 4 hours because weird bug
                    x2 = x1 + 190
                    y2 = y1 + endtime

                    BoxPosition = [((x1 +2)*2, (y1 +2)*2), ((x2)*2), ((y2 -1)*2)]
                    BoxOutlinePosition1 = [((x1 +1.5)*2, (y1 +1.5)*2), ((x2+0.5)*2), ((y2 - 0.5)*2)]
                    BoxOutlinePosition2 = [((x1 +1)*2, (y1 +1)*2), ((x2+1)*2), ((y2)*2)]
                    # draw text, half opacity
                    d.rectangle(BoxOutlinePosition2, fill=(90,190,120,0), outline="darkred")
                    d.rectangle(BoxOutlinePosition1, fill=(90,190,120,0), outline="grey")
                    if schedule[section]["variable"] == "False":
                        d.rectangle(BoxPosition, fill=(90,190,120,180), outline="darkred")
                    else:
                        d.rectangle(BoxPosition, fill=(schedule[section]["color"] + (180,)), outline="darkred")
                    # draw text, full opacity
                    d.text([(x1 + 5)*2, (y1 + 1 +9*1)*2], schedule[section]["title"], font=fnt, fill=(0,0,0,255))
                    d.text([(x1 + 5)*2, (y1 + 1)*2], schedule[section]["section"], font=fnt, fill=(0,0,0,255))
                    d.text([(x1 + 5)*2, (y1 + 1 +9*2)*2], schedule[section]["instructor1"], font=fnt, fill=(0,0,0,255))
                    d.text([(x1 + 5)*2, (y1 + 1 +9*3)*2], schedule[section]["callnumber"], font=fnt, fill=(0,0,0,255))

                    #Print out required classes to bottom right corner in red

                    requirements = schedule[section]["requirements"]
                    count = 1
                    for requirement in requirements:

                        control = str(schedule[section]["requirements"][requirement]["control"])

                        values = []
                        for x in range(0, str(schedule[section]["requirements"][requirement]).count("value")):
                            values.append(str(schedule[section]["requirements"][requirement]["value" + str(x + 1)]))

                        if values:
                            msg = control + ": " + str(values)
                        else:
                            msg = control

                        width, height = d.textsize(msg)
                        y2 = y2 -5
                        d.text([(x2)*2 - width-10, (y2 -(height-5)*count)*2], msg, font=fnt2, fill=(200,0,0,255))

                        count = count + 0.5

        out = Image.alpha_composite(ScheduleGrid, ClassBlocks)

        #timeToSave = time.time()         
        out.save((os.path.dirname(os.path.realpath(__file__)) + "/Schedules/Schedule" + str(scheduleNum) + ".png") )  # Takes about 0.75 sec to save
        #print "Time to save photo" + str(time.time() - timeToSave)   

        sys.stdout.write("\rLoading schedules: " + str( float("{0:.2f}".format(( float(scheduleNum+1)/float(len(possibleSchedules))) *100) )) + "%    ")
        sys.stdout.flush()

        '''sys.stdout.write("\rTime left " + str( float("{0:.2f}".format((len(possibleSchedules)-1)*photoTime - scheduleNum*photoTime)) ) + " seconds")
        sys.stdout.flush()'''
        scheduleNum = scheduleNum + 1     # Takes about 1.4 sec per photo

    print "\n\nEstimated time to load %s images: %s minutes and %s seconds"%(len(possibleSchedules), int(estimate[0]), float("." + estimate[1])*60 )
    actual = str( (time.time() - startPhotos) / 60).split(".")
    print "Actual time to load %s images: %s minutes and %s seconds"%(len(possibleSchedules), int(actual[0]), float("." + actual[1])*60 )
    print "Diff = " + str( abs((time.time() - startPhotos) - (len(possibleSchedules)*photoTime)) ) + " seconds"
    print "Error in guess = " + str(  float("{0:.2f}".format(((abs((time.time() - startPhotos) - (len(possibleSchedules)*photoTime))) / (time.time() - startPhotos)) * 100 )) ) + "%" + "\n\n"


def bestSchedules(ClassDic):

    AllClasses = []
    SectionMeetingTimes = []

    condencedClassTimeDic = {}
    ignore = {}

    for classType in ClassDic:
        condenceSectionDic = {}
        for section in ClassDic[classType]:
            for otherMeeting in ClassDic[classType][section]["meetings"]:
                for meeting in ClassDic[classType][section]["meetings"]:
                    notIn = True
                    if (ClassDic[classType][section]["meetings"][meeting] != ClassDic[classType][section]["meetings"][otherMeeting]) and (ClassDic[classType][section]["meetings"][meeting]["starttime"] == ClassDic[classType][section]["meetings"][otherMeeting]["starttime"]) and (ClassDic[classType][section]["meetings"][meeting]["endtime"] == ClassDic[classType][section]["meetings"][otherMeeting]["endtime"]):
                        for alreadyIn in ignore:
                            if ignore[alreadyIn] == ClassDic[classType][section]["meetings"][otherMeeting]:
                                notIn = False
                        if notIn:
                            ignore[str(ClassDic[classType][section]["meetings"])] = copy.deepcopy(ClassDic[classType][section]["meetings"][meeting])
                            ignore[str(ClassDic[classType][section]["section"])] = copy.deepcopy(ClassDic[classType][section])
                            sectionDay = str(ClassDic[classType][section]["meetings"][meeting]["day"]) + str(str(ClassDic[classType][section]["meetings"][otherMeeting]["day"]))
                            sectionName = str(ClassDic[classType][section]["section"])
                            condenceSectionDic[sectionName] = copy.deepcopy(ClassDic[classType][section])
                            meetingsDic = {}
                            meetingsDic[str(meeting)] = copy.deepcopy(ClassDic[classType][section]["meetings"][meeting])
                            meetingsDic[meeting]["day"] = sectionDay
                            condenceSectionDic[sectionName]["meetings"] = meetingsDic


        for section in ClassDic[classType]:
            notIn = True
            for alreadyIn in ignore:
                if ignore[alreadyIn] == ClassDic[classType][section]:
                    notIn = False
            if notIn:
                condenceSectionDic[str(ClassDic[classType][section]["section"])] = copy.deepcopy(ClassDic[classType][section])

        condencedClassTimeDic[str(classType)] = copy.deepcopy(condenceSectionDic)



    condencedClassDic = {}
    condencedSectionListDic = {}
    ignore = {}

    for classType in condencedClassTimeDic:
        condenceSectionDic = {}
        for section in condencedClassTimeDic[classType]:
            for otherSection in condencedClassTimeDic[classType]:
                notIn = True
                if (condencedClassTimeDic[classType][section] != condencedClassTimeDic[classType][otherSection]) and (condencedClassTimeDic[classType][section]["meetings"]["meeting0"]["starttime"] == condencedClassTimeDic[classType][otherSection]["meetings"]["meeting0"]["starttime"]) and (condencedClassTimeDic[classType][section]["meetings"]["meeting0"]["endtime"] == condencedClassTimeDic[classType][otherSection]["meetings"]["meeting0"]["endtime"]) and (condencedClassTimeDic[classType][section]["meetings"]["meeting0"]["day"] == condencedClassTimeDic[classType][otherSection]["meetings"]["meeting0"]["day"]) and (condencedClassTimeDic[classType][section]["activity"] == condencedClassTimeDic[classType][otherSection]["activity"]):
                    for alreadyIn in ignore:
                        if ignore[alreadyIn] == condencedClassTimeDic[classType][section]:
                            notIn = False
                    if notIn:
                        ignore[str(condencedClassTimeDic[classType][section])] = condencedClassTimeDic[classType][otherSection]
                        sectionName = str(condencedClassTimeDic[classType][section]["section"]) + "/" + str(((str(condencedClassTimeDic[classType][otherSection]["section"]).split(" "))[1][3:]))
                        sectionProf = str(condencedClassTimeDic[classType][section]["instructor1"]) + "/" + str(str(condencedClassTimeDic[classType][otherSection]["instructor1"]))
                        sectionNum = str(condencedClassTimeDic[classType][section]["callnumber"]) + "/" + str(str(condencedClassTimeDic[classType][otherSection]["callnumber"]))
                        condenceSectionDic[sectionName] = condencedClassTimeDic[classType][section]
                        condenceSectionDic[sectionName]["section"] = sectionName
                        condenceSectionDic[sectionName]["instructor1"] = sectionProf
                        condenceSectionDic[sectionName]["callnumber"] = sectionNum
                        condencedSectionListDic[sectionName] = condencedClassTimeDic[classType][section]
                        condencedSectionListDic[sectionName]["section"] = sectionName
                        condencedSectionListDic[sectionName]["instructor1"] = sectionProf
                        condencedSectionListDic[sectionName]["callnumber"] = sectionNum

        for section in condencedClassTimeDic[classType]:
            notIn = True
            for alreadyIn in ignore:
                if ignore[alreadyIn] == condencedClassTimeDic[classType][section]:
                    notIn = False
            if notIn:
                condenceSectionDic[str(condencedClassTimeDic[classType][section]["section"])] = condencedClassTimeDic[classType][section]
                condencedSectionListDic[str(condencedClassTimeDic[classType][section]["section"])] = condencedClassTimeDic[classType][section]

        condencedClassDic[str(classType)] = condenceSectionDic







    # Create all possiple best schedule times
    listOfDayTimes = []
    for day in ["M","T","W","R","F"]:
        dayTimes = []
        for x in range(5):
            dayTimes.append([1200 -x*100,1700 +x*100,str(day)])
        listOfDayTimes.append(dayTimes)

    AllGoodTimes = list((list(tup) for tup in itertools.product(*listOfDayTimes)))
    goodSchedules = []

    for goodScheduleTime in AllGoodTimes:

        # Create list of All classes
        for classToAdd in condencedClassDic:

            ClassTimes = []
            for classSection in condencedClassDic[classToAdd]:

                meetings = condencedClassDic[classToAdd][classSection]["meetings"]

                SectionMeetingTimes = []
                overlap = False
                for meeting in meetings:
                    days = condencedClassDic[classToAdd][classSection]["meetings"][str(meeting)]["day"]
                    for day in days:

                        cltimeS = condencedClassDic[classToAdd][classSection]["meetings"][meeting]["starttime"]
                        cltimeF = condencedClassDic[classToAdd][classSection]["meetings"][meeting]["endtime"]

                        classStart = (cltimeS.split(":"))
                        del classStart[-1]
                        starttime = ( str(classStart[0]) + str(classStart[1]) ) 


                        classEnd = (cltimeF.split(":"))
                        del classEnd[-1]
                        endtime = ( str(classEnd[0]) + str(classEnd[1]) )

                        for times in goodScheduleTime:
                            if times[2] == day:
                                if ((int(starttime) + 400) < (int(times[0])) or (int(endtime) + 400) > (int(times[1]))):
                                    overlap = True
                        SectionMeetingTimes.append([starttime,endtime,day,condencedClassDic[classToAdd][classSection]["title"],condencedClassDic[classToAdd][classSection]["section"]])
                if not overlap or condencedClassDic[classToAdd][classSection]["variable"] == "False":
                    ClassTimes.append(SectionMeetingTimes)
            if ClassTimes:
                AllClasses.append(ClassTimes)


        # Save time and space by getting rid of all duplicates from the list of classes.
        sortedAllClasses = []
        for section in AllClasses:
            section.sort()
            sortedAllClasses.append( list(section for section,_ in itertools.groupby(section)) )
        sortedAllClassList = []
        for section in sortedAllClasses:
            sortedAllClassTimes = []
            for times in section:
                times.sort()
                sortedAllClassTimes.append( list(times for times,_ in itertools.groupby(times)) )
            sortedAllClassList.append(sortedAllClassTimes)

        sortedGoodScedules = []
        for elem in sortedAllClassList:
            if elem not in sortedGoodScedules:
                sortedGoodScedules.append(elem)

        if len(sortedGoodScedules) == len(ClassDic): #Makes sure all classes are in the schedule

            # Calculate how many possible schedules there are.
            possibilities = 1
            for title in sortedGoodScedules:
                possibilities = possibilities* len(title)

            for x in range(10):
                print sortedGoodScedules[x]

            # Make sure there aren't too many schedules to go through, set limit to about how long it takes to go through 6 minutes of possible schedules.
            if possibilities <= 86020:
                PossibleSchedules = list((list(tup) for tup in product(*sortedGoodScedules))) # List of all possible schedules generates a lot of schedules.

                #Takes a while:

                cores = mp.cpu_count()

                splitSchedules = chunkify(PossibleSchedules, cores)
                result = []
                try:
                    pool = mp.Pool(processes=cores)
                    result = pool.map(removeOverlaps, splitSchedules)
                except:
                    pass
                print goodScheduleTime
                TruePossibleSchedules = []
                for x in range(len(result)):
                    TruePossibleSchedules = TruePossibleSchedules + result[x]

                TruePossibleSchedules.sort()
                sortedTruePossibleSchedules = list(TruePossibleSchedules for TruePossibleSchedules,_ in itertools.groupby(TruePossibleSchedules))

                # Turn into a list of dicts of the class sections 
                selectList = []
                for schedule in sortedTruePossibleSchedules:
                    selectDict = {}
                    for classSection in schedule:
                        selectDict[str(classSection[0][-1])] = condencedSectionListDic[str(classSection[0][-1])]
                    selectList.append(selectDict)

                if selectList:
                    goodSchedules.append(selectList)
                if len(goodSchedules) >= 1:
                    break
            else:
                print goodScheduleTime
                print "That one had too many"

    print selectList
    time.sleep(50)
    return selectList


start = time.time()

makeDatabase()

end = time.time()
print "\nTime to create database of every section of every class offered: " + str(end - start)

pickClass("Electricity & Magnetism")
pickClass("Differential Equations")
pickClass("CAL 103B")
pickClass("Mechanics of Solids")
pickClass("Engineering Design III")
pickClass("Circuits and Systems")

startMon = "9:00"
endMon = "18:00"

startTus = "9:00"
endTus = "18:00"

startWen = "9:00"
endWen = "18:00"

startThu = "9:00"
endThu = "18:00"

startFri = "14:00"
endFri = "18:00"


daytimes = [startMon,endMon,startTus,endTus,startWen,endWen,startThu,endThu,startFri,endFri]

timeConstraint = []
for x in range(0,10, 2):
    blah = ["M","M","T","T","W","W","R","R","F","F"]
    broken1 = daytimes[x].split(":")
    startD = broken1[0] + broken1[1]
    broken2 = daytimes[x+1].split(":")
    endD = broken2[0] + broken2[1]

    timeConstraint.append([startD,endD, blah[x]])

bestChoice = raw_input("\n\n\n\nWant the best schedules? ")
if bestChoice.lower() == "yes" or bestChoice.lower() == "y" or bestChoice.lower() == "ya":
    best = True
else:
    lucky = raw_input("\n\n\n\nAre you feeling lucky??? (Do you want to only create one schedule) ")
    if lucky.lower() == "yes" or lucky.lower() == "y" or lucky.lower() == "ya":
        isLucky = True
        isMult = False
    else:
        isLucky = False
        mult = raw_input("\n\n\n\nWould you like to limit the number of schedules made? ")
        if mult.lower() == "yes" or mult.lower() == "y" or mult.lower() == "ya":
            isMult = True
            multNum = raw_input("\n\n\n\nHow many? ")
            try:
                int(multNum)
            except:
                print "Ummm... That's not a number, so I'll set it to 6."
                multNum = 6
                time.sleep(3)
        elif any(char.isdigit() for char in mult):
            isMult = True
            multNum = mult
            try:
                int(multNum)
            except:
                print "Ummm... That's not a number, so I'll set it to 6."
                multNum = 6
                time.sleep(3)
        else:
            isMult = False


if best == True:
    combos = bestSchedules(selectedClasses)
    CreateScheduleImage(combos)
else:
    if combos == "Bad":
        print "\nTry giving less time range for classes or pick a section you definitely want to be in instead of a whole class, espetially if a class you picked has many sections, to lower the amount of possibilities\n"
        largeClass = []
        msg = ""
        for classType in selectedClasses:
            if len(selectedClasses[classType]) > 12:
                largeClass.append(classType)
                msg += "\n" + classType + " with " + str(len(selectedClasses[classType])) + " sections."

        print "Classes that you should select section for include: " + msg

    elif isLucky and combos:
        randSchedule = []
        rando = random.randint(0, len(combos)-1)
        print "Random number: " + str(rando)
        randSchedule.append(combos[rando])
        if len(randSchedule) <= 600:
            CreateScheduleImage(randSchedule)
        else:
            print "That is too many freaking possibilities, it will take over 10 minutes to load the schedules, use less variable classes"
            print "Schedules: " + str(len(randSchedule))

    elif isMult and combos:
        multSchedule = []
        randSchedule = []
        randNums = []
        while True:
            if len(randNums) == int(multNum) or len(randNums) == len(combos):
                break
            repeat = False
            rando = random.randint(0, len(combos)-1)
            for num in randNums:
                if rando == num:
                    repeat = True
            if repeat == False:
                randNums.append(rando)
        print "Random number: " + str(randNums)
        for x in randNums:
            randSchedule.append(combos[x])
        if len(randSchedule) <= 600:
            CreateScheduleImage(randSchedule)
        else:
            print "That is too many freaking possibilities, it will take over 10 minutes to load the schedules, use less variable classes"
            print "Schedules: " + str(len(randSchedule))

    elif combos:
        if len(combos) <= 600:
            CreateScheduleImage(combos)
        else:
            print "That is too many freaking possibilities, it will take over 10 minutes to load the schedules, use less variable classes"
            print "Schedules: " + str(len(combos))

    else: 
        print "\nNo combinations available\n"


runEnd = time.time()
print "Total run time: " + str(runEnd - runStart)

Output:

Output

\$\endgroup\$
  • \$\begingroup\$ You are aware that most scheduling optimization problems are provably hard? Like... really hard? \$\endgroup\$ – Vogel612 Aug 16 '17 at 8:57
  • \$\begingroup\$ I don't get it, you are saying that the product function does not work, but the provided code which uses it is claimed to work… \$\endgroup\$ – 301_Moved_Permanently Aug 16 '17 at 10:53
  • \$\begingroup\$ @MathiasEttinger Thanks for pointing that out, I changed it to "has enough to debug" as that is what I had meant, it doesn't work since the code in question isn't working, but you can run it and it will run the product method as it would in the complete code. \$\endgroup\$ – Jake Aug 16 '17 at 13:47
  • \$\begingroup\$ @Vogel612 I am painfully aware of how hard these problems are, as I have been working on this code for about two weeks now. But seeing as I, a kid probably much less skilled at programming than most people on this site, was able to optimize it as much as I have, makes me confident that at least someone can see a way to solve this problem. \$\endgroup\$ – Jake Aug 16 '17 at 13:51
  • \$\begingroup\$ @Vogel612 Turns out it wasn't all that hard, just gotta put some of my sloppy ingenuity into it lol :) \$\endgroup\$ – Jake Aug 16 '17 at 16:27
1
\$\begingroup\$

Only a small improvement: Instead of your weird, twice used construction

        good = True
        if overlapping:
            good = False
        if good:
            TruePossibleSchedules.append(PossibleSchedules[schedule])

you may simply write

        if not overlapping:
            TruePossibleSchedules.append(PossibleSchedules[schedule])

as you never used the value of good for other things.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestion! Funnily enough I came up with the exact same code a few days ago. It did improve speeds by a few seconds. That section of code is exactly the section of code I'm trying to bypass with the new code I'm asking about, thats why I didn't include it in the code I posted, sorry if you thought I was asking about the first code, I'll clarify that in the post. Ill update the code from before too. \$\endgroup\$ – Jake Aug 16 '17 at 14:27
  • \$\begingroup\$ When I realized this fix he other day I felt so embarrassed that people saw it, it must have been really late when I wrote that lol. \$\endgroup\$ – Jake Aug 16 '17 at 14:35
1
\$\begingroup\$

Unnecessary complicated

sys.stdout.write("\rCalculating real schedules: " + str( float("{0:.2f}".format(( float(schedule+1)/float(len(PossibleSchedules))) *100) )) + "%    ")

may become much simpler:

sys.stdout.write("\rCalculating real schedules: {:.2f}%    ".format(float(schedule+1)/len(PossibleSchedules) *100))

because of:

  1. Joining all partial strings as you use the format() method.
  2. Omiting str(float ( as .2f format specifier itself performs it
  3. Omiting float() from float(len(PossibleSchedules) as the conversion is performed implicitly
  4. Omiting 0 from {:.2f} as you don't use a changed order of format() parameters

Still will be nicer to perform the calculation in advance:

percentage = float(schedule + 1) / len(PossibleSchedules) * 100
sys.stdout.write("\rCalculating real schedules: {:.2f}%    ".format(percentage))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Again, this is not the code in question, but thank you for the correction, this will be nice to know for the future. \$\endgroup\$ – Jake Aug 16 '17 at 14:42
1
\$\begingroup\$

After playing around with the idea and tinkering with the code I came up with quite a profound improvement. The new code I wrote:

def product(*args):
    pools = map(tuple, args)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]

        results_to_delete = []
        for schedule in result:
            for classOne in schedule:
                for classTwo in schedule:
                    if classOne is not classTwo:
                        for meetingOne in classOne:
                            for meetingTwo in classTwo:
                                if meetingOne[2]==meetingTwo[2] and (int(meetingOne[0])<=int(meetingTwo[1]) and int(meetingOne[1])>=int(meetingTwo[0])):
                                    results_to_delete.append(result.index(schedule))

        results_to_delete_sorted = []
        for elem in results_to_delete:
            if elem not in results_to_delete_sorted:
                results_to_delete_sorted.append(elem)

        if results_to_delete_sorted:
            for nextDelete in reversed(results_to_delete_sorted):
                del result[nextDelete]

    for prod in result:

        yield tuple(prod)

Output:

-> python Schedule.py
Loading classes: Done        
Time to create database of every section of every class offered: 4.77547621727

Want the best schedules? n

Are you feeling lucky??? (Do you want to only create one schedule) n

Would you like to limit the number of schedules made? 6

Time to calculate and store all possible true schedules: 0.170253038406
True Schedules: 21
Possibilities: 138240
Time taken to process Schedules: 0.170150995255
Random number: [19, 14, 10, 2, 15, 18]
Preparing...
Preparing...

Estimated time to load 6 images: 0 minutes and 7.32254362104 seconds
Loading schedules: 100.0%    

Estimated time to load 6 images: 0 minutes and 7.32254362104 seconds
Actual time to load 6 images: 0 minutes and 7.0474832058 seconds
Diff = 0.275052547455 seconds
Error in guess = 3.9%

Total run time: 21.251388073

-> python Schedule.py
Loading classes: Done        
Time to create database of every section of every class offered: 4.84699702263

Want the best schedules? n

Are you feeling lucky??? (Do you want to only create one schedule) n

Would you like to limit the number of schedules made? 6
Commandeering your 4 cores...
Thanks for letting me borrow those      

Time to calculate and store all possible true schedules: 16.4491579533
True Schedules: 21
Possibilities: 138240
Time taken to process Schedules: 16.4490189552
Random number: [6, 7, 16, 17, 2, 3]
Preparing...
Preparing...

Estimated time to load 6 images: 0 minutes and 6.38367891312 seconds
Loading schedules: 100.0%    

Estimated time to load 6 images: 0 minutes and 6.38367891312 seconds
Actual time to load 6 images: 0 minutes and 6.59872508052 seconds
Diff = 0.215077161789 seconds
Error in guess = 3.26%

Total run time: 40.6167318821

As you can see, this brings the time taken to get a list of schedules without overlap down from 16.4491579533 seconds to 0.170253038406 seconds which is literally 9561.6% faster, so I'd say that's quite an improvement.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

I am adding another answer because I have made it faster yet again, depending on how many possibilities, so I didn't edit or delete the other answer because it is still relevant.

def faster(result):

    results_to_delete = []
    for schedule in result:
        for classOne in schedule:
            for classTwo  in schedule:
                if classOne is not classTwo:
                    for meetingOne in classOne:
                        for meetingTwo in classTwo:
                            if meetingOne[2]==meetingTwo[2] and (int(meetingOne[0])<=int(meetingTwo[1]) and int(meetingOne[1])>=int(meetingTwo[0])):
                                results_to_delete.append(result.index(schedule))

    results_to_delete_sorted = []
    for elem in results_to_delete:
        if elem not in results_to_delete_sorted:
            results_to_delete_sorted.append(elem)

    if results_to_delete_sorted:
        for nextDelete in reversed(results_to_delete_sorted):
            del result[nextDelete]

    return result

def productSchedules(*args):
    pools = map(tuple, args)
    result = [[]]
    cores = 4
    try:
        cores = mp.cpu_count()
    except:
        cores = 4

    for pooly in pools:
        result = [x+[y] for x in result for y in pooly]

        splitSchedules = chunkify(result, cores)
        results = []

        pool = mp.Pool(processes=cores)
        results = pool.map(faster, splitSchedules)

        pool.close()
        pool.join()

        trueResults = []
        for x in range(len(results)):
            trueResults = trueResults + results[x]

        result = trueResults

        sys.stdout.write("\rCalculating real schedules: {:.2f}%    ".format(float(pools.index(pooly))/(len(pools)-1)  *100)) 

    for prod in result:

        yield tuple(prod)

When using the same classes as the previous answer, it took this code:

NEW:
Time to calculate and store all possible true schedules: 0.532428979874
True Schedules: 21
Possibilities: 138240
Time taken to process Schedules: 0.532146930695

Which is 212.7% slower than:

LAST ANSWER:
Time to calculate and store all possible true schedules: 0.170253038406
True Schedules: 21
Possibilities: 138240
Time taken to process Schedules: 0.170150995255

But, when dealing with massive lists, it is immensely faster:

ORIGIONAL:
-> python Schedule.py
Loading classes: Done        
Time to create database of every section of every class offered: 4.80000782013

Want the best schedules? n

Are you feeling lucky??? (Do you want to only create one schedule) y
Commandeering your 4 cores...
Thanks for letting me borrow those      

Time to calculate and store all possible true schedules: 340.109536171   *
True Schedules: 1429
Possibilities: 2350080
Time taken to process Schedules: 340.096308947
Random number: 515

Estimated time to load 1 images: 0 minutes and 1.4 seconds
Loading schedules: 100.0%    

Estimated time to load 1 images: 0 minutes and 1.4 seconds
Actual time to load 1 images: 0 minutes and 1.23541712761 seconds
Diff = 0.164559030533 seconds
Error in guess = 13.32%

Total run time: 359.528627157

LAST ANSWER:
-> python Schedule.py
Loading classes: Done        
Time to create database of every section of every class offered: 4.88494277

Want the best schedules? n

Are you feeling lucky??? (Do you want to only create one schedule) n

Would you like to limit the number of schedules made? 6

Time to calculate and store all possible true schedules: 24.3771910667   *
True Schedules: 1429
Possibilities: 2350080
Time taken to process Schedules: 24.3690268993
Random number: [661, 77, 621, 287, 1000, 27]
Preparing...
Preparing...

Estimated time to load 6 images: 0 minutes and 7.04940247536 seconds
Loading schedules: 100.0%    

Estimated time to load 6 images: 0 minutes and 7.04940247536 seconds
Actual time to load 6 images: 0 minutes and 6.98810195922 seconds
Diff = 0.0612914562225 seconds
Error in guess = 0.88%

Total run time: 46.3684411049

NEW:
-> python Schedule.py
Loading classes: Done        
Time to create database of every section of every class offered: 5.04908514023

Want the best schedules? n

Are you feeling lucky??? (Do you want to only create one schedule) n

Would you like to limit the number of schedules made? 6

Time to calculate and store all possible true schedules: 8.99596405029   *
True Schedules: 1429
Possibilities: 2350080
Time taken to process Schedules: 8.92583394051
Random number: [650, 238, 352, 956, 57, 503]
Preparing...
Preparing...

Estimated time to load 6 images: 0 minutes and 7.97566509246 seconds
Loading schedules: 100.0%    

Estimated time to load 6 images: 0 minutes and 7.97566509246 seconds
Actual time to load 6 images: 0 minutes and 7.38800001144 seconds
Diff = 0.587633132935 seconds
Error in guess = 7.95%

Total run time: 35.5436708927

Which is 170.98% faster than the previous answers code, and 3680.69% faster than the original code.

So in conclusion, if 0.3 seconds is really that important then I could just check how many possibilities it will run through and if it is over some threshold then I could have it run the new code instead of the old code, but in reality I don't care about 0.3 seconds so I will just have this new code in my program, no need for all that code to save such little time.

enter image description here

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

So for each daterange, you're looking into all other dateranges to find any that are overlapping. That will run in O(n²) and be very slow if you have a lot of ranges.

You can do this in a more efficient way. Here's how I do it.

  • Sort the dates by startdate, then enddate
  • For each range i: 0 > max:
  • Compare range[i] and range[i+1]. If the range[i+1] startdate is bigger then the range[i] enddate then you can stop comparing. None of those following ranges will overlap either.
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.