Project 1: Socks

Bob is trying to maximize the efficiency of his sock collection. In order to avoid having to pair and fold socks, he buys just one kind of white sock. That way, he can draw two random socks from his drawer, and they will be of the same type. Bob explains this principle to his (n-1) roommates, who all decide to buy into this scheme. In particular, all n roommates share a single large drawer full of socks. However, the roommates insist on having at least 2 colors of socks for variety. So Bob agrees to stock both black and white socks, an equal number of each.

Over time the white socks begin to go grey. A white sock's shade s starts at 255 (white) on a greyscale range (0-255) and decreases by 2 every time the sock is worn/washed, until it reaches 127 (mid-grey). As a result, when Bob or his roomates each draw two originally-white socks from the drawer, they may have different shades of white/grey. Black socks also gradually go grey. A black sock starts at 0 (black) on the greyscale range, and increases by 1 every time the sock is worn/washed, until it reaches 64 (dark grey).

The sock drawer has a fixed capacity C where C is a parameter. Each turn in the simulation corresponds to a day. Each roomate R selects socks from the drawer in turn, in random order depending on when R gets dressed that day. R may not be satisfied by the first two socks he/she selects. If the two worn socks significantly differ in shade, then people will notice. In particular, if the socks differ by more than 6 units in shade, then an embarrassment score of |s₁ - s₂| accumulates to R's aggregate embarrassment, where s₁ and s₂ are the shades of the two socks.

To mitigate this problem, each roomate chooses four socks at random from the drawer, and selects two of them to wear. Worn socks are subsequently washed and replaced into the sock drawer. The third and fourth socks may each be put back into the drawer unworn, or discarded altogether, whichever the roomate decides. Also, socks that have reached a shade level of 127 or 64 are worn out, and have a 25% chance of developing a hole and needing to be immediately discarded after being worn.

When six or more socks of a color have been discarded, Bob buys a new pack of six pristine socks of that color (they're cheaper when you buy multiple pairs at a time) and adds them to the drawer to restore it to its full capacity. If there were more than 6 discarded socks of a color on a turn, but less than 12, then the extra beyond six will count towards the next batch of discarded socks. If 12 or more socks of a color are discarded on a turn, 2 new packs of socks will be bought that turn, etc. Every time a pack of socks is bought, Bob spends $10 and shares the cost with his roommates.

The simulator will take as input a budget B which is an upper bound on the amount that the roommates can spend on socks for the entire simulation. The length T of the simulation is also a simulator input. In the event that the budget is reached before the end of the simulation, the simulator will not replenish discarded socks, leading to a reduced number of socks in the sock drawer. It is possible that a profligate set of roomates could end up with insufficiently many socks to wear each day. If a roommate faces a situation where there are fewer than 2 socks left in the drawer, that roommate will go without socks that day and suffer an embarrassment score of 256².

You get to write code to determine day to day sock choices. You have incomplete information about the distribution of shades of socks in the drawer, because you can't track which socks were worn by other roomates. You do not know the current number of discarded socks. You do know C, n, B, T, the day number, your full embarrassment history, and the total amount spent on socks since the start of the simulation. (The initial set of socks is not included in the cost.)

Goals:

• Given an annual budget what strategy stays under that budget in the long term, while minimizing embarrassment. Note that you can adjust your strategy on the fly if you see that expenses are getting out of hand. Note also that there will always be a baseline spend rate simply due to socks with holes, even if Bob or his roommates do not discard any additional socks.

• Bob wonders whether putting in a bit more work during sock selection might help the overall embarrassment score. Would choosing five socks rather than four (and having to option to replace or discard the three that are not worn that day) lead to less embarrassment for a given budget? How much less embarrassment?

• Bob also wonders whether pooling of socks is intrinsically better or worse than having each roomate manage their own separate sock drawer using the same strategy. Try to address this question by comparing simulations with many roommates against multiple suitably-chosen simulations with one roommate. Note that when there's just one roommate, your player can track the current state of all socks.

The simulator will take certain parameters as input, including the size C of the sock drawer, the number n of roomates, and a random number seed for repeatability of runs. C will be a multiple of 4, to ensure an even balance of pairs of white and black socks. C will be bigger than 4n+10 to ensure that the drawer always has enough socks. (Question: Why 4n+10? Would this need to change if roomates chose five socks per turn?) Each roomate will make decisions according to the corresponding group's code. Each roommate could be running a different group's code, or we could also have runs in which all roomates use different instances of a single group's code. The simulator will allow you to choose either 4 or 5 socks as the selection unit for the simulation. On each turn the simulator will choose the appropriate number of socks and supply them to the roomate's code, which selects 2 to wear and specifies what should be done with the extra sock(s). The simulator will keep track of embarrassment scores for each roomate, and will automatically replenish socks (and add $10 to the money spent) as needed.

For the tournament at the end of the project, we'll likely run relatively long simulations, to make sure that we capture the long-term behavior of your strategies.

Some initial things to think about:

• Is it ever possible that the minimum embarrassment on a turn is achieved by pairing an originally-white sock with an originally-black sock?