Archivo FIX-IT CodeGolf (GCJ 2010 1B-A)
https://stackoverflow.com/questions/2892126
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
El año pasado (2009), el Mermelada de código de Google presentó un problema interesante como el primer problema en la ronda 1B: Árbol de decisión
Como el problema parecía adaptado para los idiomas de LISP, teníamos espontáneamente un emocionante Codegolf Aquí, en el que algunos idiomas lograron resolver el problema en menos caracteres que cualquier variedad LISP, utilizando bastantes técnicas diferentes.
El problema de la ronda 1b de este año (Archivo fijo-it) también parece adaptado para una familia particular de idiomas, unix shell scripts. Entonces, continuar la "tradición 1B-A" sería apropiado. : P ¿Pero qué idioma terminará con el código más corto? ¡Vamos a Codegolf y veamos!
Descripción del problema (adaptado de la página oficial):
Tú te das T Casos de prueba. Cada caso de prueba contiene norte líneas que enumeran la ruta completa de todos Directorios actualmente existentes en su computadora. Por ejemplo:
/home
/home/awesome
/home/awesome/wheeeeeee
/home/awesome/wheeeeeee/codegolfrocks
/home/thecakeisalie
A continuación, se le da METRO líneas que enumeran la ruta completa de los directorios que le gustaría crear. Están en el mismo formato que los ejemplos anteriores. Puede crear un directorio utilizando el mkdir Comando, pero solo puede hacerlo si el directorio principal ya existe. Por ejemplo, para crear los directorios /pyonpyon/fumufumu/yeahyeah y /pyonpyon/fumufumu/yeahyeahyeah, necesitarías usar mkdir cuatro veces:
mkdir /pyonpyon
mkdir /pyonpyon/fumufumu
mkdir /pyonpyon/fumufumu/yeahyeah
mkdir /pyonpyon/fumufumu/yeahyeahyeah
Para cada caso de prueba, devuelva el número de veces que debe llamar mkdir Para crear todos los directorios que le gustaría crear.
Aporte
La entrada consiste en un archivo de texto cuya primera línea contiene el entero T, el número de casos de prueba. El resto del archivo contiene los casos de prueba.
Cada caso de prueba comienza con una línea que contiene los enteros norte y METRO, separado por un espacio.
El siguiente norte Las líneas contienen la ruta de cada directorio actualmente existente en su computadora (sin incluir el directorio raíz /). Esta es una concatenación de una o más cuerdas alfanuméricas en minúsculas no vacías, cada una precedida por un solo /.
El seguimiento METRO Las líneas contienen la ruta de cada directorio que le gustaría crear.
Producción
Para cada caso, imprima una línea que contenga Case #X: Y, dónde X es el número de caso y Y es la solución.
Límites
1 ≤ t ≤ 100.
0 ≤ n ≤ 100.
1 ≤ m ≤ 100.
Cada ruta contiene como máximo 100 caracteres.
Cada ruta aparece solo una vez en la lista de directorios que ya están en su computadora, o en la lista de directorios deseados. Sin embargo, una ruta puede aparecer en ambas listas, como en el ejemplo del caso #3 a continuación.
Si un directorio está en la lista de directorios que ya están en su computadora, su directorio principal también se enumerará, con la excepción del directorio raíz /.
El archivo de entrada tiene como máximo 100,000 bytes de largo.
Ejemplo
Se pueden descargar casos de prueba de muestra más grandes aquí.
Aporte:
3
0 2
/home/sparkle/pyon
/home/sparkle/cakes
1 3
/z
/z/y
/z/x
/y/y
2 1
/moo
/moo/wheeeee
/moo
Producción:
Case #1: 4
Case #2: 4
Case #3: 0
Código de golf
Publique su código más corto en cualquier idioma que resuelva este problema. La entrada y la salida se pueden manejar a través de Stdin y Stdout o por otros archivos de su elección. Incluya un descargo de responsabilidad si su código tiene el potencial de modificar o eliminar los archivos existentes cuando se ejecuta.
El ganador será la solución más corta (por recuento de bytes) en un idioma con una implementación existente antes del comienzo de la ronda 1B 2010. Por lo tanto, si es libre de usar un lenguaje que acaba de inventar para enviar un 0 byte Solución, no contará y probablemente obtendrá votos descendentes. ^_^
Clasificación
Solución
Golfscript, 74 69 65
Ahora en una sola línea!
Esta solución es de 63 caracteres, pero no se ejecutará en una cantidad razonable de tiempo para los casos de prueba con miles de rutas (más de 8 minutos), por lo que he optado por no contarlo.
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]|}/}*,@-n@}/
La solución más rápida de 65 caracteres:
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]+}/.&}*,@-n@}/
¡Felicitaciones a Marcog por el algoritmo!
Otros consejos
Pitón, 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
Esta solución arroja un eoferror, pero dado que esto se produce a Stderr, está dentro de las reglas. Dado que la salida en la que se nos interesa todo va a Stdout, podemos completarlo e ignorar Stderr.
Puede leer lo anterior (o algunas de las otras publicaciones) y pensar que no debería funcionar. Hay un poco de truco de por qué, y explicaré esto aquí. Si lee la pregunta cuidadosamente, nos dice que para cada directorio en la primera lista, todos sus directorios de padres también se incluyen en la lista (por ejemplo, si /home /marcog está presente, por lo que es /hogar) [1]. La pregunta también nos garantiza que cada lista no tendrá duplicados [2]. Esto nos permite lanzar todos los directorios en la primera lista en el mismo conjunto en el que arrojamos los directorios de la segunda lista. Dado que la pregunta no garantiza duplicados por lista, sabemos que la primera lista dará como resultado exactamente n entradas en el conjunto. Por lo tanto, podemos obtener la respuesta final restando N del tamaño del conjunto final.
1] "Las siguientes líneas N dan la ruta de un directorio que ya existe en su computadora. Esta lista incluirá todos los directores que ya están en su computadora que no sean el directorio raíz".
2] "Ninguna ruta aparecerá dos veces en la lista de directorios ya en su computadora, o en la lista de directorios que desea crear".
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'
Como siempre con los programas de golf que dependen de las opciones de línea de comandos de intérprete, la diferencia de descuento de opciones con respecto al valor predeterminado se ha agregado a la longitud del código real.
Sangrado, comentado
#! 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 mayor parte de la magia es la extracción de rama desde la raíz. El truco es utilizar una regex para localizar los puntos de corte interesantes (a saber: antes de cada corte y el final de la cadena), pero extraer la cadena usando Perl's $PREMATCH (Dollar Backtick; Markdown no me permitirá incluirlo correctamente) en lugar de las instalaciones habituales de coincidencia de patrones.
\b Localiza un límite de palabras, que se resuelve con todas las palabras '(directorios') comienza y termina. Solo queremos su final, así que prependemos un \w. Pero eso cortaría el último personaje del camino, que es un problema si obtenemos ambos /foo/bar y /foo/baz en el mismo conjunto de datos. Entonces excluyimos dicho personaje del partido con \K. Nada de esto sería necesario si Perl tuviera un \>-El (emacs regexes) metacharacter.
Como programa independiente (106)
for$i(1..<>){($n,$m,%d)=split$",<>;
for(1..$n+$m){$_=<>;$d{$`}++while/\w\K\b/g}
say"Case #$i: ",keys(%d)-$n}
Nuevas líneas para la legibilidad; Ninguno de ellos es necesario o contado.
Utiliza características que se encuentran solo en las últimas versiones de Perl, así que ejecute Perl -M5.010 o posterior.
Solución de lua, 172 bytes:
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 por diversión, no hay posibilidad de ser muy corto, por supuesto. El recuento es después de eliminar un espacio en blanco insignificante, que dejé aquí para legibilidad.
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);
}
}
}
}
Esta última versión tiene una peculiaridad. Cuenta erróneamente que el directorio raíz tiene que crearse una vez, para compensar la variable n siendo -1 al comienzo del bucle, en lugar de la 0. Se garantiza porque el directorio raíz está garantizado de no estar en 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++"/")
Similar (pero mucho más corto: P) a la otra solución Haskell.
Termina por error, y eso se espera. Si eso sigue o no las reglas es un poco más propensa a debatir que para otras soluciones. Las secuencias de salida y error no están mezcladas. Pero si Stdout se amortigua, los resultados nunca se envían. Eso está bien para el uso interactivo (luego simplemente copie la salida de la consola de pasta a un archivo), pero en su mayoría descarta la redirección. Para hacerlo corto, ./filefixit <input 2>/dev/null Hace el truco.
El problema se puede evitar insertando ruido de la línea en la línea 3: []!_="" (8 bytes más, 226 en total)
Para mayor claridad, exactamente la misma semántica con sangría completa e identificadores significativos:
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 ++ "/")
Intento, 175 169 168 135 130 128
ADVERTENCIA: Asegúrese de ejecutar en un directorio vacío, ya que esto eliminará su contenido a primera hora de prueba.
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
Rubí, 151 149 144
Traducción directa a rubí de Solución Python de 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}"}
Posdata
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
Uso: $ 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]}
Esto requiere GHC -XScopedTypeVariables cambiar.
Versión legible:
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
Otra versión más de la solución de Marcog, esta vez en Scala. Corre con scala, pero necesitaría ser puesto en una clase para permitir la compilación 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 caracteres
Otra adaptación de la versión Marcog Python. Corre 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()}
Para ejecutarlo sin el -F Opción, crece en 15 caracteres, ya que luego necesita esta 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)
Uso: $ pyon thisfile.pyon <input >output
Basado en la solución PostScript.
Dado que el desarrollo de Pyonscript todavía está en progreso, este código funciona en la implementación tal como existía al comienzo de la ronda 1B 2010: http://github.com/kirarinsnow/pyonscript
J - 205 159 140 caracteres
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)
correr:
script.ijs < gcj-input
Aún así, genera una línea adicional:/
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: genera un mensaje de error pero aún funciona correctamente.
