靴下を干す時

色違いの靴下を干そうとするとすごい間抜けなことになる．

ぬれた洋服の色って見づらいから，二つを並べないと違いがわからない．コード(Java)で書くと

class Socks {
  private final int color;
  private boolean isDamaged;

  public boolean isSameColor(Sock otherSocks) {
    return ( color == otherSocks.color);
  }

  public boolean isDamaged() {
   return isDamaged;
  }
}

しかインターフェースがないSocksクラスが入ったスタックを，

class Pair {
  private Socks a;
  private Socks b;

  Pair(Socks a, Socks b) {
    this.a = a;
    this.b = b;
  }
}

のリストにまとめるということになる．今どうやってるかと言うと，

public void hangSocks(Stack<Socks> items, List<Pair> hanger) {
  Stack temp = new Stack();

  while (!items.empty() ) {
    Socks socksA = items.pop();
    if (socksA.isDamaged()) {
      continue;  // 痛んでたら捨てて次のをとる
    }
    while (!items.empty()) {
       Socks socksB = items.pop();
       if (socksB.isDamaged() ) {
         continue;
       } else if (socksA.isSameColor(socksB)) {
         hanger.add(new Pair(socksA, socksB); // たまたま同じ色だったらハンガーにかける
         break;
       } else {
         temp.push(socksB); // 違う色だったらひとまず別のところに置く
       }
    }
    // このループを経てハンガーにかけられなかったら靴下は半端だから自動的に捨てる
    // 一時的においた靴下を元のスタックに戻す．
    for (Socks socks : temp) {
       items.push(socks);
    }
  }
}

というふうに，非常に場当たり的なかけ方をしているので死ぬほど効率が悪い．O(n^2)のはず．

最初に同じ色の靴下のリストを作ってしまう

public void hangSocks(Stack<Socks> items, List<Pair> hanger) {
  List<Socks> samples = new ArrayList<Socks>();
  List<Stack<Socks>> temp = new ArrayList<Stack<Socks>>();
  while (!items.empty()) {
    Socks socks = items.pop();
    if (socks.isDamaged()) continue;
    int i;
    for (i=0; i < samples.size(); i++) {
      if (socks.isSameColor(samples.get(i))) {
        temp.get(i).add(socks);
        break;
      }
    }
    if (i == samples.size() ) {
      samples.add(socks);
      Stack stack = new Stack();
      stack.push(socks);
      temp.add(socks);
    }
  }

  for (Stack<Socks> list : temp) {
    Socks stock;
    for (Socks socks : list) {
      if (stock == null) {
        stock = socks;
      } else {
        hanger.add(new Pair(stock, socks));
        stock = null;
      }
    }
  }
}

は色の数が少なければだいぶ効率的だが，メモリ消費量の点で採用していないのかもしれない．コードの長さ自体も長いし．

最初におもむろにPairを組んでhangerに突っ込んだあとにswapして揃える形式で効率の良いアルゴリズムがあればいいなあと思うが厳しいのかもしれない．