PUZZLEUP 2015

newkid

lugionline 发表于 2015-8-8 08:07
1680?

我原来想得太简单了，没有把朝向考虑进去。
本来一开始我也是考虑24个贴面的变化，写了一半给简化了，看来不能简化，这下子我估计SQL算不出来了（纯穷举法）。

lugionline

1680恐怕不是一个正确的答案，我拿魔方比划了一下，每个角除了位置需要考虑，每个角的朝向也是要考虑的因数

〇〇

newkid 发表于 2015-8-8 11:11
我原来想得太简单了，没有把朝向考虑进去。
本来一开始我也是考虑24个贴面的变化，写了一半给简化了，看 ...

Pl/sql

〇〇

lugionline 发表于 2015-8-8 11:57
1680恐怕不是一个正确的答案，我拿魔方比划了一下，每个角除了位置需要考虑，每个角的朝向也是要考虑的因数

把6面都摊开,颜色序列不同的总数

newkid

#3 HALF OF ITS SQUARE

All digits of a number are different and for all of its digits that has at least two other digits on its right, the half of the square of that digit is greater than the multiplication of the two digits immediately following on its right.

What is the greatest number having this property?


一个数的所有的位都各不相同，对于每一位数，如果它的右边至少有两位数，那么这位数的平方的一半比起它右边紧跟着的两位数的乘积更大。


具备这个属性的最大的数是什么？

--------
没什么难度，一分钟内就能把SQL写出来。

newkid

第二题SQL解法：

把大立方体的中心设置为(X,Y,Z)坐标系的原点。计算出每个小方块的坐标, 列举三种最基本的旋转(三个维度各转90度)，叠加组合得到所有的旋转。
用TRANSLATE模拟旋转和变化是OO的灵感。

--- 立方体大小
VAR N NUMBER;
EXEC :N:=2;

--- 颜色数
VAR C NUMBER;
EXEC :C:=2;


WITH d AS -------构造X,Y,Z的可能坐标
(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=:N/2
UNION ALL SELECT -LEVEL FROM DUAL CONNECT BY LEVEL<=:N/2
UNION ALL SELECT 0 FROM DUAL WHERE MOD(:N,2)=1 ------- 如果N为奇数则将中心作为原点
)
,c AS ( --------用笛卡尔积得到所有坐标，为每个点赋予唯一编号。用字符做编号以便用TRANSLATE旋转
SELECT d1.i x,d2.i y,d3.i z,CHR(64+ROW_NUMBER() OVER(ORDER BY d1.i,d2.i,d3.i)) id
   FROM d d1,d d2,d d3
)  
,r AS (-------把大立方体分别沿着X,Y,Z轴旋转90度。所有位置都可通过上述旋转叠加组合得来
SELECT template,MIN(template) OVER() original
FROM (
     SELECT LISTAGG(id) WITHIN GROUP(ORDER BY x,y,z) template
       FROM (
             SELECT 1 as tpl_id,x,y,z,id FROM c -------原位不动
             UNION ALL  
             SELECT 2, x ,z ,-y,id FROM c  -------沿着X轴上翻90度。X不变，其他两个互换，其中一个取反
             UNION ALL  
             SELECT 3, z ,y ,-x,id FROM c  -------沿着Y轴上翻90度
             UNION ALL  
             SELECT 4, y ,-x ,z,id FROM c  -------沿着Z轴顺时针翻90度
            )
     GROUP BY tpl_id
     )
)
,all_r(template,rn) AS ( --------叠加组合所有旋转
SELECT template,1 rn from r
UNION ALL
SELECT TRANSLATE(all_r.template,r.original,r.template)
      ,ROW_NUMBER() OVER(PARTITION BY TRANSLATE(all_r.template,r.original,r.template) ORDER BY 1) rn ---- 变换之后的位置可能有重复的，只留下任意一个
  FROM all_r,r
WHERE all_r.rn=1 ---- 只留下任意一个
)
CYCLE template SET cycle_flag TO 'Y' DEFAULT 'N'
,all_p AS ( --------- 在叠加组合结果中去除重复，得到24种旋转结果
SELECT template,MIN(template) OVER() original FROM all_r GROUP BY template
)
,all_c AS ( ---------每个位置可能出现的所有颜色的全排列
SELECT REPLACE(SYS_CONNECT_BY_PATH(color,','),',') color
  FROM (SELECT LEVEL as color FROM DUAL CONNECT BY LEVEL<=:C) ---颜色用1,2,3表示
WHERE LEVEL=POWER(:N,3)
CONNECT BY LEVEL<=POWER(:N,3)
)
SELECT COUNT(DISTINCT color)
FROM (SELECT MIN(TRANSLATE(all_p.template,all_p.original,all_c.color)) color ---- 通过模版的变换保留最小值作为代表
        from all_p,all_c
      GROUP BY all_c.color
      )
;

jsu@JSU12P> EXEC :C:=3;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.00
jsu@JSU12P> /

COUNT(DISTINCTCOLOR)
--------------------
                 333

newkid

第二题附加题，一个SQL跑不出来，因为递归过程中很难去除重复。改用PLSQL可以得到结果：

----取出所有贴面的中心，共24点。
----把24种旋转放到一张小表
DROP table all_p;
create table all_p as
WITH d AS -------构造X,Y,Z的可能坐标
(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=2
UNION ALL SELECT -LEVEL FROM DUAL CONNECT BY LEVEL<=2
)
,c AS ( --------用笛卡尔积得到所有坐标，为每个点赋予唯一编号。用字符做编号以便用TRANSLATE旋转
SELECT d1.i x,d2.i y,d3.i z,CHR(64+ROW_NUMBER() OVER(ORDER BY d1.i,d2.i,d3.i)) id
   FROM d d1,d d2,d d3
  WHERE d1.i IN (-2,2) AND d2.i NOT IN (-2,2) AND d3.i NOT IN (-2,2)
        OR d1.i NOT IN (-2,2) AND d2.i IN (-2,2) AND d3.i NOT IN (-2,2)
        OR d1.i NOT IN (-2,2) AND d2.i NOT IN (-2,2) AND d3.i IN (-2,2)
)  
,r AS (-------把大立方体分别沿着X,Y,Z轴旋转90度。所有位置都可通过上述旋转叠加组合得来
SELECT template,MIN(template) OVER() original
FROM (
     SELECT LISTAGG(id) WITHIN GROUP(ORDER BY x,y,z) template
       FROM (
             SELECT 1 as tpl_id,x,y,z,id  -------原位不动
               FROM c
             UNION ALL  
             SELECT 2, x ,z ,-y,id   -------沿着X轴上翻90度
               FROM c
             UNION ALL  
             SELECT 3, z ,y ,-x,id   -------沿着Y轴上翻90度
               FROM c
             UNION ALL  
             SELECT 4, y ,-x ,z,id   -------沿着Z轴顺时针翻90度
               FROM c
            )
     GROUP BY tpl_id
     )
)
,all_r(template,rn) AS ( --------叠加组合所有旋转
SELECT template,1 rn from r
UNION ALL
SELECT TRANSLATE(all_r.template,r.original,r.template)
      ,ROW_NUMBER() OVER(PARTITION BY TRANSLATE(all_r.template,r.original,r.template) ORDER BY 1) rn ---- 变换之后的位置可能有重复的，只留下任意一个
  FROM all_r,r
WHERE all_r.rn=1 ---- 只留下任意一个
)
CYCLE template SET cycle_flag TO 'Y' DEFAULT 'N'
select rownum id,template,original from (
SELECT CAST(template AS VARCHAR2(30)) template,CAST(MIN(template) OVER() AS VARCHAR2(30)) original FROM all_r GROUP BY template
);

---------------------------
---- 构造最基本的六种扭转，把结果放到一张小表。
create table twist as
WITH d AS -------构造X,Y,Z的可能坐标
(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=2
UNION ALL SELECT -LEVEL FROM DUAL CONNECT BY LEVEL<=2
)
,c AS ( --------用笛卡尔积得到所有坐标，为每个点赋予唯一编号。用字符做编号以便用TRANSLATE旋转
SELECT d1.i x,d2.i y,d3.i z,CHR(64+ROW_NUMBER() OVER(ORDER BY d1.i,d2.i,d3.i)) id
      --,DENSE_RANK() OVER(ORDER BY DECODE(d1.i,:N,d1.i,-:N,d1.i),DECODE(d2.i,:N,d2.i,-:N,d2.i),DECODE(d3.i,:N,d3.i,-:N,d3.i)) AS COLOR
   FROM d d1,d d2,d d3
  WHERE d1.i IN (-2,2) AND d2.i NOT IN (-2,2) AND d3.i NOT IN (-2,2)
        OR d1.i NOT IN (-2,2) AND d2.i IN (-2,2) AND d3.i NOT IN (-2,2)
        OR d1.i NOT IN (-2,2) AND d2.i NOT IN (-2,2) AND d3.i IN (-2,2)
)  
SELECT template,(SELECT LISTAGG(id) WITHIN GROUP(ORDER BY x,y,z) FROM c) original
FROM (
     SELECT LISTAGG(id) WITHIN GROUP(ORDER BY x,y,z) template
       FROM (
             -- SELECT 1 as tpl_id,x,y,z,id FROM c  -------原位不动
             -- UNION ALL  
             SELECT 2 as tpl_id, CASE WHEN z IN (1,2)   THEN y ELSE x END x,CASE WHEN z IN (1,2)   THEN -x ELSE y END y,z,id FROM c  ------- 上层扭90度
             UNION ALL  
             SELECT 3, CASE WHEN z IN (-1,-2) THEN y ELSE x END,CASE WHEN z IN (-1,-2) THEN -x ELSE y END,z,id FROM c  ------- 下层扭90度
             UNION ALL  
             SELECT 4, x,CASE WHEN x IN (-1,-2) THEN -z ELSE y END,CASE WHEN x IN (-1,-2) THEN y ELSE z END,id FROM c  ------- 左层扭90度
             UNION ALL  
             SELECT 5, x,CASE WHEN x IN (1,2)   THEN -z ELSE y END,CASE WHEN x IN (1,2)   THEN y ELSE z END,id FROM c  ------- 右层扭90度
             UNION ALL  
             SELECT 6, CASE WHEN y IN (-1,-2) THEN -z ELSE x END,y,CASE WHEN y IN (-1,-2) THEN x ELSE z END,id FROM c  ------- 前层扭90度
             UNION ALL  
             SELECT 7, CASE WHEN y IN (1,2)   THEN -z ELSE x END,y,CASE WHEN y IN (1,2)   THEN x ELSE z END,id FROM c  ------- 后层扭90度
            )
     GROUP BY tpl_id
     )
;

---------------------------

---- 存放结果
create table all_t (position varchar2(30) NOT NULL,lvl NUMBER);


DECLARE
   t1 date;
   i number :=1;
BEGIN
   delete all_t;
   insert into all_t(position,lvl) SELECT original,0 FROM all_p WHERE ROWNUM=1;
   
   LOOP
       ------- 每次循环做一次扭转，所有花色都可通过六种基本扭转叠加组合而来
       ------- 扭转后去除旋转的重复结果，只留下一种
       t1 := sysdate;
       INSERT INTO all_t(position,lvl)
       WITH tmp AS (
       SELECT DISTINCT (SELECT MIN(TRANSLATE(TRANSLATE(all_t.position,t.original,t.template),all_p.original,all_p.template)) FROM all_p) position
         FROM all_t,twist t
        where all_t.lvl=i-1
       )
       SELECT position,i FROM tmp WHERE position NOT IN (SELECT position FROM all_t);
       EXIT when SQL%ROWCOUNT=0;
      
       DBMS_OUTPUT.PUT_LINE('insert lvl='||i||' rows:'||SQL%ROWCOUNT||' seconds:'||round((sysdate-t1)*24*60*60,2));
       DBMS_APPLICATION_INFO.SET_CLIENT_INFO('insert lvl='||i||' rows:'||SQL%ROWCOUNT||' seconds:'||round((sysdate-t1)*24*60*60,2));
      
       i:=i+1;
       COMMIT;
   END LOOP;
END;
/


insert lvl=1 rows:6 seconds:0
insert lvl=2 rows:27 seconds:0
insert lvl=3 rows:120 seconds:0
insert lvl=4 rows:534 seconds:0
insert lvl=5 rows:2256 seconds:0
insert lvl=6 rows:8969 seconds:0
insert lvl=7 rows:33058 seconds:1
insert lvl=8 rows:114149 seconds:3
insert lvl=9 rows:360508 seconds:12
insert lvl=10 rows:930588 seconds:38
insert lvl=11 rows:1350852 seconds:80
insert lvl=12 rows:782536 seconds:108
insert lvl=13 rows:90280 seconds:66
insert lvl=14 rows:276 seconds:10

PL/SQL procedure successfully completed.

Elapsed: 00:05:18.80

jsu@JSU12P> select count(*) from all_t;

  COUNT(*)
----------
   3674160

〇〇

321是符合条件的一个数

lugionline

985432107 可以手工算？

〇〇

lugionline 发表于 2015-8-13 08:19
985432107 可以手工算？

把思路用程序体现