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

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

問題

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

SQL による解答

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

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 が付いているのは後から働く

  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")

SQL の最初に WITH RECURSIVE としているので、この 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 として、入力のスタート地点に固定

再帰

 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' のケース）

  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)

最短経路選択

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

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

懸念事項

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

  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 のテーブルを再帰の中でサブクエリにして使う事は出来ない

  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
;