World's most popular travel blog for travel bloggers.

[Solved]: Sorting an unordered pile of items into drawers with minimal drawer movements

, , No Comments
Problem Detail: 

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?
Asked By : JesseTG

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48817

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback