センター試験「情報関係基礎」2018年の迷路をCindyScriptで書く

2020年12月8日 07:30

　タイトル画像のような迷路を解く。「解く」というのは，スタート（S)からゴール（G)まで，戻らずにいく経路を求めるという意味だ。
　白が道。たとえば (X,Y) が(2,2) のマスは行き止まりのなので，(3,4) から左にいく経路は進めない。このような，袋小路になるマスを調べて塗っていくと，右のように経路が判明する。

　問題では，このような袋小路を塗っていく手順（アルゴリズム）がまず説明される。

ステップ１
　外周を除く領域について，上の行から下の行の順に，各行のマスを左から右の順に行き止まりかどうか調べ，行き止まりなら塗る。最後のマスまで調べたらステップ2に進む。
ステップ２
　ステップ1で1マスも塗られなかったら手順を終了する。そうでなければステップ１に戻る。

　この説明に基づいて，どのマスが塗られていくかを具体的に問題にして答えさせる。
　次にコーディング。マスの白は0，黒は１で表した2次元配列 Masu を用意する。

　縦横のマスの数は，変数 tate , yoko に格納する。また，ステップ２の判断のためにフラグ nutta を用意する。（問題文では「フラグ」という用語は使われていない）
　図５で，前半１１行目までが袋小路を塗る手続き，１２行目からが結果を表示する手続きだ。

　問題ではこのあと，アルゴリズムの改訂版を示して問題としているが，そちらの説明は省略する。

　さて，実際のコーディングだが，初期状態とでき上がりを，初めに示した図１，図２のように両方表示したいので，表示部分を関数化した。（dispmasu()）
　袋小路を塗っていく部分も，改良型アルゴリズムの分もコーディングすることにして，それぞれ関数化した。( main1() と main2() )
　授業で使うとしたら main1() だけでよいだろう。

　しかし，これだけではもちろん完成しない。
　初期設定が必要だ。マスの配列 Masu の定義，スタートとゴールの設定はもちろんそうだが，これ以外にもある。
　Masu の転置と表示用配列の準備だ。
　問題文の図4のように配列を定義すると次のようにするのが自然だろう。

Masu=[
[1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,0,1,0,0,1,0,0,1],
[1,0,1,0,1,1,0,1,0,1,1],
[1,0,0,0,0,1,0,0,0,0,1],
[1,1,0,1,1,1,1,0,1,0,1],
[1,0,0,0,0,0,0,0,1,0,1],
[1,0,1,1,1,1,1,1,1,0,1],
[1,0,0,0,0,1,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1]
];

図4を再掲する。

Start と Goal の 9 は１になっているが，このあと 0 にする。（後述）
しかし，これだと，図５の手順で

　yを2からサまで1ずつ増やしながら
　　xを2からサまで1ずつ増やしながら
　　　a ← Masu[x-1,y]+・・・・

がうまくいかない。
「xを2からサまで1ずつ増やしながら」は図１（図4）で「左から右へ進む」ということを意図しているのだが，配列の要素を表すインデックスがこれだと逆になるからだ。
　Cindyscript では，この配列をリストで表し，インデックスはアンダースコアを用いて Masu_3_2 のように表すがこれは3行目の左から2番目の要素を表す。問題文の配列の表現で Masu[3,2] とすると，x=3,y=2 だから，これは２行目の左から3番目の要素だ。図４の，X,Y の向きをよく見て欲しい。x, y が逆になるわけだ。
　これはCindyscriptの問題ではなく，他の言語の配列でも同様だ。
また，このことは，迷路の図を表示するときにも問題になる。Masu[x,1] でxを 1,2,3 ・・・　としていくと図4のy方向（縦）にとっていくことになり，「x座標を1,2,3,・・・としていく」ことにはならないからだ。また，座標平面では y 座標は下から上に大きくなっていくので，これも方向が逆になる。
　このことは，この問題に限らず，2次元の配列（行列）を用いて座標平面上に要素を表示するときに必ずついてくる問題である。実際，授業でも生徒が理解しにくい事柄である。（経験済）
　したがって，コードを問題の通りにやっていくなら，Masu を転置する必要がある。Cindyscript では行列（2次元配列）Masu に対して，関数 transposeを用いて transpose(Masu) とすれば転置行列が得られる。

　次に，表示用の配列だが，図2のように，塗ったマスは灰色で塗りたいので，Masu をそのまま使うのではうまくいかない。白，黒，灰色の3色が必要だからだ。そこで，そのための配列を用意しておく。初めは Masu と同じにしておく。初期状態を残しておきたいので，これを Colror0 とし，出来上がりを Color とする。
　もうひとつ。「スタートとゴールには9が格納されている」となっているが，表示のため，またデータを作りやすくするため，変数 Start と Goal を用意して位置を示し，配列の値は0とすることにした。

Masu=[
[1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,0,1,0,0,1,0,0,1],
[1,0,1,0,1,1,0,1,0,1,1],
[1,0,0,0,0,1,0,0,0,0,1],
[1,1,0,1,1,1,1,0,1,0,1],
[1,0,0,0,0,0,0,0,1,0,1],
[1,0,1,1,1,1,1,1,1,0,1],
[1,0,0,0,0,1,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1]
];
Start=4;
Goal=8;
yoko=length(Masu_1);
tate=length(Masu);
Masu_1_Start=0;    // 表示のため，9ではなく0にする
Masu_tate_Goal=0;
Masu=transpose(Masu);
Color0=Masu;
Color=Masu;

　これで，袋小路を塗る手続きについては問題の図５の形でできる。これを main1()とする。

main1():=(
 nutta=1;
 while(nutta>0,
   nutta=0;
   repeat(tate-2,y,start->2,
     repeat(yoko-2,x,start->2,
       s=Masu_(x-1)_y+Masu_(x+1)_y+Masu_x_(y-1)+Masu_x_(y+1);
       if(Masu_x_y==0 & s==3,
         Masu_x_y=1;
         nutta=1;
         Color_x_y=0.3;
       );
     );
  );
);
);

なお，最初に nutta=1 としているのは while ループが少なくとも一度は実行されるための措置である。問題の図５のコードでは欠落している。（というより，図５は do 〜 while（条件）の構文だろう）

　次に，図５の後半，迷路の表示部分だが，図５のコードでは白と黒としか表示されず，図２のようにはならない。
　そこで，コンソールではなく描画面（xy平面）に表示するが，すると前述のように y 座標の問題が生じる。したがって，授業で使うならその点を説明して書くことになる。図５の問題の中には空欄はないので，全部作り込んでもよいが，空欄を設けて埋めさせる方が実習の授業としてはいいだろう。
　なお，引数の org は表示位置の左下を表す。grid(org)はグリッド表示で別に関数を作ってある。グリッドが必要なわけは，道を白の四角で表示すると方眼が表示されないからである。color オプションを使って表示色を決めるので，if で条件分岐する必要もない。


dispmasu(org,mat):=(
 grid(org);
 repeat(tate,y,
   repeat(yoko,x,
     col=apply(1..3,1-mat_x_y);
     drawtext(org+[x-0.25,tate-y-0.35],"■",color->col,size->68);
   );
 );
 drawtext(org+[Start+0.2,tate-1+0.1],"S",size->22);
 drawtext(org+[Goal+0.2,0.1],"G",size->22);
);

問題文の表示部分を再掲しよう。問題文には，スタート / ゴールのS,Gを表示するコードはない。

Cindyscript では，これらを Initialization スロットに書き，全体の動作は Draw スロットに書く。

drawtext([2,11],"問題",size->22);
dispmasu([0,0],Color0);
main1();
drawtext([14,11],"解答",size->22);
dispmasu([12,0],Color);

プログラムが正しくできれば次のように表示される。

　さて，次に，これを Python で書くことに取り組んだのだが，かなり難航した。どこで難航したかは次のレポート「センター試験「情報関係基礎」2018年の迷路をPythonで書く」に書くことにする。