Puzzleup 2013挑战赛即将开始

newkid

lugionline 发表于 2013-8-16 06:55
有两个吧
x
-------------------

你写的代码呢？
题目要求找最大。

newkid

〇〇 发表于 2013-8-16 16:35
利用instr的第4个参数，终于改对了
set num 20
SQL> with t as (select level-1 l from dual connect b ...

INSTR用得好，比我用REGEXP_COUNT快。

newkid

52楼单个SQL的问题在于 test2, 里面有个笛卡尔积：
                      select t1.p||t2.p as num
                                       from test t1,test t2
                                      where (t1.p<>t2.p)

然后再带上三个EXISTS过滤，当然慢了。

我给你改了一下还好点，但是因为总体思路不佳，再改也好不到哪去，你要是有兴趣就按此思路自己把剩下的做完。

with tm as (select lpad(level,4,'0') lv from dual connect by level<=9999)
,test as (select lv p
                ,p1
                ,p1+p2 as p12
                ,p1+p2+p3 as p123
                ,p2+p3+p4 as p234
                ,p3+p4 as p34
                ,p4
           from (select TO_NUMBER(substr(lv,1,1)) as  p1, TO_NUMBER(substr(lv,2,1)) as  p2
                       ,TO_NUMBER( substr(lv,3,1)) as  p3, TO_NUMBER(substr(lv,4,1)) as  p4,lv  from tm)
           where p1+p2+p3+p4 in (1,4,9,16,25,36)
                 and REGEXP_COUNT(lv,0) in (0,1,2)
                 and REGEXP_COUNT(lv,1) in (0,1,2)
                 and REGEXP_COUNT(lv,2) in (0,1,2)
                 and REGEXP_COUNT(lv,3) in (0,1,2)
                 and REGEXP_COUNT(lv,4) in (0,1,2)
                 and REGEXP_COUNT(lv,5) in (0,1,2)
                 and REGEXP_COUNT(lv,6) in (0,1,2)
                 and REGEXP_COUNT(lv,7) in (0,1,2)
                 and REGEXP_COUNT(lv,8) in (0,1,2)
                 and REGEXP_COUNT(lv,9) in (0,1,2)
)
,test2 as (select num p from (select num
                                    ,substr(num,2,4) as num11
                                    ,substr(num,3,4) as num12
                                    ,substr(num,4,4) as num13
                               from (select t1.p||t2.p as num
                                       from test t1,test t2
                                      where (t1.p<>t2.p)
                                      AND t1.p234+t2.p1  IN (4,9,16,25,36)
                                      AND t1.p34+t2.p12  IN (4,9,16,25,36)
                                      AND t1.p4+t2.p123   IN (4,9,16,25,36)
                                     )
                               where REGEXP_COUNT(num,0) in (0,1,2)
                                     and REGEXP_COUNT(num,1) in (0,1,2)
                                     and REGEXP_COUNT(num,2) in (0,1,2)
                                     and REGEXP_COUNT(num,3) in (0,1,2)
                                     and REGEXP_COUNT(num,4) in (0,1,2)
                                     and REGEXP_COUNT(num,5) in (0,1,2)
                                     and REGEXP_COUNT(num,6) in (0,1,2)
                                     and REGEXP_COUNT(num,7) in (0,1,2)
                                     and REGEXP_COUNT(num,8) in (0,1,2)
                                     and REGEXP_COUNT(num,9) in (0,1,2)
                              ) a
                        --where exists (select 1 from test where p=a.num11)
                        --      and exists (select 1 from test where p=a.num12)
                        --      and exists (select 1 from test where p=a.num13)
            )
SELECT * FROM TEST2

lastwinner

HelloWorld_001 发表于 2013-8-16 14:41
newkid找到的81978100367936已经是符合条件最大的了
49#说的另外个数字是14位里面最长的了。剩下的就更小了 ...

没看你代码，说说我的思路，仅供参考
平方数只可能是4/9/16/25
第一步，找出所有四个数字之和能构成这4个数的组合（需要满足每个数字最多只出现两次，考虑到排列，数量可能不会少）
第二步，用connect by nocycle来连接，条件是本记录的后三位=下一级记录的前三位，并且需要控制本记录中用过2次的数字不是下一级记录中的最后一个数字（这是为了过滤掉少数不合规的记录，以此减少无谓的连接），并且level<=17
第三步，找出满足条件的最大值，可以使用regexp_count来判断每个数字最多出现2次（当然，instr也可以

〇〇

newkid 发表于 2013-8-16 21:44
INSTR用得好，比我用REGEXP_COUNT快。

我原来想象从满足条件的4位数中4个4个拼接会比1个1个拼快，结果不是
这个递归的收敛很快

〇〇

〇〇 发表于 2013-8-17 05:36
我原来想象从满足条件的4位数中4个4个拼接会比1个1个拼快，结果不是
这个递归的收敛很快

10  select lv,count(*) from r group by lv order by lv;

                  LV             COUNT(*)
-------------------- --------------------
                   1                   10
                   2                  100
                   3                  990
                   4                 1194
                   5                 1332
                   6                 1481
                   7                 1640
                   8                 1865
                   9                 1034
                  10                  427
                  11                  135
                  12                   46
                  13                   18
                  14                    2

〇〇

〇〇 发表于 2013-8-17 05:36
我原来想象从满足条件的4位数中4个4个拼接会比1个1个拼快，结果不是
这个递归的收敛很快

前面分析过，第5个数与第1个数的差绝对值，只能是0，5、7、9之一，实际第5个数只能是1-2个数候选
这样4次递归，也不过2^4=16倍，比1000多个笛卡儿少积再筛选少多了

lugionline

newkid 发表于 2013-8-16 21:40
你写的代码呢？
题目要求找最大。

哦，我看错了，还以为找最长的呢

lugionline

大家的做法肯定都差不多

with
d (n, m, c) as
(
        select 0, power(4, 0) * 3, power(4, 0) * 1 union all
        select n + 1, power(4, n + 1) * 3, power(4, n + 1) * 1 from d where n < 9
),
s (x, c, p1, p2, p3, p4, l) as
(
        select cast(d.n as varchar(max)), d.c, 0, 0, 0, d.n, 1 from d where n > 0 union all
        select s.x + cast(d.n as varchar(max)), s.c + d.c, s.p2, s.p3, s.p4, d.n, s.l + 1 from s, d
        where (d.m & (s.c + d.c)) < d.m
                and (s.l + 1 < 4 or (s.p2 + s.p3 + s.p4 + d.n) in (select n*n from d))
)
select x from
(
        select x, rank() over (order by l desc) r from s
) s where r = 1

〇〇

lugionline 发表于 2013-8-17 08:54
大家的做法肯定都差不多

with

d.m & (s.c + d.c)) ?