Ответ 1

Golfscript, 74 69 65

Теперь на одной строке!
Это решение составляет 63 символа, но не будет работать в течение разумного промежутка времени для тестовых примеров с тысячами путей (более 8 минут), поэтому я решил не считать его.

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

Более быстрое решение с 65 символами:

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

Престижность для алгоритма!

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

Ответ 3

Perl, 111 106 100

perl -naE 'BEGIN{<>}++$i;($n,$m,%d)[email protected];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 (долларовый обратный ход, уценка не позволит мне включить что правильно) вместо обычных возможностей сопоставления образцов.

\b находит границу слова, которая разрешает начало и конец всех слов (каталогов). Мы хотим только их окончания, поэтому мы добавим \w. Но это вырезало бы последний символ из пути, что является проблемой, если мы получим как /foo/bar, так и /foo/baz в одном наборе данных. Поэтому мы исключаем указанный символ из матча с помощью \K. Ничего из этого не было бы необходимо, если бы Perl имел метасимвол \> -like (Emacs regexes).

В качестве автономной программы (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 или новее.

Ответ 4

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

Ответ 5

Bash, 175 169 168 135 130 128 h2 >

ПРЕДУПРЕЖДЕНИЕ: Обязательно запускайте пустую директорию, так как это сначала уничтожит ее содержимое для каждого теста.

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

Ответ 6

С#, 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.

Ответ 7

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 <input >output

Ответ 8

Ruby, 151 149 144

Прямой перевод на Ruby of marcog Python solution:

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

Ответ 9

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

Ответ 10

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

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

Ответ 11

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

Ответ 12

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

Ответ 13

AWK - 123 121 символ

Другая адаптация версии python marcog. Запустите с помощью 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=" |/"}

Ответ 14

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

Ответ 15

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

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