He superado la primera ronda del Google Code Jam 08 resolviendo dos de los tres problemas planteados utilizando HTML+Javascript. Con el tercero no he podido plantearlo, ni por tanto implementarlo. Aquí presento el código de los dos primeros problemas.
El primero consistía en una lista de buscadores y una lista de búsquedas formada por los nombres de los buscadores, de tal forma que un buscador nunca debería recibir una consulta sobre su propio nombre (ya que la leyenda urbana dice que el Universo podría implosionar 
En todos los casos he usado un esqueleto con HTML en el que la entrada de datos se hace con un simple textarea y la salida se muestra en un div llamado output cuando se pulsa sobre el botón de inicio:
<html><body>
<textarea id="input" style="width:99%;height:40%;"></textarea>
output
<pre><span id="output" style="width:99%;height:40%;overflow:scroll;" style="font:22px monospace; border:1px inset gray;"></span></pre>
<input type="button" value="go" onclick="run()" />
</body></html>
El código Javascript para el primer problema es el siguiente:
function $(elm) { return document.getElementById(elm); }
function log(s) { $('output').innerHTML+= s+"\n"; }
var search= {
engines: [],
queue: [],
init: function (input) {
this.engines= [];
this.queue= [];
enginesnum= parseInt(input.shift()) // get engines num
while (enginesnum--) {
elm= input.shift();
this.engines.push(elm);
}
queueitems= parseInt(input.shift()) // get queue items
while (queueitems--) {
elm= input.shift();
this.queue.push(elm);
}
},
getbest: function () {
// search the best engine to switch now in order to delay next switch
// if some engine is not in the queue, it must be the best:
for (engine in this.engines) if (!~this.queue.indexOf(this.engines[engine])) return this.engines[engine];
// well, bad luck, all engines needed in the future. The best the will be the one needed later in time
// so, copy the candidates and remove them one per one by following the queue until only one is left (the later needed)
var candidates= this.engines.slice(); // copy the engines array
var queueindex=0;
while (candidates.length>1) {
// remove from candidates every element in queue until one is left
if (~candidates.indexOf(this.queue[queueindex])) candidates.splice(candidates.indexOf(this.queue[queueindex]),1);
queueindex++;
}
return candidates.shift();
},
solve: function () {
var switches=0;
var current= this.getbest();
while (this.queue.length) {
if (this.queue[0]==current) {
switches++;
current= this.getbest();
}
this.queue.shift();
}
return switches;
}
}
function run() {
ii= $('input').value.split(/\n/);
var total= parseInt(ii.shift()) // get cases num
var num=1;
while (total--) {
search.init(ii);
var sol= search.solve();
log('Case #'+num+': '+sol);
num++;
}
}
El segundo problema consistía en averiguar el número de trenes necesarios para cada una de las dos estaciones de un simple trayecto entre ambas pero con distintos horarios, duraciones y tiempos de preparación tras un viaje. Si en el instante en el que el horario marca que debe salir un tren no hay uno esperando ya en la estación, se debe añadir a la lista de los que deben estar presentes al principio. Datos.
function $(elm) { return document.getElementById(elm); }
function log(s) { $('output').innerHTML+= s+"\n"; }
sortfunction= function(a,b) {return a-b;}
var trains= {
departures: [],
turnaround: 0,
time2int: function (hour) {
hour= hour.split(':');
return hour[0]*60+Math.round(hour[1]);
},
init: function (input) {
this.turnaround= parseInt(input.shift()), // get turnaround time
this.departures= [];
froms=input.shift().split(' ');
fromAtoB= parseInt(froms[0]); // get num departures from a to b
fromBtoA= parseInt(froms[1]); // get num departures from b to a
while (fromAtoB--) {
elm= input.shift();
elm=elm.split(" ");
elm= [this.time2int(elm[0]),this.turnaround+this.time2int(elm[1])-this.time2int(elm[0]),'A'];
this.departures.push(elm);
}
while (fromBtoA--) {
elm= input.shift();
elm=elm.split(" ");
elm= [this.time2int(elm[0]),this.turnaround+this.time2int(elm[1])-this.time2int(elm[0]),'B'];
this.departures.push(elm);
}
this.departures.sort( function(a,b){return a[0]-b[0]} )
},
checktrain: function (obj) {
for (train in obj.trains) {
if (obj.trains[train]<=obj.hour) {
//delete the train available from trains and return it
mytrain= obj.trains.splice(train,1);
return mytrain[0];
}
}
return false;
},
solve: function () {
var a=[], trainsA=0;
var b=[], trainsB=0;
while (this.departures.length) {
departure= this.departures.shift();
// check for availability of train
trainsAtOrigin= ( departure[2]=='A' ? a : b );
trainsAtDest= ( departure[2]=='A' ? b : a );
hour= departure[0];
spent= departure[1];
available = this.checktrain( {'trains':trainsAtOrigin,'hour':hour} );
if ( !available ) {
// ads new train on destination with spent time and reorder
trainsAtDest.push(hour+spent);
trainsAtDest.sort(sortfunction);
( departure[2]=='A' ? trainsA++ : trainsB++ );
} else {
// else moves existing train from origin to destination available after spent time
trainsAtDest.push(hour+spent);
trainsAtDest.sort(sortfunction);
}
}
return [trainsA,trainsB];
}
}
function run() {
ii= $('input').value.split(/\n/);
var total= parseInt(ii.shift()) // get cases num
var num=1;
while (total--) {
trains.init(ii);
var sol= trains.solve()
log('Case #'+num+': '+sol.join(' '));
num++;
}
}
Contactar
3 comentarios:
Plas plas plas! Ara si q dic jo q estas ocioset!
I slept few hours, but I still do not understand the logic behind the train code.
Anyway, thank you for sharing your code :-)
@Anónimo: A l'altra posa el nom, covarde. Jeje.
@Andrea: What I do is start by sorting the train departures. Then I go one after one. I keep an array with the available trains at each station and the hour of availability (counting the turnaround time). I start with two empty array. So, with every departure, I see if there is a train available, if there is one, i remove it from the availables at that station and put it in the destination station with the new hour of availability. Else, if there is no train, then I increase the need of trains for that station and put it in the array of available trains at the destination station. Not so difficult.
Publicar un comentario