PHPizando

No solo mi primera presentacion en el google codejam, si no tambien mi primer post. Lamentablemente no pude clasificar por que falle. Cometi el error de intentar resolver los problemas con ansi c, lo cierto es que no soy muy bueno con el y perdi mucho tiempo, por lo que opte por usar PHP.

A continuacion voy a traducir el problema, y voy a mostrarles la solucion que propuse, el algoritmo funciona correctamente y resuelve el problema.

Hay una leyenda urbana que dice que si buscas Google en Google el universo hara implosion. Tenemos un secreto para contarte… es cierto! por favor no lo intentes o le cuentes a alguien. Bien, solo estamos bromeando.

Esto es cierto en un universo muy muy lejano. En ese universo, si buscas el nombre del buscador en que te encuentras ese universo se destruira.

Para combatir con esto, tenemos una interesante solucion. Todas las busquedas esran puestas juntas. Seran pasadas a un sistema central que decide que decide que busqueda va a cada buscador. El sistema central manda una serie de busquedas a un buscador, y puede cambiar a otro buscador en cualquier momento. Las busquedas son procesadas en el orden que se van recibiendo. El sistema central nunca enviara una busqueda que sea igual al nombre del buscador en el que esta, en ese caso debera cambiar de buscador. Para reducir costos, el numero de cambios de buscador a buscador debe ser minimo.

Como entrada para resolver este problema contaremos con un archivo, que tendra el siguiente formato;
En la primer linea dira la cantidad de casos a resolver, luego nos describiran los N casos,de la siguiente forma;
numero de buscadores
buscadores1
buscadores2
buscadoresN
numero de busquedas
busqueda1
busqueda2
busquedaN

Ejemplo;
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol

Y la salida de este ejemplo seria;
Case #1: 1
Case #2: 0

La solucion que yo propuse es la siguiente;

Casos::loadData("datos.in");

$i=1;
while(($caso=array_shift(Casos::$Casos))){
	echo 'Case #'.$i.': '.$caso->calcular()."\r\n";
	$i++;
}

class Caso{
	public $engines=array();
	public $querys=array();

	public function calcular(){

		$aux=$this->engines;
		$total=0;

		while (($qry=array_shift($this->querys))){

			$aux=$this->quitar($qry,$aux);
			if(count($aux)==0){
				$aux=$this->quitar($qry,$this->engines);
				$total++;
			}
		}

		return $total;
	}

	public function quitar($qry,$unaArr){

		$aux=array();

		while(($aEng=array_shift($unaArr))){
			if($qry!=$aEng){
				array_push($aux,$aEng);
			}
		}

		return $aux;
	}

}

abstract class Casos{
	public static $Casos=array();

	public function loadData($file){
		$archivo = file($file);
		$i=0;
		for($m=0;$m<$archivo[0];$m++){
			$caso=new Caso();
			$i++;
			$totalEng=$archivo[$i];
			for($j=0;$jengines,$archivo[$i]);
			}
			$i++;
			$totalQry=$archivo[$i];
			for($j=0;$jquerys,$archivo[$i]);
			}
			array_push(self::$Casos,$caso);
		}
	}
}

Para el que quiera el problema original en ingles puede hacerlo en http://code.google.com/codejam/