「ドキドキ登山」を SQL で解いてみた

SQL で解きました
再帰 SQL が２本必要だったので、意外と大変でした

問題

解答

 WITH RECURSIVE test_data(case_id, actual, expected) AS (
         VALUES ('/*00*/', '2512:C', 'DEFGH'),
                ('/*01*/', '1:A', 'CDEFGH'),
                ('/*02*/', ':C', 'ABDEFGH'),
                ('/*03*/', '2345:B', 'AGH'),
                ('/*04*/', '1256:E', 'ABCDH'),
                ('/*05*/', '1228:A', 'ADEFG'),
                ('/*06*/', '5623:B', 'AEFGH'),
                ('/*07*/', '8157:C', 'ABDEFGH'),
                ('/*08*/', '74767:E', 'ABCFGH'),
                ('/*09*/', '88717:D', 'ABCEFGH'),
                ('/*10*/', '148647:A', 'ACDEFH'),
                ('/*11*/', '374258:H', 'BCDEFH'),
                ('/*12*/', '6647768:F', 'ABCDEH'),
                ('/*13*/', '4786317:E', 'ABFGH'),
                ('/*14*/', '3456781:C', ''),
                ('/*15*/', '225721686547123:C', 'CEF'),
                ('/*16*/', '2765356148824666:F', 'ABCDEH'),
                ('/*17*/', '42318287535641783:F', 'BDE'),
                ('/*18*/', '584423584751745261:D', 'FGH'),
                ('/*19*/', '8811873415472513884:D', 'CFG'),
                ('/*20*/', '74817442725737422451:H', 'BCDEF'),
                ('/*21*/', '223188865746766511566:C', 'ABGH'),
                ('/*22*/', '2763666483242552567747:F', 'ABCG'),
                ('/*23*/', '76724442325377753577138:E', 'EG'),
                ('/*24*/', '327328486656448784712618:B', ''),
                ('/*25*/', '4884637666662548114774288:D', 'DGH'),
                ('/*26*/', '84226765313786654637511248:H', 'DEF'),
                ('/*27*/', '486142154163288126476238756:A', 'CDF'),
                ('/*28*/', '1836275732415226326155464567:F', 'BCD'),
                ('/*29*/', '62544434452376661746517374245:G', 'G'),
                ('/*30*/', '381352782758218463842725673473:B', 'A')

             ), labels AS (
         SELECT row_number() over() AS way_no
              , label
           FROM (VALUES('A'), ('B'), ('C'), ('D')
                     , ('E'), ('F'), ('G'), ('H')) AS t(label)

             ), sideways AS (
         SELECT t.way_no
              , string_agg(label, '' ORDER BY label) AS sideway
           FROM labels
           JOIN generate_series(1, 8) AS t(way_no)
             ON labels.way_no = t.way_no
             OR labels.way_no = (t.way_no + 1) % 8
             OR (labels.way_no = 8 AND t.way_no = 7)
       GROUP BY 1
       ORDER BY 1

             ), start_directions AS (
         SELECT case_id
              , SPLIT_PART(actual, ':', 2) AS start_dir
           FROM test_data

             ), way_numbers AS (
         SELECT case_id
              , UNNEST(
                    REGEXP_SPLIT_TO_ARRAY(
                        SPLIT_PART(actual, ':', 1),
                        ''
                    )
                ) AS way_no
           FROM test_data

             ), way_numbers_with_order AS (
         SELECT way_numbers.case_id
              , ROW_NUMBER() OVER(PARTITION BY case_id) AS "order"
              , CASE
                WHEN LENGTH(way_numbers.way_no) = 0
                THEN NULL
                ELSE way_numbers.way_no::INTEGER
                END AS way_no
           FROM way_numbers

             ), danger_ways AS (
         SELECT case_id
              , "order"
              , sideway
           FROM way_numbers_with_order AS wnwo
LEFT OUTER JOIN sideways AS sw
             ON wnwo.way_no = sw.way_no

             ), danger_ways_detail AS (
         SELECT case_id
              , 0::BIGINT AS "order"
              , NULL AS sideway
              , start_dir AS cur_dir
           FROM start_directions

          UNION

         SELECT dwd.case_id
              , dw."order"
              , CASE
                WHEN dw.sideway ~ dwd.cur_dir
                THEN dw.sideway
                ELSE NULL
                END AS sideway
              , CASE
                WHEN dw.sideway ~ dwd.cur_dir
                THEN REGEXP_REPLACE(dw.sideway, dwd.cur_dir, '')
                ELSE dwd.cur_dir
                END AS cur_dir
           FROM danger_ways_detail AS dwd
LEFT OUTER JOIN danger_ways AS dw
             ON dwd.case_id = dw.case_id
            AND dwd."order" + 1 = dw."order"

             ), routes AS (
         SELECT case_id
              , label
           FROM test_data
     CROSS JOIN labels
       ORDER BY 1, 2

             ), routes_by_case AS (
         SELECT case_id
              , label
              , 0::BIGINT AS order
              , NULL AS sideway
              , label AS cur_dir
           FROM routes

          UNION

         SELECT rbc.case_id
              , rbc.label
              , sideways."order"
              , CASE
                WHEN sideways.sideway ~ rbc.cur_dir
                THEN sideways.sideway
                ELSE NULL
                END AS sideway
              , CASE
                WHEN sideways.sideway ~ rbc.cur_dir
                THEN REGEXP_REPLACE(sideways.sideway, rbc.cur_dir, '')
                ELSE rbc.cur_dir
                END AS cur_dir
           FROM routes_by_case AS rbc
LEFT OUTER JOIN (
         SELECT ROW_NUMBER() OVER(
                    PARTITION BY case_id ORDER BY "order" DESC
                ) AS "order"
              , case_id
              , sideway
           FROM danger_ways
              ) AS sideways
             ON rbc.case_id = sideways.case_id
            AND rbc."order" + 1 = sideways."order"

              ), dead_directions AS (
         SELECT t.case_id
              , sd.start_dir AS dead_direction
           FROM (
         SELECT case_id
              , SUM(CASE
                    WHEN sideway IS NULL THEN 0
                    ELSE 1
                    END)AS way_count
           FROM danger_ways_detail
       GROUP BY 1
       ORDER BY 1) AS t
LEFT OUTER JOIN start_directions AS sd
             ON t.case_id = sd.case_id
            AND t.way_count = 0
          WHERE sd.start_dir IS NOT NULL

             ), dead_or_alive AS (
         SELECT case_id
              , "order"
              , label
              , routes_by_case.sideway
              , dwd.sideway
              , CASE
                WHEN routes_by_case.sideway = dwd.sideway
                THEN '死'
                ELSE '生'
                END AS judge
           FROM routes_by_case
           JOIN (

             SELECT case_id
                  , ROW_NUMBER() OVER(
                        PARTITION BY case_id ORDER BY "order" desc
                    ) AS "order"
                  , sideway
               FROM danger_ways_detail
              WHERE "order" <> 0 AND "order" IS NOT NULL

              ) AS dwd
          USING (case_id, "order")
       ORDER BY 1, 3, 2

             ), results AS (
         SELECT t.case_id
              , STRING_AGG(label, '' ORDER BY LABEL) as "result"
           FROM (
         SELECT case_id
              , label
              , MIN(judge) AS judge
           FROM dead_or_alive
       GROUP BY 1, 2
       ORDER BY 1, 2) AS t
LEFT OUTER JOIN dead_directions AS dd
             ON dd.case_id = t.case_id
            AND dd.dead_direction = t.label
          WHERE dd.dead_direction IS NULL
            AND t.judge = '生'
       GROUP BY 1)

         SELECT res.case_id
              , res."result"
              , td.expected
              , CASE
                WHEN td.expected = res."result"
                THEN '.'
                ELSE 'NG'
                END AS assert
           FROM results AS res
           JOIN test_data AS td USING(case_id)
;

結果

 case_id | result  | expected | assert
---------+---------+----------+------
 /*00*/  | DEFGH   | DEFGH    | .
 /*01*/  | CDEFGH  | CDEFGH   | .
 /*02*/  | ABDEFGH | ABDEFGH  | .
 /*03*/  | AGH     | AGH      | .
 /*04*/  | ABCDH   | ABCDH    | .
 /*05*/  | ADEFG   | ADEFG    | .
 /*06*/  | AEFGH   | AEFGH    | .
 /*07*/  | ABDEFGH | ABDEFGH  | .
 /*08*/  | ABCFGH  | ABCFGH   | .
 /*09*/  | ABCEFGH | ABCEFGH  | .
 /*10*/  | ACDEFH  | ACDEFH   | .
 /*11*/  | BCDEFH  | BCDEFH   | .
 /*12*/  | ABCDEH  | ABCDEH   | .
 /*13*/  | ABFGH   | ABFGH    | .
 /*15*/  | CEF     | CEF      | .
 /*16*/  | ABCDEH  | ABCDEH   | .
 /*17*/  | BDE     | BDE      | .
 /*18*/  | FGH     | FGH      | .
 /*19*/  | CFG     | CFG      | .
 /*20*/  | BCDEF   | BCDEF    | .
 /*21*/  | ABGH    | ABGH     | .
 /*22*/  | ABCG    | ABCG     | .
 /*23*/  | EG      | EG       | .
 /*25*/  | DGH     | DGH      | .
 /*26*/  | DEF     | DEF      | .
 /*27*/  | CDF     | CDF      | .
 /*28*/  | BCD     | BCD      | .
 /*29*/  | G       | G        | .
 /*30*/  | A       | A        | .
(29 rows)

解説

test_data

 WITH RECURSIVE test_data(case_id, actual, expected) AS (
         VALUES ('/*00*/', '2512:C', 'DEFGH'),
                ('/*01*/', '1:A', 'CDEFGH'),
                ('/*02*/', ':C', 'ABDEFGH'),
                ('/*03*/', '2345:B', 'AGH'),
                ('/*04*/', '1256:E', 'ABCDH'),
                ('/*05*/', '1228:A', 'ADEFG'),
                ('/*06*/', '5623:B', 'AEFGH'),
                ('/*07*/', '8157:C', 'ABDEFGH'),
                ('/*08*/', '74767:E', 'ABCFGH'),
                ('/*09*/', '88717:D', 'ABCEFGH'),
                ('/*10*/', '148647:A', 'ACDEFH'),
                ('/*11*/', '374258:H', 'BCDEFH'),
                ('/*12*/', '6647768:F', 'ABCDEH'),
                ('/*13*/', '4786317:E', 'ABFGH'),
                ('/*14*/', '3456781:C', ''),
                ('/*15*/', '225721686547123:C', 'CEF'),
                ('/*16*/', '2765356148824666:F', 'ABCDEH'),
                ('/*17*/', '42318287535641783:F', 'BDE'),
                ('/*18*/', '584423584751745261:D', 'FGH'),
                ('/*19*/', '8811873415472513884:D', 'CFG'),
                ('/*20*/', '74817442725737422451:H', 'BCDEF'),
                ('/*21*/', '223188865746766511566:C', 'ABGH'),
                ('/*22*/', '2763666483242552567747:F', 'ABCG'),
                ('/*23*/', '76724442325377753577138:E', 'EG'),
                ('/*24*/', '327328486656448784712618:B', ''),
                ('/*25*/', '4884637666662548114774288:D', 'DGH'),
                ('/*26*/', '84226765313786654637511248:H', 'DEF'),
                ('/*27*/', '486142154163288126476238756:A', 'CDF'),
                ('/*28*/', '1836275732415226326155464567:F', 'BCD'),
                ('/*29*/', '62544434452376661746517374245:G', 'G'),
                ('/*30*/', '381352782758218463842725673473:B', 'A')

• SQL 見たままの共通表が出来る

 case_id |              actual              | expected
---------+----------------------------------+----------
 /*00*/  | 2512:C                           | DEFGH
 /*01*/  | 1:A                              | CDEFGH
 /*02*/  | :C                               | ABDEFGH
 /*03*/  | 2345:B                           | AGH
 /*04*/  | 1256:E                           | ABCDH
 /*05*/  | 1228:A                           | ADEFG
 /*06*/  | 5623:B                           | AEFGH
 /*07*/  | 8157:C                           | ABDEFGH
 /*08*/  | 74767:E                          | ABCFGH
 /*09*/  | 88717:D                          | ABCEFGH
 /*10*/  | 148647:A                         | ACDEFH
 /*11*/  | 374258:H                         | BCDEFH
 /*12*/  | 6647768:F                        | ABCDEH
 /*13*/  | 4786317:E                        | ABFGH
 /*14*/  | 3456781:C                        |
 /*15*/  | 225721686547123:C                | CEF
 /*16*/  | 2765356148824666:F               | ABCDEH
 /*17*/  | 42318287535641783:F              | BDE
 /*18*/  | 584423584751745261:D             | FGH
 /*19*/  | 8811873415472513884:D            | CFG
 /*20*/  | 74817442725737422451:H           | BCDEF
 /*21*/  | 223188865746766511566:C          | ABGH
 /*22*/  | 2763666483242552567747:F         | ABCG
 /*23*/  | 76724442325377753577138:E        | EG
 /*24*/  | 327328486656448784712618:B       |
 /*25*/  | 4884637666662548114774288:D      | DGH
 /*26*/  | 84226765313786654637511248:H     | DEF
 /*27*/  | 486142154163288126476238756:A    | CDF
 /*28*/  | 1836275732415226326155464567:F   | BCD
 /*29*/  | 62544434452376661746517374245:G  | G
 /*30*/  | 381352782758218463842725673473:B | A
(31 rows)

labels

             ), labels AS (
         SELECT row_number() over() AS way_no
              , label
           FROM (VALUES('A'), ('B'), ('C'), ('D')
                     , ('E'), ('F'), ('G'), ('H')) AS t(label)

• こちらも見たままの共通表
• label は８方向のそれぞれの名前

 way_no | label
--------+-------
      1 | A
      2 | B
      3 | C
      4 | D
      5 | E
      6 | F
      7 | G
      8 | H
(8 rows)

sideways

             ), sideways AS (
         SELECT t.way_no
              , string_agg(label, '' ORDER BY label) AS sideway
           FROM labels
           JOIN generate_series(1, 8) AS t(way_no)
             ON labels.way_no = t.way_no
             OR labels.way_no = (t.way_no + 1) % 8
             OR (labels.way_no = 8 AND t.way_no = 7)
       GROUP BY 1
       ORDER BY 1

• A から H がそれぞれ隣り合う方角を繋ぐ横道を列挙する
• 横道番号(way_no) が 1 なら AB, 2 なら BC, 8 なら AH といった具合

 way_no | sideway
--------+---------
      1 | AB
      2 | BC
      3 | CD
      4 | DE
      5 | EF
      6 | FG
      7 | GH
      8 | AH
(8 rows)

start_directions

             ), start_directions AS (
         SELECT case_id
              , SPLIT_PART(actual, ':', 2) AS start_dir
           FROM test_data

• 各テストケースについて、石が落ち始める方角

 case_id | start_dir
---------+-----------
 /*00*/  | C
 /*01*/  | A
 /*02*/  | C
 /*03*/  | B
 /*04*/  | E
 /*05*/  | A
 /*06*/  | B
 /*07*/  | C
 /*08*/  | E
 /*09*/  | D
 /*10*/  | A
 /*11*/  | H
 /*12*/  | F
 /*13*/  | E
 /*14*/  | C
 /*15*/  | C
 /*16*/  | F
 /*17*/  | F
 /*18*/  | D
 /*19*/  | D
 /*20*/  | H
 /*21*/  | C
 /*22*/  | F
 /*23*/  | E
 /*24*/  | B
 /*25*/  | D
 /*26*/  | H
 /*27*/  | A
 /*28*/  | F
 /*29*/  | G
 /*30*/  | B
(31 rows)

way_numbers

             ), way_numbers AS (
         SELECT case_id
              , UNNEST(
                    REGEXP_SPLIT_TO_ARRAY(
                        SPLIT_PART(actual, ':', 1),
                        ''
                    )
                ) AS way_no
           FROM test_data

• テストケース毎に山頂から順に横道番号を列挙
• 文字列から配列に分割して、UNNEST で行に展開する

 case_id | way_no
---------+--------
 /*00*/  | 2
 /*00*/  | 5
 /*00*/  | 1
 /*00*/  | 2
 /*01*/  | 1
 /*02*/  |
 /*03*/  | 2
 /*03*/  | 3
 /*03*/  | 4
 /*03*/  | 5
 /*04*/  | 1
 /*04*/  | 2
 /*04*/  | 5
 /*04*/  | 6
  ...(省略)...
 /*30*/  | 8
 /*30*/  | 4
 /*30*/  | 2
 /*30*/  | 7
 /*30*/  | 2
 /*30*/  | 5
 /*30*/  | 6
 /*30*/  | 7
 /*30*/  | 3
 /*30*/  | 4
 /*30*/  | 7
 /*30*/  | 3
(429 rows)

way_numbers_with_order

             ), way_numbers_with_order AS (
         SELECT way_numbers.case_id
              , ROW_NUMBER() OVER(PARTITION BY case_id) AS "order"
              , CASE
                WHEN LENGTH(way_numbers.way_no) = 0
                THEN NULL
                ELSE way_numbers.way_no::INTEGER
                END AS way_no
           FROM way_numbers

• 横道番号に山頂から数えた連番を付与
• 横道番号を TEXT から INTEGER に変換
• ついでに空文字の横道番号を NULL に変換

 case_id | order | way_no
---------+-------+--------
 /*00*/  |     1 |      2
 /*00*/  |     2 |      5
 /*00*/  |     3 |      1
 /*00*/  |     4 |      2
 /*01*/  |     1 |      1
 /*02*/  |     1 |
 /*03*/  |     1 |      2
 /*03*/  |     2 |      3
 /*03*/  |     3 |      4
 /*03*/  |     4 |      5
 /*04*/  |     1 |      1
 /*04*/  |     2 |      2
 /*04*/  |     3 |      5
 /*04*/  |     4 |      6
 /*05*/  |     1 |      1
 ...(省略)...
 /*30*/  |    19 |      8
 /*30*/  |    20 |      4
 /*30*/  |    21 |      2
 /*30*/  |    22 |      7
 /*30*/  |    23 |      2
 /*30*/  |    24 |      5
 /*30*/  |    25 |      6
 /*30*/  |    26 |      7
 /*30*/  |    27 |      3
 /*30*/  |    28 |      4
 /*30*/  |    29 |      7
 /*30*/  |    30 |      3
(429 rows)

danger_ways

             ), danger_ways AS (
         SELECT case_id
              , "order"
              , sideway
           FROM way_numbers_with_order AS wnwo
LEFT OUTER JOIN sideways AS sw
             ON wnwo.way_no = sw.way_no

• 横道番号と具体的な道の内容を導出
• これ、名前をミスってて、これらの道はまだ danger ではない

 case_id | order | sideway
---------+-------+---------
 /*00*/  |     1 | BC
 /*00*/  |     2 | EF
 /*00*/  |     3 | AB
 /*00*/  |     4 | BC
 /*01*/  |     1 | AB
 /*02*/  |     1 |
 /*03*/  |     1 | BC
 /*03*/  |     2 | CD
 /*03*/  |     3 | DE
 /*03*/  |     4 | EF
 /*04*/  |     1 | AB
 /*04*/  |     2 | BC
 /*04*/  |     3 | EF
 /*04*/  |     4 | FG
 /*05*/  |     1 | AB
 ...(省略)...
 /*30*/  |    21 | BC
 /*30*/  |    22 | GH
 /*30*/  |    23 | BC
 /*30*/  |    24 | EF
 /*30*/  |    25 | FG
 /*30*/  |    26 | GH
 /*30*/  |    27 | CD
 /*30*/  |    28 | DE
 /*30*/  |    29 | GH
 /*30*/  |    30 | CD
(429 rows)

danger_ways_detail

             ), danger_ways_detail AS (
         SELECT case_id
              , 0::BIGINT AS "order"
              , NULL AS sideway
              , start_dir AS cur_dir
           FROM start_directions

          UNION

         SELECT dwd.case_id
              , dw."order"
              , CASE
                WHEN dw.sideway ~ dwd.cur_dir
                THEN dw.sideway
                ELSE NULL
                END AS sideway
              , CASE
                WHEN dw.sideway ~ dwd.cur_dir
                THEN REGEXP_REPLACE(dw.sideway, dwd.cur_dir, '')
                ELSE dwd.cur_dir
                END AS cur_dir
           FROM danger_ways_detail AS dwd
LEFT OUTER JOIN danger_ways AS dw
             ON dwd.case_id = dw.case_id
            AND dwd."order" + 1 = dw."order"

• order 0 (山頂) から横道番号を１つずつ増やして sideway を発見したら cur_dir を変える
• 再帰的に最後の order まで繋げたら終了
• order のいくつ目でどの横道に入ったのか分かる

 case_id | order | sideway | cur_dir
---------+-------+---------+---------
 /*00*/  |     0 |         | C
 /*00*/  |     1 | BC      | B
 /*00*/  |     2 |         | B
 /*00*/  |     3 | AB      | A
 /*00*/  |     4 |         | A
 /*00*/  |       |         | A
 /*01*/  |     0 |         | A
 /*01*/  |     1 | AB      | B
 /*01*/  |       |         | B
 /*02*/  |     0 |         | C
 /*02*/  |     1 |         | C
 /*02*/  |       |         | C
 /*03*/  |     0 |         | B
 /*03*/  |     1 | BC      | C
 /*03*/  |     2 | CD      | D
 /*03*/  |     3 | DE      | E
 /*03*/  |     4 | EF      | F
 /*03*/  |       |         | F
  ...(省略)...
 /*30*/  |    14 |         | G
 /*30*/  |    15 |         | G
 /*30*/  |    16 |         | G
 /*30*/  |    17 | FG      | F
 /*30*/  |    18 |         | F
 /*30*/  |    19 |         | F
 /*30*/  |    20 |         | F
 /*30*/  |    21 |         | F
 /*30*/  |    22 |         | F
 /*30*/  |    23 |         | F
 /*30*/  |    24 | EF      | E
 /*30*/  |    25 |         | E
 /*30*/  |    26 |         | E
 /*30*/  |    27 |         | E
 /*30*/  |    28 | DE      | D
 /*30*/  |    29 |         | D
 /*30*/  |    30 | CD      | C
 /*30*/  |       |         | C
(491 rows)

routes

             ), routes AS (
         SELECT case_id
              , label
           FROM test_data
     CROSS JOIN labels
       ORDER BY 1, 2

• テストケース毎に A から H までを生成

 case_id | label
---------+-------
 /*00*/  | A
 /*00*/  | B
 /*00*/  | C
 /*00*/  | D
 /*00*/  | E
 /*00*/  | F
 /*00*/  | G
 /*00*/  | H
 /*01*/  | A
 ...(省略)...
 /*29*/  | H
 /*30*/  | A
 /*30*/  | B
 /*30*/  | C
 /*30*/  | D
 /*30*/  | E
 /*30*/  | F
 /*30*/  | G
 /*30*/  | H
(248 rows)

routes_by_case

             ), routes_by_case AS (
         SELECT case_id
              , label
              , 0::BIGINT AS order
              , NULL AS sideway
              , label AS cur_dir
           FROM routes

          UNION

         SELECT rbc.case_id
              , rbc.label
              , sideways."order"
              , CASE
                WHEN sideways.sideway ~ rbc.cur_dir
                THEN sideways.sideway
                ELSE NULL
                END AS sideway
              , CASE
                WHEN sideways.sideway ~ rbc.cur_dir
                THEN REGEXP_REPLACE(sideways.sideway, rbc.cur_dir, '')
                ELSE rbc.cur_dir
                END AS cur_dir
           FROM routes_by_case AS rbc
LEFT OUTER JOIN (
         SELECT ROW_NUMBER() OVER(
                    PARTITION BY case_id ORDER BY "order" DESC
                ) AS "order"
              , case_id
              , sideway
           FROM danger_ways
              ) AS sideways
             ON rbc.case_id = sideways.case_id
            AND rbc."order" + 1 = sideways."order"

• テストケース毎に麓から登っていく際に入る横道を列挙していく

 case_id | label | order | sideway | cur_dir
---------+-------+-------+---------+---------
 /*00*/  | A     |     0 |         | A
 /*00*/  | A     |     1 |         | A
 /*00*/  | A     |     2 | AB      | B
 /*00*/  | A     |     3 |         | B
 /*00*/  | A     |     4 | BC      | C
 /*00*/  | A     |       |         | C
 /*00*/  | B     |     0 |         | B
 /*00*/  | B     |     1 | BC      | C
 /*00*/  | B     |     2 |         | C
 /*00*/  | B     |     3 |         | C
 /*00*/  | B     |     4 | BC      | B
 /*00*/  | B     |       |         | B
 /*00*/  | C     |     0 |         | C
 /*00*/  | C     |     1 | BC      | B
 ...(省略)...
 /*30*/  | H     |    18 |         | F
 /*30*/  | H     |    19 |         | F
 /*30*/  | H     |    20 | EF      | E
 /*30*/  | H     |    21 |         | E
 /*30*/  | H     |    22 |         | E
 /*30*/  | H     |    23 |         | E
 /*30*/  | H     |    24 |         | E
 /*30*/  | H     |    25 |         | E
 /*30*/  | H     |    26 | EF      | F
 /*30*/  | H     |    27 |         | F
 /*30*/  | H     |    28 |         | F
 /*30*/  | H     |    29 |         | F
 /*30*/  | H     |    30 |         | F
 /*30*/  | H     |       |         | F
(3928 rows)

dead_directions

              ), dead_directions AS (
         SELECT t.case_id
              , sd.start_dir AS dead_direction
           FROM (
         SELECT case_id
              , SUM(CASE
                    WHEN sideway IS NULL THEN 0
                    ELSE 1
                    END)AS way_count
           FROM danger_ways_detail
       GROUP BY 1
       ORDER BY 1) AS t
LEFT OUTER JOIN start_directions AS sd
             ON t.case_id = sd.case_id
            AND t.way_count = 0
          WHERE sd.start_dir IS NOT NULL

• 山頂から落ちる石が一度も横道に入らない場合、石が落ち始めた方向が潰される
• 横道数が 0 の場合にのみ start_dir が dead_direction として残る

 case_id | dead_direction
---------+----------------
 /*02*/  | C
 /*07*/  | C
 /*09*/  | D
(3 rows)

dead_or_alive

             ), dead_or_alive AS (
         SELECT case_id
              , "order"
              , label
              , routes_by_case.sideway
              , dwd.sideway
              , CASE
                WHEN routes_by_case.sideway = dwd.sideway
                THEN '死'
                ELSE '生'
                END AS judge
           FROM routes_by_case
           JOIN (

             SELECT case_id
                  , ROW_NUMBER() OVER(
                        PARTITION BY case_id ORDER BY "order" desc
                    ) AS "order"
                  , sideway
               FROM danger_ways_detail
              WHERE "order" <> 0 AND "order" IS NOT NULL

              ) AS dwd
          USING (case_id, "order")
       ORDER BY 1, 3, 2

• ケース毎方向毎のルートと、山頂からの岩のルートを逆にしたものを JOIN する
• 同じ横道に入っている場合は '死' 判定される
• ケース、方向、横道番号毎の判定が得られる

 case_id | order | label | sideway | sideway | judge
---------+-------+-------+---------+---------+-------
 /*00*/  |     1 | A     |         |         | 生
 /*00*/  |     2 | A     | AB      | AB      | 死
 /*00*/  |     3 | A     |         |         | 生
 /*00*/  |     4 | A     | BC      | BC      | 死
 /*00*/  |     1 | B     | BC      |         | 生
 /*00*/  |     2 | B     |         | AB      | 生
 /*00*/  |     3 | B     |         |         | 生
 /*00*/  |     4 | B     | BC      | BC      | 死
 /*00*/  |     1 | C     | BC      |         | 生
 /*00*/  |     2 | C     | AB      | AB      | 死
 /*00*/  |     3 | C     |         |         | 生
 /*00*/  |     4 | C     |         | BC      | 生
 ...(省略)...
 /*30*/  |    16 | H     |         |         | 生
 /*30*/  |    17 | H     |         |         | 生
 /*30*/  |    18 | H     |         |         | 生
 /*30*/  |    19 | H     |         |         | 生
 /*30*/  |    20 | H     | EF      |         | 生
 /*30*/  |    21 | H     |         | GH      | 生
 /*30*/  |    22 | H     |         |         | 生
 /*30*/  |    23 | H     |         | AH      | 生
 /*30*/  |    24 | H     |         |         | 生
 /*30*/  |    25 | H     |         |         | 生
 /*30*/  |    26 | H     | EF      |         | 生
 /*30*/  |    27 | H     |         |         | 生
 /*30*/  |    28 | H     |         | AB      | 生
 /*30*/  |    29 | H     |         |         | 生
 /*30*/  |    30 | H     |         |         | 生
(3432 rows)

results

             ), results AS (
         SELECT t.case_id
              , STRING_AGG(label, '' ORDER BY LABEL) as "result"
           FROM (
         SELECT case_id
              , label
              , MIN(judge) AS judge
           FROM dead_or_alive
       GROUP BY 1, 2
       ORDER BY 1, 2) AS t
LEFT OUTER JOIN dead_directions AS dd
             ON dd.case_id = t.case_id
            AND dd.dead_direction = t.label
          WHERE dd.dead_direction IS NULL
            AND t.judge = '生'
       GROUP BY 1)

• '生' と '死' を MIN() すると、'死' がある場合には '死' が返ってくる
• dead_directions を JOIN して、岩が横道に行かない場合を合流させる
• dead_direction が無く、かつ判定が '生' の方角のラベルを結合する

 case_id | result
---------+---------
 /*00*/  | DEFGH
 /*01*/  | CDEFGH
 /*02*/  | ABDEFGH
 /*03*/  | AGH
 /*04*/  | ABCDH
 /*05*/  | ADEFG
 /*06*/  | AEFGH
 /*07*/  | ABDEFGH
 /*08*/  | ABCFGH
 /*09*/  | ABCEFGH
 /*10*/  | ACDEFH
 /*11*/  | BCDEFH
 /*12*/  | ABCDEH
 /*13*/  | ABFGH
 /*15*/  | CEF
 /*16*/  | ABCDEH
 /*17*/  | BDE
 /*18*/  | FGH
 /*19*/  | CFG
 /*20*/  | BCDEF
 /*21*/  | ABGH
 /*22*/  | ABCG
 /*23*/  | EG
 /*25*/  | DGH
 /*26*/  | DEF
 /*27*/  | CDF
 /*28*/  | BCD
 /*29*/  | G
 /*30*/  | A
(29 rows)