Файл Fix-it codegolf (GCJ 2010 1B-A)

Question

В прошлом году (2009) Google Code Jam представлял интересную проблему в качестве первой проблемы в Раунде 1B: Дерево решений

Поскольку проблема казалась адаптированной для Lisp-подобных языков, у нас спонтанно появился захватывающий кодогольф в SO, в котором нескольким языкам удалось решить проблему за меньшее количество символов, чем в любой разновидности Lisp, используя целый ряд различных методов.

Задача A раунда 1B этого года ( File Fix-it) также выглядит специально для определенного семейства языков, сценариев оболочки Unix. Поэтому продолжение "традиции 1B-A" было бы уместным.:p Но на каком языке получится самый короткий код? Давайте кодогольф и посмотрим!

Описание проблемы (адаптировано с официальной страницы):

Вам даны тесты 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 ниже.

Если каталог находится в списке каталогов, уже имеющихся на вашем компьютере, его родительский каталог также будет указан, за исключением корневого каталога. /,

Длина входного файла не более 100000 байт.

пример

Более крупные примеры тестов можно скачать здесь.

Входные данные:

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 или другими файлами по вашему выбору. Пожалуйста, включите заявление об отказе от ответственности, если ваш код может изменить или удалить существующие файлы при выполнении.

Победитель будет самым коротким решением (по количеству байтов) в языке с реализацией, существовавшей до начала 1-го раунда 2010 года. Поэтому, пока вы можете свободно использовать язык, который вы только что создали, чтобы представить 0-байт Решение, это не будет учитываться, и вы, вероятно, получите отрицательные отзывы. ^_^

Турнирная таблица

• 65 GolfScript
• 100 Perl
• 121 AWK (не включая опции переводчика)
• 128 Баш
• 144 рубина
• 145 Python
• 158 PyonScript
• 159 Дж
• 172 Луа
• 182 PostScript
• 189 Скала
• 218 Haskell
• 284 Ява
• 398 C#

Answer 1

Golfscript, 74 69 65

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

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

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

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

Слава Маркогу за алгоритм!

Answer 2

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

Answer 3

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

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

Answer 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

Answer 5

Рубин, 151 149 144

Прямой перевод в Python для Ruby of Marcog:

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

Answer 6

Баш, 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

Answer 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

Answer 8

Хаскелл, 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 ++ "/")

Answer 9

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.

Answer 10

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 все еще продолжается, этот код работает над реализацией, существовавшей в начале 1-го раунда 2010 года: http://github.com/KirarinSnow/PyonScript

Answer 11

Скала, 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)}

Answer 12

Ява, 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));}}}

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

Answer 13

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

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

Answer 14

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

Answer 15

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