La ronda de clasificacion fue dura y realmente interesante, pone a prueba la capacidad de enfrentar problemas, no me fue muy bien realmente aun que es mi primera vez que participo, amigos y compañeros me ayudaron en analisis del segundo y tercer problema aunque no con resultados exitosos :( pero bueno fue un momento para compartir conocimiento con ellos ,ver la forma como ellos trataban de solucionar y de dar aportes, a pesar del resultado logre desarrollar el punto 1 (Alien Language) y la verdad fue facil, al principio me enrrede en una solucion recursiva pero me inspire y pude descartarla, de no haberlo hecho no hubiera completado ese punto, les cuento como solucione ese punto al final.
Problem A: Alien LanguageCategory: Brute Force, String Manipulation
URL: http://code.google.com/codejam/contest/dashboard?c=90101#s=p0la idea principal es dada una serie de palabras N de longitud L, buscar en los D casos todas las palabras y encontrar similitud en ellos , los casos estaban dados por (abc..z) donde cada caracter dentro de los () podia ser , es decir o a, b, .. etc, un ejemplo mas claro es:
abc como palabra a encontrar en el caso y el caso es (ab)(bc)c la solucion seria que pueden encontrarse las siguientes soluciones para este caso, [abc,acc,bbc,bcc] y abc esta una sola ves asi la respuesta seria 1, pense haciendo una fucion que me generara n vectores posibles para sacar las combinaciones posibles, pero realizar esta funcion me tomaria mucho tiempo y en este momento analizando todo lo que paso no creo que me hubiese servido de mucha ayuda :P, la forma como enfrente este problema fue, en vez de crear una funcion que realizara los n vectores de combinaciones, use expresiones regulares en perl, asi primero convertia los () en [] para poder evaluarlas por medio de =~/Expresion/ entonces asi sabria si existia la palabra en el caso.
Esta es mi solucion para ese problema, funciona de igual manera para el set de dato pequeño y el grande (aprox 5000 palabras, 500 casos :P)
my ($L,$D,$N,$caso)="";
my (@lineas,@cabecera,@palabras,@respuesta)=();
open(Entrada,"A-large.in");
@lineas=< Entrada>;
@cabecera=split(" ",$lineas[0]);
close(Entrada);
$L=$cabecera[0];
$D=$cabecera[1];
$N=$cabecera[2];
for(my $i=1;$i<=$D;$i++){
$palabras[@palabras]=$lineas[$i];
}
for(my $i=($D+1);$i<@lineas;$i++){
my $contador=0;
$caso=$lineas[$i];
$caso=~s/\(/\[/g;
$caso=~s/\)/\]/g;
for(my $j=0;$j<@palabras;$j++){
if($palabras[$j]=~$caso){
$contador++;
}
}
$respuesta[@respuesta]=$contador;
}
open(Salida,">output-large");
for(my $i=0;$i<@respuesta;$i++){
print Salida "Case #".($i+1).": ".$respuesta[$i]."\n";
}
close(Salida);
En fin obtuve 33 puntos de 99 posibles :P es mi primera vez que participo , pero no sera la ultima, quiero agradecerles a mis amigos (colegas con quien trabajo) por el apoyo brindado
