puzzleup 2018

newkid

#17 DIGITAL DISPLAY

A 2x2 digital display consists of 12 segments. You will create a shape by turning some of the segments on. Rules:

At least one of the segments will be on.
When multiple segments are on, those segments will form a connected shape.

How many different shapes can be created?

For example, for a square-shaped display with 4 segments, the answer would be 13.
1 shape with all segments on; 4 shapes for one, two or three turned on segments each.




一个2x2的数字显示屏由12段组成（形状如汉字的"田"，由12段发光二极管构成）。 你可以通过点亮一些段来创建形状。规则：

至少有一段被点亮。
当多个段被点亮时，这些段将构成连通的形状。

总共可以创建多少种不同的形状？

例如，对于具有4个段的方形显示屏，答案为13。
所有段都点亮，这是1种形状；
一段，两段或三段点亮，每种情形各有4种形状。  
-----------------
这个是可以用SQL玩出来的。

newkid

在写今天的SQL的时候，突然想起一个技巧可以用在以前的一个题目，参见本贴的#70楼，M哥发起的挑战：
倒个100升看看，桶大小分别是 43, 59, 100, 分成 50，50

把以前的SQL稍微改良一下，马上跑出来了：

with
move AS (
   SELECT p  ---- 源水桶编号
         ,m  ---- 目标水桶编号
         ,' 43 59100' 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,found,rn) as (
select '  0  0100', CAST('0  0100' AS VARCHAR2(4000)),0,1 FROM DUAL
UNION ALL
SELECT new_s
      ,path||','||new_s
      ,COUNT(CASE WHEN new_s='  0 50 50' THEN 1 END) OVER() found
      ,ROW_NUMBER() OVER(PARTITION BY new_s ORDER BY LENGTH(path)) rn
  FROM t
      ,move
      ,LATERAL(SELECT  DECODE(1,p,ps,m,ms,SUBSTR(s,1,3))
                      ||DECODE(2,p,ps,m,ms,SUBSTR(s,4,3))
                      ||DECODE(3,p,ps,m,ms,SUBSTR(s,7,3)) new_s
                 FROM (SELECT  LPAD(SUBSTR(s,(p-1)*3+1,3)-d,3) ps ,LPAD(SUBSTR(s,(m-1)*3+1,3)+d,3) ms
                        FROM (SELECT LEAST(TO_NUMBER(SUBSTR(s,(p-1)*3+1,3)),TO_NUMBER(SUBSTR(c,(m-1)*3+1,3)-SUBSTR(s,(m-1)*3+1,3))) d FROM DUAL)
                      )
               )
WHERE found=0
       AND TO_NUMBER(SUBSTR(t.s,(p-1)*3+1,3))<>0 -----源水桶有水
       AND SUBSTR(t.s,(m-1)*3+1,3)<SUBSTR(c,(m-1)*3+1,3) -----目标水桶有空
       AND INSTR(path,new_s
                )=0
       AND t.rn=1
)
select path from t where s='  0 50 50'
;

PATH
------------------------------------------------------------------------------------------------------------------------------------------------------
0  0100, 43  0 57,  0 43 57, 43 43 14, 27 59 14, 27  0 73,  0 27 73, 43 27 30, 11 59 30, 11  0 89,  0 11 89, 43 11 46,  0 54 46, 43 54  3, 38 59  3, 3
8  0 62,  0 38 62, 43 38 19, 22 59 19, 22  0 78,  0 22 78, 43 22 35,  6 59 35,  6  0 94,  0  6 94, 43  6 51,  0 49 51, 43 49  8, 33 59  8, 33  0 67,
0 33 67, 43 33 24, 17 59 24, 17  0 83,  0 17 83, 43 17 40,  1 59 40,  1  0 99,  0  1 99, 43  1 56,  0 44 56, 43 44 13, 28 59 13, 28  0 72,  0 28 72, 4
3 28 29, 12 59 29, 12  0 88,  0 12 88, 43 12 45,  0 55 45, 43 55  2, 39 59  2, 39  0 61,  0 39 61, 43 39 18, 23 59 18, 23  0 77,  0 23 77, 43 23 34,
7 59 34,  7  0 93,  0  7 93, 43  7 50,  0 50 50

〇〇

17#数字显示


2x2数字显示屏由12个线段组成。 您将通过打开一些线段来创建形状。规则：

至少有一个线段打开。
当多个线段打开时，这些线段将形成连接形状。

可以创建多少种不同的形状？

例如，对于具有4个线段的方形显示器，答案为13。
1个形状，所有线段都在;
1111

打开一个，两个或三个线段的形状各4个。
1: 1000，0100，0010，0001
2: 1100，1001，0110，0011
3: 1110，0111，1011，1101

〇〇

〇〇 发表于 2018-11-22 11:05
17#数字显示

关键在于判断打开超过2个线段的形状要全连接的

solomon_007

〇〇 发表于 2018-11-22 11:05
17#数字显示

题目看得有点不是很明白，

举例中的 2: 1100，1001，0110，0011,   那为什么 1010，0101 这个两个不算形状呢？ 没搞懂

能解释一下吗？

solomon_007

solomon_007 发表于 2018-11-22 11:22
题目看得有点不是很明白，

举例中的 2: 1100，1001，0110，0011,   那为什么 1010，0101 这个两个不算 ...

明白了，打开的，要求是连接的

〇〇

solomon_007 发表于 2018-11-22 11:51
明白了，打开的，要求是连接的

图
http://www.puzzleup.com/2018/img/puzzle/2018/17-1.png
http://www.puzzleup.com/2018/img/puzzle/2018/17-2.png

〇〇

solomon_007 发表于 2018-11-22 11:22
题目看得有点不是很明白，

举例中的 2: 1100，1001，0110，0011,   那为什么 1010，0101 这个两个不算 ...

4个线段，16种形状，去掉一个全关的，去掉这2个不连的正好13

〇〇

感觉cte可以，只要规定新加入的必须连上已有的，因为形状对称，只要考虑第一象限的一半
先画个壳子，连接条件，线不能重复，新线的点必须已经存在
with point (n,a,b) as(
select level,ceil(level/3),mod(level-1,3)+1 from dual connect by level<=9),
line (n,n1,n2) as(select rownum,p1.n,p2.n from point p1,point p2 where abs(p2.a-p1.a) + abs(p2.b-p1.b)=1 and p1.n<p2.n),
shap (lv,nn,s) as(select 1,n,power(2,n) from line
union all
select lv+1,n,s+power(2,n) from shap,line where  bitand(s,power(2,n))=0 and
lv<2)
select count(*) from shap;

solomon_007

〇〇 发表于 2018-11-22 11:56
图
http://www.puzzleup.com/2018/img/puzzle/2018/17-1.png
http://www.puzzleup.com/2018/img/puzzle ...

有图一下子就明白了