puzzleup 2018

solomon_007 · 发表于 2018-8-24 09:36

newkid 发表于 2018-8-23 21:31
给你们俩一人发个章吧，要什么直接点。

九尾狐狸

nayi224 · 发表于 2018-8-24 10:55

newkid 发表于 2018-8-23 21:31
给你们俩一人发个章吧，要什么直接点。

紫蜘蛛

newkid · 发表于 2018-8-24 21:48

你们真识货，都是绝版的徽章。

再来一个SQL题，昨天在微信上看到的：
三个水桶, 容量分别为3升,5升，8升, 8升桶装满了水，其他两个为空。
如何通过最少次数将水平均分成两份，4+4放在5和8的桶里。

三个水桶的水量按照从小桶到大桶排列，初始状态是 008, 终止状态是 044, 用SQL找出这个变化路径。

newkid · 发表于 2018-8-24 22:30

自己先玩一把：
PATH
-----------------------------------------------------------------------------------------------
008->053->323->026->206->251->341->044
008->305->035->332->152->107->017->314->044
008->305->350->053->323->026->206->251->341->044
008->305->035->053->323->026->206->251->341->044
008->053->323->305->035->332->152->107->017->314->044
008->053->350->305->035->332->152->107->017->314->044
008->053->323->350->305->035->332->152->107->017->314->044
008->305->035->332->152->053->323->026->206->251->341->044
008->305->035->332->350->053->323->026->206->251->341->044
008->053->323->026->206->305->035->332->152->107->017->314->044
008->305->035->332->152->350->053->323->026->206->251->341->044
008->305->035->332->152->107->017->053->323->026->206->251->341->044
008->053->323->026->206->251->341->305->035->332->152->107->017->314->044
008->053->323->026->206->251->350->305->035->332->152->107->017->314->044
008->053->323->026->206->251->341->350->305->035->332->152->107->017->314->044
008->305->035->332->152->107->017->314->350->053->323->026->206->251->341->044

16 rows selected.

solomon_007 · 发表于 2018-8-25 11:01

newkid 发表于 2018-8-24 21:48
你们真识货，都是绝版的徽章。

再来一个SQL题，昨天在微信上看到的：

SQL> with r(a,b,c) as (select 1,-1,0 from dual
  2                      union all
  3                   select 1,0,-1 from dual
  4                      union all
  5                   select -1,0,1 from dual
  6                      union all
  7                   select -1,1,0 from dual
  8                      union all
  9                   select 0,1,-1 from dual
10                      union all
11                   select 0,-1,1 from dual),
12  t(n,x,y,z,path,node) as (select 1,
13                            0,
14                            0,
15                            8,
16                            '008',
17                            '008'
18                      from dual
19                      union all
20                   select t.n+1,
21                            t.x + r.a*s.v x,
22                            t.y + r.b*s.v y,
23                            t.z + r.c*s.v z,
24                            t.path||'->'||to_char(t.x + r.a*s.v)||to_char(t.y + r.b*s.v)||to_char(t.z + r.c*s.v),
25                            to_char(t.x + r.a*s.v)||to_char(t.y + r.b*s.v)||to_char(t.z + r.c*s.v)
26                      from t,
27                            (select level v from dual connect by level<=5) s,
28                            r
29                      where s.v in (3-t.x,5-t.y,8-t.z,t.x,t.y,t.z)
30                      and t.x + r.a*s.v + t.y + r.b*s.v + t.z + r.c*s.v = 8
31                      and t.x + r.a*s.v between 0 and 3
32                      and t.y + r.b*s.v between 0 and 5
33                      and t.z + r.c*s.v between 0 and 8
34                      and ( case when r.a = 1 and r.b=-1 then t.x + r.a*s.v - 3
35                                  when r.a = 1 and r.c=-1 then t.x + r.a*s.v - 3
36                                  when r.b = 1 and r.a=-1 then t.y + r.b*s.v - 5
37                                  when r.b = 1 and r.c=-1 then t.y + r.b*s.v - 5
38                                  when r.c = 1 and r.a=-1 then t.z + r.c*s.v - 8
39                                  when r.c = 1 and r.b=-1 then t.z + r.c*s.v - 8
40                            end = 0
41                            or
42                            case when r.a = 1 and r.b=-1 then t.y + r.b*s.v
43                                  when r.a = 1 and r.c=-1 then t.z + r.c*s.v
44                                  when r.b = 1 and r.a=-1 then t.x + r.a*s.v
45                                  when r.b = 1 and r.c=-1 then t.z + r.c*s.v
46                                  when r.c = 1 and r.a=-1 then t.x + r.a*s.v
47                                  when r.c = 1 and r.b=-1 then t.y + r.b*s.v
48                            end = 0)
49                      )
50  cycle node set flag to 'Y' default 'N'
51  select path from t where flag = 'N' and node = '044'
52  /
PATH
--------------------------------------------------------------------------------
008->053->323->026->206->251->341->044
008->305->035->332->152->107->017->314->044
008->305->035->053->323->026->206->251->341->044
008->305->350->053->323->026->206->251->341->044
008->053->323->305->035->332->152->107->017->314->044
008->053->350->305->035->332->152->107->017->314->044
008->305->035->332->152->053->323->026->206->251->341->044
008->305->035->332->350->053->323->026->206->251->341->044
008->053->323->350->305->035->332->152->107->017->314->044
008->305->035->332->152->350->053->323->026->206->251->341->044
008->053->323->026->206->305->035->332->152->107->017->314->044
008->305->035->332->152->107->017->053->323->026->206->251->341->044
008->053->323->026->206->251->341->305->035->332->152->107->017->314->044
008->053->323->026->206->251->350->305->035->332->152->107->017->314->044
008->305->035->332->152->107->017->314->350->053->323->026->206->251->341->044
008->053->323->026->206->251->341->350->305->035->332->152->107->017->314->044
16 rows selected

solomon_007 · 发表于 2018-8-25 11:08

newkid 发表于 2018-8-24 22:30
自己先玩一把：
PATH
------------------------------------------------------------------------------ ...

你应该再奖励我一个章，这个有点费脑筋

newkid · 发表于 2018-8-26 02:05

solomon_007 发表于 2018-8-25 11:08
你应该再奖励我一个章，这个有点费脑筋

好吧，既然陪我玩，就奖励你一个。

12C写法:
with
move AS (
SELECT p  ---- 源水桶编号
      ,m  ---- 目标水桶编号
      ,'358' c ---- 水桶容量
FROM (SELECT LEVEL p FROM DUAL CONNECT BY LEVEL<=3),(SELECT LEVEL m FROM DUAL CONNECT BY LEVEL<=3)
WHERE p<>m
)
,t(s,path) as (
select '008', CAST('008' AS VARCHAR2(1000)) FROM DUAL
UNION ALL
SELECT new_s
   ,path||'->'||new_s
  FROM t
   ,move
   ,LATERAL(SELECT  SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)) ps
                  ,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)) ms
            FROM DUAL
            )
   ,LATERAL(SELECT  DECODE(1,p,ps,m,ms,SUBSTR(s,1,1))
                  ||DECODE(2,p,ps,m,ms,SUBSTR(s,2,1))
                  ||DECODE(3,p,ps,m,ms,SUBSTR(s,3,1)) new_s
            FROM DUAL
            )
WHERE s<>'044'
   AND SUBSTR(t.s,p,1)<>0 -----源水桶有水
   AND SUBSTR(t.s,m,1)<SUBSTR(c,m,1) -----目标水桶有空
   AND INSTR(path,new_s
            )=0
)
select path from t where s='044'
;

with
move AS (
SELECT p  ---- 源水桶编号
      ,m  ---- 目标水桶编号
      ,'358' c ---- 水桶容量
FROM (SELECT LEVEL p FROM DUAL CONNECT BY LEVEL<=3),(SELECT LEVEL m FROM DUAL CONNECT BY LEVEL<=3)
WHERE p<>m
)
,t(s,path) as (
select '008', CAST('008' AS VARCHAR2(1000)) FROM DUAL
UNION ALL
SELECT new_s
   ,path||'->'||new_s
  FROM t
   JOIN move ON s<>'044'
               AND SUBSTR(t.s,p,1)<>0 -----源水桶有水
               AND SUBSTR(t.s,m,1)<SUBSTR(c,m,1) -----目标水桶有空
   CROSS APPLY (SELECT  SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)) ps
                  ,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)) ms
                  FROM DUAL
                  )
   CROSS APPLY (SELECT  DECODE(1,p,ps,m,ms,SUBSTR(s,1,1))
                  ||DECODE(2,p,ps,m,ms,SUBSTR(s,2,1))
                  ||DECODE(3,p,ps,m,ms,SUBSTR(s,3,1)) new_s
                  FROM DUAL
                  )
WHERE INSTR(path,new_s
            )=0
)
select path from t where s='044'
;

11G写法很啰嗦：

with
move AS (
SELECT p  ---- 源水桶编号
      ,m  ---- 目标水桶编号
      ,'358' c ---- 水桶容量
FROM (SELECT LEVEL p FROM DUAL CONNECT BY LEVEL<=3),(SELECT LEVEL m FROM DUAL CONNECT BY LEVEL<=3)
WHERE p<>m
)
,t(s,path) as (
select '008', CAST('008' AS VARCHAR2(1000)) FROM DUAL
UNION ALL
SELECT DECODE(1,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,1,1))
   ||DECODE(2,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,2,1))
   ||DECODE(3,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,3,1))
   ,path||'->'||DECODE(1,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,1,1))
   ||DECODE(2,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,2,1))
   ||DECODE(3,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,3,1))
  FROM t
   ,move
WHERE s<>'044'
   AND SUBSTR(t.s,p,1)<>0 -----源水桶有水
   AND SUBSTR(t.s,m,1)<SUBSTR(c,m,1) -----目标水桶有空
   AND INSTR(path,DECODE(1,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,1,1))
   ||DECODE(2,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,2,1))
   ||DECODE(3,p,SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),m,SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)),SUBSTR(s,3,1))
            )=0
)
select * from t where s='044'
;

11g 模拟12C LATERAL的写法：

with
move AS (
SELECT p  ---- 源水桶编号
      ,m  ---- 目标水桶编号
      ,'358' c ---- 水桶容量
FROM (SELECT LEVEL p FROM DUAL CONNECT BY LEVEL<=3),(SELECT LEVEL m FROM DUAL CONNECT BY LEVEL<=3)
WHERE p<>m
)
,t(s,path) as (
select '008', CAST('008' AS VARCHAR2(1000)) FROM DUAL
UNION ALL
SELECT new_s.column_value
   ,path||'->'||new_s.column_value
  FROM t
   ,move
   ,TABLE(CAST(MULTISET(SELECT SUBSTR(s,p,1)-LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)) FROM DUAL) AS SYS.ODCIVARCHAR2LIST)) ps
   ,TABLE(CAST(MULTISET(SELECT SUBSTR(s,m,1)+LEAST(SUBSTR(s,p,1),SUBSTR(c,m,1)-SUBSTR(s,m,1)) FROM DUAL) AS SYS.ODCIVARCHAR2LIST)) ms
   ,TABLE(CAST(MULTISET(SELECT  DECODE(1,p,ps.column_value,m,ms.column_value,SUBSTR(s,1,1))
                              ||DECODE(2,p,ps.column_value,m,ms.column_value,SUBSTR(s,2,1))
                              ||DECODE(3,p,ps.column_value,m,ms.column_value,SUBSTR(s,3,1))  FROM DUAL) AS SYS.ODCIVARCHAR2LIST)) new_s
WHERE s<>'044'
   AND SUBSTR(t.s,p,1)<>0 -----源水桶有水
   AND SUBSTR(t.s,m,1)<SUBSTR(c,m,1) -----目标水桶有空
   AND INSTR(path,new_s.column_value
            )=0
)
select path from t where s='044'
;