# Copyright Materialize, Inc. and contributors. All rights reserved. # # Use of this software is governed by the Business Source License # included in the LICENSE file at the root of this repository. # # As of the Change Date specified in that file, in accordance with # the Business Source License, use of this software will be governed # by the Apache License, Version 2.0. # https://github.com/MaterializeInc/advent-of-code-2023/blob/main/week1/aoc_1210.md mode cockroach statement ok CREATE TABLE input (input TEXT); statement ok INSERT INTO input VALUES ( 'SJJL|-.LFSS.S-|7-L-L-L|F7FS|J.LL-.|J.L7SJ|.J-7F..-S7|7SFSSSJLLJ|-..L..J-L7JJS.J-7-LJ-|.J7||.LF.7.7SF7LL-.|7-7F77|LFJFSS77JF.S.|.-F J..-.--S|SL.|S.7L7-|SFL.FJF7L-LJ-SFL|L|--F.-FS|7.LJLJ.-.|LF|J.L-JJJ7F|S..FSSSLL-F.-FFL7-7LLLFJ.LFSSJFF7F.7F|F7LJ|F||L7.7.7|7-|J77S JL7|JSJ|FLLSLFF|-7JSJSJFL|L.J|||J-S.S..|-SF-|----JS.-J|JJ.|-F||.FL..JLL7.-LJ7FSJFL..|F7JJJ|LLJFFJJFLL7.LJJJF--FFLS-|LLLS-..-|S|J7F |JFF-L|F7|.F.L7J-7F-.LSF7J-|S7|FLS--JF.SF.S.S.LSLL..F7.SS7L|7J|.---|7JL|7SLL|SS.JLLL|L.7..JL||JL|JL.S777.|-JSSL|S.7JJFLJ.SJ-.|L|FJ 7|L-S7|JFL.SJ7FL|.LLJ.F7SF-.-SL77-FJ7S-J|SS-|L-J|J.7F|.7.S.LS-|.JJJ|.S|.|777-LJ-.J.7-LSSL|SJ.J.-F.-LSS-SJ.LL|S7|FJL77.FFFJJ.-LS-|- SJ.-|..-LF7-FS.S|7F|LJ--SS-SFFF||S7|FF.7..F7|JFJJJ--7JLS||S7J--J-JF-|7SFJ|7.||||7LS|-..FJ.|S77JF.F77L.|.-F.L.-J-FL-JFL-|.S.LJ|J.L7 FF7F-.7.-LS-FF.--LL.|.7L-J7FS-.F--S7.LJLL.-7FF|7J7L..S7LJL7-JLF-S7JJ|-LS7S-|JLF7LFSJSF7L-F.7S-|7S-.F||.J.-F|-SJL|SFF7|-|F--||7LJ7F S.J7L.F|S-.F|FSJ|--|L.JS77JL7.SS7|FJFFF-F|.SF7LL.JFL7SJJLL|LLSS.L|F.|F-|S|JJ--FJLFJJ7..77.S|LJFJJS.-7S-LJ|L|S-J|FLLLJFSSFS.J-FS|LJ SF.77J-L-7|FF-J-77-L-F|J.|F.J7SJL..SF||S77.7J|J.L-|-7L-JSJ.S.-FL-F7FL|SSFS7-|S-.L.FF-L-F..J-FS77.JJ-SF7SS--.JLLSJ.F7LS.JS|..J|J|7S J|L-7|77|-F-SF7-..7|.77L7.LJLLL..LSJFLJ|-|L7|-S||||F|LLF77-LF||-|S.JL.|.LF7S7.FFF--SFF.-J-F.F7JJ.7JLJ-7S-LLSFLJ7.-JF.SSLLSSSJSSF7. .|.L.|.|FJ.L||.77L-SJ.|F7-.L7LJ7LJ||.SJF-.||SF..L|JSL.-S.SFLSJLJ7S-FFFJ7F.J-L...|LFLF-SSLS7F|7J.-.F||.|L|JLJ|LJ...FSJ||---7|.--LF. LFJ|7L|S||..J|7S..J--.77F7-7F.S-J777.||FFL|.|-FJSSFFLSJ.|J-.JS-FSS.|F7.S.SJ-JJS.-S|LJJ-JLJS-7SSF7JS7.|J77-JS7J.F|JFFF|S-F||SS.|LFF FJ-|F7.F-LLF-.J7LS|LJSSF|.7S||-F|7S.J.|JSJLLJF-LS|SFJ7LL7SSS7S.S-|.S7||SLFSLFL|.LJ-S77|L|F|S-.7F7F.JJ-FL|J7S.7J.FJ7S|JJ|L7F7F|S|.| ..JF.-L|JFL-FS|FJ77..S|-SLFLL7||SL|-L-.|.7JLF7J--7J-7S7L77JLJFS.J.7..7S7F7|S7|.LFLJS-.L|LS7FJFL-L-L-7S77-LJ-.JFFJ.J7L.FJSJLFSJ|L7F FFLS|-S.|F|SLFL|SF|JLS|FFFSJLJ|F.J|LSJJ7FS|LL7-.J-LFJ|7JJ.7|J.-JF.L...LS7LFJJF7JJ.L...|S..-7.-S.JFLLSLFS|JFJ-.L|L.L7FSJ.|LFL-F7F.7 SJ-7LS7.-FL|F.FJ|7|SJL7-J77L-FF.F-|7-|7JL.SF7|FSL-J|.LL.|.7LSJS||7SL7.7.JSFFJFS-7.LLLS..7L.SFFJ--|-SFF7||SJS-7|-|J-.SSJ|.77.|-L.F- .LJJ-L7.---.S-7.7|FS..SJ|SLJ|FS|SLLLFJ7.F-F7LL7S-S-JF.7F7LL-J-.|L|-|-.L.7SSS|SL||-|JFFL.J7SJSF.F.F7S|FL--LLJ-L.SJ.LLJLLFS7J-.|FJ.J JSFLJ|.JJFFLF|F|LJ||L7-J7JS.|LL7JSFSJJSSLFJ7|L.FJJLL-FFLSS.FJ-.SSSLLJL777FL.-..7SF-.-.SFF-.J7F|JJS---L|.L|-.FSJ-||S-LJFS.S7|J-7J-S L77SLFJ7FJ.|-|.|7LJS7LL.-7.LFJLSFJ|S-FJ..LJ.7-SJ-|LJ77|JFLSF|.SJ.|L--L|S7-SS.-.F-JS--|SLS-SS-F77LF..JS-FJF.SJ7.FJ|-SF-LSLL||J.|-.7 .-S|S--FSJ--7|F7-L|-SS-JL|FLFFJL7-FJJSJS7SJL7.SS|S|.LLSS7FS-.J-JSF.|777--7.|J|7S|.L|L|SL|SSF|7L.F|JF.FJ--.J-|S.S.SSS..SL-|S.S.L|-J 7JSJ7|J7--LSS|7SLFSJ-.SF-|77||....7.L7J|7|7|.-.LJ..LSJ7|SFLSFJF|JFL7F|7|LJFJ7|LJSSJ.7-|7JSJL.J|F.|.J7-F7-F|-S.-LS-.-JS.SSS|JLS||F- SJL.LL7JJS-S|-SF-LS.7FL-F7L|F7.SFFF7J77-SLF|.LFFLLSS7S|----SLL7FL7||LFFSJLF-.|7F--JF7..JL---S.SSSJF|SLSJ.-L|LFJJL-7S-7FF--SL||FLSL F7S.|7SL-|.F|.L.-.7L|LLL-L7SJL-JJJ|J-FJLSLF7F7JFJ7.FL|7J.7F.|.JSL.|L7S---.F-.-.FSL|LLSFLF|7.7-|J7-|-7..-SJF-|S|J7LL7FSJ|F.7JJF.7|J S.L|SL|JF..SLJL|S.F7-||77LLFJ.S|S-LL.J-7|FF-SJJJL|J.FLJLL7JFFJ..FFJLSSSS-|-77-S-.F777--|S.---.F-SLL|S7S7SJLSF-S.-|LJ7-L--7..-|.7L. F.|7.-JL|7L.JFF|LLLJF-S7F|LF-7LL|7|.J-S..S|FFJ7.FSL.|-LJ-|JLLL.LLL-7-F-|L-L-|.77SJSF-SF7.SFJL|.F|.SS..FL7L.7FSL7SL7SJSSFSS|SF.-F77 .SLL.JL|L.77S.77L|SJF..FL|-F.S-SS.7SS-LLFS|L.S7J7L|F|L-7|JJ-77SF-77|LFLSF7LJFS||LJJ|J7.-LFF-L.|LF.LS|J-.LJ|J.L|--J7.S.-L.-LFF7F77- --J-.SL--L7JJSFJLJS.FL.7-F7-SJS.L.S.LF|7J-|77FS|-J-|S.FSLS.7.J|J.LLF-LL.S--7S.-LSS|JLJF.S|.F7SLSS.L-L.|F-JL|LFS-S.J77-L7.|7|S|.S.| 7SJS-|F-.F...LFSJFLFLFFFJ||JL--J|S.LJ-LL|7S-FF-J.7F.JJ|L-.JF7J|L|S-.LJ|S.SFSLLS.L7SJFSJ.SL--L|F.S.SLS.|S.-..7F7|LSF|SJFS7FJ7S|J.-J 7...J.L--7S-SF.LSJ7JLJFL7LFFLJ..|FFL-7FSJ|S|LLL.FL7-LL|-JFF-||L-JF7FLJJLL-|S...S.|L.-FJF.FS-.7.JJ|.L7J.LSSS7.S..J-7|-SFSSF7S..SL7F LJFFJJFLS..|.L7J.-S7-.-|--|7JJFL-.|JF|.S.-.J|F7|SFSF|-L-SJLL.-.---L7FS-LL7|FS7L.J|||S-F|SJFL7F7|-L7L.SS.FL.LSF-7|F.F.|7FJLJF7L--SL -J-S.F--.SFF..L7JJ.FSLJLLSS7F7JJJ.JLLLF|.7SFSL7L|-FSS.|7LS777LL7--.7F-.L|L.-F-7..|LS-J.LJL..F.S-J7-7LL7-L7LF|LS.J7LL|77S-F.S.|.7FS J|LJ7LS|-.|7L777|-|LL77JF--7LSF|L||S...-.JLS.|..7-|LL7S.JF.-.JFJF7JFFL.|S-7.J.7.JJ-LJL-7LF--LL|J.L|-LL7L-FF7-.-SL.S7.LF.|JFS--7.FS 7-L7SSSL7S|S|-L|.7.S|-7.SJSF7|S7J7|JLLSFJS.FL.L-LSFF.SF-7-7-S||S.JLFSLS-F-S|LSFS.JL-77|7.7-7.|FJL|SL-.JLLS-J|.SJF|-|LFSLJF-JFSJ|F. SLL.-JJJLFFSFF|JJLF-|-SSFL7.|-FF|-J7.SS|FS7J7.S7.7|-FS7L-.SJ-|FF.7-|SF..7S7F-S-S||L-7|SFF-.S|--|7S-L7JJLFJ..|.SJFS.7J---L--.S|F-7J .F.FLJJ|J|JF|LJ-SL.|77FJ-LL|S-JJ7F-LLSL-SFLLFJ7SS|JJFFF7JFF-J.-..|7F-7|-JFF.FJJ.L.|J|SJJ|..J||J.J|.|7-S---F..-SLS.7.7SFF-L.7.S||-7 JF-SFL.S|LL7FF-.F...JSS||.7-JFJLFS.J|7|S7SJ|-J.|-|L|JS.7F-7F|F|.|JSJSS7FLLS.S7--L-7.--SSLJL||77-F|.FJ7|7JS|F7JJ-L-J-|JSSSF..LF-LJS L-F|F77SFS7JS-JFS77FF|SJFFLJS|LJ7J-.L.L--FSS77S.J.7FLLSLS|77LFLJ|7|L-7..-F77S.-S--F..|JLF|-7L.S7J|F|-LJ.FJ7|.7SSL.7JS.-.L|-FLL-JF7 7F|FF-SLLJL|||FL-F.77L.L-J.J|F-||.7.-S7F-7F-7.|LSS7LL.SJS--L|L-F.JSS-|7FSSSLJ.-|L|7F|F-LS.J-LLL-SLFF.F7SFSJLJ-S.LLFJF|7JLF.S7-F--F -L7J-FL-L|...7.SL.FSJ||7--FF7L7.J-FSL-SFL.F|7|||7F.-F..--L-S--JLFJ7J.|7-LJ.L|L..L|.7|7.|S7FLLJS-J|S7|JJSFJJ.7JLJ7FS-L7S7FSSF-L-S7| .J|.JJL7--SS-S|L-LLLF|S7JJ7L-F-S.|-|7FL-.7SJ7S.FSF.|S7|-|L.L..-L.-LJL-|7-7L.7S7F|77JL77SL7|JLLF|LJS|LJFL-FSL.F.-JSS7-FF|S.||..S7SF JF-77L-L.FS-SLLJFSL.-7|S.L7.S.JLS7SJ.7J7|LJJSLSJF.-F|SFFS|||F77-.-.J||7FLJF--7LL|L.7.77SF|FJF-LJFJS|-FJ|L|L.7JJ|F..|L.LL..J-|J-|.L 7.|L-.-SFFS||.-|JLLLJ7-7JF|7F||SL-FS-J7SSJFJ--|J-SJ-|F||JL7F|F|J.LJS-JJ-S|JS.J.|.|7-F.7|LS--F7-.F|JJ.LS--.-|.J|J|SF.FS-JS.LLLF7S-F SFL.FJF7S.JF7JS7--|S.JJ7F--SS7L|SJ.J.SJ|SJ77-SLSFJJ7|-77-S7L-7S..-.L.JS.S7FFF|-77.SS-LF|LSFLFLJJL|FL.-LL|J-JFJ7-.L|.LSJ.77LJFF7L7. .L-F-F.FS7.F7JL7.7J7J|J|SFSJ7LLSSFJ-FSJ-.7.SLFJJF.FJJ|7.L777J7.S77...7|SFS-.L7.FS.J.-S.FJS7SJLJS-J|LJ-.J|L--F|S||SLJFJJJJSSF-L.FLJ |7.SS-FSS-FL||SL.7L|7.7FL.77S|F.S-.LFSS.SJJ-77JFL7F-SS.SLFLFSJ|.LF7SJJFJ||F7F|SLF.||JSF-J-..-77S.|.S||F7--7FL7LLS7||-.7|JJ-.7FLS-F 7JL-..7.L.-SS.J7FS-L-L|F.JLF-.|.7.F-SL.-7JF.S7-FSJ-|F.LJ--FJ.SLF--|L7.F-L7-S-77.S.7.JFSLJ-FS77JJ|||S7J-JSJ.|-|F7L--L7S|LF-J|LS..-- F.-JSF-.SF7LFF-F7-.|.77SF|.SFL.-S|L7-7.--F77SSSL-FSLF7FL7|SLFLS|FF7L-JJJL7.J-|-|F-.-L7-.JJ|F7.7-F-L.LJ7JJSLJFL.7|L7LS7|L-FJ7L-LJJS |-J7.L---.7-77-7FLF7.JJ-LS.|-S|-S7JS7SJ|.J|L..SJ.J|7SL.7|.LJ.S-7F--.7S.J-.SS7.7SS7-SFLJ|SJ-|L7|S.FF7S-7S.SF7S.|JL-S-F|.777FJSFL77J 7JFF7-|S.J.FSJ-.L|S|L.-JJJSLS7F|7J-7FLS7SF|.|J7LJ-|S7..7SJL...SS7J.|L|SFJ.7F-.--F.777J77L.F|-L-|.7SS..7JL-S-L.J7FFFSSS77-S..L|..L| J7JFL-||F.S--LFLS7L|.L.SJL.-LFFSJJ.7FJL|SJ-JJJS7|LSL7.F-J7.-|L-J.|.JL77J7J.|..FLSJ.LLJ||LLL|.SF77S--J-.-|S7F||77F|JJLF|-L..|-|7--7 .|7SJS-....7LJ.7L-SF--|L.LLFJSFF|.JF.-LFF7LJJ7.JJ..7L|-S.FLJ7-F7S-||J77SFJ.LSLLF|.F-F7-|FF7FJ.7LF.L-J-.F7.F7JFFS|--L7-.-S|7-LF|..S 7F7.JLSJ7|7L.FJ|J7JJLF7JJFJ7.L-J-FJFFLL|.LFL-L|-|J|-||J-F-.JF-|7J..7F.S|J7.SFJS7.JLLL-S7SJSF-77JL-LF77L-S|FS.JLJ7SLF|FJ.F|-S|L|-JF .J-.|J--F--J-77-|7-JJ.7SJSJJ7|F|.FLJ.7JFJ.J-L.S|-7|-J7.FLSS|J-|--.JS7-L.7L7S7JSJJ||-S-L-7J|SLJF7FJSS|.L.F-F7LL.F7.7-L.7SL|.777|J77 J7-7.|S-LS7|FJLJ-SF||S7777-|.77FSL|SFLFF.SS7|L-.JFSJ7.|L|LJF|J|7-S7S7-FL.FJJ77|SL|J.SJ-|FL-|7.JJS-S|SS|L-7LJ-S7-J-F-JLL-|LSJ|JLJ7. S77SS7J.JFFL7|S-L.SSFL.S|SJ||JJ7.SSJS|LJ--.J|-.-S7JLJJSFJ-L-FS|SL77JLJ-LJS|FJL---L|.S7LF-JJ7-|S|....SJLJSJ-.LJ.FL7.FLS.7L.-LJ-S7|S FL|JJF|FFFJ.JJSL--F.FJFJ-FLLLJ|F|SLLSL77JS7L.777--JFJ|F|JS|.|.-|7L..L-SL7-7JSF-|.J.J--S|JSS|S.F|.L7LSSFSL-.F|F|7S--JJ|S-F7F-7LLFL|'); query II WITH MUTUALLY RECURSIVE lines(line TEXT, row_no INT) AS ( SELECT regexp_split_to_array(input, '\n')[i], i FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i ), symbols(symb TEXT, row_no INT, col_no INT) as ( SELECT substring(line, j, 1), row_no, j FROM lines, generate_series(1, length(line)) j ), -- Each location that is pipe has two neighbors edge1(r1 INT, c1 INT, r2 INT, c2 INT) AS ( SELECT row_no, col_no, CASE WHEN symb = '-' THEN row_no WHEN symb = '|' THEN row_no - 1 WHEN symb = 'F' THEN row_no + 1 WHEN symb = 'L' THEN row_no - 1 WHEN symb = 'J' THEN row_no WHEN symb = '7' THEN row_no ELSE NULL END, CASE WHEN symb = '-' THEN col_no - 1 WHEN symb = '|' THEN col_no WHEN symb = 'F' THEN col_no WHEN symb = 'L' THEN col_no WHEN symb = 'J' THEN col_no - 1 WHEN symb = '7' THEN col_no - 1 ELSE NULL END FROM symbols WHERE symb != '.' AND symb != 'S' ), edge2(r1 INT, c1 INT, r2 INT, c2 INT) AS ( SELECT row_no, col_no, CASE WHEN symb = '-' THEN row_no WHEN symb = '|' THEN row_no + 1 WHEN symb = 'F' THEN row_no WHEN symb = 'L' THEN row_no WHEN symb = 'J' THEN row_no - 1 WHEN symb = '7' THEN row_no + 1 ELSE NULL END, CASE WHEN symb = '-' THEN col_no + 1 WHEN symb = '|' THEN col_no WHEN symb = 'F' THEN col_no + 1 WHEN symb = 'L' THEN col_no + 1 WHEN symb = 'J' THEN col_no WHEN symb = '7' THEN col_no ELSE NULL END FROM symbols WHERE symb != '.' AND symb != 'S' ), -- Symmetrized graph symm(r1 INT, c1 INT, r2 INT, c2 INT) AS ( SELECT r1, c1, r2, c2 FROM ( SELECT * FROM edge1 UNION ALL SELECT * FROM edge2 UNION ALL SELECT r2, c2, r1, c1 FROM edge1 UNION ALL SELECT r2, c2, r1, c1 FROM edge2 UNION ALL SELECT row_no, col_no, row_no + 1, col_no FROM symbols WHERE symb = 'S' UNION ALL SELECT row_no, col_no, row_no, col_no + 1 FROM symbols WHERE symb = 'S' UNION ALL SELECT row_no, col_no, row_no - 1, col_no FROM symbols WHERE symb = 'S' UNION ALL SELECT row_no, col_no, row_no, col_no - 1 FROM symbols WHERE symb = 'S' ) GROUP BY r1, c1, r2, c2 HAVING COUNT(*) = 2 ), reach(r INT, c INT) AS ( SELECT row_no, col_no FROM symbols WHERE symb = 'S' UNION SELECT r2, c2 FROM reach, symm WHERE r = r1 AND c = c1 ), part1(part1 BIGINT) AS ( SELECT COUNT(*)/2 FROM reach ), -- Part 2: how many cells are *inside* the loop? -- All (1, *) and (*, 1) cells have their upper left outside the loop (outer edge of the diagram). -- Each cell inherits from its UL neighbor, toggled by any pipe except '7' and 'L' pipe. -- Rewrite the pipe to have symbols, and resolve 'S' to actual oriented pipe. pipe(r INT, c INT, symb TEXT) AS ( SELECT r, c, symb FROM reach, symbols WHERE r = row_no AND c = col_no AND symb != 'S' UNION SELECT row_no, col_no, CASE WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 + 1 AND col_no = s2.c2 THEN 'J' -- toggle WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN '-' -- toggle WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '7' -- no toggle WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'L' -- no toggle WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '|' -- toggle WHEN row_no = s1.r1 AND col_no = s1.c1 - 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'F' -- toggle ELSE '???' END FROM symbols, symm s1, symm s2 WHERE symb = 'S' AND row_no = s1.r1 AND col_no = s1.c1 AND row_no = s2.r1 AND col_no = s2.c1 ), -- Enclosed(1,*) and Enclosed(*,1) are all false. -- Enclosed(x+1,y+1) = Enclosed(x,y) perhaps toggled by pipe(x,y) status(r INT, c INT, encl BOOL) AS ( SELECT row_no, col_no, false FROM symbols WHERE row_no = 1 OR col_no = 1 UNION SELECT row_no + 1, col_no + 1, CASE WHEN pipe.symb IN (VALUES ('J'),('-'),('|'),('F')) THEN NOT encl ELSE encl END FROM status LEFT JOIN pipe ON (status.r = pipe.r AND status.c = pipe.c) JOIN symbols ON (status.r = symbols.row_no AND status.c = symbols.col_no) ), part2(part2 BIGINT) AS ( SELECT COUNT(*) FROM status WHERE encl = true AND (r, c) NOT IN (SELECT r, c FROM pipe) ) SELECT * FROM part1, part2; ---- 1439 2073 query T multiline EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR WITH MUTUALLY RECURSIVE lines(line TEXT, row_no INT) AS ( SELECT regexp_split_to_array(input, '\n')[i], i FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i ), symbols(symb TEXT, row_no INT, col_no INT) as ( SELECT substring(line, j, 1), row_no, j FROM lines, generate_series(1, length(line)) j ), -- Each location that is pipe has two neighbors edge1(r1 INT, c1 INT, r2 INT, c2 INT) AS ( SELECT row_no, col_no, CASE WHEN symb = '-' THEN row_no WHEN symb = '|' THEN row_no - 1 WHEN symb = 'F' THEN row_no + 1 WHEN symb = 'L' THEN row_no - 1 WHEN symb = 'J' THEN row_no WHEN symb = '7' THEN row_no ELSE NULL END, CASE WHEN symb = '-' THEN col_no - 1 WHEN symb = '|' THEN col_no WHEN symb = 'F' THEN col_no WHEN symb = 'L' THEN col_no WHEN symb = 'J' THEN col_no - 1 WHEN symb = '7' THEN col_no - 1 ELSE NULL END FROM symbols WHERE symb != '.' AND symb != 'S' ), edge2(r1 INT, c1 INT, r2 INT, c2 INT) AS ( SELECT row_no, col_no, CASE WHEN symb = '-' THEN row_no WHEN symb = '|' THEN row_no + 1 WHEN symb = 'F' THEN row_no WHEN symb = 'L' THEN row_no WHEN symb = 'J' THEN row_no - 1 WHEN symb = '7' THEN row_no + 1 ELSE NULL END, CASE WHEN symb = '-' THEN col_no + 1 WHEN symb = '|' THEN col_no WHEN symb = 'F' THEN col_no + 1 WHEN symb = 'L' THEN col_no + 1 WHEN symb = 'J' THEN col_no WHEN symb = '7' THEN col_no ELSE NULL END FROM symbols WHERE symb != '.' AND symb != 'S' ), -- Symmetrized graph symm(r1 INT, c1 INT, r2 INT, c2 INT) AS ( SELECT r1, c1, r2, c2 FROM ( SELECT * FROM edge1 UNION ALL SELECT * FROM edge2 UNION ALL SELECT r2, c2, r1, c1 FROM edge1 UNION ALL SELECT r2, c2, r1, c1 FROM edge2 UNION ALL SELECT row_no, col_no, row_no + 1, col_no FROM symbols WHERE symb = 'S' UNION ALL SELECT row_no, col_no, row_no, col_no + 1 FROM symbols WHERE symb = 'S' UNION ALL SELECT row_no, col_no, row_no - 1, col_no FROM symbols WHERE symb = 'S' UNION ALL SELECT row_no, col_no, row_no, col_no - 1 FROM symbols WHERE symb = 'S' ) GROUP BY r1, c1, r2, c2 HAVING COUNT(*) = 2 ), reach(r INT, c INT) AS ( SELECT row_no, col_no FROM symbols WHERE symb = 'S' UNION SELECT r2, c2 FROM reach, symm WHERE r = r1 AND c = c1 ), part1(part1 BIGINT) AS ( SELECT COUNT(*)/2 FROM reach ), -- Part 2: how many cells are *inside* the loop? -- All (1, *) and (*, 1) cells have their upper left outside the loop (outer edge of the diagram). -- Each cell inherits from its UL neighbor, toggled by any pipe except '7' and 'L' pipe. -- Rewrite the pipe to have symbols, and resolve 'S' to actual oriented pipe. pipe(r INT, c INT, symb TEXT) AS ( SELECT r, c, symb FROM reach, symbols WHERE r = row_no AND c = col_no AND symb != 'S' UNION SELECT row_no, col_no, CASE WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 + 1 AND col_no = s2.c2 THEN 'J' -- toggle WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN '-' -- toggle WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '7' -- no toggle WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'L' -- no toggle WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '|' -- toggle WHEN row_no = s1.r1 AND col_no = s1.c1 - 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'F' -- toggle ELSE '???' END FROM symbols, symm s1, symm s2 WHERE symb = 'S' AND row_no = s1.r1 AND col_no = s1.c1 AND row_no = s2.r1 AND col_no = s2.c1 ), -- Enclosed(1,*) and Enclosed(*,1) are all false. -- Enclosed(x+1,y+1) = Enclosed(x,y) perhaps toggled by pipe(x,y) status(r INT, c INT, encl BOOL) AS ( SELECT row_no, col_no, false FROM symbols WHERE row_no = 1 OR col_no = 1 UNION SELECT row_no + 1, col_no + 1, CASE WHEN pipe.symb IN (VALUES ('J'),('-'),('|'),('F')) THEN NOT encl ELSE encl END FROM status LEFT JOIN pipe ON (status.r = pipe.r AND status.c = pipe.c) JOIN symbols ON (status.r = symbols.row_no AND status.c = symbols.col_no) ), part2(part2 BIGINT) AS ( SELECT COUNT(*) FROM status WHERE encl = true AND (r, c) NOT IN (SELECT r, c FROM pipe) ) SELECT * FROM part1, part2; ---- Explained Query: With cte l0 = Project (#0, #2, #3) // { arity: 3 } Map (substr(#1{line}, #2{j}, 1)) // { arity: 4 } FlatMap generate_series(1, char_length(#1{line}), 1) // { arity: 3 } Project (#1, #2) // { arity: 2 } Map (array_index(regexp_split_to_array["\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{i}))) // { arity: 3 } FlatMap generate_series(1, (regexp_split_to_array["\n", case_insensitive=false](#0{input}) array_length 1), 1) // { arity: 2 } ReadStorage materialize.public.input // { arity: 1 } cte l1 = Project (#0..=#2, #4, #5) // { arity: 5 } Map ((#2{symb} = "-"), case when #3 then #0{row_no} else case when (#2{symb} = "|") then (#0{row_no} - 1) else case when (#2{symb} = "F") then (#0{row_no} + 1) else case when (#2{symb} = "L") then (#0{row_no} - 1) else case when (#2{symb} = "J") then #0{row_no} else case when (#2{symb} = "7") then #0{row_no} else null end end end end end end, case when #3 then (#1{col_no} - 1) else case when (#2{symb} = "|") then #1{col_no} else case when (#2{symb} = "F") then #1{col_no} else case when (#2{symb} = "L") then #1{col_no} else case when (#2{symb} = "J") then (#1{col_no} - 1) else case when (#2{symb} = "7") then (#1{col_no} - 1) else null end end end end end end) // { arity: 6 } Get l0 // { arity: 3 } cte l2 = Project (#0..=#2, #4, #5) // { arity: 5 } Map ((#2{symb} = "-"), case when #3 then #0{row_no} else case when (#2{symb} = "|") then (#0{row_no} + 1) else case when (#2{symb} = "F") then #0{row_no} else case when (#2{symb} = "L") then #0{row_no} else case when (#2{symb} = "J") then (#0{row_no} - 1) else case when (#2{symb} = "7") then (#0{row_no} + 1) else null end end end end end end, case when #3 then (#1{col_no} + 1) else case when (#2{symb} = "|") then #1{col_no} else case when (#2{symb} = "F") then (#1{col_no} + 1) else case when (#2{symb} = "L") then (#1{col_no} + 1) else case when (#2{symb} = "J") then #1{col_no} else case when (#2{symb} = "7") then #1{col_no} else null end end end end end end) // { arity: 6 } Get l0 // { arity: 3 } cte l3 = Project (#0..=#3) // { arity: 4 } Filter (#4{count} = 2) // { arity: 5 } Reduce group_by=[#0..=#3] aggregates=[count(*)] // { arity: 5 } Union // { arity: 4 } Project (#0, #1, #3, #4) // { arity: 4 } Filter (#2{symb} != ".") AND (#2{symb} != "S") // { arity: 5 } Get l1 // { arity: 5 } Project (#0, #1, #3, #4) // { arity: 4 } Filter (#2{symb} != ".") AND (#2{symb} != "S") // { arity: 5 } Get l2 // { arity: 5 } Project (#3, #4, #0, #1) // { arity: 4 } Filter (#2{symb} != ".") AND (#2{symb} != "S") AND (#3) IS NOT NULL AND (#4) IS NOT NULL // { arity: 5 } Get l1 // { arity: 5 } Project (#3, #4, #0, #1) // { arity: 4 } Filter (#2{symb} != ".") AND (#2{symb} != "S") AND (#3) IS NOT NULL AND (#4) IS NOT NULL // { arity: 5 } Get l2 // { arity: 5 } Project (#0, #1, #3, #1) // { arity: 4 } Filter (#2{symb} = "S") // { arity: 4 } Map ((#0{row_no} + 1)) // { arity: 4 } Get l0 // { arity: 3 } Project (#0, #1, #0, #3) // { arity: 4 } Filter (#2{symb} = "S") // { arity: 4 } Map ((#1{col_no} + 1)) // { arity: 4 } Get l0 // { arity: 3 } Project (#0, #1, #3, #1) // { arity: 4 } Filter (#2{symb} = "S") // { arity: 4 } Map ((#0{row_no} - 1)) // { arity: 4 } Get l0 // { arity: 3 } Project (#0, #1, #0, #3) // { arity: 4 } Filter (#2{symb} = "S") // { arity: 4 } Map ((#1{col_no} - 1)) // { arity: 4 } Get l0 // { arity: 3 } cte l4 = Project (#0, #1) // { arity: 2 } Filter (#2{symb} = "S") // { arity: 3 } Get l0 // { arity: 3 } cte l5 = ArrangeBy keys=[[#0{r1}, #1{c1}]] // { arity: 4 } Get l3 // { arity: 4 } Return // { arity: 2 } With Mutually Recursive cte l6 = Distinct project=[#0, #1] // { arity: 2 } Union // { arity: 2 } Get l4 // { arity: 2 } Project (#4, #5) // { arity: 2 } Join on=(#0{r} = #2{r1} AND #1{c} = #3{c1}) type=differential // { arity: 6 } implementation %0:l6[#0{r}, #1{c}]UKK » %1:l5[#0{r1}, #1{c1}]KK ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 2 } Filter (#0{r}) IS NOT NULL AND (#1{c}) IS NOT NULL // { arity: 2 } Get l6 // { arity: 2 } Get l5 // { arity: 4 } cte l7 = Reduce aggregates=[count(*)] // { arity: 1 } Project () // { arity: 0 } Get l6 // { arity: 2 } cte l8 = Distinct project=[#0..=#2] // { arity: 3 } Union // { arity: 3 } Project (#0, #1, #4) // { arity: 3 } Join on=(#0{r} = #2{row_no} AND #1{c} = #3{col_no}) type=differential // { arity: 5 } implementation %0:l6[#0{r}, #1{c}]UKK » %1:l0[#0{row_no}, #1{col_no}]KKf ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 2 } Filter (#0{r}) IS NOT NULL AND (#1{c}) IS NOT NULL // { arity: 2 } Get l6 // { arity: 2 } ArrangeBy keys=[[#0{row_no}, #1{col_no}]] // { arity: 3 } Filter (#2{symb} != "S") // { arity: 3 } Get l0 // { arity: 3 } Project (#0, #1, #8) // { arity: 3 } Map (case when ((#0{row_no} = #0{r1}) AND (#0{row_no} = (#6{r2} + 1)) AND (#1{col_no} = #7{c2}) AND (#1{col_no} = (#1{c1} + 1))) then "J" else case when ((#0{row_no} = #0{r1}) AND (#0{row_no} = #6{r2}) AND (#1{col_no} = (#1{c1} + 1)) AND (#1{col_no} = (#7{c2} - 1))) then "-" else case when ((#0{row_no} = #0{r1}) AND (#0{row_no} = (#6{r2} - 1)) AND (#1{col_no} = #7{c2}) AND (#1{col_no} = (#1{c1} + 1))) then "7" else case when ((#0{row_no} = #6{r2}) AND (#0{row_no} = (#0{r1} + 1)) AND (#1{col_no} = #1{c1}) AND (#1{col_no} = (#7{c2} - 1))) then "L" else case when ((#0{row_no} = (#0{r1} + 1)) AND (#0{row_no} = (#6{r2} - 1)) AND (#1{col_no} = #1{c1}) AND (#1{col_no} = #7{c2})) then "|" else case when ((#0{row_no} = #0{r1}) AND (#0{row_no} = #6{r2}) AND (#1{col_no} = (#1{c1} - 1)) AND (#1{col_no} = (#7{c2} - 1))) then "F" else "???" end end end end end end) // { arity: 9 } Join on=(#0{row_no} = #2{r1} = #4{r1} AND #1{col_no} = #3{c1} = #5{c1}) type=delta // { arity: 8 } implementation %0:l4 » %1:l3[#0{r1}, #1{c1}]KK » %2:l5[#0{r1}, #1{c1}]KK %1:l3 » %0:l4[#0{row_no}, #1{col_no}]KKef » %2:l5[#0{r1}, #1{c1}]KK %2:l5 » %0:l4[#0{row_no}, #1{col_no}]KKef » %1:l3[#0{r1}, #1{c1}]KK ArrangeBy keys=[[#0{row_no}, #1{col_no}]] // { arity: 2 } Get l4 // { arity: 2 } ArrangeBy keys=[[#0{r1}, #1{c1}]] // { arity: 2 } Project (#0, #1) // { arity: 2 } Get l3 // { arity: 4 } Get l5 // { arity: 4 } cte l9 = ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 3 } Get l17 // { arity: 3 } cte l10 = Project (#0..=#2, #5) // { arity: 4 } Join on=(#0{r} = #3{r} AND #1{c} = #4{c}) type=differential // { arity: 6 } implementation %0:l9[#0{r}, #1{c}]KK » %1:l8[#0{r}, #1{c}]KK Get l9 // { arity: 3 } ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 3 } Get l8 // { arity: 3 } cte l11 = Project (#2, #3, #6, #7) // { arity: 4 } Map ((#0{r} + 1), (#1{c} + 1)) // { arity: 8 } Join on=(#0{r} = #4{row_no} AND #1{c} = #5{col_no}) type=differential // { arity: 6 } implementation %0[#0{r}, #1{c}]KK » %1:l0[#0{row_no}, #1{col_no}]KK ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 4 } Union // { arity: 4 } Map (null) // { arity: 4 } Union // { arity: 3 } Negate // { arity: 3 } Project (#0..=#2) // { arity: 3 } Join on=(#0{r} = #3 AND #1{c} = #4) type=differential // { arity: 5 } implementation %1[#0, #1]UKKA » %0:l9[#0{r}, #1{c}]KK Get l9 // { arity: 3 } ArrangeBy keys=[[#0, #1]] // { arity: 2 } Distinct project=[#0, #1] // { arity: 2 } Project (#0, #1) // { arity: 2 } Get l10 // { arity: 4 } Get l17 // { arity: 3 } Get l10 // { arity: 4 } ArrangeBy keys=[[#0{row_no}, #1{col_no}]] // { arity: 2 } Project (#0, #1) // { arity: 2 } Get l0 // { arity: 3 } cte l12 = Distinct project=[#0] // { arity: 1 } Project (#1) // { arity: 1 } Get l11 // { arity: 4 } cte l13 = Reduce group_by=[#0] aggregates=[any((#0{symb} = #1{right_col0_0}))] // { arity: 2 } FlatMap wrap1("J", "-", "|", "F") // { arity: 2 } Get l12 // { arity: 1 } cte l14 = ArrangeBy keys=[[#0]] // { arity: 1 } Get l12 // { arity: 1 } cte l15 = Union // { arity: 2 } Get l13 // { arity: 2 } Project (#0, #2) // { arity: 2 } Map (false) // { arity: 3 } Join on=(#0 = #1) type=differential // { arity: 2 } implementation %1:l14[#0]UK » %0[#0]K ArrangeBy keys=[[#0]] // { arity: 1 } Union // { arity: 1 } Negate // { arity: 1 } Project (#0) // { arity: 1 } Get l13 // { arity: 2 } Get l12 // { arity: 1 } Get l14 // { arity: 1 } cte l16 = Union // { arity: 2 } Get l15 // { arity: 2 } Project (#0, #2) // { arity: 2 } FlatMap guard_subquery_size(#1{count}) // { arity: 3 } Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 } Project (#0) // { arity: 1 } Get l15 // { arity: 2 } cte l17 = Distinct project=[#0..=#2] // { arity: 3 } Union // { arity: 3 } Project (#0, #1, #3) // { arity: 3 } Filter ((#0{row_no} = 1) OR (#1{col_no} = 1)) // { arity: 4 } Map (false) // { arity: 4 } Get l0 // { arity: 3 } Project (#2, #3, #6) // { arity: 3 } Map (case when #5{any} then NOT(#0{encl}) else #0{encl} end) // { arity: 7 } Join on=(#1 = #4) type=differential // { arity: 6 } implementation %0:l11[#1]K » %1[#0]K ArrangeBy keys=[[#1]] // { arity: 4 } Get l11 // { arity: 4 } ArrangeBy keys=[[#0]] // { arity: 2 } Union // { arity: 2 } Get l16 // { arity: 2 } Project (#0, #2) // { arity: 2 } Map (null) // { arity: 3 } Join on=(#0 = #1) type=differential // { arity: 2 } implementation %1:l14[#0]UK » %0[#0]K ArrangeBy keys=[[#0]] // { arity: 1 } Union // { arity: 1 } Negate // { arity: 1 } Distinct project=[#0] // { arity: 1 } Project (#0) // { arity: 1 } Get l16 // { arity: 2 } Get l12 // { arity: 1 } Get l14 // { arity: 1 } Return // { arity: 2 } With cte l18 = Project (#0, #1) // { arity: 2 } Filter (#2{encl} = true) // { arity: 3 } Get l17 // { arity: 3 } cte l19 = Reduce aggregates=[count(*)] // { arity: 1 } Union // { arity: 0 } Negate // { arity: 0 } Project () // { arity: 0 } Join on=(#0 = #2{right_col0_2} AND #1 = #3{right_col1_3}) type=differential // { arity: 4 } implementation %1[#0, #1]UKKA » %0:l18[#0, #1]UKKef ArrangeBy keys=[[#0, #1]] // { arity: 2 } Get l18 // { arity: 2 } ArrangeBy keys=[[#0{right_col0_2}, #1{right_col1_3}]] // { arity: 2 } Distinct project=[#0{right_col0_2}, #1{right_col1_3}] // { arity: 2 } Project (#0, #1) // { arity: 2 } Get l8 // { arity: 3 } Project () // { arity: 0 } Get l18 // { arity: 2 } Return // { arity: 2 } CrossJoin type=differential // { arity: 2 } implementation %0[×]U » %1[×]U ArrangeBy keys=[[]] // { arity: 1 } Project (#1) // { arity: 1 } Map ((#0{count} / 2)) // { arity: 2 } Union // { arity: 1 } Get l7 // { arity: 1 } Map (0) // { arity: 1 } Union // { arity: 0 } Negate // { arity: 0 } Project () // { arity: 0 } Get l7 // { arity: 1 } Constant // { arity: 0 } - () ArrangeBy keys=[[]] // { arity: 1 } Union // { arity: 1 } Get l19 // { arity: 1 } Map (0) // { arity: 1 } Union // { arity: 0 } Negate // { arity: 0 } Project () // { arity: 0 } Get l19 // { arity: 1 } Constant // { arity: 0 } - () Source materialize.public.input Target cluster: quickstart EOF