AdventOfCode 2023 Day 13

作者

Day 13: Point of Incidence

Part One

第一关是找出导致镜像的镜子位置，下面的例子，镜子出现在5/6列之间。

#.##..##.
..#.##.#.
##......#

分两种情况考虑，行镜像以及列镜像

列镜像

先分别求出镜像的左侧字符串与右侧字符串，再对比reverse转换之后的字符串是否相等即可

  SELECT blank._row, v.id, 
         case when v.id <= length(line) / 2 then substring(line from 1 for v.id) else substring(line from 2 * v.id - length(line) + 1 for length(line) - v.id) end as l_str,
         case when v.id <= length(line) / 2 then substring(line from v.id + 1 for v.id) else substring(line from v.id + 1 for length(line)) end as r_str
  FROM origin, blank, 
      (select id from seq limit (select max(length(line)) from origin)) v
  WHERE origin._row > blank.pre_row
  AND origin._row < blank._row
  AND v.id < length(line)
  ) t
  GROUP BY _row, id
  HAVING COUNT(case when l_str = reverse(r_str) then 1 end) = COUNT(*)

行镜像

行镜像比较简单，仅需直接对比字符串即可，需要自关联找出镜像的那一行字符串。

  SELECT blank._row, h.id - blank.pre_row as id, origin.line as up, mirror.line as down
  FROM origin 
  JOIN blank
  ON origin._row > blank.pre_row
  AND origin._row < blank._row
  JOIN (select id from seq limit (select max(_row) from origin)) h
  ON h.id > blank.pre_row
  AND h.id < blank._row - 1
  AND origin._row <= h.id
  LEFT JOIN origin as mirror
  ON mirror._row = (case when 2 * h.id - origin._row + 1 < blank._row then 2 * h.id - origin._row + 1 end)
  ) t
  GROUP BY _row, id
  HAVING COUNT(case when up = down OR down is null then 1 end) = COUNT(*)

最终SQL

WITH RECURSIVE origin AS (
  SELECT row_number() over () as _row, line
  FROM (
    SELECT line
    FROM lance_input
    UNION ALL
    SELECT null
  ) t
), blank AS (
  SELECT case when pre_row is null then 0 else pre_row end as pre_row, _row
  FROM (
    SELECT lag(_row) over () as pre_row, _row
    FROM origin
    WHERE line is null
  ) t
), seq AS (
  SELECT 1 as id
  UNION ALL
  SELECT id + 1 as id
  FROM seq
)
SELECT SUM(id)
FROM (
  SELECT _row, id
  FROM (
  SELECT blank._row, v.id, 
         case when v.id <= length(line) / 2 then substring(line from 1 for v.id) else substring(line from 2 * v.id - length(line) + 1 for length(line) - v.id) end as l_str,
         case when v.id <= length(line) / 2 then substring(line from v.id + 1 for v.id) else substring(line from v.id + 1 for length(line)) end as r_str
  FROM origin, blank, 
      (select id from seq limit (select max(length(line)) from origin)) v
  WHERE origin._row > blank.pre_row
  AND origin._row < blank._row
  AND v.id < length(line)
  ) t
  GROUP BY _row, id
  HAVING COUNT(case when l_str = reverse(r_str) then 1 end) = COUNT(*)

  UNION ALL

  SELECT _row, id * 100
  FROM (
  SELECT blank._row, h.id - blank.pre_row as id, origin.line as up, mirror.line as down
  FROM origin 
  JOIN blank
  ON origin._row > blank.pre_row
  AND origin._row < blank._row
  JOIN (select id from seq limit (select max(_row) from origin)) h
  ON h.id > blank.pre_row
  AND h.id < blank._row - 1
  AND origin._row <= h.id
  LEFT JOIN origin as mirror
  ON mirror._row = (case when 2 * h.id - origin._row + 1 < blank._row then 2 * h.id - origin._row + 1 end)
  ) t
  GROUP BY _row, id
  HAVING COUNT(case when up = down OR down is null then 1 end) = COUNT(*)
) s

Part Two

第二关，通过修改一个字符，从而找出另一个潜在的镜子。如下面的例子，之前的镜子出现在2/3列之间。如果修改了5行第一个字符，则镜子出现在1/2列之间。

....##.
#####..
.....#.
....###
#..####
####...
....###

过滤条件

之前的条件，是镜像的列或者行全部相同，因此过滤条件是

# 列镜像
HAVING COUNT(case when l_str = reverse(r_str) then 1 end) = COUNT(*)

# 行镜像
HAVING COUNT(case when up = down OR down is null then 1 end) = COUNT(*)

现在的条件，是修改一个字符后，同样实现镜像，那么过滤条件应该修改为如下，即只差一行/列就完全一致

# 列镜像
HAVING COUNT(case when l_str = reverse(r_str) then 1 end) + 1 = COUNT(*)

# 行镜像
HAVING COUNT(case when up = down OR down is null then 1 end) + 1 = COUNT(*)

Levenshtein Distance

但是仅仅这个条件是不够的，不匹配的那一行/列，应该只差一个字符。因此需要使用到levenshtein distance，求出两个字符串的差异度。

test=# SELECT levenshtein('GUMBO', 'GAMBOL');
 levenshtein
-------------
           2
(1 row)

最终SQL

WITH RECURSIVE origin AS (
  SELECT row_number() over () as _row, line
  FROM (
    SELECT line
    FROM lance_input
    UNION ALL
    SELECT null
  ) t
), blank AS (
  SELECT case when pre_row is null then 0 else pre_row end as pre_row, _row
  FROM (
    SELECT lag(_row) over () as pre_row, _row
    FROM origin
    WHERE line is null
  ) t
), seq AS (
  SELECT 1 as id
  UNION ALL
  SELECT id + 1 as id
  FROM seq
)
SELECT sum(id) from (
  SELECT _row, id, SUM(levenshtein(l_str, reverse(r_str))) as levenshtein_distance
  FROM (
  SELECT blank._row, v.id, length(line) as len ,
         case when v.id <= length(line) / 2 then substring(line from 1 for v.id) else substring(line from 2 * v.id - length(line) + 1 for length(line) - v.id) end as l_str,
         case when v.id <= length(line) / 2 then substring(line from v.id + 1 for v.id) else substring(line from v.id + 1 for length(line)) end as r_str
  FROM origin, blank, 
      (select id from seq limit (select max(length(line)) from origin)) v
  WHERE origin._row > blank.pre_row
  AND origin._row < blank._row
  AND v.id < length(line)
  ) t
  GROUP BY _row, len, id
  HAVING COUNT(case when l_str = reverse(r_str) then 1 end) + 1 = COUNT(*)


  UNION ALL

  SELECT _row, id * 100, SUM(levenshtein(up, down)) as levenshtein_distance
  FROM (
  SELECT blank._row, blank._row - blank.pre_row - 1 as lines, h.id - blank.pre_row as id, origin.line as up, mirror.line as down
  FROM origin 
  JOIN blank
  ON origin._row > blank.pre_row
  AND origin._row < blank._row
  JOIN (select id from seq limit (select max(_row) from origin)) h
  ON h.id > blank.pre_row
  AND h.id < blank._row - 1
  AND origin._row <= h.id
  LEFT JOIN origin as mirror
  ON mirror._row = (case when 2 * h.id - origin._row + 1 < blank._row then 2 * h.id - origin._row + 1 end)
  ) t
  GROUP BY _row, lines, id
  HAVING COUNT(case when up = down OR down is null then 1 end) + 1 = COUNT(*)
) t where levenshtein_distance = 1

发表评论