オフラインリアルタイムどう書くE20 を SQL で解く

- SQL パワーで解けたのでシェアします

## 問題

- 問題: http://nabetani.sakura.ne.jp/hena/orde20maze/
- 回答集: https://qiita.com/Nabetani/items/7baf181b4a1b7eacc79a

## SQL による解答

- https://gist.github.com/yancya/a3ac5fef2318201705f0dec70fad17ec

```rb
require 'pg'

def main(str)
  start, goal = str.chars
  PG.connect.exec_params(<<~SQL, [start, goal]).first['cnt']
  WITH RECURSIVE patterns("from", "to") AS (
VALUES ('0', '1'), ('0', '6'), ('1', '0'), ('1', '7'), ('2', '3'),
       ('3', '2'), ('3', '4'), ('3', '9'), ('4', '3'), ('4', '5'),
       ('5', '4'), ('5', 'B'), ('6', '0'), ('6', 'C'), ('7', '1'),
       ('7', '8'), ('8', '7'), ('8', '9'), ('9', '8'), ('9', '3'),
       ('9', 'A'), ('9', 'F'), ('A', '9'), ('B', '5'), ('C', '6'),
       ('C', 'D'), ('C', 'I'), ('D', 'C'), ('E', 'K'), ('F', '9'),
       ('F', 'G'), ('G', 'F'), ('G', 'M'), ('H', 'N'), ('I', 'C'),
       ('I', 'O'), ('J', 'K'), ('J', 'P'), ('K', 'J'), ('K', 'E'),
       ('K', 'L'), ('L', 'K'), ('L', 'M'), ('M', 'L'), ('M', 'G'),
       ('M', 'S'), ('N', 'H'), ('N', 'T'), ('O', 'I'), ('P', 'J'),
       ('P', 'Q'), ('P', 'V'), ('Q', 'P'), ('Q', 'R'), ('R', 'Q'),
       ('R', 'X'), ('S', 'M'), ('S', 'T'), ('S', 'Y'), ('T', 'S'),
       ('T', 'N'), ('U', 'V'), ('V', 'U'), ('V', 'P'), ('V', 'W'),
       ('W', 'V'), ('X', 'R'), ('Y', 'S'), ('Y', 'Z'), ('Z', 'Y'))

     , routes AS (
SELECT 0 AS "cnt"
     , ARRAY[]::TEXT[] AS "visited" -- 閉路に対応
     , "from" AS "cur"
  FROM patterns
 WHERE "from" = $1::TEXT

 UNION ALL

SELECT "cnt" + 1 AS "cnt"
     , ARRAY_APPEND("visited", routes."cur") AS "visited"
     , patterns."to" AS "cur"
  FROM routes
  JOIN patterns
    ON routes."cur" = patterns."from"
   AND NOT ARRAY[patterns."to"] <@ routes."visited")

SELECT MIN("cnt") AS "cnt"
  FROM routes
 WHERE "cur" = $2::TEXT;
  SQL
end

main('DE') #=> "13"
```

## 解説

### 移動可能な道を列挙したテーブル

- この部分で、0 -> 1 とか、K -> J のような移動可能な道を表したテーブル（共通表式）を作成する
- `WITH` に `RECURSIVE` が付いているのは後から働く

```sql
  WITH RECURSIVE patterns("from", "to") AS (
VALUES ('0', '1'), ('0', '6'), ('1', '0'), ('1', '7'), ('2', '3'),
       ('3', '2'), ('3', '4'), ('3', '9'), ('4', '3'), ('4', '5'),
       ('5', '4'), ('5', 'B'), ('6', '0'), ('6', 'C'), ('7', '1'),
       ('7', '8'), ('8', '7'), ('8', '9'), ('9', '8'), ('9', '3'),
       ('9', 'A'), ('9', 'F'), ('A', '9'), ('B', '5'), ('C', '6'),
       ('C', 'D'), ('C', 'I'), ('D', 'C'), ('E', 'K'), ('F', '9'),
       ('F', 'G'), ('G', 'F'), ('G', 'M'), ('H', 'N'), ('I', 'C'),
       ('I', 'O'), ('J', 'K'), ('J', 'P'), ('K', 'J'), ('K', 'E'),
       ('K', 'L'), ('L', 'K'), ('L', 'M'), ('M', 'L'), ('M', 'G'),
       ('M', 'S'), ('N', 'H'), ('N', 'T'), ('O', 'I'), ('P', 'J'),
       ('P', 'Q'), ('P', 'V'), ('Q', 'P'), ('Q', 'R'), ('R', 'Q'),
       ('R', 'X'), ('S', 'M'), ('S', 'T'), ('S', 'Y'), ('T', 'S'),
       ('T', 'N'), ('U', 'V'), ('V', 'U'), ('V', 'P'), ('V', 'W'),
       ('W', 'V'), ('X', 'R'), ('Y', 'S'), ('Y', 'Z'), ('Z', 'Y'))
```

### 経路列挙

```sql
     , routes AS (
SELECT 0 AS "cnt"
     , ARRAY[]::TEXT[] AS "visited" -- 閉路に対応
     , "from" AS "cur"
  FROM patterns
 WHERE "from" = $1::TEXT

 UNION ALL

SELECT "cnt" + 1 AS "cnt"
     , ARRAY_APPEND("visited", routes."cur") AS "visited"
     , patterns."to" AS "cur"
  FROM routes
  JOIN patterns
    ON routes."cur" = patterns."from"
   AND NOT ARRAY[patterns."to"] <@ routes."visited")
```

- SQL の最初に `WITH RECURSIVE` としているので、この SQL での共通表式では再帰が可能となる

#### 再帰の初回

```sql
SELECT 0 AS "cnt"
     , ARRAY[]::TEXT[] AS "visited" -- 閉路に対応
     , "from" AS "cur"
  FROM patterns
 WHERE "from" = $1::TEXT
```

- `"cnt"` は歩数。初回は一歩も動いていないので 0 で固定
- `"visited"` は踏んだことのあるパネル名の配列。最初はどこも踏んだことが無いので空配列
- `"cur"` は現在位置。`WHERE "from" = $1::TEXT` として、入力のスタート地点に固定

#### 再帰

```sql
 UNION ALL

SELECT "cnt" + 1 AS "cnt"
     , ARRAY_APPEND("visited", routes."cur") AS "visited"
     , patterns."to" AS "cur"
  FROM routes
  JOIN patterns
    ON routes."cur" = patterns."from"
   AND NOT ARRAY[patterns."to"] <@ routes."visited")
```

- 初期化された `routes` テーブルを基にして、再帰でループする
- `routes` に `patterns` を `JOIN` する。条件は下記の２つ
  - 現在地が道の `"from"` と等しい
  - `"visited"` が `ARRAY[patterns."to"]` を内包しない（逆流やループを防止する
- 下記の 3 カラムからなるタプルを生成して、`routes` に対して `UNION ALL` する
  - `"cnt"` は一歩進める為に `routes."cnt"` を `+1` したものを次の `"cnt"` とする
  - `"visited"` には、既に踏んだことのあるパネルとして `routes."cur"` を末尾に追加する
  - `JOIN` している `patterns` から `"to"` を持ってきて現在位置 `"cur"` とする
  
#### 再帰の終了

- 既に踏んだことのあるパネルや壁としか隣接していない状態になると、それ以上 `UNION ALL` で行が増えなくなる。そうなったときはじめて、再帰クエリは終了し、次のセクションを実行する
  
#### 経路の実態

- 試しに、`routes` の実態を見てみる（入力が 'DE' のケース）

```sql
  WITH RECURSIVE patterns("from", "to") AS (
VALUES ('0', '1'), ('0', '6'), ('1', '0'), ('1', '7'), ('2', '3'),
       ('3', '2'), ('3', '4'), ('3', '9'), ('4', '3'), ('4', '5'),
       ('5', '4'), ('5', 'B'), ('6', '0'), ('6', 'C'), ('7', '1'),
       ('7', '8'), ('8', '7'), ('8', '9'), ('9', '8'), ('9', '3'),
       ('9', 'A'), ('9', 'F'), ('A', '9'), ('B', '5'), ('C', '6'),
       ('C', 'D'), ('C', 'I'), ('D', 'C'), ('E', 'K'), ('F', '9'),
       ('F', 'G'), ('G', 'F'), ('G', 'M'), ('H', 'N'), ('I', 'C'),
       ('I', 'O'), ('J', 'K'), ('J', 'P'), ('K', 'J'), ('K', 'E'),
       ('K', 'L'), ('L', 'K'), ('L', 'M'), ('M', 'L'), ('M', 'G'),
       ('M', 'S'), ('N', 'H'), ('N', 'T'), ('O', 'I'), ('P', 'J'),
       ('P', 'Q'), ('P', 'V'), ('Q', 'P'), ('Q', 'R'), ('R', 'Q'),
       ('R', 'X'), ('S', 'M'), ('S', 'T'), ('S', 'Y'), ('T', 'S'),
       ('T', 'N'), ('U', 'V'), ('V', 'U'), ('V', 'P'), ('V', 'W'),
       ('W', 'V'), ('X', 'R'), ('Y', 'S'), ('Y', 'Z'), ('Z', 'Y'))

     , routes AS (
SELECT 0 AS "cnt"
     , ARRAY[]::TEXT[] AS "visited" -- 閉路に対応
     , "from" AS "cur"
  FROM patterns
 WHERE "from" = 'D'

 UNION ALL

SELECT "cnt" + 1 AS "cnt"
     , ARRAY_APPEND("visited", routes."cur") AS "visited"
     , patterns."to" AS "cur"
  FROM routes
  JOIN patterns
    ON routes."cur" = patterns."from"
   AND NOT ARRAY[patterns."to"] <@ routes."visited")

SELECT *
  FROM routes
;
```

```
 cnt |               visited               | cur
-----|-------------------------------------|-----
   0 | {}                                  | D
   1 | {D}                                 | C
   2 | {D,C}                               | 6
   2 | {D,C}                               | I
   3 | {D,C,6}                             | 0
   3 | {D,C,I}                             | O
   4 | {D,C,6,0}                           | 1
   5 | {D,C,6,0,1}                         | 7
   6 | {D,C,6,0,1,7}                       | 8
   7 | {D,C,6,0,1,7,8}                     | 9
   8 | {D,C,6,0,1,7,8,9}                   | 3
   8 | {D,C,6,0,1,7,8,9}                   | A
   8 | {D,C,6,0,1,7,8,9}                   | F
   9 | {D,C,6,0,1,7,8,9,3}                 | 2
   9 | {D,C,6,0,1,7,8,9,3}                 | 4
   9 | {D,C,6,0,1,7,8,9,F}                 | G
  10 | {D,C,6,0,1,7,8,9,3,4}               | 5
  10 | {D,C,6,0,1,7,8,9,F,G}               | M
  11 | {D,C,6,0,1,7,8,9,3,4,5}             | B
  11 | {D,C,6,0,1,7,8,9,F,G,M}             | L
  11 | {D,C,6,0,1,7,8,9,F,G,M}             | S
  12 | {D,C,6,0,1,7,8,9,F,G,M,L}           | K
  12 | {D,C,6,0,1,7,8,9,F,G,M,S}           | T
  12 | {D,C,6,0,1,7,8,9,F,G,M,S}           | Y
  13 | {D,C,6,0,1,7,8,9,F,G,M,L,K}         | J
  13 | {D,C,6,0,1,7,8,9,F,G,M,L,K}         | E
  13 | {D,C,6,0,1,7,8,9,F,G,M,S,T}         | N
  13 | {D,C,6,0,1,7,8,9,F,G,M,S,Y}         | Z
  14 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J}       | P
  14 | {D,C,6,0,1,7,8,9,F,G,M,S,T,N}       | H
  15 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P}     | Q
  15 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P}     | V
  16 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,Q}   | R
  16 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,V}   | U
  16 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,V}   | W
  17 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,Q,R} | X
(36 rows)
```

### 最短経路選択

```sql
SELECT MIN("cnt") AS "cnt"
  FROM routes
 WHERE "cur" = $2::TEXT;
```

- `routes` に全ての経路が列挙されてるので、あとは `cnt` の最小値を得るだけ
- `$2` にゴールの文字が入り、`WHERE` で絞り込む
- `MIN("cnt") AS "cnt"` で最小の歩数を返しておしまい

## 懸念事項

- 例えば入力が`'DE'` であれば、`"cur"` が `'E'` である行が見つかった時点で、それ以降の行の生成は必要無いので再帰を中断してしまいたいが、今のところ方法が思いつかない

```txt
  12 | {D,C,6,0,1,7,8,9,F,G,M,S}           | Y
  13 | {D,C,6,0,1,7,8,9,F,G,M,L,K}         | J
  13 | {D,C,6,0,1,7,8,9,F,G,M,L,K}         | E __________________
  13 | {D,C,6,0,1,7,8,9,F,G,M,S,T}         | N ここから下は不要なはず
  13 | {D,C,6,0,1,7,8,9,F,G,M,S,Y}         | Z
  14 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J}       | P
  14 | {D,C,6,0,1,7,8,9,F,G,M,S,T,N}       | H
  15 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P}     | Q
  15 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P}     | V
  16 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,Q}   | R
  16 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,V}   | U
  16 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,V}   | W
  17 | {D,C,6,0,1,7,8,9,F,G,M,L,K,J,P,Q,R} | X
```

- 下記のようにするとエラーが出る
  - 'ecursive reference to query "routes" must not appear within a subquery'
  - 再帰 SQL のテーブルを再帰の中でサブクエリにして使う事は出来ない

```sql
  WITH RECURSIVE patterns("from", "to") AS (
VALUES ('0', '1'), ('0', '6'), ('1', '0'), ('1', '7'), ('2', '3'),
       ('3', '2'), ('3', '4'), ('3', '9'), ('4', '3'), ('4', '5'),
       ('5', '4'), ('5', 'B'), ('6', '0'), ('6', 'C'), ('7', '1'),
       ('7', '8'), ('8', '7'), ('8', '9'), ('9', '8'), ('9', '3'),
       ('9', 'A'), ('9', 'F'), ('A', '9'), ('B', '5'), ('C', '6'),
       ('C', 'D'), ('C', 'I'), ('D', 'C'), ('E', 'K'), ('F', '9'),
       ('F', 'G'), ('G', 'F'), ('G', 'M'), ('H', 'N'), ('I', 'C'),
       ('I', 'O'), ('J', 'K'), ('J', 'P'), ('K', 'J'), ('K', 'E'),
       ('K', 'L'), ('L', 'K'), ('L', 'M'), ('M', 'L'), ('M', 'G'),
       ('M', 'S'), ('N', 'H'), ('N', 'T'), ('O', 'I'), ('P', 'J'),
       ('P', 'Q'), ('P', 'V'), ('Q', 'P'), ('Q', 'R'), ('R', 'Q'),
       ('R', 'X'), ('S', 'M'), ('S', 'T'), ('S', 'Y'), ('T', 'S'),
       ('T', 'N'), ('U', 'V'), ('V', 'U'), ('V', 'P'), ('V', 'W'),
       ('W', 'V'), ('X', 'R'), ('Y', 'S'), ('Y', 'Z'), ('Z', 'Y'))

     , routes AS (
SELECT 0 AS "cnt"
     , ARRAY[]::TEXT[] AS "visited" -- 閉路に対応
     , "from" AS "cur"
  FROM patterns
 WHERE "from" = 'D'

 UNION ALL

SELECT "cnt" + 1 AS "cnt"
     , ARRAY_APPEND("visited", routes."cur") AS "visited"
     , patterns."to" AS "cur"
  FROM routes
  JOIN patterns
    ON routes."cur" = patterns."from"
   AND NOT ARRAY[patterns."to"] <@ routes."visited"
 WHERE NOT (SELECT 'E' IN (SELECT "cur" FROM routes)))
       -- ↑ここが真になると新しい行が出てこなくなり、再帰が終わるハズ
       -- と思ったけど、再帰クエリの中でサブクエリを使うとエラーが出る

SELECT *
  FROM routes
;
```