(2007.1.19)がーん，思い切り問題を勘違いしていた。「どのマスも一度だけ通って，通り抜ける」のがポイントで，それで星２つ問題だったんだ。
16個の部屋がある。
入り口から直進し外壁に当たる毎に適当な方向に向きを変えて直進し全ての部屋を訪れ出口から出るには最低何回外壁で跳ね返れば良いか？
(2007.1.19)以下に問題文を全て転記する。「一度だけ」がポイント。
----- ここから -----
イノシシ年なので，「猪突猛進」の問題です。
市松模様にカーペットがはられた広い部屋を，イノシシがどのマスも一度だけ通って，通り抜けます。常に直進し，壁にぶつかると適当に向きを変えます。
例えば図左のような３ｘ３＝９のマスの部屋は，2回壁にぶつかるだけで抜けられます。
さて，図右のような４ｘ４＝１６マスの部屋を通り抜けるには最低何回壁にぶつかる必要があるでしょうか。回数と道筋を答えてください。
----- ここまで -----
(2007.1.19)以下私の勘違いで全て間違い。本日新聞によると応募数179通，正解率11%だって。私と同じミスをした人が沢山いたと思われる。
単純に考えても以下のように4回の跳ね返りで通り抜けることが出来る。
と言うことはこれより少ない3回で通り抜ける方法があるってこと(じゃなきゃ問題にならない)。
回数を限定しないとプログラムを作成することが困難なので3回で通り抜けることを前提にする。
入り口と出口は限定されているけど跳ね返りの3点は外壁上のどこにあるか判らない。
入り口(開始点)をS，出口(終了点)をE，途中の3点をA,B,Cとすると以下のような軌跡が考えられる。
この例では3回の跳ね返りで出口に到達しているが，右上の部屋を訪れていないので正解にはならない。
S,A,B,C,Eの位置は壁の上を連続的に変化するのでプログラムは難しそうであるが，各矩形の1辺をN分割して，離散的な位置で調べることにする。
小矩形の1辺をN分割すると，外壁上の点は全部で 4*4*N 個あることになる。
単純に考えると以下のようにプログラムできる。
外壁上の4*4*N個の点を Q[ ] に求めておく。
for( a=0; a< 4*4*N; a++) {
A = Q[a];
for( b=0; b< 4*4*N; b++) {
B = Q[b];
for( c=0; c< 4*4*N; c++) {
C = Q[c];
SA, AB, BC, CE の4つの直線と16個の矩形の交わりを探す。全ての矩形と交差すればA,B,Cが答えになる。
}
}
}
S,Eも1点でなく入口，出口の線上を移動できるのでN点を考慮しなければならない。これもループにしてどこかに入れなければならない。
外に入れるか中に入れるか悩んだがプログラムが単純になるので中に入れることにした。
外壁上の4*4*N個の点を Q[ ] に求めておく。
for( a=0; a< 4*4*N; a++) {
A = Q[a];
for( b=0; b< 4*4*N; b++) {
B = Q[b];
for( c=0; c< 4*4*N; c++) {
C = Q[c];
for( Sの候補値) {
for( Eの候補値) {
SA, AB, BC, CE の4つの直線と16個の矩形の交わりを探す。全ての矩形と交差すればS,A,B,C,Eが答えになる。
}
}
}
}
}
本当はSとEのループはもう少し気の利いた枝刈りをしなければならないけどプログラムが単純になるのでこのままにした。
プログラムが複雑にならない程度に以下のようなことを考慮する。
線と矩形の交わりは矩形の頂点と直線の位置関係から求めることが出来る。
以下の図で矩形の頂点A,B,C,Dの4点が直線に対して同じ領域にあれば矩形と直線は交わらない。
直線と点の位置関係を求めるには外積を使う。
以上の考え方でプログラムを作成すると以下のようになる。
const ulong bit0 = 0x00000001; // 16個の矩形と直線との交わりを表現する
const int N = 10; // 一つの矩形の点の数
const int N4 = 4*N; // 一辺にある調査点の数
const int Nrect = 4*N4; // 4辺全てにある調査点の数
struct Point {
int x;
int y;
};
int operator==( const Point& p1, const Point& p2) // 点が同じ位置にあるか?
{
return p1.x == p2.x && p1.y == p2.y;
}
Point Q[Nrect+10/*予備*/]; // 外壁上の全ての調査点
void set_point( Point& p, int ix, int iy) // Pointに(ix,iy)を設定する
{
p.x = ix;
p.y = iy;
}
void get_rect_point( int irect, Point& lb, Point& lt, Point& rb, Point& rt)
// 16個の小矩形の4点の座標位置を求める。
{
assert( irect >= 0 && irect < 16);
// +--+--+--+--+
// |12|13|14|15|
// +--+--+--+--+
// | 8| 9|10|11|
// +--+--+--+--+
// | 4| 5| 6| 7|
// +--+--+--+--+
// | 0| 1| 2| 3|
// +--+--+--+--+
// ↑Y →X
int ix = ( irect % 4 ) * N;
int iy = ( irect / 4 ) * N;
set_point( lb, ix+0, iy+0);
set_point( lt, ix+0, iy+N);
set_point( rb, ix+N, iy+0);
set_point( rt, ix+N, iy+N);
}
int get_point_line_relation( const Point& p, const Point& p1, const Point& p2)
{
// 直線 p1-p2 と 点 p の位置関係を返す。
// p1-p2 と p1-p の外積を求めることで解決する。
int ax = p2.x - p1.x;
int ay = p2.y - p1.y;
int bx = p.x - p1.x;
int by = p.y - p1.y;
int vp = ax*by - ay*bx;
return vp;
}
YesNo is_cross_rect_line( const Point& lb, const Point& lt, const Point& rb, const Point& rt, const Point& p1, const Point& p2)
{
// 以下の矩形と直線p1-p2 が交わるか?
// lt---rt
// | |
// lb---rb
…
}
int get_cross( const Point& p1, const Point& p2) // 直線と16個の矩形が交わるかどうか調べる
{
// +--+--+--+--+
// |12|13|14|15|
// +--+--+--+--+
// | 8| 9|10|11|
// +--+--+--+--+
// | 4| 5| 6| 7|
// +--+--+--+--+
// | 0| 1| 2| 3|
// +--+--+--+--+
// 16個の矩形と直線p1-p2 と交わる矩形を求める。
// 結果は矩形を示すビットで返す。
int bits = 0;
for( int i=0; i< 16; i++) { // 16個の矩形を調べる
// 矩形の4つの点を求める
Point lb, lt, rb, rt;
get_rect_point( i, lb, lt, rb, rt);
if( is_cross_rect_line( lb, lt, rb, rt, p1, p2)) { // 矩形と直線が交わるか?
bits |= bit0 << i; // 交わる場合その矩形を示すビットをONにする
}
}
return bits; // !=0 の場合交わる
}
void make_Q( int& nQ, int& ix, int& iy, int dx, int dy) // 外壁の初期データを作成するために使う
{
for( int i=0; i< N4; i++) {
ix += dx;
iy += dy;
nQ++;
Q[nQ].x = ix;
Q[nQ].y = iy;
}
}
int main( int argc, cstring argv[])
{
Point A, B, C, S, E; // S → A → B → C → E の順に進む
// 外壁上の調査点 Q[]を作成しておく。
int nQ = 0;
int ix = 0, iy = 0;
make_Q( nQ, ix, iy, +1, +0); // 下辺
make_Q( nQ, ix, iy, +0, +1); // 右辺
make_Q( nQ, ix, iy, -1, +0); // 上辺
make_Q( nQ, ix, iy, +0, -1); // 左辺
assert( nQ == Nrect);
for( int a=0; a< 3*N4; a++) {
if( a % N == 0) continue; // 矩形上の点は問題外
A = Q[a];
for( int b=0; b< Nrect; b++) {
if( b % N == 0) continue; // 矩形上の点は問題外
B = Q[b];
if( A == B) continue; // 同じ点は調べない
for( int c=0; c< Nrect; c++) {
if( c % N == 0) continue; // 矩形上の点は問題外
if( c >= N && c < N+N) continue; // Cは出口と同じ外壁上には無い
C = Q[c];
if( C == A || C == B) continue; // 同じ点は調べない
for( int s=1; s< N-1; s++) {
S = Q[3*N4+s];
if( S == A || S == B || S == C) continue; // 同じ点は調べない
for( int e=1; e< N-1; e++) {
E = Q[N4+e];
if( E == A || E == B || E == C || E == S) continue; // 同じ点は調べない
// SA, AB, BC, CE と 矩形の関係を求める。
int crossSA = get_cross( S, A); // 16個の矩形と直線SAが交わるか?
int crossAB = get_cross( A, B); // 16個の矩形と直線ABが交わるか?
int crossBC = get_cross( B, C); // 16個の矩形と直線BCが交わるか?
int crossCE = get_cross( C, E); // 16個の矩形と直線CEが交わるか?
int cross = crossSA | crossAB | crossBC | crossCE;
if( cross == 0xFFFF) { // 16個の矩形全てと交わる?
発見
}
}
}
}
}
}
return 0;
}
最初に作成したプログラムが出力した答え(最初の1個)は以下の通り。
Find 1111 c63 f800 13ec S 0 39 A 1 0 B 40 28 C 0 37 E 40 1
これを図にしてみると以下のようになる。
ありゃダメじゃん。赤い矢印の部分が矩形の頂点にある。これではダメだ。ダメなことはFindの後ろの文字列でも判る。
後ろの文字列は16個の矩形と直線の交わりをビットで表現している。
しかし何となくこの手法で解けることが判った。
Cも入口上にある。入口は壁が無いので，ここで跳ね返ることは無いはず。これも何とかしないと。
上記改良を加えてプログラムを実行する。
ハングアップか？
答えが全然出力されない。しかしこの手法で良さそうなことが判っているのでひたすら待つ。
おー，答えが出力された。ありゃSとEもループに入れてしまったので沢山出過ぎる。
SとEが入口，出口の線上を移動しても16個の矩形との重なりが同じ場合は出力を抑制するようにした。
再び実行。待つこと18分，答えは8件出力されました。直線が16個の矩形の頂点のどこを通過するかによって微妙に違う答えになっている。
Nの値を増やすと爆発するので要注意。
最近結構豆類を食べるようになった(ふじっ子のおまめさんシリーズを良く購入する)。納豆や甘納豆も食べる。
昨年末に生まれて初めて豆きんとんを買った。昔は豆きんとんなんて嫌いだったんだけどなー。
結構おいしいと感じたので年明けに買いに行ったらあれだけあった豆きんとんがどこにも見あたらない。
豆きんとんて年末しか売っていないものなのか。栗きんとんも見あたらないし…
解速度
Pentium Xeon2.4GHz で約18分