Kir*_*now 16 language-agnostic rosetta-stone
去年(2009年),Google Code Jam引发了一个有趣的问题,即第1B轮第一个问题:决策树
由于问题似乎是针对类似Lisp的语言量身定制的,我们在SO上自发地拥有了一个激动人心的代码高手,其中一些语言使用了许多不同的技术设法用比任何Lisp变种更少的字符来解决问题.
今年的第1B轮问题A(File Fix-it)似乎也适用于特定的语言系列,Unix shell脚本.所以继续"1B-A传统"是合适的.:p但哪种语言最终会得到最短的代码？让我们看看codegolf吧!
问题描述(改编自官方页面):
您将获得T测试用例.每个测试用例包含N行,列出计算机上当前存在的所有目录的完整路径.例如:
/home
/home/awesome
/home/awesome/wheeeeeee
/home/awesome/wheeeeeee/codegolfrocks
/home/thecakeisalie
接下来,您将获得M行,其中列出了您要创建的目录的完整路径.它们的格式与前面的示例相同.您可以使用该mkdir命令创建目录,但只有父目录已存在才能创建目录.例如,要创建目录/pyonpyon/fumufumu/yeahyeah和/pyonpyon/fumufumu/yeahyeahyeah,你将需要使用mkdir四次:
mkdir /pyonpyon
mkdir /pyonpyon/fumufumu
mkdir /pyonpyon/fumufumu/yeahyeah
mkdir /pyonpyon/fumufumu/yeahyeahyeah
对于每个测试用例,返回您必须调用的次数,mkdir以创建您要创建的所有目录.
输入
输入包含一个文本文件,其第一行包含整数T,即测试用例的数量.该文件的其余部分包含测试用例.
每个测试用例都以包含整数N和M的行开头,用空格分隔.
接下来的N行包含计算机上当前存在的每个目录的路径(不包括根目录/).这是一个或多个非空的小写字母数字字符串的串联,每个字符串前面都有一个字符串/.
以下M行包含您要创建的每个目录的路径.
产量
对于每种情况,打印一行包含Case #X: Y,X案例编号在哪里,Y是解决方案.
范围
1≤T≤100.
0≤N≤100.
1≤M≤100.
每个路径最多包含100个字符.
每个路径只在计算机上已有的目录列表中或所需目录列表中出现一次.但是,路径可能出现在两个列表中,如下面的示例#3中所示.
如果目录位于计算机上已有的目录列表中,则还将列出其父目录,但根目录除外/.
输入文件最多为100,000字节.
例
可以在此处下载更大的样本测试用例.
输入:
3
0 2
/home/sparkle/pyon
/home/sparkle/cakes
1 3
/z
/z/y
/z/x
/y/y
2 1
/moo
/moo/wheeeee
/moo
输出:
Case #1: 4
Case #2: 4
Case #3: 0
Code Golf
请用解决此问题的任何语言发布您的最短代码.输入和输出可以通过stdin和stdout或您选择的其他文件来处理.如果您的代码有可能在执行时修改或删除现有文件,请附上免责声明.
获胜者将是在2010年第1B轮开始之前存在实现的语言中最短的解决方案(按字节数).因此,您可以自由使用您刚刚编写的语言,以便提交0字节解决方案,它不会计算,你可能会得到downvotes.^ _ ^
排名
mar*_*cog 10
r=raw_input;c=0;r()
while 1:N,M=map(int,r().split());d={};c+=1;exec"e=r()\nwhile e:d[e]=e,_=e.rsplit('/',1)\n"*(N+M);print'Case #%d:'%c,len(d)-N
此解决方案抛出EOFError,但由于这是输出到stderr,因此它在规则范围内.由于我们感兴趣的输出全部转到stdout,我们可以管道并忽略stderr.
您可能会阅读上述(或其他一些帖子),并认为它不应该起作用.为什么会有一些技巧,我将在这里解释一下.如果你仔细阅读这个问题,它会告诉我们,对于第一个列表中的每个目录,所有它的父目录也都包含在列表中(例如,如果/ home/marcog存在,那么/ home)[1].这个问题也保证了我们每个列表都没有重复[2].这使我们可以将第一个列表中的所有目录放入我们从第二个列表中抛出目录的同一个集合中.由于问题保证每个列表没有重复,我们知道第一个列表将导致集合中的N个条目.因此,我们可以通过从最终集合的大小中减去N来得到最终答案.
[1]"接下来的N行各自给出了计算机上已存在的一个目录的路径.此列表将包括计算机上已存在的除根目录之外的每个目录."
[2]"在您的计算机上已有的目录列表中或您要创建的目录列表中,不会出现两次路径."
现在单行!
此解决方案为63个字符,但对于具有数千个路径(超过8分钟)的测试用例,将无法在合理的时间内运行,因此我选择不计算它.
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]|}/}*,@-n@}/
更快的65字符解决方案:
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]+}/.&}*,@-n@}/
感谢Marcog的算法!