How to create optimized schedule that avoids duplicates [closed]

Question

I've got a list of games between teams that takes place over a sixteen day period:

| Date | Game                        |
|------|-----------------------------|
| 1    | hot ice vs playerz          |
| 1    | caps vs quiet storm         |
| 1    | slick ice vs blizzard       |
| 1    | flow vs 4x4's               |
| 2    | avalanche vs cold force     |
| 2    | freeze vs in too deep       |
| 2    | game spot vs rare air       |
| 2    | out of order vs cold as ice |
| 3    | playerz vs avalanche        |
| 3    | quiet storm vs freeze       |
| 3    | blizzard vs game spot       |
| 3    | 4x4's vs out of order       |
| 14   | freeze vs avalanche         |
| 14   | out of order vs game spot   |
| 14   | in too deep vs cold force   |
| 14   | cold as ice vs rare air     |
| 15   | blizzard vs quiet storm     |
| 15   | playerz vs 4x4's            |
| 15   | slick ice vs caps           |
| 15   | hot ice vs flow             |
| 16   | game spot vs freeze         |
| 16   | avalanche vs out of order   |
| 16   | rare air vs in too deep     |
| 16   | cold force vs cold as ice   |

There are 16 teams that make up this schedule, and what I'd like to do in Python is find all of the 8 game combinations that allow me to "see" each team once. The only limitation is that I can only see one game per day. At this point all I can think of is a ton of nested for loops that generates all possible schedules, and then checking each one after to see if it is valid. A valid schedule is one that has one game per date and sees each team once.

Answer 1

You could use a backtracking algorithm to iterate through different combinations of matches and filtering them according to the constraints you mentioned.

First step would be to format your data into a collection like a python list or dict. Then implement a recursive backtracking algorithm that selects one match per day, and checks to make sure the chosen match doesn't include teams you have already selected.

Here is a rough example that uses the data you provided in your question:

def combinations(matches, day, schedules, current):
    """Backtracking function for selecting unique schedules."""
    # base case when you have a match from each day
    if day > max(matches.keys()):  
        schedules.append(current[:])
        return
    # skip over days where there are no matches
    while day not in matches:
        day += 1
    # select one match for the current date
    for i in range(len(matches[day])):
        teams = matches[day][i]
        current_teams = [j for i in current for j in i]
        # check if the teams are already in the current schedule
        if teams[0] in current_teams or teams[1] in current_teams: 
            continue
        del matches[day][i]
        # recursive case
        combinations(matches, day + 1, schedules, current + [teams])
        matches[day].insert(i,teams)
    return




def format(inp):
    """Formats input data into a dictionary."""
    lines = inp.split("\n")[2:]     # split lines of input data
    matches = [(line.split("|")[1:-1]) for line in lines]
    schedule = {}
    # add matches to dict with date as key and matches as value.
    for day, match in matches:
        day = int(day.strip())
        teams = match.strip().split(" vs ")
        try:
            schedule[day].append(teams)
        except KeyError:
            schedule[day] = [teams]
    ideal = []
    # use backtracking algorithm to get desired results
    combinations(schedule, 1, ideal, [])
    show_schedules(ideal)


def show_schedules(results):
    for i, x in enumerate(results):
        print(f"Schedule {i+1}")
        for day, match in enumerate(x):
            print(f"Day: {day+1} - {match[0]} vs. {match[1]}")
        print("\n")


format(inp)  # <- entry point:`inp` is the pre-formatted data `str`

It's not exactly the most elegant code... :) With the example data this algorithm generates 32 unique schedules of 6 games. The output looks something like this but for each day of matches:

Schedule 1
Day: 1 - hot ice vs. playerz
Day: 2 - avalanche vs. cold force
Day: 3 - quiet storm vs. freeze
Day: 4 - out of order vs. game spot
Day: 5 - slick ice vs. caps
Day: 6 - rare air vs. in too deep


Schedule 2
Day: 1 - hot ice vs. playerz
Day: 2 - avalanche vs. cold force
Day: 3 - 4x4's vs. out of order
Day: 4 - cold as ice vs. rare air
Day: 5 - blizzard vs. quiet storm
Day: 6 - game spot vs. freeze

For more information on backtracking here are a few external resources or there are countless examples here on stack overflow.

https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

http://jeffe.cs.illinois.edu/teaching/algorithms/book/02-backtracking.pdf