Creating a chore wheel for a household

Question

Kind of a goofy problem, but an interesting one, one that should be, in my mind, a "solved problem". I'm mostly just interested in the algorithm, I can handle the implementation myself.

The specs are:

Assume a house of n people.
Assume m chores.
For now, for simplicity's sake, assume n == m.
Assume an exclusion list of tuple, ie, Bob doesn't have to ever clean the upstairs bathroom since he lives in a different part of the house, with his own private bathroom. He is however responsible for the other chores.
Assume a "weekly offset" integer variable that is incremented on disk. If this variable is not incremented, the program spits out the same output each time. For now, I'm simply incrementing this variable manually.
No two people should be assigned the same chore for a given week.
Each person should do "each chore they are capable of doing" exactly once before repeating a chore.

Right now for debugging purposes, I'm manually incrementing this variable and checking if the output is sane.

My code so far:

users = [
"Alice",
"Bob",
"Carl",
"Dani",
"Elmer",
]

chores = [
"Kitchen",
"Dining room",
"Upstairs bathroom",
"Living room", 
"Lawn",
] 

exclusion_list = [
("Bob", "Upstairs bathroom")
] 

weekly_offset = 0

# Generate a list of chores "doable" by each user
# Horrible method I know, but just trying to get something working
# and for trivial n and m it shouldn't matter.

user_list = {}
for i in users:
    temp_list = []
    for j in chores:
        for k in exclusion_list:
            if k[0] == i and k[1] == j:
                print("Excluded")
            else:
                temp_list.append(j)
    user_list[i] = temp_list

# Confirm this list is accurate
print(user_list)

print()

user_offset = 0
for i in user_list:
    print(i, end = ": ")
    chore_index = (weekly_offset + user_offset) % len(user_list[i]) 
    print(user_list[i][chore_index])
    user_offset += 1

First week, things are fine. Second week though I see people doubling up, which is to be expected with my naive algorithm.

I have then tried to think of an algorithm to satisfy all these specs, and now I'm not even sure if it's possible.

This situation must certainly be analogous to other computational problems, should it not? Perhaps something in the area of OS dev, process scheduling perhaps?

What algorithm would you suggest or what is this problem analogous to?

For the fun of it, additional features I am planning on implementing at some point:

m > n (Some chores wouldn't get done each week, but have an "essential" flag to chores to ensure it would never be skipped)
n > m (Ensure rest days are distributed fairly)
Being able to modify the code to add or remove a user and still continue to satisfy the "Each person should do "each chore they are capable of doing" exactly once before repeating a chore" specification.

user_8581025 · Answer

The specs are:

Assume a house of n people.

Assume m chores.

For now, for simplicity's sake, assume n == m.

Assume an exclusion list of tuple, ie, Bob doesn't have to ever clean the upstairs bathroom since he lives in a different part of the house, with his own private bathroom. He is however responsible for the other chores.

Assume a "weekly offset" integer variable that is incremented on disk. If this variable is not incremented, the program spits out the same output each time. For now, I'm simply incrementing this variable manually.

No two people should be assigned the same chore for a given week.

Each person should do "each chore they are capable of doing" exactly once before repeating a chore.

The conditions on your specs are not compatible. The last condition above requires a chain of chores which has a length of the number of chores a user is capable of doing. But it leads to a contradiction if we introduce exclusion_list, i.e. the fourth condition.

For example, if we ignore the exclusion_list, one possible solution is the following:

# Abbreviations:
# K == "Kitchen", D == "Dining room", U == "Upstairs bathroom"
# Lr == "Living room", L == "Lawn"

Week   1     2     3     4     5

Alice: K  -> D  -> U  -> Lr -> L
Bob:   D  -> U  -> Lr -> L  -> K
Carl:  U  -> Lr -> L  -> K  -> D
Dani:  Lr -> L  -> K  -> D  -> U
Elmer: L  -> K  -> D  -> U  -> Lr

Each user has a chain of length 5.

But, if we apply the exclusion_list, Bob should have a chain of length 4. It means Bob will do 4 different chores in 5 weeks like below:

Week   1     2     3     4    5

Bob:   D  -> Lr -> L  -> K -> D

In 5 weeks, there's (5 kinds of chores) * (5 weeks) = 25 chores to do. And, since other 4 users will do 5 different kinds of chores in 5 weeks (since they should have a chain of length 5), the number of remaining chores, after assigning to the 4 users, is 25 - ((5 kinds of chores) * (4 users)) = 25 - 20 = 5. And these 5 chores are all different kinds. It contradicts that Bob should have a chain of length 4.

It can be seen much easier if we assume a very simple case which can be expressed like below:

users = [
    "Alice",
    "Bob",
]

chores = [
    "Kitchen",
    "Dining room",
]

exclusion_list = [
    ("Bob", "Kitchen")
]

Then, Alice can't do the "Dining room" chore, which Alice is capable of doing, before repeating the "Kitchen" chore, since Bob always do the "Dining room" chore.

Creating a chore wheel for a household

1 Answers