 Assign Gift Givers
This function is for those situations where a set of people, such as office coworkers, exchange gifts among themselves, with each person assigned to buy gifts for one other person.
This function walks the list of people and assigns a gift target to each of them. It has to ensure that no one is assigned his or her own name. In particular, with a list of N people, it needs to avoid the situation where the first N-1 people are chosen to give gifts among themselves and, when it is time to process the last person on the list, no one else is left.
The program is passed as a parameter a list of names, and returns a dictionary. In the dictionary, the keys are the same list of names, and the values are the name that each person should give a gift to.
For a Python list, the function
mylist.count(x)
returns the number of times that x appears in mylist.
The function
mylist.pop(i)
returns the element at index i of mylist, and also removes it from the list.
The function
mylist.index(x)
returns the index of the first occurrence of x in mylist. It's an error if x does not occur in mylist.
Source Code
1. import random
2.
3. def secretSanta( inputList ):
4. """
5. inputList: A list of names
6.
7. Returns a dictionary, the keys are givers' names,
8. the values are receivers' names.
9. """
10.
11. if len(inputList) < 2:
12. return {}
13.
14. returnDict = {}
15.
16. """ Make a copy of the input list; we remove people
17. from this list as they are assigned givers.
18. """
19.
20. receiversList = inputList[:]
21.
22. for person in inputList:
23.
24. """ If there are only two receivers left, and one
25. of them is the last person in inputList, then
26. assign the last person to the second-to-last
27. person.
28. """
29.
30. if len(receiversList) == 2:
31. if receiversList.count(inputList[-1]) == 1:
32. returnDict[person] = inputList[-1]
33. returnDict[inputList[-1]] = person
34. break;
35.
36. """ The typical situation, just randomly pick
37. someone out of receiversList and give them to
38. person. We don't want to assign someone to
39. themselves. If that happens, we assign them the
40. next person in receiversList.
41. """
42.
43. if receiversList.count(person) == 1:
44. receiverIndex = \
45. int ((len(receiversList)-1) * random.random())
46. if receiversList.index(person) <= receiverIndex:
47. receiverIndex += 1
48. else:
49. receiverIndex = \
50. int (len(receiversList) * random.random())
51.
52. returnDict[person] = \
53. receiversList.pop(receiverIndex);
54.
55. return returnDict
Suggestions
Two lists (inputList and receiversList) and one dictionary (returnDict) are used. State the goal of each one, and note which ones are modified and where. On line 46, the index() function is used to look up person in receiverList. This implies that person must be in receiverList. Is this guaranteed to be true? An invariant condition exists between returnDict and receiversList, which is that an element in one is not in the other. Check the sections of code that relate to this to ensure that the condition is always true. What is the goal of the code on lines 43-50? How many different paths to walk through exist in this code?
Hints
Walk through one iteration of the code when the function was passed an inputList equal to [ "Tom", "Joe", "Donna", "Susan", "Paul" ]. Imagine the same input list, but the next iteration of the main for loop on line 22, where person is "Joe", and assume the remaining receiversList is [ "Tom", "Donna", "Susan", "Paul" ]. Consider the fourth iteration, where person is "Susan", and assume receiversList is now [ "Donna", "Paul" ].
Explanation of the Bug
The code that appears on line 33
returnDict[inputList[-1]] = person
has a bug. Although the code looks nice and symmetric with the code on line 32, it is not correct. This is shown by walking through the third hint.
The code assumes that if the main for loop has two people left to iterate for, the receiversList has those same two people on it. So, if you have Susan and Paul left, the assumption is that receiversList will be [ "Susan", "Paul" ], and you can just assign them to each other.
In fact, this is not always true (and if it does happen to be true, the standard logic on lines 43-50 will handle it correctly anyway). The problem that lines 30-34 is trying to avoid is something shown in the third hint: person is "Susan", Paul is the next (and last) person to be processed by the main for loop, and Paul is on receiversList with someone other than Susan (in the example shown in the third hint, Donna and Paul are on receiversList). What might happen is that Susan is assigned Donna; in this case, Paul is stuck with himself.
This is an A.logic error. Line 32 is correct because it creates a "Susan" : "Paul" element in returnDict. But, line 33 should be creating "Paul" : "Donna", not "Paul" : "Susan". How can the code accomplish this? We know that Paul is the last person in receiversList because he was last in inputList and receiversList originated as a copy of inputList. Because receiversList has two elements, and "Paul" is the last element, "Donna" must be the first one. So, line 33 should read as follows:
returnDict[inputList[-1]] = receiversList[0]
|
