「プログラマ脳を鍛える数学パズル」を解いてみる上級編#6【アルゴリズム学習】
概要
翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題をC++で解きます。
この本ではRuby,JavaScript,Cでの解答はありますが、C++は載っていないため練習として解いてみようと思います。
記事、コード共にまだまだな部分も多いので、何かお気づきの点があれば、コメントお願いいたします。
入門編#1はコチラ
初級編#1はコチラ
中級編#1はコチラ
上級編#1はコチラ
ぜひ、いいねと思ったらスキお願いいたします！！！
問題1
Q66：図形の一筆書き
解答1
ソースコード
#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 W 4
#define H 3
#define S (W+1)*(H+1)
int panel[4][4]={{0,0,0,0},{1,0,0,1},{0,1,1,0},{1,1,1,1}};
//y行の次数を数え、一番下まで検索する
//figure：作成するパネルの次数が奇数かどうか（奇数の場合は１）
//y：現在探索中の行
//odds：奇数の次数の数
int search(bitset<S> figure,int y,int odds){
//奇数の次数が2より大きくなったときに中止
if(odds>2){
return 0;
}
if(y==H){
//一番下の行の次数を数える
rep(p,W+1){
if(figure[p+(W+1)*y]){
odds++;
}
}
if(odds==0 || odds==2){
return 1;
}else{
return 0;
}
}
int cnt=0;
int size=0;
//4つの箇所に入りうるパネルパターンを全て考える
rep(i,4){
rep(j,4){
rep(k,4){
rep(l,4){
size++;
int next_odds=odds;
bitset<S> next_figure=figure;
std::vector<int> jisu(5,0);
//上の行の次数を数える
jisu[0]=panel[i][0];
jisu[1]=panel[i][1]+panel[j][0];
jisu[2]=panel[j][1]+panel[k][0];
jisu[3]=panel[k][1]+panel[l][0];
jisu[4]=panel[l][1];
rep(p,W+1){
if(jisu[p]%2==1){
next_figure.flip(p+(W+1)*y);
}
if(next_figure[p+(W+1)*y]){
next_odds++;
}
}
//下の行を更新する
jisu[0]=panel[i][2];
jisu[1]=panel[i][3]+panel[j][2];
jisu[2]=panel[j][3]+panel[k][2];
jisu[3]=panel[k][3]+panel[l][2];
jisu[4]=panel[l][3];
rep(p,W+1){
if(jisu[p]%2==1){
next_figure.flip(p+(W+1)*(y+1));
}
}
cnt+=search(next_figure,y+1,next_odds);
}
}
}
}
return cnt;
}
int main(void){
bitset<S> figure("01110100011000101110");
std::cout << search(figure,0,0) << std::endl;
}
実行結果
問題2
Q67：クロスワードパズルを作成せよ！
解答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 W 6
#define H 5
std::vector<std::vector<int>> pazzle;
//チェック用に白のマスの数字を置き換える
void fill(int x,int y,int from,int to){
if(x>=0 && x<W+2 && y>=0 && y<H+2 && pazzle[y][x]==from){
pazzle[y][x]=to;
fill(x-1,y,from,to);
fill(x+1,y,from,to);
fill(x,y-1,from,to);
fill(x,y+1,from,to);
}
}
//pazzule中になるnumの数を数える
int countNum(int num){
int cnt=0;
repi(i,1,H+2){
repi(j,1,W+2){
if(pazzle[i][j]==num){
cnt++;
}
}
}
return cnt;
}
//分断されていないかを調べる
bool check(){
int x=1;
int y=1;
if(pazzle[y][x]==1){
x+=1;
}
//つながっている白マスを全て他の数字に置き換え、その時に白マスが残っていなければ条件を満たしていると考える
fill(x,y,0,2);
int result=countNum(0);
fill(x,y,2,0);
if(result==0){
return true;
}else{
return false;
}
}
//パズルを左上から1マスずつ作っていく。最後まで作れると1通りとする
//x,yの位置を白か黒に置き換える
int search(int x,int y){
if(x==W+1){
x=1;
y=y+1;
}
if(y==H+1){
return 1;
}
//何もせずに次を探索
int cnt=search(x+1,y);
//黒のマスに変化させて探索
if(pazzle[y][x-1]!=1 && pazzle[y-1][x]!=1){
pazzle[y][x]=1;
if(check()){
cnt+=search(x+1,y);
}
pazzle[y][x]=0;
}
return cnt;
}
int main(void){
//初期化
std::vector<int> t(W+2);
rep(i,H+2){
pazzle.push_back(t);
}
rep(i,H+2){
rep(j,W+2){
if(i==0 || i==H+1 || j==0 || j==W+1){
pazzle[i][j]=-1;
}else{
pazzle[i][j]=0;
}
}
}
std::cout << search(1,1) << std::endl;
}
実行結果
今回の学び・感想
・q66はシンプルに上から次数を数える方法で実装を行った。４つあるパネルの表現として、各頂点の数で配列を作成し、それを用いて計算した。分かりやすく実装できたが、早さやコードのシンプルさを優先するなら本に載っているビット演算を用いて行う方が良かった
・q67について、「rubyでは6秒ほど時間がかかりますが、CやC++といった言語であれば、上記の方法でも1秒未満で処理できます」と書かれているように、短い処理時間で実行できた。ただし、サイズが大きくなると対応できなくなるので(具体的には7＊7を超えたあたりで2秒を超えた)、q66と同様にビット演算を用いた実装する必要がある。
・今回取り組んだ2問は上級編の他の問題に比べ、簡単だったと思う。
参考文献
「プログラマを鍛える数学パズル」著:増井敏克