Файл для исправления codegolf (GCJ 2010 1B-A)

https://stackoverflow.com/questions/2892126

04-10-2019
|

Вопрос

В прошлом году (2009), Замятие кода Google показал интересную задачу в качестве первой задачи в раунде 1B: Дерево принятия решений

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

Задача A раунда 1B этого года (Файл Для исправления) также, похоже, адаптирован для определенного семейства языков, сценариев оболочки Unix.Так что продолжение "традиции 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 или другими файлами по вашему выбору. Пожалуйста, включите отказ от ответственности, если ваш код потенциально может изменять или удалять существующие файлы при выполнении.

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

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

65 Гольфскрипт
100 Perl
121 AWK ( АВК ) (не включая опции переводчика)
128 Удар
144 Рубин
145 Питон
158 PyonScript
159 J
172 Lua
182 Постскриптум
189 Скала
218 Хаскелл
284 Java
398 C#

Решение

Golfscript, 74 69 65

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

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

Чем более высокое решение 65 символов:

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

Кедос для Marcog для алгоритма!

Другие советы

Питон, 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, но поскольку это выводится на Стдерр, он находится в правилах. Поскольку вывод, которым мы заинтересованы в том, чтобы все идет в Stdout, мы можем трусить это и игнорировать STDERR.

Вы можете прочитать вышеупомянутые (или некоторые другие сообщения) и думать, что он не должен работать. Есть немного трюка, почему, и я объясню это здесь. Если вы внимательно прочитаете вопрос, он говорит нам, что для каждого каталога в первом списке все его родительские каталоги также включены в список (например, присутствуют, если / home / marcog, поэтому есть / home) [1]. Вопрос также гарантирует нам каждый список не будет дубликатов [2]. Это позволяет нам бросить все каталоги в первый список в тот же, в который мы бросаем каталоги из второго списка. Поскольку вопрос не гарантирует никаких дубликатов в списке, мы знаем, что первый список приведет к ровно 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'

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

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

#! 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 или более поздней.

Раствор 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);
            }
        }
    }
}

Эта последняя версия имеет quirk. Это по ошибке считает корневой каталог, как следует создавать один раз, чтобы компенсировать переменную n --1 в начале цикла вместо желаемого 0. Это работает, потому что корневой каталог гарантирован не в 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 <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 ++ "/")

Баш, 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 Решение Python 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}"}

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

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

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

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

Пищевой

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.

Поскольку разработка Py RepScript все еще продолжается, этот код работает в реализации, поскольку оно существовало в начале раунда 1b 2010: http://github.com/kirarinsnow/pyenscript

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