support stone mexico entrar create classroom advantage language-agnostic rosetta-stone

language-agnostic - entrar - rosetta stone en mexico



Archivo Fix-it codegolf(GCJ 2010 1B-A) (15)

El año pasado (2009), el Google Code Jam presentó un problema interesante como el primer problema en la Ronda 1B: Árbol de decisiones

Como el problema parecía estar hecho a la medida de lenguajes similares a Lisp, espontáneamente tuvimos un emocionante juego de codegolf aquí en SO, en el que unos pocos lenguajes lograron resolver el problema en menos caracteres que cualquier otra variedad de Lisp, utilizando varias técnicas diferentes.

El problema A ( File Fix-it ) de la Ronda 1B de este año también parece estar diseñado para una familia particular de idiomas, los scripts de shell de Unix. Por lo tanto, sería apropiado continuar con la "tradición 1B-A". : 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):

Se le dan los casos de prueba T Cada caso de prueba contiene N líneas que enumeran la ruta completa de todos los directorios que existen actualmente en su computadora. Por ejemplo:

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

A continuación, se le asignan M líneas que enumeran la ruta completa de los directorios que desea crear. Están en el mismo formato que los ejemplos anteriores. Puede crear un directorio utilizando el comando mkdir , pero solo puede hacerlo si el directorio principal ya existe. Por ejemplo, para crear los directorios /pyonpyon/fumufumu/yeahyeah y /pyonpyon/fumufumu/yeahyeahyeah , necesitaría 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 tiene que llamar a mkdir para crear todos los directorios que desea crear.

Entrada

La entrada consta de 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 números enteros N y M , separados por un espacio.

Las siguientes N 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 cadenas alfanuméricas en minúsculas no vacías, cada una precedida por una sola / .

Las siguientes líneas M contienen la ruta de cada directorio que desea crear.

Salida

Para cada caso, imprima una línea que contenga el Case #X: Y , donde 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, puede aparecer una ruta en ambas listas, como en el caso del ejemplo # 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 aparecerá en la lista, con la excepción del directorio raíz / .

El archivo de entrada tiene una longitud máxima de 100,000 bytes.

Ejemplo

Los casos de prueba de muestra más grandes se pueden descargar aquí .

Entrada:

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

Salida:

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

Codigo golf

Por favor, publique su código más corto en cualquier idioma que resuelva este problema. La entrada y la salida pueden manejarse mediante stdin y stdout o por otros archivos de su elección. Incluya un descargo de responsabilidad si su código tiene la posibilidad de modificar o eliminar archivos existentes cuando se ejecuta.

El ganador será la solución más corta (por recuento de bytes) en un lenguaje con una implementación existente antes del inicio de la Ronda 1B 2010. Entonces, si bien es libre de usar un idioma que acaba de crear para enviar un 0 bytes. solución, no contará, y probablemente obtendrá votos bajos. ^ _ ^

Posiciones

Golfscript, 74 69 65

¡Ahora en una sola línea!
Esta solución tiene 63 caracteres, pero no se ejecutará en un tiempo razonable para casos de prueba con miles de rutas (más de 8 minutos), por lo que opté por no contarla.

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!

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

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 aún está en progreso, este código funciona en la implementación tal como existía al inicio de la Ronda 1B 2010: http://github.com/KirarinSnow/PyonScript

AWK - 123 121 caracteres

Otra adaptación de la versión de marcog python. Ejecutar 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 la opción -F , crece en 15 caracteres, ya que luego necesita esta parte:

BEGIN{FS=" |/"}

Bash, 175 169 168 135 130 128

ADVERTENCIA: Asegúrese de ejecutar en un directorio vacío, ya que esto eliminará su contenido primero por 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

C #, 489 442 400 398

Solo por diversión, no hay posibilidad de ser muy corto, por supuesto. La cuenta es después de eliminar el espacio en blanco insignificante, que dejé aquí para facilitar la lectura.

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 debe crearse una vez, para compensar que la variable n sea -1 al comienzo del bucle, en lugar del 0. deseado. Funciona porque se garantiza que el directorio raíz no está 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 de Haskell.

Termina por error, y eso se espera. Si eso sigue o no las reglas es un poco más propenso a debatir que para otras soluciones. Los flujos de salida y de error no se mezclan. Pero si stdout se almacena en búfer, los resultados nunca se envían. Eso está bien para el uso interactivo (entonces simplemente copie y pegue la salida de la consola en un archivo), pero en general elimina la redirección. Para abreviar, ./filefixit <input 2>/dev/null hace el truco.

El problema se puede evitar insertando el ruido de línea en la línea 3: []!_="" (8 bytes más, 226 en total)

Para mayor claridad, la misma semántica exacta 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 ++ "/")

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 el cambio de GHC -XScopedTypeVariables .

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

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 extra: /

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.

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 la línea de comandos del intérprete, la diferencia de bytecount de las opciones con respecto a la predeterminada 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 la rama desde la raíz. El truco es usar una expresión regular para ubicar los puntos de corte interesantes (es decir, antes de cada barra y el final de la cadena), pero para extraer la cadena mediante $PREMATCH Perl (dólar-backtick; markdown no me permite incluir eso correctamente) en lugar de las instalaciones habituales de coincidencia de patrones.

/b localiza un límite de palabra, que se resuelve en todas las palabras ''(directorios'') inicio y final. Sólo queremos su final, por lo que anteponemos a /w . Pero eso eliminaría el último carácter de la ruta, lo cual es un problema si obtenemos /foo/bar y /foo/baz en el mismo conjunto de datos. Así que excluimos dicho carácter del partido con /K Nada de esto sería necesario si Perl tuviera un metacarácter similar a /> (Emex regexes).

Como un 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 en.

Utiliza características que solo se encuentran en las últimas versiones de Perl, por lo que se ejecuta con perl -M5.010 o posterior.

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

Esta solución lanza un error EOFError, pero como se envía a stderr, está dentro de las reglas. Dado que la salida que nos interesa todo va a la salida estándar, podemos canalizar eso e ignorar stderr.

Puede leer lo anterior (o algunas de las otras publicaciones) y pensar que no debería funcionar. Hay un pequeño truco para explicar por qué, y explicaré esto aquí. Si leyó la pregunta detenidamente, nos dice que para cada directorio de la primera lista, todos los directorios principales también se incluyen en la lista (por ejemplo, si / home / marcog está presente, también lo está / home) [1]. La pregunta también nos garantiza que cada lista no tendrá duplicados [2]. Esto nos permite lanzar todos los directorios de la primera lista en el mismo conjunto en el que lanzamos los directorios de la segunda lista. Como 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 al restar N del tamaño del conjunto final.

[1] "Las siguientes N líneas indican la ruta de un directorio que ya existe en su computadora. Esta lista incluirá todos los directorios que ya estén en su computadora, excepto el directorio raíz".

[2] "Ninguna ruta aparecerá dos veces en la lista de directorios que ya se encuentran en su computadora, o en la lista de directorios que desea crear".

Scala, 190 189

Otra versión más de la solución de marcog, esta vez en Scala. Se ejecuta con scala , pero se debería colocar 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)}

Ruby, 151 149 144

Traducción directa a Python de Ruby of 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}"}

Solución 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