puzzleup 2016

〇〇

newkid 发表于 2016-10-20 23:54
先写个草稿。

和第一题的区别是,路经都是预先画好的

〇〇

newkid 发表于 2016-10-20 23:54
先写个草稿。

p p2 v都是什么意思？

〇〇

newkid 发表于 2016-10-20 22:41
最后结论是什么？等我有空也来写一个。lugi看来是对今年的题很失望，都没法显示出他的实力。

我在187楼的写法出来的结果没有排除最后一步有交叉的情况，但把条件写在where就不出数，写在on就溢出

〇〇

〇〇 发表于 2016-10-21 08:32
p p2 v都是什么意思？

我猜y是中线,实线0 2 4 6 8 虚拟出1 3 5 7,x是左右坐标
         X          Y ID
---------- ---------- --
         0          0 A
        -1          1 B
         1          1 C
         0          2 D
        -1          3 E
         1          3 F
        -2          4 G
         0          4 H
         2          4 I
        -1          5 J
         1          5 K
        -2          6 L
         0          6 M
         2          6 N
        -1          7 O
         1          7 P
         0          8 Q

〇〇

〇〇 发表于 2016-10-21 14:05
我猜y是中线,实线0 2 4 6 8 虚拟出1 3 5 7,x是左右坐标
         X          Y ID
---------- -------- ...

貌似有些点都连不上
MIN(TRANSL
----------
CEGDF
DFGIJ
CEGJL
CDJHF
CEGHL
CEGJI
CDGHL
FHJGI
DFLHG
DEIFG
DEHLF
DEGHJ
EHGJI
CEHJI
FGIJL
CDFHL
EGFLH
CEIJL
CEHGI
CDFGI
DFHEG
GHLIJ
DEILJ

已选择23行。

已用时间:  00: 00: 00.04
SQL> with p as (
  2  SELECT 0 y,1 cnt from dual
  3  union all select 1,2 FROM DUAL
  4  union all select 2,1 FROM DUAL
  5  union all select 3,2 FROM DUAL
  6  union all select 4,1 FROM DUAL
  7  union all select 5,2 FROM DUAL
  8  union all select 6,1 FROM DUAL
  9  union all select 7,2 FROM DUAL
10  union all select 8,1 FROM DUAL
11  )
12  ,p2 as (select * from(
13  select 1-cnt+(level-1)*2 x,y,CHR(64+ROW_NUMBER() OVER(ORDER BY Y,LEVEL)) id
14    from p
15  connect by y=prior y and level<=cnt and prior sys_guid() is not null
16  order by id
17  )where id not in('A','B','K','M'))
18  select * from p2;

         X          Y ID
---------- ---------- --
         1          1 C
         0          2 D
        -1          3 E
         1          3 F
         0          4 G
        -1          5 H
         1          5 I
         0          6 J
         1          7 L

已选择9行。

〇〇

总结出了小图
with c as(select level c from dual connect by level<=4),
p as(select rownum id,r.c r,c.c c,(c.c+r.c)-1 t from c,c r where r.c+c.c<=5 and r.c<=3)
select s.id sp,e.id ep,m.id mp from p s,p e,p m
where (s.r=e.r and e.c-s.c>1 and m.r=s.r and m.c>s.c and m.c<e.c) --横向跨多点
or (s.c=e.c and e.r-s.r>1 and m.c=s.c and m.r>s.r and m.r<e.r) --/向跨多点
or (s.t=e.t and e.r-s.r>1 and m.t=s.t and m.r>s.r and m.r<e.r) --\向跨多点
;
和大图
with c as(select level c from dual connect by level<=5),
p as(select rownum id,r.c r,c.c c,(c.c+r.c)-1 t from c,c r where r.c+c.c>=4 and r.c+c.c<=8
and (r.c,c.c)not in((1,3),(3,5)))
/*select * from p*/
select s.id sp,e.id ep,m.id mp from p s,p e,p m
where (s.r=e.r and e.c-s.c>1 and m.r=s.r and m.c>s.c and m.c<e.c) --横向跨多点
or (s.c=e.c and e.r-s.r>1 and m.c=s.c and m.r>s.r and m.r<e.r) --/向跨多点
or (s.t=e.t and e.r-s.r>1 and m.t=s.t and m.r>s.r and m.r<e.r) --\向跨多点
;
的点公式,

newkid

with p as (  ---------- 每层Y坐标，有几个点
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 (  ---------- 找出所有可能的线段，要么是纵向（斜率999）要么是斜线，斜率1或-1
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
      ,s.id||e.id id
      ,s.x
      ,s.y
      ,e.x x2
      ,e.y y2
  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)
)
,crossing AS (  ------ 找出所有两两交叉的线段
SELECT m1.id,m2.id id2
  FROM v m1, v m2
WHERE m1.id<>m2.id
       AND ((m1.x-m2.x)*(m1.y-m2.y2)-(m1.x-m2.x2)*(m1.y-m2.y))*((m1.x2-m2.x)*(m1.y2-m2.y2)-(m1.x2-m2.x2)*(m1.y2-m2.y))<=0
       AND ((m2.x-m1.x)*(m2.y-m1.y2)-(m2.x-m1.x2)*(m2.y-m1.y))*((m2.x2-m1.x)*(m2.y2-m1.y2)-(m2.x2-m1.x2)*(m2.y2-m1.y))<=0
)
,tp as (select substr(s,level)||substr(s,1,level-1) tp from (select '12345' s from dual) connect by level<=5)  ---- TRANSLATE使用的循环变形模版
,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)
              -----------不能有交叉
              and NOT EXISTS (SELECT 1 FROM crossing c where (c.id,c.id2) in ((v1.id,v3.id),(v1.id,v4.id),(v2.id,v4.id),(v2.id,v5.id),(v3.id,v5.id)))
       ),tp2
group by s
)
;

  COUNT(*)
----------
       140
      
---------------------例子
with p as (
SELECT 0 y,4 cnt from dual
union all select 1,3 FROM DUAL
union all select 2,2 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
      ,(e.y-s.y)/(e.x-s.x)  as k
      ,s.id||e.id id
      ,s.x
      ,s.y
      ,e.x x2
      ,e.y y2
  from p2 s,p2 e
where s.id<>e.id and s.y=e.y or s.x<>e.x and (e.y-s.y)/(e.x-s.x) in (1,-1)
)
,crossing AS (
SELECT m1.id,m2.id id2
  FROM v m1, v m2
WHERE m1.id<>m2.id
       AND ((m1.x-m2.x)*(m1.y-m2.y2)-(m1.x-m2.x2)*(m1.y-m2.y))*((m1.x2-m2.x)*(m1.y2-m2.y2)-(m1.x2-m2.x2)*(m1.y2-m2.y))<=0
       AND ((m2.x-m1.x)*(m2.y-m1.y2)-(m2.x-m1.x2)*(m2.y-m1.y))*((m2.x2-m1.x)*(m2.y2-m1.y2)-(m2.x2-m1.x2)*(m2.y2-m1.y))<=0
)
,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)
              and NOT EXISTS (SELECT 1 FROM crossing c where (c.id,c.id2) in ((v1.id,v3.id),(v1.id,v4.id),(v2.id,v4.id),(v2.id,v5.id),(v3.id,v5.id)))
       ),tp2
group by s
)
;


  COUNT(*)
----------
         9

〇〇

用我的思路,终于调通了,42周岁的第一个程序

with c as(select level c from dual connect by level<=5),
p as(select rownum id,power(2,rownum)pw,r.c r,c.c c,(c.c+r.c)-1 t from c,c r where r.c+c.c>=4 and r.c+c.c<=8
and (r.c,c.c)not in((1,3),(3,5)))
,p2i as(select s.id sp,e.id ep,m.id mp,m.pw from p s,p e,p m
where (s.r=e.r and e.c-s.c>1 and m.r=s.r and m.c>s.c and m.c<e.c) --横向跨多点
or (s.c=e.c and e.r-s.r>1 and m.c=s.c and m.r>s.r and m.r<e.r) --/向跨多点
or (s.t=e.t and e.r-s.r>1 and m.t=s.t and m.r>s.r and m.r<e.r) --\向跨多点
)
,p2w as
(select sp,ep,sum(pw)pw from p2i group by sp,ep
union all
select ep,sp,sum(pw)pw from p2i group by sp,ep
)
--select * from p2w
,p2all as(select s.id sp,e.id ep,case when s.r=e.r then 1 when s.c=e.c then 2 when s.t=e.t then 3 end d
from p s,p e
where (s.r=e.r and e.c<>s.c) or (s.c=e.c and e.r<>s.r) or (s.t=e.t and e.r<>s.r))
,p2 as(select sp,ep,d,pw pwm,power(2,ep)pwe from p2all a left join p2w b using(sp,ep))
,
r(lv,path,p,tw,d1,d2)as --tw total power,d1 方向
(
select 1,cast(id as varchar(50)),id,pw,0,0 from p
union all
select lv+1,path||','||ep,ep,tw+nvl(pwm,0)+pwe,d,d2*10+d from r,p2
where
lv<5 and p=sp and bitand(tw,nvl(pwm,0)+pwe)=0 and d1<>d)
select min(path) from r,p2 where lv=5 and
(substr(path,1,instr(path,',')-1)=ep and p=sp and  bitand(tw,nvl(pwm,0))=0 and d1<>d and substr(d2,1,1)<>d)
group by tw+nvl(pwm,0)
;
把前2行换成
with c as(select level c from dual connect by level<=4),
p as(select rownum id,power(2,rownum)pw,r.c r,c.c c,(c.c+r.c)-1 t from c,c r where r.c+c.c<=5 and r.c<=3)
则计算小图形

lugionline

〇〇 发表于 2016-10-22 08:00
用我的思路,终于调通了,42周岁的第一个程序

with c as(select level c from dual connect by level=4 an ...

恭喜恭喜，生日快乐，呵呵

〇〇

newkid 发表于 2016-10-21 21:42
with p as (  ---------- 每层Y坐标，有几个点
SELECT 0 y,1 cnt from dual
union all select 1,2 FROM D ...

我的程序和newkid的对比：
好处
1.二进制路径免于一个图形的起点轮换
2.变成4边形，3角形更容易
坏处
1.2进制数位操作对顶点的个数有限制
2.遇到第一期那样的问题就不行了