search_piet5.cpp

search_piet5.cpp

#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define FOR(i, a, b) \
  for (int i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define ALL(f, x, ...)                               \
  ([&](decltype(x)& ALL) {                           \
    return (f)(begin(ALL), end(ALL), ##__VA_ARGS__); \
  })(x)
void ASYNC_IO() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

template <class IT>
bool next_combination(IT first1, IT last1, IT first2, IT last2) {
  if ((first1 == last1) || (first2 == last2)) {
    return false;
  }
  IT m1 = last1;
  IT m2 = last2;
  --m2;
  while (--m1 != first1 && !(*m1 < *m2)) {
  }
  bool result = (m1 == first1) && !(*first1 < *m2);
  if (!result) {
    while (first2 != m2 && !(*m1 < *first2)) ++first2;
    first1 = m1;
    std::iter_swap(first1, first2);
    ++first1;
    ++first2;
  }
  if ((first1 != last1) && (first2 != last2)) {
    m1 = last1;
    m2 = first2;
    while ((m1 != first1) && (m2 != last2)) {
      std::iter_swap(--m1, m2);
      ++m2;
    }
    std::reverse(first1, m1);
    std::reverse(first1, last1);
    std::reverse(m2, last2);
    std::reverse(first2, last2);
  }
  return !result;
}

template <class IT, typename INT>
bool next_combination(IT first, IT last, INT num) {
  auto middle = first + num;
  return next_combination(first, middle, middle, last);
}
template <typename INT>
vector<INT> combinations(INT last) {
  vector<INT> data;
  REP(i, last) data.push_back(i);
  return data;
}

int order(int from, int to) {
  // 0 <= from,to < 18
  if (from % 3 != 0 && to % 3 == 0) to += 3;
  if (from % 3 == 2 && to % 3 == 1) to += 3;
  to -= (from % 3);
  from -= (from % 3);
  if (from > to) to += 18;
  return to - from;
}
template <typename T>
vector<T> SLICE(const vector<T>& base, int begin = 0, int end = 0) {
  if (end == 0) end = base.size();
  vector<T> res;
  FOR(i, begin, end) { res.push_back(base[i]); }
  return res;
};
struct Info {
  int num;
  vector<int> orders, kinds;
  bool is_same(const Info& info) const {
    REP(i, orders.size()) if (orders[i] != info.orders[i]) return false;
    return true;
  }
};

signed main() {
  ASYNC_IO();
  auto data = combinations(18);
  FOR(n, 4, 6) {
    vector<Info> infos;
    do {
      vector<int> orders(18);
      REP(j1, n) {
        REP(j2, j1) {
          auto regist = [&](int pos) {
            // if (orders[pos] == 0)
            orders[pos]++;
          };
          regist(order(data[j1], data[j2]));
          regist(order(data[j2], data[j1]));
        }
      }
      int res = 0;
      for (auto order : orders) res += order > 0 ? 1 : 0;
      Info info = {res, orders, SLICE(data, 0, n)};
      if (infos.size() == 0) {
        infos.push_back(info);
        continue;
      }
      if (infos[0].num > info.num) continue;
      if (infos[0].num < info.num) {
        infos.clear();
        infos.push_back(info);
        continue;
      }
      if (!ALL(any_of, infos,
               [&](const auto& it) { return it.is_same(info); })) {
        infos.push_back(info);
        continue;
      }
    } while (ALL(next_combination, data, n));
    for (auto& info : infos) {
      cout << info.num << "::";
      for (auto kind : info.kinds) cout << kind << " ";
      cout << endl;
      REP(y, 3) {
        REP(x, 6) {
          if (ALL(any_of, info.kinds,
                  [&](const auto& it) { return it == 3 * x + y; })) {
            cout << "o ";
          } else {
            cout << "x ";
          }
        }
        cout << endl;
      }
      cout << endl;
    }
  }
}