Puzzleup 2010 比赛快开始了，大家用SQL解答啊

lastwinner · 发表于 2010-9-9 09:10

AND n1.n NOT IN (n2.n+1,n2.n-1) AND n2.n NOT IN (n3.n+1,n3.n-1)
   AND n4.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n6.n+1,n6.n-1)
   AND n7.n NOT IN (n8.n+1,n8.n-1) AND n8.n NOT IN (n9.n+1,n9.n-1)
   AND n1.n NOT IN (n4.n+1,n4.n-1) AND n4.n NOT IN (n7.n+1,n7.n-1)
   AND n2.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n8.n+1,n8.n-1)
   AND n3.n NOT IN (n6.n+1,n6.n-1) AND n6.n NOT IN (n9.n+1,n9.n-1)

用ABS感觉会更好，而且更简洁

对于
ABC
DEF
GHI

只需要关注BDEFH
abs(e-b)>1 and abs(e-d)>1 and abs(e-f)>1 and abs(e-h>1
and abs(b-a)>1 and abs(b-c)>1
and abs(d-a)>1 and abs(d-g)>1
and abs(h-g)>1 and abs(h-i)>1
and abs(f-c)>1 and abs(f-i)>1
跟你的这12个not in是等价的，你是从左到右从上到下，看明白了也就好理解了

〇〇 · 发表于 2010-9-9 09:19

按照对称原理，把119楼装修了下

WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
select * from(
SELECT path ,m1*m2*m3 m FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
   ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))m1
   ,REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))m2
   ,REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m3
  FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
   AND n6.n NOT IN (n7.n,n8.n,n9.n)
   AND n7.n NOT IN (n8.n,n9.n)
   AND n8.n<>n9.n
   AND n1.n NOT IN (n2.n+1,n2.n-1) AND n2.n NOT IN (n3.n+1,n3.n-1)
   AND n4.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n6.n+1,n6.n-1)
   AND n7.n NOT IN (n8.n+1,n8.n-1) AND n8.n NOT IN (n9.n+1,n9.n-1)
   AND n1.n NOT IN (n4.n+1,n4.n-1) AND n4.n NOT IN (n7.n+1,n7.n-1)
   AND n2.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n8.n+1,n8.n-1)
   AND n3.n NOT IN (n6.n+1,n6.n-1) AND n6.n NOT IN (n9.n+1,n9.n-1)
)
where substr(m1,1,1)>substr(m1,2,1) and
substr(m2,1,1)>substr(m2,2,1) and
substr(m3,1,1)>substr(m3,2,1)
ORDER BY 2 DESC)
WHERE ROWNUM=1;

lastwinner · 发表于 2010-9-9 09:24

原帖由〇〇于 10-9-9 09:05 发表

越接近正方形，面积越大

这是周长一定情况下

lastwinner · 发表于 2010-9-9 09:28

原帖由〇〇于 10-9-9 09:19 发表
按照对称原理，把119楼装修了下

WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUMsubstr(m1,2,1) and
substr(m2,1,1)>substr(m2,2,1) and
substr(m3,1,1)>substr(m3,2,1)
ORDER BY 2 DESC)
WHERE ROWNUM=1;

这里不大适合用对称
比如
783
561
是满足邻居不连续的题设的
但按你这么一过滤，就成了
783
651
才满足你的条件，然而这又违反了邻居不连续的题设

〇〇 · 发表于 2010-9-9 09:36

但
abc
def
ghi
和
cba
fed
ihg
是对称的
划掉最大值后也是对称的
这时，某一个行42,一定比24大，但确实无法保证3行的顺序都是一样的...

〇〇 · 发表于 2010-9-9 15:48

花花的速度和newkid是一样的..

n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
select * from(
SELECT path ,m1*m2*m3 m FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
   ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))m1
   ,REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))m2
   ,REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m3
  FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
   AND n6.n NOT IN (n7.n,n8.n,n9.n)
   AND n7.n NOT IN (n8.n,n9.n)
   AND /*n8.n<>n9.n
   AND n1.n NOT IN (n2.n+1,n2.n-1) AND n2.n NOT IN (n3.n+1,n3.n-1)
   AND n4.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n6.n+1,n6.n-1)
   AND n7.n NOT IN (n8.n+1,n8.n-1) AND n8.n NOT IN (n9.n+1,n9.n-1)
   AND n1.n NOT IN (n4.n+1,n4.n-1) AND n4.n NOT IN (n7.n+1,n7.n-1)
   AND n2.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n8.n+1,n8.n-1)
   AND n3.n NOT IN (n6.n+1,n6.n-1) AND n6.n NOT IN (n9.n+1,n9.n-1)*/
abs(n5.n-n2.n)>1 and abs(n5.n-n4.n)>1 and abs(n5.n-n6.n)>1 and abs(n5.n-n8.n)>1
and abs(n2.n-n1.n)>1 and abs(n2.n-n3.n)>1
and abs(n4.n-n1.n)>1 and abs(n4.n-n7.n)>1
and abs(n8.n-n7.n)>1 and abs(n8.n-n9.n)>1
and abs(n6.n-n3.n)>1 and abs(n6.n-n9.n)>1
)
where substr(m1,1,1)>substr(m1,2,1) and
substr(m2,1,1)>substr(m2,2,1) and
substr(m3,1,1)>substr(m3,2,1)
ORDER BY 2 DESC)
WHERE ROWNUM=1;

PATH
------------------------
      M
----------
637809425
211680

已用时间:  00: 00: 02.95

[ 本帖最后由〇〇于 2010-9-9 15:52 编辑 ]

〇〇 · 发表于 2010-9-9 17:05

我的写法怎么会多

with t as(select a from (select to_char(level-1,'fm999') a from dual connect by level<=1000)
where substr(a,1,1)not in(substr(a,2,1) ,substr(a,3,1))
and substr(a,2,1)<>substr(a,3,1)
and substr(a,1,1)-substr(a,2,1) not in(-1,1)
and substr(a,3,1)-substr(a,2,1) not in(-1,1)
)
,t2 as(select a.a||b.a||c.a p
,REPLACE(a.a,GREATEST(substr(a.a,1,1),substr(a.a,2,1),substr(a.a,3,1)))m1
   ,REPLACE(b.a,GREATEST(substr(b.a,1,1),substr(b.a,2,1),substr(b.a,3,1)))m2
   ,REPLACE(c.a,GREATEST(substr(c.a,1,1),substr(c.a,2,1),substr(c.a,3,1))) m3
from t a,t b, t c
where a.a not in(b.a,c.a) and b.a<>c.a
and length(translate('$1234567890','$'||b.a||a.a,'$'))=5
and length(translate('$1234567890','$'||b.a||c.a,'$'))=5
and length(translate('$1234567890','$'||c.a||a.a,'$'))=5
and substr(a.a,1,1)-substr(b.a,1,1) not in (-1,1)
and substr(c.a,1,1)-substr(b.a,1,1) not in (-1,1)
and substr(a.a,2,1)-substr(b.a,2,1) not in (-1,1)
and substr(c.a,2,1)-substr(b.a,2,1) not in (-1,1)
and substr(a.a,3,1)-substr(b.a,3,1) not in (-1,1)
and substr(c.a,3,1)-substr(b.a,3,1) not in (-1,1)
)
select count(*) from t2;

  COUNT(*)
----------
125432

已用时间:  00: 00: 26.84

WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
select count(*) from(
SELECT path ,m1*m2*m3 m FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
   ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))m1
   ,REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))m2
   ,REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m3
  FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
   AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
   AND n6.n NOT IN (n7.n,n8.n,n9.n)
   AND n7.n NOT IN (n8.n,n9.n)
   AND /*n8.n<>n9.n
   AND n1.n NOT IN (n2.n+1,n2.n-1) AND n2.n NOT IN (n3.n+1,n3.n-1)
   AND n4.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n6.n+1,n6.n-1)
   AND n7.n NOT IN (n8.n+1,n8.n-1) AND n8.n NOT IN (n9.n+1,n9.n-1)
   AND n1.n NOT IN (n4.n+1,n4.n-1) AND n4.n NOT IN (n7.n+1,n7.n-1)
   AND n2.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n8.n+1,n8.n-1)
   AND n3.n NOT IN (n6.n+1,n6.n-1) AND n6.n NOT IN (n9.n+1,n9.n-1)*/
abs(n5.n-n2.n)>1 and abs(n5.n-n4.n)>1 and abs(n5.n-n6.n)>1 and abs(n5.n-n8.n)>1
and abs(n2.n-n1.n)>1 and abs(n2.n-n3.n)>1
and abs(n4.n-n1.n)>1 and abs(n4.n-n7.n)>1
and abs(n8.n-n7.n)>1 and abs(n8.n-n9.n)>1
and abs(n6.n-n3.n)>1 and abs(n6.n-n9.n)>1
)
where substr(m1,1,1)>substr(m1,2,1) and
substr(m2,1,1)>substr(m2,2,1) and
substr(m3,1,1)>substr(m3,2,1)
)
;

NT(*)
-----
18796

时间:  00: 00: 02.70

〇〇 · 发表于 2010-9-9 17:07

WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
select count(*) from(
SELECT path ,m1*m2*m3 m FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
   ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))m1
      ,REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))m2
      ,REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m3
FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
      AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
      AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
      AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
      AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
      AND n6.n NOT IN (n7.n,n8.n,n9.n)
      AND n7.n NOT IN (n8.n,n9.n)
      AND /*n8.n<>n9.n
      AND n1.n NOT IN (n2.n+1,n2.n-1) AND n2.n NOT IN (n3.n+1,n3.n-1)
      AND n4.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n6.n+1,n6.n-1)
      AND n7.n NOT IN (n8.n+1,n8.n-1) AND n8.n NOT IN (n9.n+1,n9.n-1)
      AND n1.n NOT IN (n4.n+1,n4.n-1) AND n4.n NOT IN (n7.n+1,n7.n-1)
      AND n2.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n8.n+1,n8.n-1)
      AND n3.n NOT IN (n6.n+1,n6.n-1) AND n6.n NOT IN (n9.n+1,n9.n-1)*/
abs(n5.n-n2.n)>1 and abs(n5.n-n4.n)>1 and abs(n5.n-n6.n)>1 and abs(n5.n-n8.n)>1
and abs(n2.n-n1.n)>1 and abs(n2.n-n3.n)>1
and abs(n4.n-n1.n)>1 and abs(n4.n-n7.n)>1
and abs(n8.n-n7.n)>1 and abs(n8.n-n9.n)>1
and abs(n6.n-n3.n)>1 and abs(n6.n-n9.n)>1
)
);

UNT(*)
------
175952

时间:  00: 00: 03.26

〇〇 · 发表于 2010-9-9 18:40

substr看来不是问题

with t as(select a m,substr(a,1,1)+0 a,substr(a,2,1)+0 b,substr(a,3,1)+0 c
from (select to_char(level-1,'fm999') a from dual connect by level<=1000)
where substr(a,1,1)not in(substr(a,2,1) ,substr(a,3,1))
and substr(a,2,1)<>substr(a,3,1)
and substr(a,1,1)-substr(a,2,1) not in(-1,1)
and substr(a,3,1)-substr(a,2,1) not in(-1,1)
)
,t2 as(select a.m||b.m||c.m p
,REPLACE(a.m,GREATEST(a.a,a.b,a.c))m1
      ,REPLACE(b.a,GREATEST(b.a,b.b,b.c))m2
      ,REPLACE(c.a,GREATEST(c.a,c.b,c.c)) m3
from t a,t b, t c
where a.m not in(b.m,c.m) and b.m<>c.m
and length(translate('$1234567890','$'||b.m||a.m,'$'))=5
and length(translate('$1234567890','$'||b.m||c.m,'$'))=5
and length(translate('$1234567890','$'||c.m||a.m,'$'))=5
and length(translate('$1234567890','$'||a.m||b.m||c.m,'$'))=2
and a.a-b.a not in (-1,1)
and c.a-b.a not in (-1,1)
and a.b-b.b not in (-1,1)
and c.b-b.b not in (-1,1)
and a.c-b.c not in (-1,1)
and c.c-b.c not in (-1,1)
)
select count(*) from t2;

UNT(*)
------
125432

时间:  00: 00: 26.89

〇〇 · 发表于 2010-9-9 18:43

rule是我的好朋友
  with t as(select a m,substr(a,1,1)+0 a,substr(a,2,1)+0 b,substr(a,3,1)+0 c
  from (select to_char(level-1,'fm999') a from dual connect by level<=1000)
  where substr(a,1,1)not in(substr(a,2,1) ,substr(a,3,1))
  and substr(a,2,1)<>substr(a,3,1)
  and substr(a,1,1)-substr(a,2,1) not in(-1,1)
  and substr(a,3,1)-substr(a,2,1) not in(-1,1)
  )
  ,t2 as(select /*+rule*/a.m||b.m||c.m p
  ,REPLACE(a.m,GREATEST(a.a,a.b,a.c))m1
      ,REPLACE(b.a,GREATEST(b.a,b.b,b.c))m2
      ,REPLACE(c.a,GREATEST(c.a,c.b,c.c)) m3
  from t a,t b, t c
  where a.m not in(b.m,c.m) and b.m<>c.m
  and length(translate('$1234567890','$'||b.m||a.m,'$'))=5
  and length(translate('$1234567890','$'||b.m||c.m,'$'))=5
  and length(translate('$1234567890','$'||c.m||a.m,'$'))=5
  and length(translate('$1234567890','$'||a.m||b.m||c.m,'$'))=2
  and a.a-b.a not in (-1,1)
  and c.a-b.a not in (-1,1)
  and a.b-b.b not in (-1,1)
  and c.b-b.b not in (-1,1)
  and a.c-b.c not in (-1,1)
  and c.c-b.c not in (-1,1)
  )
  select count(*) from t2;

UNT(*)
------
125432

时间:  00: 00: 18.48

[精华] Puzzleup 2010 比赛快开始了，大家用SQL解答啊

回复 #119 newkid 的帖子

回复 #124 lastwinner 的帖子