文件修复-IT Codegolf（GCJ 2010 1B-A）

https://stackoverflow.com/questions/2892126

04-10-2019
|

题

去年（2009年）， Google Code Jam 在第1B回合中，有一个有趣的问题是第一个问题：决策树

由于问题似乎是针对类似LISP的语言量身定制的，我们自发地有了令人兴奋的Codegolf 因此，使用多种不同的技术，几种语言设法以比任何LISP品种更少的字符解决了该问题。

今年的第1B回合问题A（文件修复）似乎还针对特定的语言家族量身定制。因此，继续“ 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

代码高尔夫

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

优胜者将是最短的解决方案（通过字节计数），其语言具有在2010年第1B回合开始之前存在的实现的语言。解决方案，它不会计算，您可能会获得低价。 ^_^

积分

65 高尔夫球
100 珀尔
121 尴尬（不包括口译选项）
128 bash
144 红宝石
145 Python
158 Pyonscript
159 j
172 卢阿
182 后记
189 Scala
218 哈斯克尔
284 爪哇
398 C＃

解决方案

高尔夫球 74 69 65

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

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

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

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

感谢Marcog的算法！

其他提示

Python， 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，因此它在规则之内。由于我们对所有人感兴趣的输出都进入了Stdout，因此我们可以忽略STDERR。

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

1]“下一个n行都给出了计算机上已经存在的一个目录的路径。此列表将包括您的计算机上的每个目录，而不是根目录。”

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

佩尔， 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的perl提取字符串 $PREMATCH （Dollar-Backtick; Markdown不能让我正确地包含它）而不是通常的模式匹配设施。

\b 找到一个单词边界，该单词为所有单词“（目录”）启动和结束。我们只想要他们的结局，所以我们准备了 \w. 。但这将从路径上切掉最后一个角色，如果我们两者都得到 /foo/bar 和 /foo/baz 在同一数据集中。所以我们排除了比赛中所说的角色 \K. 。如果Perl有一个 \>- 像（Emacs Regexes）Metacharacter。

作为独立计划（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或更高版本运行。

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

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中。

哈斯克尔，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被缓冲，则永远不会发送结果。对于交互式使用，这是可以的（然后只需复制paste控制台输出到文件），但是它大多排除了重定向。简而言之 ./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 ++ "/")

bash， 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

红宝石， 151 149 144

直接翻译为Ruby的 Marcog的Python解决方案:

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}"}

后记

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

哈斯克尔：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

Scala， 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)}

尴尬 - 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=" |/"}

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开发仍在进行中，因此该代码在第1B 2010年开始时存在于实施方面： http://github.com/kirarinsnow/pyonscript

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

尽管如此，它还是输出一条线：/

Java，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));}}}

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

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow