puzzleup 2021

newkid

我用 rownum=1找出第一个答案花了三分多钟，改成 count 跑了几小时也出不来，放弃了。

jihuyao

newkid 发表于 2021-10-7 00:25
你这说的是啥？回哪一贴？

Last effort on 5-connected cells.  Basically using collections, one is all already connected and one not connected (similar to Dijkstra algorithm implement).  for any 5 digit string eg 12345 each step only picks one connected cell (if possible).  So any string goes through to 5 steps must be valid one (go to next step for coloring then, skip here).  The forcus is on find valid 5 connected cells for all combinations C(9,5).


--==================================

with t0 as (select rownum cell from dual connect by rownum<=9
), t (rn, cur_cell, str) as (
select 1, cell, ''||cell str from t0
union all
select rn+1, cell, str||cell from t, t0
where cur_cell < cell and rn<5
), tmp (rn, str, cur_str, cur_cell, sum_peer, pos) as (
select 1, str, substr(str, 2) cur_str, substr(str, 1, 1) cur_cell,
decode(mod(substr(str, 1, 1),3),0,'',substr(str, 1, 1)+1)||'|'||decode(ceil(substr(str, 1, 1)/3),3,'',substr(str, 1, 1)+3) sum_peer,
--replace above cur_str/sum_peer in regexp_instr(cur_str, sum_peer, 1, 1) as below
regexp_instr(substr(str, 2), decode(mod(substr(str, 1, 1),3),0,'',substr(str, 1, 1)+1)||'|'||decode(ceil(substr(str, 1, 1)/3),3,'',substr(str, 1, 1)+3), 1, 1) pos
from t
union all
select rn+1, str, replace(cur_str, substr(cur_str, pos, 1)) cur_str, substr(cur_str, pos, 1) cur_cell,
sum_peer||'|'||decode(mod(substr(cur_str, pos, 1),3),0,'',substr(cur_str, pos, 1)+1)||'|'||decode(mod(substr(cur_str, pos, 1),3),1,'',substr(cur_str, pos, 1)-1)||'|'||decode(ceil(substr(cur_str, pos, 1)/3),3,'',substr(cur_str, pos, 1)+3)||'|'||decode(ceil(substr(cur_str, pos, 1)/3),1,'',substr(cur_str, pos, 1)-3) sum_peer,
regexp_instr(replace(cur_str, substr(cur_str, pos, 1)), sum_peer||'|'||decode(mod(substr(cur_str, pos, 1),3),0,'',substr(cur_str, pos, 1)+1)||'|'||decode(mod(substr(cur_str, pos, 1),3),1,'',substr(cur_str, pos, 1)-1)||'|'||decode(ceil(substr(cur_str, pos, 1)/3),3,'',substr(cur_str, pos, 1)+3)||'|'||decode(ceil(substr(cur_str, pos, 1)/3),1,'',substr(cur_str, pos, 1)-3), 1, 1) pos
from tmp where rn>0 and pos>0
)
select count(*) from tmp
where rn=5
/


--====================================

find 66 valid 5 connected cells for all combinations C(9,5)=126

SQL> /

  COUNT(*)
----------
        66

Elapsed: 00:00:00.04
SQL>
SQL>

〇〇

newkid 发表于 2021-10-8 09:00
我用 rownum=1找出第一个答案花了三分多钟，改成 count 跑了几小时也出不来，放弃了。

怎么知道留下哪些中间步骤的摆法最后能成功？

〇〇

跑8 4 3就用了2分钟

with RECURSIVE
t(n,c,x,y) as (select level,chr(64+level),ceil(level/8),mod(level-1,8)+1 from  generate_series(1,8*4)level),
     s(lvl,n,
     --nlist,
     clist) as (select 1::int,
                               n,
                               --cast(n as varchar2(100)),
                               c
                          from t where t.n between 1 and 4
                         union all
                        select lvl + 1,
                               b.n,
                               --nlist||','||b.n,
                               clist||','||b.c
                          from s,t b
                         where s.n < b.n   and b.n between lvl/3*8+1 and lvl/3*8+8                              
                           and (select greatest(sum(case when a.x = b.x then 1 end),
                                                sum(case when a.y = b.y then 1 end),
                                                sum(case when a.x-b.x = a.y-b.y then 1 end),
                                                sum(case when a.x-b.x = b.y-a.y then 1 end)
                                                )
                                  from t a
                                 where position(a.c in clist||','||b.c)>0)<=3            
                            )
select max(lvl),count(*) from s;

max |  count
-----+---------
  12 | 4521939
(1 行记录)


时间：118238.091 ms (01:58.238)

〇〇

jihuyao 发表于 2021-10-8 09:11
Last effort on 5-connected cells.  Basically using collections, one is all already connected and one ...

我120楼的结果是
49个5连
16个2-3

〇〇

用2个6 3 3拼出一个6 6 3,用了1秒
with RECURSIVE
t(n,c,x,y) as (select level,chr(64+level),ceil(level/6),mod(level-1,6)+1 from  generate_series(1,6*3)level),
     s(lvl,n,
     plist,
     clist) as (select 1::bigint,
                               n,
                               lpad('1',n,'0'),
                               c
                          from t where t.n between 1 and 3
                         union all
                        select lvl + 1,
                               b.n,
                               plist||lpad('1',b.n-s.n,'0'),
                               clist||','||b.c
                          from s,t b
                         where s.n < b.n   and b.n between lvl/3*6+1 and lvl/3*6+6                              
                           and (select greatest(sum(case when a.x = b.x then 1 end),
                                                sum(case when a.y = b.y then 1 end),
                                                sum(case when a.x-b.x = a.y-b.y then 1 end),
                                                sum(case when a.x-b.x = b.y-a.y then 1 end)
                                                )
                                  from t a
                                 where position(a.c in clist||','||b.c)>0)<=3            
                            )
,j as(select substr(s.plist,1,6)||chr(10)||substr(s.plist,7,6)||chr(10)||substr(s.plist,13,6)||chr(10)||
substr(s1.plist,1,6)||chr(10)||substr(s1.plist,7,6)||chr(10)||substr(s1.plist,13,6) s
from s,s s1 where  s.lvl=9 and s1.lvl=9 and length(s.plist)=18 and length(s1.plist)=18 --lpad(s.plist,18,'0')=reverse(lpad(s1.plist,18,'0'))
and
substr(s.plist,1,6)::bigint+substr(s.plist,7,6)::bigint+substr(s.plist,13,6)::bigint+
substr(s1.plist,1,6)::bigint+substr(s1.plist,7,6)::bigint+substr(s1.plist,13,6)::bigint=333333
and
(substr(s.plist,1,6)::bigint+substr(s.plist,7,6)::bigint*10+substr(s.plist,13,6)::bigint*100+
substr(s1.plist,1,6)::bigint*1000+substr(s1.plist,7,6)::bigint*10000+substr(s1.plist,13,6)::bigint*100000)::varchar !~'[4-6]+'
and
(substr(s.plist,1,6)::bigint*100000+substr(s.plist,7,6)::bigint*10000+substr(s.plist,13,6)::bigint*1000+
substr(s1.plist,1,6)::bigint*100+substr(s1.plist,7,6)::bigint*10+substr(s1.plist,13,6)::bigint)::varchar !~'[4-6]+'
)
select * from j limit 1;
   s
--------
111000+
100011+
001**+
110010+
011100+
000111
(1 行记录)


时间：1117.182 ms (00:01.117)

〇〇

利用8 4 3临时物理表，拼出一个8 8 3,用了15分钟，真是大海捞针
create table t843 as
with RECURSIVE
t(n,c,x,y) as (select level,chr(64+level),ceil(level/8),mod(level-1,8)+1 from  generate_series(1,8*4)level),
     s(lvl,n,
     plist,
     clist) as (select 1::bigint,
                               n,
                               lpad('1',n,'0'),
                               c
                          from t where t.n between 1 and 4
                         union all
                        select lvl + 1,
                               b.n,
                               plist||lpad('1',b.n-s.n,'0'),
                               clist||','||b.c
                          from s,t b
                         where s.n < b.n   and b.n between lvl/3*8+1 and lvl/3*8+8                              
                           and (select greatest(sum(case when a.x = b.x then 1 end),
                                                sum(case when a.y = b.y then 1 end),
                                                sum(case when a.x-b.x = a.y-b.y then 1 end),
                                                sum(case when a.x-b.x = b.y-a.y then 1 end)
                                                )
                                  from t a
                                 where position(a.c in clist||','||b.c)>0)<=3            
                            )
select * from s where lvl=12;

SELECT 1902500
时间：119006.519 ms (01:59.007)



with j as(select substr(s.plist,1,8)||chr(10)||substr(s.plist,9,8)||chr(10)||substr(s.plist,17,8)||chr(10)||substr(s.plist,25,8)||chr(10)||
substr(s1.plist,1,8)||chr(10)||substr(s1.plist,9,8)||chr(10)||substr(s1.plist,17,8)||chr(10)||substr(s1.plist,25,8) s
from t843 s,t843 s1 where s.plist like '1%' and length(s.plist)=32 and length(s1.plist)=32 --lpad(s.plist,18,'0')=reverse(lpad(s1.plist,18,'0'))
and
substr(s.plist,1,8)::bigint+substr(s.plist,9,8)::bigint+substr(s.plist,17,8)::bigint+substr(s.plist,25,8)::bigint+
substr(s1.plist,1,8)::bigint+substr(s1.plist,9,8)::bigint+substr(s1.plist,17,8)::bigint+substr(s1.plist,25,8)::bigint=33333333
and
(substr(s.plist,1,8)::bigint+substr(s.plist,9,8)::bigint*10+substr(s.plist,17,8)::bigint*10^2+substr(s.plist,25,8)::bigint*10^3+
substr(s1.plist,1,8)::bigint*10^4+substr(s1.plist,9,8)::bigint*10^5+substr(s1.plist,17,8)::bigint*10^6+substr(s1.plist,25,8)::bigint*10^7)::varchar !~'[4-8]+'
and
(substr(s.plist,1,8)::bigint*10^7+substr(s.plist,9,8)::bigint*10^6+substr(s.plist,17,8)::bigint*10^5+substr(s.plist,17,8)::bigint*10^4+
substr(s1.plist,1,8)::bigint*10^3+substr(s1.plist,9,8)::bigint*10^2+substr(s1.plist,17,8)::bigint*10+substr(s1.plist,25,8)::bigint)::varchar !~'[4-8]+'
)
select * from j limit 1;

    s
----------
1000**0+
00111000+
00000111+
000**01+
11100000+
11100000+
0**1000+
00000111
(1 行记录)


时间：895913.042 ms (14:55.913)

〇〇

居然还是错的，有个斜线不对

〇〇

错在这里，+substr(s.plist,17,8)::bigint*10^5+substr(s.plist,17,8)::bigint*10^4

newkid

〇〇 发表于 2021-10-8 18:53
错在这里，+substr(s.plist,17,8)::bigint*10^5+substr(s.plist,17,8)::bigint*10^4

我也是拆成两个8X4。
你改了bug之后，跑出来什么答案？