Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

DevQuiz 2011

今年もDevQuizに参加しました。スライドパズルはいい問題でした。去年よりも盛り上がっていたように思います。

スライドパズルの結果は 4969/5000 残り31問で時間切れ。壁の本当の難しさに気づくことが遅れてしまったのが敗因です。DevQuiz2011


以下,考えたこと等をメモしておきます。

  • 基本的な考え方は,盤面をノードとしたグラフの探索で良いはず。
  • ノード数は,6x6のボードで36! 不可能な盤面もあるので 36!/2 かも。どちらにしても広大な探索空間となることは間違いない。
  • いかに沢山の探索をこなせるかと,無駄な探索を排除できるかがカギになるはず。
  • とりあえず,参考文献をあたる。手元の「アルゴリズムクイックリファレンス」に,ずばりそのものスライドパズルが扱われている。
  • グラフの探索はA*で良さそうだ。
  • とりあえず,ヒューリスティック関数はマンハッタン距離(MD)で試してみる。h*=MD×2でサクサクと解ける(もちろん解けない問題も多くある)。
  • 他も調査。下記のサイトが参考になりそう。
        15パズル自動解答プログラムの作り方
  • 反復深化(IDDFS,IDA*)という考え方があるらしい。 前述の参考書にもキーワードはあった。
  • 反復深化は評価値の閾値を変えながら何度も探索を実行するものらしい。
    • (理解が浅いだけかもしれないが)反復の度に同じ探索をやり直すので非効率では?
    • 局面数が多いので,いかに探索数を減らす or 多種の探索を行うかが至上命題。
    • 直前反復での閾値の際の局面を保存しておいて,次の反復はそこから始めれば速いかも?
      => これって A* そのものと変わらない気が・・・
    • 反復深化は,BFS,A*ではキューに溜めている局面情報を毎回探索基点からの探索を繰り返すことでオンデマンドに求めているものと考えればよいらしい。
    • 探索空間が大きい場合にはあまり実用的ではないような気がするので,今回の問題への適用はパスする。
  • とはいっても,単純にA*を用いてはメモリが足りなくなるのは明らか。
  • A*において評価値が悪い局面は,後で評価される(プライオリティキューの上位に浮上する)可能性が低いように思う。
  • スライドパズルはどちらかといえばグリーディな感じで手順が決まりそうで,一旦極端に評価値の悪い局面を経由しての最短手順はあり得そうにない。
  • プライオリティキューに最大サイズを設け,溢れた局面(悪い局面)は捨て去ることとする。
  • 忘却型プライオリティキューは set (STL)で簡単に実装できる。(処理効率には目を瞑る)
  • MDでは,壁に囲まれる部位で不利な方にタイルを動かしても評価値が向上してしまう。
    => 各点間の最短パスを事前に計算しておいて,その距離を評価値として用いることとする。
  • 他に評価値はないか? => 実際にスライドパズルで遊ぶ。
  • 自分が置かれる行,列で他のコマと順序が入れ替わっているケースは余計に手数がかかる。例えば,「12435」のようなケース。
    => このときは評価値+2としよう。
  • ヒューリスティック関数が「h* < 実際の残り手数」であれば,最短性が保障される。しかしながら,可能性のある盤面を丁寧に探しに行ってしまうので,探索時間が多くかかる。逆に「h*>実際の残り手数」であれば,最短性を犠牲にして評価値の良い局面をグリーディ的に探しに行くので早く解を見つけられる。
    => 探索時間のかかる問題は評価関数の係数を増やして求めていくこととしよう。
  • ゴール状態から逆向きに探索した状態を列挙しておいて,それらをゴールとすると効率が良さそう。
  • ゴールまで16手程度であれば,メモリ上に局面状態を展開できる。
  • これで,4750問程度
  • 現状,局面の探索では1手前の局面へ戻ることだけを抑止している。解けてない問題は,どこかでループが発生しているのかもしれない。
    => 探索先の局面でプライオリティキューにある局面へは(再)訪問しないようにしてみる。
        (キューには2百万局面保存)
  • これで,4830問
  • 解けない問題をトレース出力。壁が通路となっている問題が解けていないようだ。
  • 通路の場合,そこに入るタイルを連ねて移動させなければならない。
  • 評価関数に,各タイルの相対距離を使ってみよう。隣合うタイルが近くにあるほど評価値がよくなる。
  • これで,4969問。ここで時間切れ。残り31問なのが悔しい。

提出版のソースは下記の通りです。


int LX,RX,UX,DX;
struct {
  int x,y,idx;
} goal_pos[37];

int BW, BH, BTILE, BCMP;
bool b6x6;

class Pattern{
public:
  unsigned char board[36];
  string dir;
};

class Record : public Pattern {
public:
  Record() : next(0) {}
  unsigned int prev_dir;
  unsigned int step;
  int distance;
  int eval;
  int eval_cache;
  unsigned char x0;
  unsigned char y0;
  Record* next;
};

/////
bool g_timeout;
void CALLBACK TimeProc(UINT,UINT,DWORD,DWORD,DWORD)
{
#ifndef _DEBUG
  g_timeout = true;
#endif
}

////////////////////////////////////////////////////////
//#define PQUE_NUM 1048576
#define PQUE_NUM 2097152
#define POOL_NUM 2520000

class Pool {
public:
  Pool() : m_pool(POOL_NUM) {}
  void initialize(){
    m_pFreeHead = NULL;
    m_pFreeTail = NULL;
    m_bInVec = true;
    m_pos = 0;
  }

  Record* borrowObj(){
    if( m_bInVec ){
      if( m_pos == POOL_NUM-1 ){
        m_bInVec = false;
      }
      memset( m_pool[m_pos].board, 0, 36*sizeof(unsigned char) );
      return &(m_pool[m_pos++]);

    }else{
      Record* r = m_pFreeHead;
      if( r == NULL ){
        printf( "pool is empty\n" );
        throw 1;
      }
      m_pFreeHead = r->next;
      return r;
    }
  }

  void returnObj(Record* obj){
    obj->next = NULL;
    if( m_pFreeTail == NULL ){
      m_pFreeHead = obj;
      m_pFreeTail = obj;
    }else{
      m_pFreeTail->next = obj;
      m_pFreeTail = obj;
    }
  }

private:
  Record *m_pFreeHead, *m_pFreeTail;
  bool m_bInVec;
  int m_pos;
  vector<Record> m_pool;
};

Pool pool;

unsigned char goal_board[36];
unsigned char neighbor[37][4]; // [][4] R D L U

void goal_position(unsigned char* board)
{
  int i = 1;
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      goal_pos[i].x = x;
      goal_pos[i].y = y;
      goal_pos[i].idx = i-1;
      i++;
    }
  }
  goal_pos[0].x = -1;
  goal_pos[0].y = -1;
  goal_pos[0].idx = -1;
  goal_pos[36].x = -1;
  goal_pos[36].y = -1;
  goal_pos[36].idx = -1;

  memset( goal_board, 0, sizeof(goal_board) );
  for( int i = 0; i < BTILE-1; i++ ){
    if( board[i] == 36 ){
      goal_board[i] = 36;
    }else{
      goal_board[i] = i+1;
    }
  }

  memset( neighbor, 255, sizeof(neighbor) );
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      unsigned char v = goal_board[y*BW+x];
      if( v != 0 && v != 36 ){
        //right
        if( x < BW-1 && goal_board[y*BW+x+1] != 36 && goal_board[y*BW+x+1] != 0 ){
          neighbor[v][0] = goal_board[y*BW+x+1];
        }
        //down
        if( y < BH-1 && goal_board[(y+1)*BW+x] != 36 && goal_board[(y+1)*BW+x] != 0 ){
          neighbor[v][1] = goal_board[(y+1)*BW+x];
        }
        //left
        if( x > 0 && goal_board[y*BW+x-1] != 36 && goal_board[y*BW+x-1] != 0 ){
          neighbor[v][2] = goal_board[y*BW+x-1];
        }
        //up
        if( y > 0 && goal_board[(y-1)*BW+x] != 36 && goal_board[(y-1)*BW+x] != 0 ){
          neighbor[v][3] = goal_board[(y-1)*BW+x];
        }
      }
    }
  }
}

int board_dist[36][36]; // src to dst
void calc_distance( unsigned char* board )
{
  unsigned int base[36], work[36];
  unsigned char* pBoard = board;
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      if( *pBoard == 36 )
        base[x+y*BW] = INT_MAX;
      else
        base[x+y*BW] = -1;
      pBoard++;
    }
  }

  for( int src = 0; src < BW*BH; src++ ){
    memcpy( work, base, sizeof(work) );
    queue<int> que;
    que.push(src);
    work[src] = 0;

    while( !que.empty() ){
      int idx = que.front();
      que.pop();
      board_dist[src][idx] = work[idx];

      int x = idx%BW;
      if( x > 0 ){
        if( work[idx-1] == -1 ){
          work[idx-1] = work[idx]+1;
          que.push(idx-1);
        }
      }
      if( x < BW-1 ){
        if( work[idx+1] == -1 ){
          work[idx+1] = work[idx]+1;
          que.push(idx+1);
        }
      }
      if( idx-BW >= 0 ){
        if( work[idx-BW] == -1 ){
          work[idx-BW] = work[idx]+1;
          que.push(idx-BW);
        }
      }
      if( idx+BW < BTILE ){
        if( work[idx+BW] == -1 ){
          work[idx+BW] = work[idx]+1;
          que.push(idx+BW);
        }
      }
    }
  }
}

///////
class lessPattern{
public:
  bool operator()( const Pattern* lhs, const Pattern* rhs ) const
  {
    const __m128i* plboard = (const __m128i*)lhs->board;
    const __m128i* prboard = (const __m128i*)rhs->board;

    for( int i = 0; i <= BCMP; i++ ){
      __m128i lval = _mm_lddqu_si128(plboard);
      __m128i rval = _mm_lddqu_si128(prboard);
      __m128i less = _mm_sub_epi32( lval, rval );
      __m128i equl = _mm_cmpeq_epi32( lval, rval );
      int less_sign = _mm_movemask_epi8(less);
      int equl_sign = _mm_movemask_epi8(equl);
      if((equl_sign & 0x8000) == 0){ // !=
        return (less_sign&0x8000) != 0;
      }
      if((equl_sign & 0x0800) == 0){
        return (less_sign&0x0800) != 0;
      }
      if((equl_sign & 0x0080) == 0){
        return (less_sign&0x0080) != 0;
      }
      if((equl_sign & 0x0008) == 0){
        return (less_sign&0x0008) != 0;
      }
      plboard++;
      prboard++;
    }
    if( b6x6 ){
      int* pl = (int*)plboard;
      int* pr = (int*)prboard;
      return (*pl < *pr);
    }

    return false;
  }
};
class lessRecord2{
public:
  bool operator()( const Record* lhs, const Record* rhs ) const
  {
    const __m128i* plboard = (const __m128i*)lhs->board;
    const __m128i* prboard = (const __m128i*)rhs->board;

    for( int i = 0; i <= BCMP; i++ ){
      __m128i lval = _mm_lddqu_si128(plboard);
      __m128i rval = _mm_lddqu_si128(prboard);
      __m128i less = _mm_sub_epi32( lval, rval );
      __m128i equl = _mm_cmpeq_epi32( lval, rval );
      int less_sign = _mm_movemask_epi8(less);
      int equl_sign = _mm_movemask_epi8(equl);
      if((equl_sign & 0x8000) == 0){ // !=
        return (less_sign&0x8000) != 0;
      }
      if((equl_sign & 0x0800) == 0){
        return (less_sign&0x0800) != 0;
      }
      if((equl_sign & 0x0080) == 0){
        return (less_sign&0x0080) != 0;
      }
      if((equl_sign & 0x0008) == 0){
        return (less_sign&0x0008) != 0;
      }
      plboard++;
      prboard++;
    }
    if( b6x6 ){
      int* pl = (int*)plboard;
      int* pr = (int*)prboard;
      return (*pl < *pr);
    }

    return false;
  }
};


vector<Pattern> pattern_pool(PQUE_NUM); // 16step
set<Pattern*, lessPattern> pattern_set;
void copyBoard(unsigned char* dst, unsigned char* src);
int change_eval_up( Record* m, Record* n, unsigned val);
int change_eval_left( Record* m, Record* n, unsigned val);
int change_eval_down( Record* m, Record* n, unsigned val);
int change_eval_right( Record* m, Record* n, unsigned val);
void evaluation( Record* pRec );
int min_distance;
int max_distance;

void make_pattern()
{
  pool.initialize();
  int pattern_pool_pos = 0;

  queue<Record*> open;
  Record* initial = pool.borrowObj();
  memcpy( initial->board, goal_board, BTILE );
  evaluation(initial);
  initial->step = 0;
  initial->prev_dir = -1;
  unsigned char* pb = initial->board;
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      if( *pb == 0 ){
        initial->x0 = x;
        initial->y0 = y;
        goto out;
      }
      pb++;
    }
  }
out:
  initial->dir.clear();
  open.push(initial);
  min_distance = INT_MAX;
  max_distance = 0;
  set<Record*, lessRecord2> close;

  while( !open.empty() ){
    Record* m = open.front();
    open.pop();
    set<Record*, lessRecord2>::iterator it2 = close.find(m);
    if( it2 != close.end() ){
      pool.returnObj(m);
      continue;
    }

    if( m->step == 16 ){  // 16 step
      Pattern* p = &(pattern_pool[pattern_pool_pos]);
      copyBoard(p->board, m->board);
      p->dir.assign(m->dir.rbegin(), m->dir.rend());
      pool.returnObj(m);
      pair<set<Pattern*, lessPattern>::iterator, bool> ret = pattern_set.insert(p);
      if( ret.second ){
        pattern_pool_pos++;
        if( pattern_pool_pos > PQUE_NUM ){
          printf("pattern pool empty\n");
          throw 2;
        }
        if( m->distance < min_distance )
          min_distance = m->distance;
        if( max_distance < m->distance )
          max_distance = m->distance;
      }
      continue;
    }

    close.insert(m);

    //// next
    unsigned char x0 = m->x0;
    unsigned char y0 = m->y0;
    unsigned char* min_cur_pos = m->board+x0+y0*BW;
    //down
    if( (m->prev_dir!=0) && (y0 < BH-1) && *(min_cur_pos+BW) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos+BW);
      *(cur_pos+BW) = 0;

      n->step = m->step+1;
      n->x0 = x0;
      n->y0 = y0+1;
      change_eval_up(m, n, *cur_pos);
      n->prev_dir = 1;
      n->dir = m->dir + "U";
      open.push(n);
    }
    //right
    if( (m->prev_dir!=2) && (x0 < BW-1) && *(min_cur_pos+1) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos+1);
      *(cur_pos+1) = 0;

      n->step = m->step+1;
      n->x0 = x0+1;
      n->y0 = y0;
      change_eval_left(m, n, *cur_pos);
      n->prev_dir = 3;
      n->dir = m->dir + "L";
      open.push(n);
    }
    //up
    if( (m->prev_dir!=1) && (y0 > 0) && *(min_cur_pos-BW) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos-BW);
      *(cur_pos-BW) = 0;

      n->step = m->step+1;
      n->x0 = x0;
      n->y0 = y0-1;
      change_eval_down(m, n, *cur_pos);
      n->prev_dir = 0;
      n->dir = m->dir + "D";
      open.push(n);
    }
    //left
    if( (m->prev_dir!=3) && (x0 > 0) && *(min_cur_pos-1) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos-1);
      *(cur_pos-1) = 0;

      n->step = m->step+1;
      n->x0 = x0-1;
      n->y0 = y0;
      change_eval_right(m, n, *cur_pos);
      n->prev_dir = 2;
      n->dir = m->dir + "R";
      open.push(n);
    }
  }
}

////////////////////////////////////////////////////////
/////
bool checkGoal( unsigned char* board )
{
  const __m128i* plboard = (const __m128i*)board;
  const __m128i* prboard = (const __m128i*)goal_board;

  for( int i = 0; i <= BCMP; i++ ){
    __m128i lval = _mm_lddqu_si128(plboard);
    __m128i rval = _mm_lddqu_si128(prboard);
    __m128i equl = _mm_cmpeq_epi32( lval, rval );
    int equl_sign = _mm_movemask_epi8(equl);
    if( equl_sign != 0xffff ){
      return false;
    }
    plboard++;
    prboard++;
  }
  if( b6x6 ){
    unsigned int* pl = (unsigned int*)plboard;
    unsigned int* pr = (unsigned int*)prboard;
    if( *pl != *pr )
      return false;
  }
  return true;
}

void copyBoard(unsigned char* dst, unsigned char* src)
{
  __m128i* pdst    = (__m128i*)dst;
  const __m128i* psrc = (const __m128i*)src;

  for( int i = 0; i <= BCMP; i++ ){
    __m128i val = _mm_lddqu_si128(psrc);
    _mm_storeu_si128(pdst, val);
    pdst++;
    psrc++;
  }
  if( b6x6 ){
    int* pd = (int*)pdst;
    int* ps = (int*)psrc;
    *pd    = *ps;
  }
}

////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
int eval_scale = 2;
int eval_scale_org = 2;

int change_eval_up( Record* m, Record* n, unsigned val)
{
  assert(val!=0);
  unsigned char* prev_board = m->board;
  unsigned char* next_board = n->board;
  int px = n->x0;
  int py = n->y0;
  int nx = m->x0;
  int ny = m->y0;

  // distance
  int pidx = px+py*BW;
  int nidx = nx+ny*BW;
  int diff = board_dist[nidx][goal_pos[val].idx] - board_dist[pidx][goal_pos[val].idx];
  n->distance = m->distance + diff;

  // absolute position
  int d = 0;
  int idx = 0;
  // [note] (nx,ny) new tile position
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      unsigned char v = *(next_board+idx);
      if( v == neighbor[val][0] ){      // left
        if( ny < y )
          d++;
        else
          d--;
      }else if( v == neighbor[val][1] ){  // down
        if( (ny+1) < y )
          d++;
        else
          d--;
      }else if( v == neighbor[val][2] ){  // right
        if( ny < y )
          d++;
        else
          d--;
      }else if( v == neighbor[val][3] ){  // up
        if( (ny-1) < y )
          d++;
        else
          d--;
      }
      idx++;
    }
  }

  return (d*eval_scale);
}

int change_eval_down( Record* m, Record* n, unsigned val)
{
  assert(val!=0);
  unsigned char* prev_board = m->board;
  unsigned char* next_board = n->board;
  int px = n->x0;
  int py = n->y0;
  int nx = m->x0;
  int ny = m->y0;

  // distance
  int pidx = px+py*BW;
  int nidx = nx+ny*BW;
  int diff = board_dist[nidx][goal_pos[val].idx] - board_dist[pidx][goal_pos[val].idx];
  n->distance = m->distance + diff;

  // absolut position
  int d = 0;
  int idx = 0;
  // [note] (nx,ny) new tile position
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      unsigned char v = *(next_board+idx);
      if( v == neighbor[val][0] ){      // left
        if( ny > y )
          d++;
        else
          d--;
      }else if( v == neighbor[val][1] ){  // down
        if( (ny+1) > y )
          d++;
        else
          d--;
      }else if( v == neighbor[val][2] ){  // right
        if( ny > y )
          d++;
        else
          d--;
      }else if( v == neighbor[val][3] ){  // up
        if( (ny-1) > y )
          d++;
        else
          d--;
      }
      idx++;
    }
  }

  return (d*eval_scale);
}

int change_eval_left( Record* m, Record* n, unsigned val)
{
  assert(val!=0);
  unsigned char* prev_board = m->board;
  unsigned char* next_board = n->board;
  int px = n->x0;
  int py = n->y0;
  int nx = m->x0;
  int ny = m->y0;

  // distance
  int pidx = px+py*BW;
  int nidx = nx+ny*BW;
  int diff = board_dist[nidx][goal_pos[val].idx] - board_dist[pidx][goal_pos[val].idx];
  n->distance = m->distance + diff;

  // absolut position
  int d = 0;
  int idx = 0;
  // [note] (nx,ny) new tile position
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      unsigned char v = *(next_board+idx);
      if( v == neighbor[val][0] ){      // left
        if( (nx+1) < x )
          d++;
        else
          d--;
      }else if( v == neighbor[val][1] ){  // down
        if( nx < x )
          d++;
        else
          d--;
      }else if( v == neighbor[val][2] ){  // right
        if( (nx-1) < x )
          d++;
        else
          d--;
      }else if( v == neighbor[val][3] ){  // up
        if( nx < x )
          d++;
        else
          d--;
      }
      idx++;
    }
  }

  return (d*eval_scale);
}

int change_eval_right( Record* m, Record* n, unsigned val)
{
  assert(val!=0);
  unsigned char* prev_board = m->board;
  unsigned char* next_board = n->board;
  int px = n->x0;
  int py = n->y0;
  int nx = m->x0;
  int ny = m->y0;

  // distance
  int pidx = px+py*BW;
  int nidx = nx+ny*BW;
  int diff = board_dist[nidx][goal_pos[val].idx] - board_dist[pidx][goal_pos[val].idx];
  n->distance = m->distance + diff;

  // absolut position
  int d = 0;
  int idx = 0;
  // [note] (nx,ny) new tile position
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      unsigned char v = *(next_board+idx);
      if( v == neighbor[val][0] ){      // left
        if( (nx+1) > x )
          d++;
        else
          d--;
      }else if( v == neighbor[val][1] ){  // down
        if( nx > x )
          d++;
        else
          d--;
      }else if( v == neighbor[val][2] ){  // right
        if( (nx-1) > x )
          d++;
        else
          d--;
      }else if( v == neighbor[val][3] ){  // up
        if( nx > x )
          d++;
        else
          d--;
      }
      idx++;
    }
  }

  return (d*eval_scale);
}

//int evaluation( unsigned char* board )
void evaluation( Record* pRec )
{
  unsigned char* board = pRec->board;
  int eval = 0;
  // distance
  for( int idx = 0; idx < BTILE; idx++ ){
    if( *(board+idx) == 0 || *(board+idx) == 36 )
      continue;
    eval += board_dist[idx][goal_pos[*(board+idx)].idx];
  }
  pRec->distance = eval;

  // absolute position
  int diff = 0;
  struct {
    int x;
    int y;
  }pos[37];
  memset(pos, 0xff, sizeof(pos));
  for( int idx = 0; idx < BTILE; idx++ ){
    unsigned char val = *(board+idx);
    if( val != 36 ){
      pos[val].x = idx % BW;
      pos[val].y = idx / BW;
    }
  }
  for( int tile = 1; tile < BTILE; tile++ ){
    if( pos[tile].x != -1 ){
      if( neighbor[tile][0] != 255 ){
        diff += abs(pos[tile].x+1 - pos[neighbor[tile][0]].x);
        diff += abs(pos[tile].y - pos[neighbor[tile][0]].y);
      }
      if( neighbor[tile][1] != 255 ){
        diff += abs(pos[tile].x - pos[neighbor[tile][1]].x);
        diff += abs(pos[tile].y+1 - pos[neighbor[tile][1]].y);
      }
    }
  }

  pRec->eval = (diff*eval_scale);
}
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////

class lessRecord{
public:
  bool operator()( const Record* lhs, const Record* rhs ) const
  {
    // check same board
    const __m128i* plboard = (const __m128i*)lhs->board;
    const __m128i* prboard = (const __m128i*)rhs->board;

    for( int i = 0; i <= BCMP; i++ ){
      __m128i lval = _mm_lddqu_si128(plboard);
      __m128i rval = _mm_lddqu_si128(prboard);
      __m128i equl = _mm_cmpeq_epi32( lval, rval );
      int equl_sign = _mm_movemask_epi8(equl);
      if( equl_sign != 0xffff ){
        goto check_next;
      }
      plboard++;
      prboard++;
    }
    if( b6x6 ){
      unsigned int* pl = (unsigned int*)plboard;
      unsigned int* pr = (unsigned int*)prboard;
      if( *pl != *pr )
        goto check_next;
    }
    return false; // same

check_next:
    if( (lhs->eval_cache) != (rhs->eval_cache) ){
      return ((lhs->eval_cache) < (rhs->eval_cache));
    }else{
      return lessRecord2()(lhs, rhs);
    }
  }
};

/////
string rough_path;
bool bFine;
int FineTH;

int min_eval, min_dist;
unsigned char min_board[36];

string solver( unsigned char* board )
{
  goal_position(board);
  calc_distance(board);
  make_pattern();
printf("[min=%d][max=%d]", min_distance, max_distance);

bool bRetry;
do{
  bRetry = false;
  pool.initialize();

  set<Record*, lessRecord> open;
  set<Record*, lessRecord>::iterator it1, it2;
  pair<set<Record*, lessRecord>::iterator, bool> ret_ins;

  Record* initial = pool.borrowObj();
  memcpy( initial->board, board, BTILE );
  evaluation(initial);
printf("[%d]",initial->eval);
  initial->step = 0;
  initial->eval_cache = initial->eval;
  initial->prev_dir = -1;
  unsigned char* pb = board;
  for( int y = 0; y < BH; y++ ){
    for( int x = 0; x < BW; x++ ){
      if( *pb == 0 ){
        initial->x0 = x;
        initial->y0 = y;
        goto out;
      }
      pb++;
    }
  }
out:
  initial->dir.clear();
  open.insert(initial);

  while( !open.empty() ){
    Record* m = *(open.begin());
    open.erase(open.begin());
    if( checkGoal( m->board ) ){
      return m->dir;
    }

#if 0
    // change to Fine Search
    if( bFine == false && m->eval <= FineTH ){
printf("F:");
      bFine = true;
      eval_scale = 1;
      copyBoard(board, m->board);
      rough_path = m->dir;
      bRetry = true;
      break;
    }
    if( bFine ){
      set<Pattern*, lessPattern>::iterator it = pattern_set.find(m);
      if( it != pattern_set.end() ){
        return m->dir + (*it)->dir;
      }
    }
#endif
    //if( m->distance < min_distance ){
    //  pool.returnObj(m);
    //  continue;
    //}
    if( m->distance <= max_distance && m->distance >= min_distance ){
      set<Pattern*, lessPattern>::iterator it = pattern_set.find(m);
      if( it != pattern_set.end() ){
        printf("[%d]", m->eval);
        return m->dir + (*it)->dir;
      }
    }
    if( min_eval > m->eval_cache ){ //  for debug
      min_eval = m->eval_cache;
      min_dist = m->distance;
      copyBoard( min_board, m->board );
    }

    //// next
    unsigned char x0 = m->x0;
    unsigned char y0 = m->y0;
    unsigned char* min_cur_pos = m->board+x0+y0*BW;
    //1 DRUL
    //2 ULRD
    //up
    if( (m->prev_dir!=1) && (y0 > 0) && *(min_cur_pos-BW) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos-BW);
      *(cur_pos-BW) = 0;

      n->step = m->step+1;
      n->x0 = x0;
      n->y0 = y0-1;
      n->eval = m->eval + change_eval_down(m, n, *cur_pos);
      n->eval_cache = n->eval + n->step;
      n->prev_dir = 0;
      n->dir = m->dir + "U";

      ret_ins = open.insert(n);
      if(ret_ins.second == false)
        pool.returnObj(n);
    }
    //left
    if( (m->prev_dir!=3) && (x0 > 0) && *(min_cur_pos-1) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos-1);
      *(cur_pos-1) = 0;

      n->step = m->step+1;
      n->x0 = x0-1;
      n->y0 = y0;
      n->eval = m->eval + change_eval_right(m, n, *cur_pos);
      n->eval_cache = n->eval + n->step;
      n->prev_dir = 2;
      n->dir = m->dir + "L";

      ret_ins = open.insert(n);
      if(ret_ins.second == false)
        pool.returnObj(n);
    }
    //right
    if( (m->prev_dir!=2) && (x0 < BW-1) && *(min_cur_pos+1) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos+1);
      *(cur_pos+1) = 0;

      n->step = m->step+1;
      n->x0 = x0+1;
      n->y0 = y0;
      n->eval = m->eval + change_eval_left(m, n, *cur_pos);
      n->eval_cache = n->eval + n->step;
      n->prev_dir = 3;
      n->dir = m->dir + "R";

      ret_ins = open.insert(n);
      if(ret_ins.second == false)
        pool.returnObj(n);
    }
    //down
    if( (m->prev_dir!=0) && (y0 < BH-1) && *(min_cur_pos+BW) != 36 ){
      Record* n = pool.borrowObj();
      copyBoard(n->board, m->board);
      unsigned char* cur_pos = n->board+x0+y0*BW;
      *cur_pos = *(cur_pos+BW);
      *(cur_pos+BW) = 0;

      n->step = m->step+1;
      n->x0 = x0;
      n->y0 = y0+1;
      n->eval = m->eval + change_eval_up(m, n, *cur_pos);
      n->eval_cache = n->eval + n->step;
      n->prev_dir = 1;
      n->dir = m->dir + "D";

      ret_ins = open.insert(n);
      if(ret_ins.second == false)
        pool.returnObj(n);
    }

    ///
    pool.returnObj(m);
    if( open.size() >= PQUE_NUM ){
      it1 = open.begin();
      advance( it1, (PQUE_NUM-4096) );
      for( it2 = it1; it2 != open.end(); it2++ ){
        pool.returnObj((*it2));
      }
      open.erase(it1, open.end());
    }

    // check timeout
    if( g_timeout )
      throw -1;
  }
}while(bRetry);

  return " ";
}

/////
void main(int argc, char*argv[]) // usage: main.exe in.txt out.txt start# end# timeout(sec) eval_scale th_step
{
  unsigned int i;

  ifstream fin(argv[1]);
  if( fin == NULL ){
    OUTPUTLOG2("cannot open in-file : %s\n", argv[1]);
    return;
  }
  FILE* fout = fopen(argv[2],"w");
  if( fin == NULL ){
    OUTPUTLOG2("cannot open out-file : %s\n", argv[2]);
    return;
  }

  int start_case = 0;
  if( argc >= 4 ){
    start_case = atoi(argv[3]);
  }
  int end_case = 5000;
  if( argc >= 5 ){
    end_case = atoi(argv[4]);
  }
  int timeout_msec = 120000;
  if( argc >= 6 ){
    timeout_msec = atoi(argv[5]);
    timeout_msec *= 1000;
  }
  if( argc >= 7 ){
    eval_scale_org = atoi(argv[6]);
  }
  int th_step = 8;
  if( argc >= 8 ){
    th_step = atoi(argv[7]);
  }

  printf( "start#=%d, end#=%d, timeout=%d, eval_scale=%d, th_step=%d\n", start_case, end_case, timeout_msec, eval_scale_org, th_step );

/////////////////////////////
#if 0
  fin >> LX;
  fin >> RX;
  fin >> UX;
  fin >> DX;
#endif
  int CASE;
  fin >> CASE;
  for( int test_case = 1; test_case <= CASE; test_case++ ){
  /////////////////////////////
    char c;
    string board;
    int case_num;
    fin >> case_num;
    fin >> c;
    fin >> BW;
    fin >> c;
    fin >> BH;
    fin >> c;
    fin >> board;
    BTILE = BW*BH;
    printf("%d(%d,%d) : ", test_case, BW, BH);
    if( test_case < start_case || end_case < test_case ){
      fprintf(fout,"%d,N/A\n",case_num);
      printf("N/A\n");
      continue;
    }
    BCMP = (BTILE-1) >> 4;
    if( BCMP >= 2 ){
      BCMP = 1;
      b6x6 = true;
    }else{
      b6x6 = false;
    }

    unsigned char board_val[6*6];  // [0 - 36]   36:'='
    memset(board_val, 0, sizeof(board_val));
    REP(i,board.size()){
      if( board[i] == '=' ){
        board_val[i] = 36;
      }else if( board[i] <= '9' ){
        board_val[i] = board[i] - '0';
      }else{
        board_val[i] = board[i] - 'A' + 10;
      }
    }

    rough_path.clear();
    bFine = false;
    FineTH = th_step * eval_scale_org;
    eval_scale = eval_scale_org;
    min_eval = INT_MAX;
    min_dist = INT_MAX;

    g_timeout = false;
    MMRESULT id = timeSetEvent( timeout_msec, 1000, TimeProc, 0, TIME_ONESHOT );
    try{
      string r = solver( board_val );
      fprintf(fout,"%d,%s%s\n", case_num, rough_path.c_str(), r.c_str());
      fflush(fout);
      printf("%s%s\n", rough_path.c_str(), r.c_str());
    }catch(int e){
      fprintf(fout,"%d,N/A\n",case_num);
      if(e != -1)
        printf("[ERR]\n");
      printf("N/A, min_eval=%d, min_dist=%d\n", min_eval, min_dist);
      int i = 0;
      for( int y = 0; y < BH; y++ ){
        for( int x = 0; x < BW; x++ ){
          if( min_board[i] <10 )
            printf("%c", min_board[i]+'0');
          else if( min_board[i] == 36 )
            printf("=");
          else
            printf("%c", min_board[i]+'A'-10);
          i++;
        }
        printf("\n");
      }
    }catch(...){
      fprintf(fout,"%d,N/A\n",case_num);
      printf("[ERR2]N/A\n");
    }
    timeKillEvent(id);

    if( fin.eof() ){
      if( test_case != CASE ){
        OUTPUTLOG( "in-file error:eof" );
      }
      break;
    }
  }

  OUTPUTLOG( "program end" );
}

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/70-09ce013f
この記事にトラックバックする(FC2ブログユーザー)

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。