Pairing up Socks

On a nice day, Babai, a computer scientist, received back all 6 pairs of my b l u e \color{#3D99F6}{blue} and r e d \color{#D61F06}{red} socks in a laundry basket. He needed to pair them up into pairs of same color for me.

Being a computer scientist, he wondered what would be a good way to sort them out. Can you help him by figuring out the faster way to sort these?

Swap and Go:

  1. Lay the socks on the table side by side.
  2. While there are some b l u e \color{#3D99F6}{blue} socks in the last 6 socks, do the following:
    • Going from left to right, if there is a r e d \color{#D61F06}{red} sock to the right of a b l u e \color{#3D99F6}{blue} sock, exchange them.
  3. Now, all 6 pairs of adjacent socks are each of the same color. So, take two at a time and pair them up.

Throw into Buckets:

  1. Lay the socks on the table side by side. Take two buckets, r e d \color{#D61F06}{red} and b l u e \color{#3D99F6}{blue} .
  2. For all the socks on the table, check which of them are r e d \color{#D61F06}{red} , one by one:
    • if a sock is r e d \color{#D61F06}{red} , put it in the r e d \color{#D61F06}{red} bucket;
    • if a sock is b l u e \color{#3D99F6}{blue} , put it in the b l u e \color{#3D99F6}{blue} bucket.
  3. Now, we know that all the r e d \color{#D61F06}{red} and b l u e \color{#3D99F6}{blue} socks are each in the bucket of the same color. Taking two of them at a time from the same bucket, pair them up.
Swap and Go Throw into Buckets

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Matthew Thomas
Feb 20, 2017

The swap and go method will require multiple iterations of checking each sock to sort them into a pile of blue socks and a pile of red socks that can easily be paired.

Whereas the throw into buckets method only requires one iteration of checking each sock to sort them into blue and red.

Therefore the throw into buckets method is more efficient.

That is a nice observation. Another point is that the swap and go method would be hard to adopt to a case where there are more than 2 colors, however the buckets methods just needs more buckets which is easier to see

Agnishom Chattopadhyay - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...