オフラインリアルタイムどう書く E13 の問題を C++ で

問題：http://nabetani.sakura.ne.jp/hena/orde13hextet/
実装リンク集：http://qiita.com/Nabetani/items/50cd05989b6e2812f879

ruby の実装( http://qiita.com/Nabetani/items/ac75de3f27db2fa7e0c4 )を C++ に移植した。

c++

// clang++ -std=c++11 -Wall
#include <complex>
#include <vector>
#include <set>
#include <exception>
#include <iostream>

#define EXTENDED_DETECTION 1

using namespace std;
typedef complex<int> xy_t;

xy_t xy(char ch)
{
  int const shifts[] = { 0,1,1,2,2 };
  char const lefts[] = "afjosx";
  for( int y=0 ; y<5 ; ++y ){
    if ( lefts[y]<=ch && ch<lefts[y+1] ){
      return xy_t(shifts[y] + ch -lefts[y], y);
    }
  }
  throw runtime_error( "unexpected!");
}

vector<xy_t> neibours(xy_t a){
  vector<xy_t> r;
  xy_t me=xy('l');
  for( char ch :string("gkpqmh") ){
    r.push_back( xy(ch) - me + a);
  }
  return r;
}

int rotate6( int bits, int rot ){
  return 0x3f & (((bits<<6)+bits)>>rot);
}

int normalize(vector<int> const & neibour_maps ){
  int r = 1<<6*4;
  for( int rot=0 ; rot<6 ; ++rot ){
    multiset<int> bits;
    for( auto const & nei : neibour_maps ){
      bits.insert(rotate6(nei,rot));
    }
    int sig=0;
    for( int b : bits ){
      sig = sig*(1<<6) + b;
    }
    r=min(r,sig);
  }
  return r;
}

std::string key_to_type( int key ){
  switch( key ){
  case 308016:  return "B";
  case 288297:  return "D";
  case 295497:  return "I";
#if defined EXTENDED_DETECTION
  case 279144:  return "J";
  case 280872:  return "L";
  case 271656:  return "N";
  case 845361:  return "O";
  case 295569:  return "S";
  case 279594:  return "Y";
  case 283176:  return "Z";
#endif
  default:  return "-";
  }
}

string solve( string const & src ){
  vector<xy_t> cells;
  for( char ch : src ){
    cells.push_back( xy(ch) );
  }
  vector<int> neibour_maps;
  for( xy_t me: cells ){
    vector<xy_t> neis = neibours(me);
    int bits=0;
    for( int n=0 ; n<6 ; ++n ){
      xy_t nei = neis.at(n);
      bits |= cells.end()==find( cells.begin(), cells.end(), nei )
          ? 0
          : (1<<n);
    }
    neibour_maps.push_back(bits);
  }
  return key_to_type( normalize( neibour_maps ) );
}

struct result_t{ int win, lose; int total() const {  return win+lose;}  };

void test_( result_t & r, char const * src, char const * expected )
{
  string actual = solve( src );
  bool okay = actual==expected;
  ( okay ? r.win : r.lose ) += 1;
  cout << ( okay ? "ok " : "**NG** " ) << src << "->" << actual << " / " << expected << endl;
}

int main()
{
  #define test(x,y) test_( result, x, y )
  result_t result = {0};
  /*0*/ test( "glmq", "B" );
  /*1*/ test( "fhoq", "-" );
  /*2*/ test( "lmpr", "N" );

  /*74*/ test( "flqr", "-" );
  cout  << result.win << " / " << result.total() << endl;
}

やっぱりわかりにくい計算だよなぁと思う。
マジカルだし。

行数にして、ruby の倍ぐらいの感じ。ruby の map 関数みたいなものがあって vectorを返してくれるんならだいぶ短くなるんだけど。

multiset が使えてちょっと嬉しい。