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 output

На основе решения PostScript.

Поскольку разработка PyonScript все еще продолжается, этот код работает над реализацией, существовавшей в начале раунда 1B 2010: http://github.com/KirarinSnow/PyonScript

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.

Haskell: 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

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

Решение 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

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

Haskell, 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++"/")

Подобно (но короче: P) другое решение Haskell.

Заканчивается ошибкой, и этого следовало ожидать. Вопрос о том, следует ли это правилам или нет, вызывает больше споров, чем другие решения. Потоки вывода и ошибок действительно не смешиваются. Но если stdout находится в буфере, результаты никогда не отправляются. Это нормально для интерактивного использования (тогда просто скопируйте и вставьте вывод консоли в файл), но в основном это исключает перенаправление. Короче говоря, ./ filefixit / 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 ++ "/")

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

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

Примечание: он выводит сообщение об ошибке, но по-прежнему работает правильно.

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

Тем не менее, выводится одна дополнительная строка: /

PostScript

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 output

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

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] "Ни один путь не появится дважды в списке каталогов, уже существующих на вашем компьютере, или в списке каталогов, которые вы хотите создать."

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'

Как всегда с программами гольфа, зависящими от параметров командной строки интерпретатора, параметры ' К фактической длине кода добавлена ​​разница bytecount относительно значения по умолчанию.

С отступом, комментарии

#! 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 (обратная кавычка доллара; уценка выиграла не позвольте мне включить это должным образом) вместо обычных средств сопоставления с образцом.

\ 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 или новее.