当前位置：首页 > news >正文

苏旭晖先生写的纯SQL求解Advent of Code 2025第9题最大矩形面积第2部分

news 2026/8/2 22:10:45

原贴地址，我把它改成了能在DuckDB运行，主要是把connect by level 改为 range函数

-- 去除match_recognize, 就是合并连续区间的老套路：withday9as(selectrow_number()over()id,t.*fromread_csv('2509-input.txt',header=0)t(x,y)),vas(selectday9.*,count(*)over()ascntfromday9),sas(----------轮廓线段selectd1.idassid,d1.cnt,casewhend1.x=d2.xthen'X'else'Y'endass_direction,casewhend1.x=d2.xthend1.xelsed1.yendass_val,casewhend1.x=d2.xthenleast(d1.y,d2.y)elseleast(d1.x,d2.x)endass_v1,casewhend1.x=d2.xthengreatest(d1.y,d2.y)elsegreatest(d1.x,d2.x)endass_v2fromv d1,v d2whered2.id=d1.id+1or(d2.id=1andd1.id=d2.cnt)),ssas(------------ s1 和 s2分别是轮廓线s在起点和终点折了一次之后再回到和s平行的另外两端轮廓线（所以sid会间隔）。----------- 如果S和S1(或S和S2)构成Z字形则，则方向没有改变，在和那个端点的垂直线相交时，两段只算一段(通过least使得这两段值一样，dense_rank()把它们分到一组)----------- 如果S和S1(或S和S2)构成U字形则，则方向改变，分别算做两段，所以各自保留自己的s_valselects.*,casewhens.s_v1in(s1.s_v1,s2.s_v1)thens.s_valwhens.s_v1=s1.s_v2thenleast(s.s_val,s1.s_val)whens.s_v1=s2.s_v2thenleast(s.s_val,s2.s_val)endass_val1----- 当s的v1端点落在垂直线上时，用这个代替s_val来排序,casewhens.s_v2in(s1.s_v2,s2.s_v2)thens.s_valwhens.s_v2=s1.s_v1thenleast(s.s_val,s1.s_val)whens.s_v2=s2.s_v1thenleast(s.s_val,s2.s_val)endass_val2----- 当s的v2端点落在垂直线上时，用这个代替s_val来排序froms,s s1,s s2wherecasewhens.sid>s.cnt-2thens.sid+2-s.cntelses.sid+2end=s1.sidandcasewhens.sid<3thens.sid-2+s.cntelses.sid-2end=s2.sid),e2as(selects_direction,s_val,s_v1,s_v2,CASEWHENs_v1<=MAX(s_v2)OVER(PARTITIONBYs_direction,s_valorderbys_v1,s_v2ROWSBETWEENUNBOUNDEDPRECEDINGAND1PRECEDING)+1then0else1endasflagfrom(selects_direction,s_val,min(val2)s_v1,max(val2)s_v2from(selecta.s_direction,a.s_val,ss.s_val val2,dense_rank()over(partitionbya.s_direction,a.s_valorderbycasea.s_valwhenss.s_v1thenss.s_val1whenss.s_v2thenss.s_val2elsess.s_valend)rnfrom(selectdistincts_direction,s_valfroms)ajoinssona.s_direction<>ss.s_directionanda.s_valbetweenss.s_v1andss.s_v2)groupbys_direction,s_val,ceil(rn/2)unionallselects_direction,s_val,s_v1,s_v2froms)),eas(select/*+ materialize */s_direction,s_val,min(s_v1)s_v1,max(s_v2)s_v2from(selecte2.*,sum(flag)over(partitionbys_direction,s_valorderbys_v1)grpfrome2)groupbys_direction,s_val,grp),ras(------- 找出所有矩形，并拆成四条边selectd1.x x1,d1.y y1,d2.x x2,d2.y y2,casewhennin(1,2)then'X'else'Y'endasr_direction,casenwhen1thenleast(d1.x,d2.x)when2thengreatest(d1.x,d2.x)when3thenleast(d1.y,d2.y)when4thengreatest(d1.y,d2.y)endasr_val,casewhennin(1,2)thenleast(d1.y,d2.y)elseleast(d1.x,d2.x)endasr_v1,casewhennin(1,2)thengreatest(d1.y,d2.y)elsegreatest(d1.x,d2.x)endasr_v2fromday9 d1,day9 d2,(selecti nfromrange(1,5)t(i))whered1.id<d2.idandd1.x<>d2.xandd1.y<>d2.y)select*from(selectx1,y1,x2,y2,(abs(x1-x2)+1)*(abs(y1-y2)+1)areafromrwhereexists(select1fromewherer.r_direction=e.s_directionandr.r_val=e.s_valandr.r_v1betweene.s_v1ande.s_v2andr.r_v2betweene.s_v1ande.s_v2)groupbyx1,y1,x2,y2havingcount(*)=4----- 四条边都在多边形内)orderbyareadesclimit1;-- fetch first row with ties;