プログラミング: 今日の問題

プログラミングの問題。なんか全然綺麗にかけなかったので記事にする。

問題

今、列A、B、Cがある。ここから２つの組み合わせを選びたい。 どういうふうに選ぶかというと、

• Aから１つ、Bから１つ
• Bから１つ、Cから１つ
• Aから１つ、Cから１つ
• Cから２つ

評価関数compare2 : (X, X) -> (X, X) -> boolが与えられるときに、最大の組み合わせを選びたい。

ただしA、B、Cの長さは０かもしれず、少なくとも１つの列の長さは0より大きい。 組が作れない場合（例えばAは長さ２、Bは０、Cは０）のときは組ではなくcompare1 : X -> X -> boolが最大であるものを選ぶ。 要素の重複は認めない。

回答

愚直に書いてもまぁそんなもんか、って感じになった。 綺麗に書きなおしてみたら以外に短かかった、、、、あれれ、、、、、、

これ、実際はAとBの型は同じなんですが、Cは違うのでかなり面倒だった感じでした。

#include <memory>
#include <utility>
#include <vector>

// コンパイル通すために仮にintにしておく
using X = int;

using answer = std::pair<X*, X*>;

extern bool compare2(X*, X*, X*, X*);
extern bool compare1(X*, X*);

std::unique_ptr<std::pair<X*, X*>>
choose(std::vector<X*> A) {
  X* max = nullptr;
  for (auto a : A) {
    if (max == nullptr || compare1 (a, max)) {
      max = a;
    }
  }

  return std::unique_ptr<answer>(new std::pair<X*, X*>(max, max));
}

std::unique_ptr<std::pair<X*, X*>>
get_pair(std::vector<X*> A, std::vector<X*> B, std::vector<X*> C) {
  if ((A.size() == 0 && B.size()) == 0)
    return choose(C);
  if ((B.size() == 0 && C.size()) == 0)
    return choose(A);
  if ((A.size() == 0 && C.size()) == 0)
    return choose(B);

  X* max_a = nullptr;
  X* max_b = nullptr;

  auto f = [&](std::vector<X*> M, std::vector<X*> N) {
    for (auto & a : M) {
      for (auto & b : N) {
        if (max_a == nullptr || compare2 (a, b, max_a, max_b)) {
            max_a = a;
            max_b = b;
        }
      }
    }
  };

  f (A, B);
  f (A, C);
  f (B, C);
  f (C, C);

  return std::unique_ptr<answer>(new std::pair<X*, X*>(max_a, max_b));
}