puzzleup 2016

〇〇

newkid 发表于 2016-10-19 23:31
用SQL应该可以，把所有点及其能够通过一条直线到达的点都列出来然后自连接五次。

连了个4边形
with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
p(lv,path,l1,r1,m1)as
(
select 1,p,l,r,m from t
union all
select lv+1,path*10+p,l,r,m from t,p
where lv<5 and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<4)
or
  (instr(path,p)=1 and lv=4)
))
select min(path) from p where lv=5
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))
;

〇〇

每次连下一个点必须不在一直线没找到简单写法

〇〇

〇〇 发表于 2016-10-20 09:03
每次连下一个点必须不在一直线没找到简单写法

加了方向d判断,还不够,出现很多135241的2个只有顶点连着的3角形
with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
p(lv,path,l1,r1,m1,d)as
(
select 1,p,l,r,m,0 from t
union all
select lv+1,path*10+p,l,r,m,case when l1=l then 1 when r1=r then 2 when m1=m then 3 end from t,p
where lv<6 and d<> case when l1=l then 1 when r1=r then 2 when m1=m then 3 end
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
  (instr(path,p)=1 and lv=5)
))
--select count(*) from(
select min(path) from p where lv=6
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))+
power(2,substr(path,5,1))
;
);

〇〇

想到一个办法，求出2点中间的点存入排除列表
比如 1 8排除4
6 9排除7 8

〇〇

with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
ex as(
select 1 a,6 b, 3 x from dual union
select 1 a,8 b, 4 x from dual union
select 2 a,7 b, 4 x from dual union
select 2 a,9 b, 5 x from dual union
select 3 a,5 b, 4 x from dual union
select 6 a,8 b, 7 x from dual union
select 6 a,9 b, 7 x from dual union
select 6 a,9 b, 8 x from dual union
select 7 a,9 b, 8 x from dual),
p(lv,path,l1,r1,m1,d)as
(
select 1,p,l,r,m,0 from t
union all
select lv+1,path*10+p,l,r,m,case when l1=l then 1 when r1=r then 2 when m1=m then 3 end from t,p
where lv<6 and d<> case when l1=l then 1 when r1=r then 2 when m1=m then 3 end and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
  (instr(path,p)=1 and lv=5)
)
and not exists(select 1 from ex where ex.x=p and instr(path,a*10+b)>0 or instr(path,b*10+a)>0)
)
--select count(*) from(
select min(path) from p where lv=6
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))+
power(2,substr(path,5,1))
;
还是漏掉了124581这种情况

〇〇

with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
ex as(
select 1 a,6 b, 3 x from dual union
select 1 a,8 b, 4 x from dual union
select 2 a,7 b, 4 x from dual union
select 2 a,9 b, 5 x from dual union
select 3 a,5 b, 4 x from dual union
select 6 a,8 b, 7 x from dual union
select 6 a,9 b, 7 x from dual union
select 6 a,9 b, 8 x from dual union
select 7 a,9 b, 8 x from dual),
p(lv,path,l1,r1,m1,d)as
(
select 1,p,l,r,m,0 from t
union all
select lv+1,path*10+p,l,r,m,case when l1=l then 1 when r1=r then 2 when m1=m then 3 end from t,p
where lv<6 and d<> case when l1=l then 1 when r1=r then 2 when m1=m then 3 end and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
  (instr(path,p)=1 and lv=5)
)
and not exists(select 1 from ex where ex.x=p and (instr(path,a*10+b)>0 or instr(path,b*10+a)>0))
)
--select count(*) from(
select min(path) from p where lv=6 and
not exists(select 1 from ex where (substr(path,-2)=a*10+b or substr(path,-2)=b*10+a) and instr(path,ex.x)>0)
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))+
power(2,substr(path,5,1))
;
还是漏掉135981这种交叉

〇〇

改用2进制表示已经经过的点,where条件写了就取不出值，放在/** **/位置就会数字溢出
/*and bitand(pe,se)=0*/

with t as(
select 1 p,power(2,1)e, 1 l, 2 r, 1 m from dual union
select 2  ,power(2,2) , 2  , 1  , 1 from dual union
select 3  ,power(2,3) , 1  , 3  , 2 from dual union
select 4  ,power(2,4) , 2  , 2  , 2 from dual union
select 5  ,power(2,5) , 3  , 1  , 2 from dual union
select 6  ,power(2,6) , 1  ,null, 3 from dual union
select 7  ,power(2,7) , 2  , 3  , 3 from dual union
select 8  ,power(2,8) , 3  , 2  , 3 from dual union
select 9  ,power(2,9) ,null, 1  , 3 from dual),
ex as(
select 1 a,6 b, 3 x from dual union
select 1 a,8 b, 4 x from dual union
select 2 a,7 b, 4 x from dual union
select 2 a,9 b, 5 x from dual union
select 3 a,5 b, 4 x from dual union
select 6 a,8 b, 7 x from dual union
select 6 a,9 b, 7 x from dual union
select 6 a,9 b, 8 x from dual union
select 7 a,9 b, 8 x from dual),
x as(select a,b,sum(power(2,x))se from ex group by a,b), --se中间包含的点的2进制和
p(lv,path,l1,r1,m1,pe)as
(
select 1,p,l,r,m,e from t
union all
select lv+1,path*10+p,l,r,m,pe+e+nvl(se,0) from p inner join t on(
lv<6 and bitand(e,pe)=0 and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
(instr(path,p)=1 and lv=5)
))
left join x on(substr(path,-1)||p in (a*10+b,b*10+a) /** **/)
----where bitand(pe,se)=0
)
select min(path) from p where lv=6
group by pe-power(2,substr(path,-1))
;

newkid

最后结论是什么？等我有空也来写一个。lugi看来是对今年的题很失望，都没法显示出他的实力。

newkid

先写个草稿。


with p as (
SELECT 0 y,1 cnt from dual
union all select 1,2 FROM DUAL
union all select 2,1 FROM DUAL
union all select 3,2 FROM DUAL
union all select 4,3 FROM DUAL
union all select 5,2 FROM DUAL
union all select 6,3 FROM DUAL
union all select 7,2 FROM DUAL
union all select 8,1 FROM DUAL
)
,p2 as (
select 1-cnt+(level-1)*2 x,y,CHR(64+ROW_NUMBER() OVER(ORDER BY Y,LEVEL)) id
  from p
connect by y=prior y and level<=cnt and prior sys_guid() is not null
order by id
)
,v as (
select s.id s_id
      ,e.id e_id
      ,case when s.x=e.x then 999 else (e.y-s.y)/(e.x-s.x) end as k
  from p2 s,p2 e
where s.id<>e.id and s.x=e.x or s.x<>e.x and (e.y-s.y)/(e.x-s.x) in (1,-1)
)
,tp as (select substr(s,level)||substr(s,1,level-1) tp from (select '12345' s from dual) connect by level<=5)
,tp2 as (select tp from tp union all select reverse(tp) from tp)
select count(*) from (
select distinct min(translate('12345',tp2.tp,s))
  from (
       select v1.s_id||v2.s_id||v3.s_id||v4.s_id||v5.s_id s
         from v v1,v v2,v v3,v v4,v v5
        where v1.e_id=v2.s_id and v1.k<>v2.k
              and v2.e_id=v3.s_id and v2.k<>v3.k
              and v3.e_id=v4.s_id and v3.k<>v4.k
              and v4.e_id=v5.s_id and v4.k<>v5.k
              and v5.e_id=v1.s_id and v5.k<>v1.k
              and v2.e_id<>v1.s_id
              and v3.e_id not in (v1.s_id,v2.s_id)
              and v4.e_id not in (v1.s_id,v2.s_id,v3.s_id)
       ),tp2
group by s
)
;

  COUNT(*)
----------
       298
没有判断线段交叉情况，答案多了。又得参照第一题写法判断交叉，真烦。

lugionline

我在等你算出答案来呢，SQL没图形不好调试吧，看看有没有漏的