Fix-it File codegolf (GCJ 2010 1B-A)

https://stackoverflow.com/questions/2892126

04-10-2019
|

Domanda

L'anno scorso (2009), il Google Code Jam caratterizzato un problema interessante come il primo problema in tondo 1B: Albero decisionale

Per quanto il problema sembrava su misura per Lisp-come le lingue, abbiamo spontaneamente avuto un emozionante codegolf qui su SO, in cui alcune lingue sono riusciti a risolvere il problema in un minor numero di caratteri di qualsiasi varietà Lisp, utilizzando un certo numero di tecniche diverse.

Quest'anno la rotonda 1B Problema A ( Fix-it file ) anche sembra su misura per una particolare famiglia di linguaggi, script di shell UNIX. Così continua il "1B-Una tradizione" sarebbe opportuno. : P Ma quale linguaggio finirà con il codice più corto? Cerchiamo di codegolf e vedere!

Descrizione del problema (adattato da pagina ufficiale):

Si è data T casi di test. Ogni banco di prova contiene N linee di tale elenco il percorso completo del tutti directory attualmente esistente sul computer. Ad esempio:

/home
/home/awesome
/home/awesome/wheeeeeee
/home/awesome/wheeeeeee/codegolfrocks
/home/thecakeisalie

Avanti, si è data M linee di tale elenco il percorso completo delle directory che si desidera creare. Sono nello stesso formato come negli esempi precedenti. È possibile creare una directory con il comando mkdir, ma si può farlo solo se la directory principale esiste già. Ad esempio, per creare il /pyonpyon/fumufumu/yeahyeah directory e /pyonpyon/fumufumu/yeahyeahyeah, si avrebbe bisogno di utilizzare mkdir quattro volte:

mkdir /pyonpyon
mkdir /pyonpyon/fumufumu
mkdir /pyonpyon/fumufumu/yeahyeah
mkdir /pyonpyon/fumufumu/yeahyeahyeah

Per ogni test, restituisce il numero di volte che si deve chiamare mkdir per creare tutte le directory che si desidera creare.

ingresso

ingresso è costituito da un file di testo la cui prima riga contiene il numero intero T , il numero di casi di test. Il resto del file contiene i casi di test.

Ogni test inizia con una riga contenente i numeri interi N e M , separati da uno spazio.

Il prossimo N linee contiene il percorso di ogni directory attualmente esistente nel vostro computer (non compresa la directory principale /). Questa è una concatenazione di uno o più non vuota minuscole stringhe alfanumeriche, ognuno preceduto da un singolo /.

Il seguente M righe contengono il percorso di ogni cartella che si desidera creare.

Output

Per ogni caso, stampare una riga contenente Case #X: Y, dove X è il numero del caso e Y è la soluzione.

Limiti

1 = T = 100.

0 = n = 100.

1 = M = 100.

Ogni percorso contiene al massimo 100 caratteri.

Ogni percorso viene visualizzato solo una volta nella lista di directory già presenti sul computer, o nella lista delle directory desiderati. Tuttavia, un percorso può apparire su entrambe le liste, come nell'esempio caso # 3.

Se una directory è nella lista di directory già presente sul computer, sarà anche elencato directory superiore, con l'eccezione del / directory root.

Il file di input è al massimo di 100.000 byte.

Esempio

più grandi casi di test di esempio può essere scaricato qui .

Input:

3
0 2
/home/sparkle/pyon
/home/sparkle/cakes
1 3
/z
/z/y
/z/x
/y/y
2 1
/moo
/moo/wheeeee
/moo

Output:

Case #1: 4
Case #2: 4
Case #3: 0

Codice di golf

Si prega di inviare il vostro codice più corto in qualsiasi lingua che risolve questo problema. Ingresso e uscita possono essere gestite tramite stdin e stdout o da altri file di vostra scelta. Plfacilitare includere una dichiarazione di non responsabilità se il codice ha il potenziale per modificare o eliminare i file esistenti quando eseguito.

Il vincitore sarà la soluzione più breve (dal conte byte) in una lingua con un'implementazione esistente prima dell'inizio del Round 1B 2010. Così, mentre si è liberi di utilizzare una lingua che hai appena fatto al fine di presentare una soluzione 0 byte, non conterà, e probabilmente otterrete downvotes. ^ _ ^

Classifiche

GolfScript
Perl
AWK (non compreso opzioni di interprete)
Bash
Rubino
Python
PyonScript
J
Lua
PostScript
Scala
Haskell
Java
C #

Soluzione

Golfscript, 74 69 65

Ora su una sola riga!
Questa soluzione è di 63 caratteri, ma non verrà eseguito in un ragionevole lasso di tempo per i casi di test con migliaia di percorsi (oltre 8 minuti), così ho scelto di non conta esso.

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

La soluzione più veloce 65 carattere:

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

Complimenti a marcog per l'algoritmo!

Altri suggerimenti

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

Questa soluzione genera un EOFError, ma poiché questa è uscita a stderr è nel rispetto delle regole. Dal momento che l'uscita che ci interessa tutto va a stdout, possiamo tubo che e ignorare stderr.

Si potrebbe leggere il sopra (o alcuni degli altri posti) e pensare che non dovrebbe funzionare. C'è un po 'di trucco per il motivo per cui, e vi spiegherò questo qui. Se si legge con attenzione la questione, ci dice che per ogni directory nel primo elenco, tutti i suoi directory principali sono inclusi nella lista (per esempio se / home / marcog è presente, quindi è / home) [1]. La questione garantisce anche noi ogni lista avrà duplicati [2]. Questo ci permette di buttare tutte le directory nel primo elenco nello stesso set in cui gettiamo le directory dalla seconda lista. Dato che la questione garantisce duplicati per lista, sappiamo che il primo elenco comporterà esattamente n voci nel set. Quindi possiamo avere la risposta definitiva sottraendo N dalla dimensione del set finale.

[1] "I prossimi N righe ogni danno il percorso di una directory che esiste già sul computer. Questo elenco comprende tutte le directory già sul vostro computer diverso directory principale."

[2] "Nessun percorso verrà visualizzato due volte nella lista di directory già presenti sul computer, o nella lista di directory che si desidera creare."

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'

Come mai con programmi di golf dipendenti sulle opzioni della riga di comando interprete, differenza ByteCount le opzioni rispetto al valore predefinito è stato aggiunto alla lunghezza del codice vero e proprio.

rientrato, ha commentato

#! 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

La maggior parte della magia è l'estrazione ramo-da-root. Il trucco è quello di usi una regex per individuare i punti di taglio interessanti (vale a dire: prima di ogni barra, e la fine della stringa), ma per estrarre la stringa utilizzando $PREMATCH (dollaro-backtick di Perl; Markdown non mi permette di includere tale correttamente ) invece dei consueti servizi pattern-matching.

\b individua un limite di parola, che risolve a tutte le parole (directory) inizio e fine. Noi vogliamo solo la loro fine, così abbiamo anteporre un \w. Ma sarebbe tagliare l'ultimo carattere dal percorso, che è un problema se vogliamo ottenere entrambi /foo/bar e /foo/baz nello stesso insieme di dati. Quindi escludiamo detto carattere dal match con \K. Niente di tutto questo sarebbe necessario se Perl ha avuto un metacarattere \>-simile (Emacs regex).

Come un programma stand-alone (106)

for$i(1..<>){($n,$m,%d)=split$",<>;
for(1..$n+$m){$_=<>;$d{$`}++while/\w\K\b/g}
say"Case #$i: ",keys(%d)-$n}

Newlines per la leggibilità; nessuno di loro è necessario o contate in.

Si utilizza caratteristiche che si trovano solo nelle ultime versioni di Perl, in modo da funzionare con perl -M5.010 o successiva.

soluzione Lua, 172 byte:

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

Solo per divertimento, nessuna possibilità di essere mai stato molto breve, naturalmente. Count è dopo la rimozione di spazi vuoti insignificanti, che ho lasciato qui per facilitarne la lettura.

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

Questa ultima versione ha un capriccio. Conta erroneamente directory principale come avente da creare una volta, per compensare la variabile n è -1 all'inizio del ciclo, invece del desiderato 0. Funziona perché la directory principale è garantito che non sia in 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++"/")

simile (ma via più breve: P). Per l'altra soluzione Haskell

finisce in errore, e che si aspetta. O meno che segue le regole è un po 'più inclini a discutere di altre soluzioni. I flussi in uscita e di errore non sono infatti mischiati. Ma se stdout è tamponato, i risultati non vengono mai inviati. Questo è ok per l'uso interattivo (poi basta copiare e incollare l'output della console in un file), ma regole più che altro reindirizzamento. Per farla breve, ./filefixit <input 2>/dev/null fa il trucco.

Il problema può essere evitato inserendo linea rumore nella riga 3: []!_="" (8 byte più, 226 in totale)

Per chiarezza, l'esatto stessa semantica con il pieno rientro e identificatori significativi:

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

ATTENZIONE:. Assicurarsi di eseguire in una directory vuota, in quanto ciò spazzare via il suo contenuto prima cosa per test

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

Ruby, 151 149 144

Traduzione diretta a Ruby di di marcog soluzione 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}"}

PostScript

182 ~~212~~ ~~247~~ ~~262~~ ~~278~~ bytes

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

Utilizzo: $ 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]}

Ciò richiede interruttore -XScopedTypeVariables del GHC.

versione leggibile:

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

Ancora un'altra versione della soluzione di marcog, questa volta a Scala. Funziona con scala, ma avrebbe bisogno di essere messo in una classe per consentire la compilazione con 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 caratteri

Un altro adattamento della versione marcog pitone. Corri con 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()}

Per eseguirlo senza l'opzione -F, cresce di 15 caratteri, dato che allora ha bisogno di questa parte:

BEGIN{FS=" |/"}

PyonScript

158 ~~159~~ bytes

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)

Utilizzo: $ pyon thisfile.pyon <input >output

In base alla soluzione di PostScript.

Poiché lo sviluppo PyonScript è ancora in corso, questo codice funziona sull'attuazione come esisteva all'inizio del Round 1B 2010: http://github.com/KirarinSnow/PyonScript

J - ^{205 159} 140 caratteri

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)

Esegui:

script.ijs < gcj-input

Ancora, emette una riga in più: /

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

. Nota: emette un messaggio di errore, ma funziona ancora correttamente

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow