PUZZLEUP 2014

newkid

答案确实是AAB, 从12位到16位都是：

WITH t AS (
SELECT STR FROM (
SELECT REPLACE(SYS_CONNECT_BY_PATH(c,','),',') str,LEVEL lvl
  FROM (SELECT 'A' c FROM DUAL UNION ALL SELECT 'B' FROM DUAL)
WHERE LEVEL>=10 AND MOD(LEVEL,2)=0
CONNECT BY LEVEL<=16
)
WHERE LENGTH(REPLACE(str,'A'))=lvl/2
      AND INSTR(str,'AAA')>0
      AND INSTR(str,'AAB')>0
      AND INSTR(str,'ABA')>0
      AND INSTR(str,'ABB')>0
      AND INSTR(str,'BAA')>0
      AND INSTR(str,'BAB')>0
      AND INSTR(str,'BBA')>0
      AND INSTR(str,'BBB')>0
)
SELECT * FROM (
SELECT code,COUNT(DISTINCT str) cnt, RANK() OVER(ORDER BY COUNT(DISTINCT str) DESC) rnk
  FROM (
SELECT str,SUBSTR(str,lvl,3) code
  FROM t,(SELECT LEVEL lvl FROM DUAL CONNECT BY LEVEL<30)
WHERE lvl<=INSTR(str,'ABA')-1
)
GROUP BY code
)
WHERE rnk=1;

COD        CNT        RNK
--- ---------- ----------
AAB       4377          1

Elapsed: 00:00:15.86

Naldonado

newkid 发表于 2014-8-1 02:21
答案确实是AAB, 从12位到16位都是：

WITH t AS (

  无他意，刚试了下sql，感觉我们这条sql跑的挺快的。

peter1166

#2 Code Game  。 什么时候出？

〇〇

peter1166 发表于 2014-8-5 08:24
#2 Code Game  。 什么时候出？

2周1题

lastwinner

试考察最短的文本组合 aaababbbaa ，其包含了八组可能的组合
aaa/aab/aba/bab/abb/bbb/bba/baa

在这个10字符的排列里，A占据了6个，B占据了4个，A和B并不是等概率出现的
这10个字符通过平移字符的方式，其等价变换如下：
aaababbbaa
aababbbaaa
ababbbaaab   --此时a和b等概率出现
babbbaaaba
abbbaaabab
bbbaaababb
bbaaababbb
baaababbba

镜像字符的方式也是可以等价的，例如
aaababbbaa
镜像后，是
aabbbabaaa
这和刚才的第七种变化实际上等价（a和b对调了而已）
bbaaababbb
所以，从概率上来说，只需要考虑上面列的8种情况即可

lastwinner

各组排列中，在aba之前的组合
aaababbbaa ，aaa、aab
aababbbaaa ，aab
ababbbaaab  ，NULL
babbbaaaba ，所有其他组合
abbbaaabab ，除了bab之外的其他组合
bbbaaababb ，除了bab、abb之外的其他组合
bbaaababbb ，除了bab、abb、bbb之外的其他组合
baaababbba ，baa、aaa、aab

综上，aab出现得最多，多达7次，因此答案是aab。其次是aaa，再次是baa

lastwinner

上述8组，在镜像后，还寻找在aba之前的
aabbbabaaa ，除baa、aaa
aaabbbabaa ，除baa
baaabbbaba ，所有其他组合
abaaabbbab ，NULL
babaaabbba ，bab
bbabaaabbb ，bba、bab
bbbabaaabb ，bbb、bba、bab
abbbabaaab ，abb、bbb、bba、bab
此时aab仅占3次，bab最多，是7次，其次是bba，6次，再次是bbb，5次



两次总的来看，aab总计10次，依然是最高。
上述推导还不完整，上述只能证明，当字符串都按最小组合出现时，aab最佳。
实际上10字符的组合，共有power(2,10)种，大多数组合里重复的字符串很多，例如aaaaaaabaa，光aaa就有4个。
而上面仅仅是其中的16个组合，尚需证明在其余的组合里，aab的优势最大，这个没法通过数据总体上分布均匀，A和B出现的总次数相等之类的来证明其余的组合里aab优势最大。

lastwinner

newkid 发表于 2014-8-1 02:21
答案确实是AAB, 从12位到16位都是：

WITH t AS (

你这个条件 WHERE LENGTH(REPLACE(str,'A'))=lvl/2
从逻辑上说是不对的，举个简单的例子，就这三字节的八个组合，从整体上看，A、B的分布是均匀，不能因此就直接不考虑这三字节的组合。当然，我们最小要从4字节的字符串来考虑，否则组合只出现一次，何来先后？

实际上我认为应该通过数学归纳法来证明，假如在4字节的字符串里aab占优，在5字节的字符串里aab也占优，那么证明出6字节的字符串里aab也是占优的，就严密了

考虑字符串的最后两位，只可能是
aa
ab
ba
bb
四种，当字符串长度增加1时，我们可以将其只加到字符串的末尾，于是就有8种情况
aaa
aab
aba
abb
baa
bab
bba
bbb

这八种情况无论是哪种出现，都不改变之前的某组合占优情况，因为除了aba之外的其余7种各出现了一次
因此剩下的事情，就是用sql计算出4字符串和5字符串里，均最占优的组合，就是要求的结果

newkid

lastwinner 发表于 2014-8-5 14:48
你这个条件 WHERE LENGTH(REPLACE(str,'A'))=lvl/2
从逻辑上说是不对的，举个简单的例子，就这三字节的八 ...

那就要看怎么理解题意了。
我的理解是TEXT中一半字符是A, 另外一半是B，所以才有这个WHERE。如果不是这么理解，出现概率就等于废话了。
按题目要求，在“同一个”TEXT中要"同时"包含八种代码。所以最小长度为10。小于10的就不用考虑。

newkid

Naldonado 发表于 2014-8-4 22:15
无他意，刚试了下sql，感觉我们这条sql跑的挺快的。

你们的计划是怎么样的，ORACLE的计划又是怎么样的？