Edited at

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

More than 1 year has passed since last update.


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


問題


SQL による解答

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 のような移動可能な道を表したテーブル(共通表式)を作成する


  • WITHRECURSIVE が付いているのは後から働く

  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 テーブルを基にして、再帰でループする


  • routespatternsJOIN する。条件は下記の2つ


    • 現在地が道の "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
;