はじめに

前回の記事を書いてから、J言語をさらに勉強しました。
今の自分ならなんでもできる気がします。
という訳で、今回はJ言語で迷路作ります。

J言語にシンタックスハイライトがつけられるよ！

ついにQiitaのシンタックスハイライトがJ言語に対応しました！

拡張子は"ijs"やで

+/%!i.100  NB. ネイピア数の近似値を求める

めちゃくちゃ見やすい……(感動)

そもそもJ言語って何？

J言語は素晴らしいプログラミング言語です。¹

配列の処理にとても優れていて、さらに驚くほど短く記述できます。
計算途中に変数を使う必要がほとんどありません。

九九の表示くらいなら、たった8バイトで可能です。

   */~1+i.9
1  2  3  4  5  6  7  8  9
2  4  6  8 10 12 14 16 18
3  6  9 12 15 18 21 24 27
4  8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81

1行目の式を打ち込んでEnterキーを叩くと、8バイトの記号の羅列からは想像できないような、綺麗な九九が出力されます！
このスマートなところがJ言語の魅力です。

迷路作るやつ

本題です。

迷路を作る動詞²を作りました。
出来たものがこちらです。

MakeMaze.ijs

MakeMaze=:(([{.]$:0,.~0,~[$1:)&(+>:)?) :(](](>@{:@]$:0:`]`[}){.@[(-:@+;;)&>[{~{i:1:) ::]^:_~[;?~@4<@{((,-)2*#:1 2)+"1[)

短い！　たったの119バイト！
……少し長いと感じるかもしれませんが、迷路を作れてこれは短くないですか？³　119バイトで迷路作れる言語なんて、たぶんほかにないですよ。たぶん。

使い方

縦幅と横幅をリスト(一次元配列)で渡すと、道が0、壁が1の迷路がランダムに生成されます。
いい感じに見やすくして、スタートとゴールを決めて遊んでください。

   ]maze=: MakeMaze 8 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1
1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1
1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1
1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1
1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1
1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1
1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1
1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1
1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1
1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

   maze{' #'
#####################
#       #   #       #
# ### ### # # # ### #
# #   #   # # #   # #
# ##### ### # ### # #
# #       # # #   # #
# # ####### # # #####
# #   #     # # #   #
# # ### ##### # # ###
# # #   #   # # # # #
# # # # # # # # # # #
#   # # # #   #   # #
##### ### ######### #
#     #   #     #   #
# ##### ##### # # # #
#             #   # #
#####################

   ,.>maze{'  ';'[]'
[][][][][][][][][][][][][][][][][][][][][]
[]              []      []              []
[]  [][][]  [][][]  []  []  []  [][][]  []
[]  []      []      []  []  []      []  []
[]  [][][][][]  [][][]  []  [][][]  []  []
[]  []              []  []  []      []  []
[]  []  [][][][][][][]  []  []  [][][][][]
[]  []      []          []  []  []      []
[]  []  [][][]  [][][][][]  []  []  [][][]
[]  []  []      []      []  []  []  []  []
[]  []  []  []  []  []  []  []  []  []  []
[]      []  []  []  []      []      []  []
[][][][][]  [][][]  [][][][][][][][][]  []
[]          []      []          []      []
[]  [][][][][]  [][][][][]  []  []  []  []
[]                          []      []  []
[][][][][][][][][][][][][][][][][][][][][]

解説

今回作った動詞MakeMazeは接続詞⁴:によってモナド⁵とダイアド⁶の処理が別で定義されています。

このままでは分かりづらいので分解して解説します。

DigField=: ] (] (>@{:@] $: 0:`]`[}) {.@[ (-:@+ ; ;)&> [ {~ { i: 1:) ::]^:_~ [ ; ?~@4 <@{ ((, -)2*#:1 2) +"1 [
MakeMaze=: ([ {. ] DigField 0 ,.~ 0 ,~ [ $ 1:)&(+ >:) ?

迷路は「すべて壁のフィールドを作ってそこに道を掘り進めていく」という方法で作ります。
(穴掘り法というアルゴリズムです。)

フィールド生成

MakeMaze=: ([ {. ] DigField 0 ,.~ 0 ,~ [ $ 1:)&(+ >:) ?

これに迷路のサイズ(縦幅と横幅のリスト)が渡されます。

J言語では処理が右から進むので、右から解説します。

?
乱数を生成します。
これで掘り始めの座標をランダムに決めます。

&(+ >:)
引数を2倍して1足します。⁷
これは、周りとそれぞれの道のマスの間に壁のマスが入るからです。

[
左の引数をそのまま返します。
この場合は2倍して1足された迷路のサイズです。

]
右の引数をそのまま返します。
この場合は2倍して1足された掘り始めの座標です。

[ $ 1:⁸
配列を作る動詞$が、指定されたサイズで、すべての要素が1のテーブル(二次元配列)を作ります。
これが迷路のフィールドになります。

0 ,.~ 0 ,~ ……
,~で迷路の下に、,.~で迷路の右に0を連結します。あらかじめ周りに道を作っておくことで、範囲外のチェックをしなくてよくなります。⁹
~は左右の引数を入れ替える副詞¹⁰です。

   z=: 3 3 $ 1
   z
1 1 1
1 1 1
1 1 1
   0 , z
0 0 0
1 1 1
1 1 1
1 1 1
   0 ,~ z
1 1 1
1 1 1
1 1 1
0 0 0
   0 ,.~ z
1 1 1 0
1 1 1 0
1 1 1 0
   0 ,.~ 0 ,~ z
1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 0

] DigField ……
DigFieldに掘り始めの座標を渡して、迷路を掘り出します。
DigFieldについては後で解説します。

[ {. ……
配列から指定サイズを取り出す動詞{.で、掘り終わった迷路から元のサイズの分だけ取り出します。
範囲外に出ないように付けた周りの道(下と右に付けた0)を取り除くためです。

迷路掘り出し

DigField=: ] (] (>@{:@] $: 0:`]`[}) {.@[ (-:@+ ; ;)&> [ {~ { i: 1:) ::]^:_~ [ ; ?~@4 <@{ ((, -)2*#:1 2) +"1 [

DigFieldには、右から迷路のフィールド、左から座標が渡されます。

((, -)2*#:1 2) +"1 [
(, -)2*#:1 2は計算すると

です。¹¹ ¹²
これは、掘り進める向きを表します。上からそれぞれ、右、下、左、上に2マス掘り進めるための座標の増分です。

そしてこれを現在の座標に足して、掘り進む先の座標を計算します。(…… +"1 [)
"はランク¹³を指定する接続詞です。
この場合、リストを基準に足し算したいので、リストを意味するランク1を指定します。

?~@4 <@{ ……
?~@4¹⁴は0～3のランダムな順列を出します。
そしてこのそれぞれのインデックスの要素を{で取得して座標を入れ替えて、掘り進める順番をランダムにしています。
{に接続詞@でボックス化の動詞<をつけることで、取得と同時にボックスに入れています。ボックスとは、なんでも包み込んでくれる便利なやつです。

[ ; ……
現在の座標も後で使うので、;で連結しておきます。

] (] (>@{:@] $: 0:`]`[}) {.@[ (-:@+ ; ;)&> [ {~ { i: 1:) ::]^:_~ ……

いよいよ実際に迷路を掘り出してる部分に入っていきます。

::]^:_~
^:は繰り返しの接続詞で、_(無限大)と合わせて使うことで、「右の引数と同じ結果が返るまで繰り返し」という動作になります。ほかの言語でいうwhileのようなものです。
ここで、繰り返しの判断に使いたいのは迷路のフィールドの方なので、右の引数にそれを持ってくるために~で左右の引数を入れ替えています。

::は左の動詞でエラーが出たときに右の動詞を実行する接続詞で、ほかの言語でいうtry-catchのようなものです。
::]はエラーが出たとき]が右の引数をそのまま返すので、^:_による繰り返しが終了します。
なので、::]^:_を付けたときの動作は「エラーが出るまでループ」といったものになります。このループで上下左右のマスをすべて検証します。

[ {~ { i: 1:
現在の座標から上下左右に進んだマスを{で取得し¹⁵、その中から1を、つまりまだ壁で掘られていないマスの座標をi:で探索します。
そして、見つかったらその座標のインデックスが返るので[ {~ ……で座標を取得します。見つからなかった場合ははみ出したインデックスが返るので、座標を取得するときにindex errorが出て、ループが終了します。

{.@[ (-:@+ ; ;)&> ……
{.は配列の最初の要素を返します。
つまり、{.@[は連結しておいた現在の座標です。
そして、現在の座標と進む先の座標のボックスを>で外し、;でそれらを結合したものと、足して(+)2で割った(-:)間の座標を、;で結合して、掘り出す座標のボックスのリストを作っています。

(5, 1) から (5, 3) に進むとき

   5 1 ; 5 3  NB. ボックスに入れて結合する
+---+---+
|5 1|5 3|
+---+---+
   5 1 -:@+ 5 3  NB. 足して2で割る
5 2
   5 1 (-:@+ ; ;) 5 3  NB. 2つの結果を結合する
+---+---+---+
|5 2|5 1|5 3|
+---+---+---+

間の座標を出すのは、進んだ先だけを掘るのではなく、進んだ道のりを掘らなくてはならないからです。

0:`]`[}¹⁶
フィールドの、上で出した3つの座標の位置を、副詞}で0に置き換えます。
つまり、進んだ部分に道を掘ります。

>@{:@] $: ……
{:は配列の最後の要素を返します。
>@{:@]は掘り出した座標のボックスのリストの最後の要素のボックスを外したもの、つまり、進んだ先の座標です。
そして、今掘り進めたフィールドを右から、掘り進んだ先の座標を左から、その動詞自身を示す$:に渡します。
つまり、再帰をしているということです。
この再帰によって、掘った先からまた掘り始めます。
再帰が終わってフィールドが返ってくると、ループで次の方向に掘り進めます。

解説を省略した部分も結構ありますが、これらの処理がいい感じに合わさって、迷路が作られていきます。

おわりに

J言語では記号に様々な役割があり、一行のプログラムで、迷路を作るなどの複雑な処理をすることができます。
無駄のない記述ができる、とてもかっこいいプログラミング言語だと、私は思っています。

J言語は今、流行ろうとしています。(私の予想です。)
QiitaのシンタックスハイライトがJ言語に対応したり、J言語入門という記事が書かれたりしていて¹⁷、「J言語を布教するなら今しかない！」と思ってるので、これからJ言語の記事をどんどん書いていきます。

~~たぶん。~~

参考サイト

NuVoc
Vocabulary
迷路を簡単に自動生成するアルゴリズムが面白い【穴掘り法】 - YouTube

個人の感想です。 ↩
関数のようなものです。J言語では verb や noun (数値や文字列) といった「品詞」という概念がありますが、私の記事では親しみやすいように、noun を「名詞」、abverb を「副詞」、conjunction を「接続詞」、verb を「動詞」というように日本語で表記します。 ↩
もし、もっと短くできる方法があったら、コメントで教えていただけるとうれしいです。「MakeMazeという名前を短くする」以外でお願いします。語呂がよくてお気に入りなので。 ↩
動詞や名詞同士を結合して、新たな動詞を作る演算子のことです。 ↩
単項、右から1つの引数が渡されている場合のことです。 ↩
2項、左右から引数が渡されている場合のことです。 ↩
実際は自身と自身に1足したものを足すという処理をしていますが、結果は同じです。こちらのほうが短く記述できます。 ↩
1:というように1にコロンが付いているのは、文法上その場所が動詞でなくてはならないからです。1:は1を返す動詞です。 ↩
J言語ではPythonなどと同じように、負のインデックスは最後尾からの順番を意味します。なので、0を連結するのは下と右だけで十分です。 ↩
動詞や名詞の右に付けて、新たな動詞を作る演算子のことです。接続詞との違いは、動詞や名詞1つだけに適用することです。 ↩
数字の前の_(アンダーバー)は負の符号です。_2はマイナス2のことです。また、_単体では無限大を意味します。 ↩
1 2を#:で2進数に変換したものに2を掛け、(, -)で符号を逆にしたものを連結しています。 ↩
次元の数を表す概念です。ランク0はアトム(単体の数値や文字)、ランク1はリスト(1次元配列)、ランク2はテーブル(2次元配列)を表し、"は計算をどのランクに適応するかを指定します。 ↩
ここでの副詞~は「右の引数を左にも渡す」という役割をします。?~4は4?4になります。 ↩
現在の座標のマスも取得されますが、計算に影響はありません。 ↩
x f`g`h} yは(x f y) (x g y)} (x h y)を意味します。(フィールド) 0:`]`[} (座標)は0 (座標)} (フィールド)です。 ↩
だいたい同じ人の仕業です。 ↩

J言語で迷路を作る