J言語で迷路を作る

# はじめに

[前回](https://qiita.com/Raclamusi/items/237a447ddd2dfc1a03bb)の記事を書いてから、J言語をさらに勉強しました。
今の自分ならなんでもできる気がします。
という訳で、今回はJ言語で迷路作ります。

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

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

```j:拡張子は"ijs"やで
+/%!i.100  NB. ネイピア数の近似値を求める
```

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

# そもそもJ言語って何？

***J言語は素晴らしいプログラミング言語です。***[^per-imp]

[^per-imp]: 個人の感想です。

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

九九の表示くらいなら、**たった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言語の魅力です。

# 迷路作るやつ

本題です。

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

[^verb]: 関数のようなものです。J言語では verb や noun (数値や文字列) といった「品詞」という概念がありますが、私の記事では親しみやすいように、noun を「名詞」、abverb を「副詞」、conjunction を「接続詞」、verb を「動詞」というように日本語で表記します。

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

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

[^ask]: もし、もっと短くできる方法があったら、コメントで教えていただけるとうれしいです。「`MakeMaze`という名前を短くする」以外でお願いします。語呂がよくてお気に入りなので。

# 使い方

縦幅と横幅を*リスト*(一次元配列)で渡すと、道が`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`は接続詞[^conjunction]`:`によって*モナド*[^monad]と*ダイアド*[^dyad]の処理が別で定義されています。

[^conjunction]: 動詞や名詞同士を結合して、新たな動詞を作る演算子のことです。
[^monad]: 単項、右から1つの引数が渡されている場合のことです。
[^dyad]: 2項、左右から引数が渡されている場合のことです。

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

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

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

## フィールド生成

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

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

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

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

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

[^plus-inc]: 実際は自身と自身に1足したものを足すという処理をしていますが、結果は同じです。こちらのほうが短く記述できます。

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

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

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

[^one-colon]: `1:`というように`1`にコロンが付いているのは、文法上その場所が動詞でなくてはならないからです。`1:`は`1`を返す動詞です。

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

[^out-check]: J言語ではPythonなどと同じように、負のインデックスは最後尾からの順番を意味します。なので、`0`を連結するのは下と右だけで十分です。
[^adverb]: 動詞や名詞の右に付けて、新たな動詞を作る演算子のことです。接続詞との違いは、動詞や名詞1つだけに適用することです。

```
   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`)を取り除くためです。

## 迷路掘り出し

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

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

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

```
 0  2
 2  0
 0 _2
_2  0
```

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

[^minus]: 数字の前の`_`(アンダーバー)は負の符号です。`_2`はマイナス2のことです。また、`_`単体では無限大を意味します。
[^how-calc]: `1 2`を`#:`で2進数に変換したものに2を掛け、`(, -)`で符号を逆にしたものを連結しています。

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

[^rank]: 次元の数を表す概念です。ランク`0`はアトム(単体の数値や文字)、ランク`1`はリスト(1次元配列)、ランク`2`はテーブル(2次元配列)を表し、`"`は計算をどのランクに適応するかを指定します。

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

[^tilde]: ここでの副詞`~`は「右の引数を左にも渡す」という役割をします。`?~4`は`4?4`になります。

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

---

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

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

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

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

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

[^current-coord]: 現在の座標のマスも取得されますが、計算に影響はありません。

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

```text:(5,&nbsp;1)&nbsp;から&nbsp;(5,&nbsp;3)&nbsp;に進むとき
   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:`]`[}``**[^amend]
フィールドの、上で出した3つの座標の位置を、副詞`}`で`0`に置き換えます。
つまり、進んだ部分に道を掘ります。

[^amend]: ``x f`g`h} y``は`(x f y) (x g y)} (x h y)`を意味します。``(フィールド) 0:`]`[} (座標)``は`0 (座標)} (フィールド)`です。

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

---

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

# おわりに

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

J言語は今、流行ろうとしています。(私の予想です。)
[QiitaのシンタックスハイライトがJ言語に対応](https://qiita.com/unsigned-wrong-wrong-int/items/a97ccce29b7b084b127a)したり、[J言語入門](https://qiita.com/unsigned-wrong-wrong-int/items/e15a87999cedfc6b9ced)という記事が書かれたりしていて[^uww]、「J言語を布教するなら今しかない！」と思ってるので、これからJ言語の記事をどんどん書いていきます。

~~たぶん。~~

[^uww]: だいたい同じ人の仕業です。

# 参考サイト

[NuVoc](https://code.jsoftware.com/wiki/NuVoc)
[Vocabulary](https://www.jsoftware.com/help/dictionary/vocabul.htm)
[迷路を簡単に自動生成するアルゴリズムが面白い【穴掘り法】 - YouTube](https://youtu.be/yHXkuBPNvmk)