16

去年（2009 年），Google Code Jam将一个有趣的问题作为第 1B 轮的第一个问题：决策树

由于这个问题似乎是为类似 Lisp 的语言量身定做的，因此我们自发地在 SO 上进行了一次令人兴奋的 codegolf，其中一些语言设法用比任何 Lisp 种类更少的字符解决了这个问题，使用了相当多的不同技术。

今年的 Round 1B Problem 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

代码高尔夫

请以解决此问题的任何语言发布您的最短代码。输入和输出可以通过标准输入和标准输出或您选择的其他文件进行处理。如果您的代码在执行时有可能修改或删除现有文件，请包含免责声明。

获胜者将是在 2010 年第 1B 轮开始之前存在实施的语言中最短的解决方案（按字节数计算）。因此，尽管您可以自由使用您刚刚编写的语言来提交 0 字节解决方案，它不会计算在内，你可能会被否决。^_^

积分榜

4

15 回答 15

10

蟒蛇，193 175 173 171 166 165 164 156 151 149 147 146 145

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，因此它在规则范围内。由于我们感兴趣的输出都发送到标准输出，我们可以通过管道将其忽略并忽略标准错误。

您可能会阅读上述（或其他一些帖子）并认为它不应该工作。为什么会有一些技巧，我将在这里解释这一点。如果你仔细阅读这个问题，它会告诉我们，对于第一个列表中的每个目录，它的所有父目录也都包含在列表中（例如，如果 /home/marcog 存在，那么 /home 也存在）[1]。这个问题还保证我们每个列表都没有重复项 [2]。这使我们可以将第一个列表中的所有目录放入我们将第二个列表中的目录放入的同一集合中。由于该问题保证每个列表没有重复项，因此我们知道第一个列表将导致集合中恰好有 N 个条目。因此，我们可以通过从最终集合的大小中减去 N 来得到最终答案。

[1] “接下来的 N 行每一行都给出了您计算机上已经存在的一个目录的路径。此列表将包括您计算机上除根目录之外的所有目录。”

[2] “在您计算机上已有的目录列表或您希望创建的目录列表中，没有路径会出现两次。”

于 2010-05-23T15:31:53.380 回答
8

高尔夫球手，74 69 65

现在在一条线上！
这个解决方案是 63 个字符，但是对于具有数千条路径（超过 8 分钟）的测试用例，它不会在合理的时间内运行，所以我选择不计算它。

n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]|}/}*,@-n@}/

更快的 65 个字符的解决方案：

n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]+}/.&}*,@-n@}/

感谢 marcog 的算法！

于 2010-05-23T14:58:17.033 回答
4

Perl，111 106 100

perl -naE 'BEGIN{<>}++$i;($n,$m,%d)=@F;for(1..$n+$m){$_=<>;$d{$`}++while/\w\K\b/g}say"Case #$i: ",keys(%d)-$n'

与依赖解释器命令行选项的高尔夫程序一样，选项相对于默认值的字节数差异已添加到实际代码长度中。

缩进，注释

#! perl -na      # activate line mode and autosplit
BEGIN { <> }     # skip test case count

# now for each test case:

++$i;            # increment test counter
($n,$m,%d) = @F; # read N and M;
                 # clear out directory hash

for (1..$n+$m) { # for each expected pathname:
  $_ = <>;          # read it
  $d{$`}++          # add to hash...
    while /\w\K\b/g # ...all branches from root
}

say "Case #$i: ", keys(%d) - $n

最神奇的是从根提取分支。诀窍是使用正则表达式来定位有趣的切割点（即：在每个斜线之前，以及字符串的结尾），但是使用 Perl 提取字符串$PREMATCH（美元反引号；markdown 不会让我正确地包含它）而不是通常的模式匹配工具。

\b定位一个单词边界，它解析为所有单词的“（目录”）开始和结束。我们只想要他们的结尾，所以我们在前面加上一个\w. 但这会从路径中删除最后一个字符，如果我们同时在同一个数据集中获取这两个字符，这是一个/foo/bar问题/foo/baz。因此，我们将所述字符从与 的匹配中排除\K。\>如果 Perl 有类似- 的（Emacs 正则表达式）元字符，那么这些都不是必需的。

作为独立程序 (106)

for$i(1..<>){($n,$m,%d)=split$",<>;
for(1..$n+$m){$_=<>;$d{$`}++while/\w\K\b/g}
say"Case #$i: ",keys(%d)-$n}

易读的换行符；它们都不是必需的或计算在内。

它使用仅在最新版本的 Perl 中提供的功能，因此请使用 perl -M5.010 或更高版本运行。

于 2010-05-24T00:42:33.800 回答
3

Lua解决方案，172字节：

r,n=io.read,"*n"for i=1,r(n)do a,c,s=r(n),0,{}for i=1,a+r()do k=""for x in r():gmatch"[^/]+"do k=k.."/"..x c=c+(s[k]or 1);s[k]=0 end end print("Case #"..i..": "..(c-a))end
于 2010-05-23T19:23:33.050 回答
2

巴什，175 169 168 135 130 128

警告：确保在空目录中运行，因为这将在每次测试的第一件事中清除其内容。

read t
for((;x++<t;));do
rm -r *
read n m
for((i=n+m;i--;));do
read d
mkdir -p .$d
done
echo Case \#$x: $[`find|wc -l`-n-1]
done
于 2010-05-23T14:37:50.093 回答
2

后记

182 212 247 262 278字节

1[([){exch}/C{concatstrings}/R{(%lineedit)run}>>begin 1
R{(: )[(Case #)3{=only}repeat<<>>R 1 index add{()<<R]{99 string
cvs C<C>C dup 3 index[<>put}forall pop}repeat[length[sub =}for

用法：$ gs -q -dNODISPLAY -dNOPROMPT thisfile.ps <input >output

于 2010-05-23T16:58:14.577 回答
2

红宝石，151 149 144

直接翻译marcog的Python解决方案的Ruby ：

gets.to_i.times{|i|n,m=gets.split.map &:to_i
d={}
(n+m).times{gets.strip.split('/').inject{|a,p|d[a+='/'+p]=a}}
puts"Case ##{i+1}: #{d.size-n}"}
于 2010-05-23T21:21:38.210 回答
2

哈斯克尔，218

import Data.List
main=interact$(!1).tail.lines
(l:j)!i=let{[n,m]=map read$words l;(p,k)=splitAt(n+m)j}in"Case #"++show i++": "++show(length(nub$(>>=s)p)-n)++"\n"++k!(i+1)
s(_:p)=map(flip take p)$elemIndices '/'(p++"/")

与其他 Haskell 解决方案类似（但更短：P）。

以错误告终，这是意料之中的。与其他解决方案相比，这是否遵循规则更容易引起争议。输出流和错误流确实没有混淆。但如果 stdout 被缓冲，则永远不会发送结果。这对于交互式使用是可以的（然后只需将控制台输出复制粘贴到文件中），但它主要排除了重定向。简而言之，./filefixit <input 2>/dev/null就可以了。

可以通过在第 3 行插入线路噪声来避免该问题：（[]!_=""多 8 个字节，共 226 个）

为清楚起见，具有完全缩进和有意义标识符的完全相同的语义：

import Data.List
main = interact $ testsStartingAt 1 . tail . lines
testsStartingAt _   []   = "" -- this line optional
testsStartingAt i (l:ls) = testOutput ++ testsStartingAt (i+1) ls'
    where [n,m]       = map read $ words l
          (paths,ls') = splitAt (n+m) ls
          testResult  = length (nub $ concatMap splitPath paths) - n
          testOutput  = "Case #" ++ show i ++ ": " ++ show testResult ++ "\n"
splitPath (_:p) = map (flip take p) $ elemIndices '/' (p ++ "/")
于 2010-05-23T23:40:23.857 回答
1

C#，489 442 400 398

只是为了好玩，当然没有机会很短。计数是在删除无关紧要的空白之后，我把它留在这里是为了便于阅读。

namespace System
{
    class P
    {
        static void Main(string[]a)
        {
            int c = 0, n, m, d, l = 1;
            var f = IO.File.ReadAllLines(a[0]);

            while (c < int.Parse(f[0]))
            {
                var o = f[l++].Split(' ');
                n = int.Parse(o[0]);
                m = int.Parse(o[1]);
                var p = new Collections.Generic.HashSet<string>();

                while (n-- > 0)
                    p.Add(f[l++]);

                while (m-- > 0)
                    for (o = f[l++].Split('/'), d = 0; d++ < o.Length; )
                        if (p.Add(string.Join("/", o, 0, d)))
                            n++;

                Console.Write("Case #{0}: {1}\n", ++c, n);
            }
        }
    }
}

这个最新版本有一个怪癖。它错误地将根目录计算为必须创建一次，以补偿在循环开始时变量 n 为 -1，而不是所需的 0。它之所以有效，是因为保证根目录不在 N 中。

于 2010-05-23T16:31:38.263 回答
0

爪哇，277

import java.util.*;enum A{_;{Scanner s=new Scanner(System.in);for(int
t=s.nextInt(),i=0,n,j;i++<t;){Set x=new
HashSet();n=s.nextInt();for(j=s.nextInt();j-->-n;){String b="";for(String
c:s.next().split("/"))x.add(b+=c+'/');}System.out.println("Case #"+i+": "+(x.size()-n-1));}}}

注意：它会输出一条错误消息，但仍然可以正常工作。

于 2010-05-23T16:48:11.723 回答
0

哈斯克尔：299

import Data.List
import Text.Printf
a[]=[]
a(x:z)=(r-n):next where{;[n,m]=map read$words x;t=n+m;r=length$nub$concatMap(f.reverse)$take t z;next=a$drop t z;f""=[];f y=y:f z where(a,b:z)=span(/='/')y}
main=do{z<-getContents;putStr$unlines[printf"Case #%d: %d"x v|(x::Int,v)<-zip[1..]$a$tail$lines z]}

这需要GHC的-XScopedTypeVariables开关。

可读版本：

import Data.List
import Text.Printf

a [] = []
a (x:xs) = (r-n) : next where
    [n,m] = map read $ words x
    t = n+m
    r = length $ nub $ concatMap (f . reverse) $ take t xs
    next = a $ drop t xs
    f "" = []
    f y = y : f bs where
        (a,b:bs) = span (/= '/') y

cleanUp a = unlines [printf "Case #%d: %d" x v | (x::Int,v::Int) <- zip [1..] a]

main = do
    z<-getContents
    putStr$cleanUp$a$tail$lines z
于 2010-05-23T20:40:38.577 回答
0

PyonScript

158 159字节

1({[([){exch}/R{(%lineedit)run}>>begin R{(: )[(Case #)3{=only}repeat<<>>R 1
index +{<><<R]{str cat<C>cat dup 3 index[<>put}forall pop}repeat[length[-
=}for}1)

用法：$ pyon thisfile.pyon <input >output

基于 PostScript 解决方案。

由于 PyonScript 开发仍在进行中，此代码适用于 2010 年第 1B 轮开始时存在的实现：http: //github.com/KirarinSnow/PyonScript

于 2010-05-23T22:19:31.943 回答
0

AWK - 123 121 个字符

marcog python版本的另一个改编。运行awk -F'[ \]' -f fixit.awk

function p(){if(c++>1)print"Case #"c-2": "length(k)-n}
/\//{for(y=i=1;i<NF;)k[y=y"/"$++i];next}
{p();n=$1;delete k}
END{p()}

要在没有-F选项的情况下运行它，它会增加 15 个字符，因为它需要这部分：

BEGIN{FS=" |/"}
于 2010-05-24T10:39:21.150 回答
0

斯卡拉，190 189

marcog 解决方案的另一个版本，这次是在 Scala 中。与 一起运行scala，但需要放入一个类中以允许与scalac.

for(c←1 to readInt){val I=readLine split" "map(_.toInt)
var d=Set("")
for(i←1-I(0)to I(1)){var a="";for(w←readLine split"/"){a+="/"+w;d+=a}}
printf("Case #%d: %d\n",c,d.size-I(0)-2)}
于 2010-05-24T14:19:18.967 回答
0

J - 205 159 140 个字符

c=:0
f=:3 :0
c=:>:c
'a b'=:({.,+/)".>{.y
('Case #',(":c),': ',":a-~3 :'#~.,/>\"1<;.1"1 y'>(>:i.b){y)1!:2<2
(>:b)}.y
)
f^:_(}.<;._2 (1!:1)<3)

跑：

script.ijs < gcj-input

尽管如此，它还是输出了额外的一行：/

于 2010-05-25T08:21:24.690 回答