7
$\begingroup$

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away.

My wardrobe is set up as follows:

  • My drawers are categorized by the type of clothing they hold, and I'm very particular about that; this means I can't put t-shirts in my pants drawer (otherwise I'll be too flustered over it to sleep). Of course, I know this categorization, and I know which drawer is which even in the dark.
  • I have $N$ pieces of clean laundry, and $M$ drawers arranged vertically (with the drawer at the top being $D_0$)
  • I can open and close drawers as I see fit, but if drawer $D_i$ is open, I can't put any clothes in drawer $D_{i+1}$ (because it's blocked by $D_i$).
  • All of my drawers are already closed when I enter the room.
  • When I finish, I have to close all open drawers.

Considerate gentleman that I am, I don't want to wake up my roommate (this was a college dorm, so we slept in the same room). I resolved to not turn on the lights and make as little noise as possible.

This means that I have to put away my laundry under the following constraints:

  • I can't see into my laundry bag, so I only know what I grab as soon as I pull it out.
  • Opening and closing a drawer makes noise. Pulling items out of my laundry bag, or actually putting them in the drawer, does not.
  • I can only put away one item of clothing at a time; I can't fold like clothes and put them in piles (and then put those piles away) because the floor's too dirty and there's no space on the furniture within reach of me.
  • I can put an item of clothing back in my bag and take out another, but the one I take out next could be the one I had just put back in (remember, I have no control over what I pull out of the bag).

Given this, I have three questions:

  • How can I put my laundry away while opening and closing the drawers as few times as possible?
  • Has anyone else thought of this problem or something similar?
  • Does this problem have any practical applications?
$\endgroup$
  • $\begingroup$ Can you silently stuff an item back into the laundry bag and extract something else, or must you treat it as a stack? $\endgroup$ – Kyle Jones Oct 28 '15 at 20:23
  • $\begingroup$ Never thought of that as a possible variable. Let's say I can put an item back and pull something else out (but the item I pull out again could be the item I just put back in). $\endgroup$ – JesseTG Oct 28 '15 at 20:25
  • $\begingroup$ @KyleJones With that strategy, Jesse may not get any sleep with high probability. $\endgroup$ – Raphael Oct 29 '15 at 6:04
  • 1
    $\begingroup$ There are several practical answers, of course. 1) Don't do it while your roomie is asleep. 2) Create a clean area of space for pre-sorting and folding. 3) Wash by kind. 4) Pre-sort by drawer in the laundry room, while pulling items out of the washing machine. (Get one bag per drawer if there's not clean space there either.) $\endgroup$ – Raphael Oct 29 '15 at 6:06
  • 1
    $\begingroup$ As for the computer science question: interesting. It's mostly an exercise in probability theory, I guess: unless you can obtain some control over what item you get next, your algorithm has little to work with. $\endgroup$ – Raphael Oct 29 '15 at 6:08
4
$\begingroup$

How about the following:

  1. Go through your bag; fold and stack items for drawers $D_i$ and $D_{i+1}$, $i \in 2\mathbb{N}$, in/on drawer $D_i$ (which you open on demand).

    Make sure you have the items for $D_{i+1}$ on top; that may require quite some reordering pancake-style, but you don't seem concerned about such operations.

    Note that there is always enough room (two drawer heights) to do this, assuming the drawers are roughly equal and your clothes fit into them as it is.

  2. For each open drawer $D_i$,

    • pick up the stack for $D_{i+1}$ (and put in the bag, if necessary),
    • close $D_i$,
    • open $D_{i+1}$,
    • put the stack in there, and
    • close $D_{i+1}$.

This algorithm requires $2M$ drawer movements if all drawers get clothing, so it is worst-case optimal.

It will waste some movements if there are items for $D_{i+1}$ but not $D_i$; if only odd drawers get items, we execute twice the drawer movements necessary. Since this is the worst that can happen, we still have a $2$-approximation.

$\endgroup$
  • 2
    $\begingroup$ One good thing about this algorithm is that it's deterministic. You won't need to roll any dice which may wake up your roomie. $\endgroup$ – Raphael Oct 29 '15 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.