「プログラマ脳を鍛える数学パズル」を解いてみる上級編#5【アルゴリズム学習】

概要

翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題をC++で解きます。
この本ではRuby,JavaScript,Cでの解答はありますが、C++は載っていないため練習として解いてみようと思います。
記事、コード共にまだまだな部分も多いので、何かお気づきの点があれば、コメントお願いいたします。

入門編#1はコチラ
初級編#1はコチラ
中級編#1はコチラ
上級編#1はコチラ

ぜひ、いいねと思ったらスキお願いいたします！！！

問題1

Q64：迷路で待ち合わせ

解答2

ソースコード
注意：処理時間がかなりかかります

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long
#define N 5
#define S N*N

int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};

struct move_log{
   int x;
   int y;
   int pre;
   bool equals(move_log t){
       if(t.x==x && t.y==y && t.pre==pre){
           return true;
       }
       return false;
   }
};

//同じログがあるかどうか調べる
int check(std::vector<move_log> p1){
   move_log last=p1.back();
   int cnt=0;
   rep(i,p1.size()){
       if(p1[i].equals(last)){
           cnt++;
       }
   }
   return cnt;
}

//2人が合うかどうかを調べる
bool search(bitset<S> maze,std::vector<move_log> p1,int d1,std::vector<move_log> p2,int d2,int cnt){
   if(p1.size()==p2.size()){
       if(p1.back().x==p2.back().x && p1.back().y==p2.back().y){
           return true;
       }
       if(p1.back().x==N-1 && p1.back().y==N-1){
           return false;
       }
       if(p2.back().x==0 && p2.back().y==0){
           return false;
       }
   }
   
   if(check(p1)>1){
       return false;
   }
   
   move_log pre=p1.back();
   rep(i,4){
       if(d1==0){
           d1=4;
       }
       int d=(d1-1+i)%4;
       
       move_log tmp;
       tmp.x=pre.x+dir[d][0];
       tmp.y=pre.y+dir[d][1];
       tmp.pre=d;
       std::vector<move_log> next_p2=p1;

       if(tmp.x>=0 && tmp.x<N && tmp.y>=0 && tmp.y<N && (maze[tmp.x+N*tmp.y]==0)){
           next_p2.push_back(tmp);
           return search(maze,p2,d2,next_p2,d,cnt+1);
           break;
       }
   }
   return false;
}


int main(void){
   //初期化
   move_log a;
   a.x=0;
   a.y=0;
   a.pre=-1;
   move_log b;
   b.x=N-1;
   b.y=N-1;
   b.pre=-1;
   
   int cnt=0;
   std::vector<move_log> p1_move;
   std::vector<move_log> p2_move;
   p1_move.push_back(a);
   p2_move.push_back(b);
   int g=0;
   
   //迷路をbitsetで表現
   rep(i,pow(2,S)){
       bitset<S> map(i);
       if(!map[0] && !map[S-1]){
           g++;
         if(search(map,p1_move,3,p2_move,1,0)){
             cnt++;
         } 
       }
   }
   std::cout << "ans:"<<cnt << std::endl;
}

実行結果

問題2

Q65：面倒なキャッチボール

解答2

ソースコード
注意：処理時間がかなりかかります

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long
std::vector<int> start;
std::vector<int> goal;

int SIZE=10;

int DEPTH;


//条件に合う投げ方ができるかどうかを調べる
bool throwable(std::vector<int> balls,int pre,int depth){
   if(balls==goal){
       std::cout << "ans"<<depth << std::endl;
       return true;
   }
   if(depth>DEPTH){
       return false;
   }
   
   //受け手の位置を取得
   std::vector<int>::iterator iter=std::find(all(balls),0);
   int recipient=std::distance(balls.begin(),iter);
   
   //枝刈り
   if((recipient%(SIZE/2))+1>=DEPTH-depth ){
       return false;
   }
   
   //受け手の正面を計算
   int front=(recipient+(SIZE/2))%(SIZE);
   
   //受け手に投げる
   bool flag=false;
   repi(i,-1,2){
       if(i+front>=0 && i+front<SIZE && (front+i)/(SIZE/2)==front/(SIZE/2)){
           if(i+front!=pre){//枝刈り
               balls[recipient]=balls[i+front];
               balls[i+front]=0;
               if(throwable(balls,recipient,depth+1)){
                   flag=true;
                   return true;
               }
               balls[i+front]=balls[recipient];
               balls[recipient]=0;
           }
       }
   }
   return flag;
}

int main(void){
   //初期化
   repi(i,1,SIZE){
       start.push_back(i);
   }
   start.push_back(0);
   
   goal.push_back(0);
   repi(i,2,SIZE){
       goal.push_back(i);
   }
   goal.push_back(1);
   
   //反復深化で検索
   for (DEPTH = 1; ; DEPTH++) {
       if(throwable(start,-1,0))break;
   }
   
}

実行結果

今回の学び

・今回は両方とも，処理時間を縮めることができなかった．時間のある時に，修正して短縮していきたい．

・q64は，単純にマスを移動する方法で考えた．迷路が成り立っているかどうかの判定を入れることで，もう少し短縮させることができると思う．ビット演算の実装については，十分な理解ができなったので，実装をあきらめた．ビット演算のほうが圧倒的に早いと思うので，理解して実装し直したい．

・q65は，最後に紹介されていた「反復深化」を用いて実装を行った．枝刈りの方法として，”投げてきた人に投げ返さない”と”残り回数で条件を満たせない”を行った．もっと効果的な枝刈りの方法を見つけて，時間を短縮したい．

参考文献

「プログラマを鍛える数学パズル」著:増井敏克

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問