title: Creating a chore wheel for a household
body: <p>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.</p>
  
  <p>The specs are:</p>
  
  <ul>
  <li><p>Assume a house of n people.</p></li>
  <li><p>Assume m chores.</p></li>
  <li><p>For now, for simplicity's sake, assume n == m.</p></li>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  <li><p>No two people should be assigned the same chore for a given week.</p></li>
  <li><p><strong>Each person should do "each chore they are capable of doing" exactly once before repeating a chore.</strong></p></li>
  </ul>
  
  <p>Right now for debugging purposes, I'm manually incrementing this variable and checking if the output is sane.</p>
  
  <p>My code so far:</p>
  
  <pre class="lang-py prettyprint-override"><code>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
  </code></pre>
  
  <p>First week, things are fine. Second week though I see people doubling up, which is to be expected with my naive algorithm. </p>
  
  <p>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.</p>
  
  <p>This situation must certainly be analogous to other computational problems, should it not? Perhaps something in the area of OS dev, process scheduling perhaps?</p>
  
  <p>What algorithm would you suggest or what is this problem analogous to? </p>
  
  <p>For the fun of it, additional features I am planning on implementing at some point:</p>
  
  <ul>
  <li><p>m > n (Some chores wouldn't get done each week, but have an "essential" flag to chores
  to ensure it would never be skipped)</p></li>
  <li><p>n > m (Ensure rest days are distributed fairly)</p></li>
  <li><p>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.</p></li>
  </ul>