Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
16
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

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

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

問題

解答

 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 は8方向のそれぞれの名前
 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 (山頂) から横道番号を1つずつ増やして 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)
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
16
Help us understand the problem. What are the problem?