Challenge 11 - Pheasant
Después de todo el tiempo perdido en el desafío 10, apenas me quedaban unas horas por delante para la finalización del concurso. Por lo que intente ir más deprisa de cara a poder finalizar el máximo de problemas posibles, de ahí que quizás el código se resienta un poco (¿más aún?).
El problema 11 nos comentaba que habían tenido un problema con su servidor de feeds, del cual se habían perdido los datos, y que teníamos que ayudarles en la labor de intentar recuperar parte de la información.
Para dicha tarea, nos proporcionaban las copias de respaldo que tenían a través del archivo https://contest.tuenti.net/resources/feeds.tar.gz. En dicho archivo podemos ver el contenido de 2 carpetas distintas: por una parte los timestamps en texto plano, y por otra el contenido de las tablas cifrado en AES-256 (32 bytes) en modo ECB (cada bloque de forma individual, lo cual es bastante inseguro). Todo ello muy bien ordenadito dentro de sus respectivas carpetas, nombradas con los dos últimos dígitos del 'userID'.
La clave AES nos las proporcionaban a través del input junto al userID, con el único añadido de que faltaban los 3 últimos bytes. Por lo que nos tocaría probar cada una de las combinaciones posibles en el rango a-zA-z.
Para la tarea de descifrado eché mano de OpenSSL, que tiene unas funciones muy cucas para trabajar con AES (a la vez que mal documentadas), pero bueno, en esta ocasión la librería está en C, así que bendito problema.
Tras hacer algunas pruebas me percaté de que los archivos presentaban tamaños irregulares, por lo que tardaba más en descifrar algunos que en descifrar otros. Por lo que desde mi punto de vista, el truco estaba en comenzar a descifrar haciendo uso de una combinación un bloque de un archivo, y si dicho texto descifrado no era legible (es decir no contenía un user-ID) pasar a la siguiente combinación (no continuando con el descifrado total del archivo para dicha combinación). Más allá de esto no pensé en alguna otra mejora, que posiblemente las haya (podéis dejarlas en los comentarios), porque tampoco andaba muy sobrado de tiempo.
Comprobé que el script de test lo superaba en apenas 1 segundo, y que el script final tardaba en torno a un par de minutos (dado que presentaba unos inputs bastante tochos). Me daba por satisfecho y me dispuse a realizar el desafio 12.
Nota: Gracías a @Uxio0 he podido averiguar otro de los trucos que aceleraban el proceso: leer los timestamps en texto plano, para así solo tener que realizar las pruebas de descifrado sobre los archivos con mayor timestamp. Esto probablemente hubiese acelerado el proceso de un par de minutos a un par de segundos.
Os dejo mi código en C++:
/* C HEADERS */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <openssl/aes.h>
/* C++ HEADERS */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <complex>
using namespace std;
int main(){
string tmp,tmp2,tmp3;
while(cin>>tmp){
int T;
tmp.erase(tmp.end()-1, tmp.end());
T=stoi(tmp);
string salida;
unsigned char userID[16];
unsigned char userKey[33];
vector<pair<int, int> > events;
bool end = false;
while(!end){
cin>>tmp;
if(tmp.back()!=';'){ //Ultima iteracion
end = true;
}else{
tmp.erase(tmp.end()-1, tmp.end());
}
size_t found = tmp.find(",");
tmp2 = tmp.substr(0, found);
strcpy((char*)userID, tmp2.c_str());
tmp3 = tmp.substr(found+1, tmp.size());
strcpy((char*)userKey, tmp3.c_str());
string filepath("./encrypted/");
filepath += tmp2.substr(tmp2.size()-2, tmp2.size());
filepath += string("/");
filepath += string((char*)userID);
filepath += string(".feed");
ifstream file(filepath.c_str(), ios::in|ios::binary|ios::ate);
if (file.is_open()){
streampos size = file.tellg();
unsigned char * entrada;
entrada = new unsigned char [size];
file.seekg (0, ios::beg);
file.read ((char*)entrada, size);
file.close();
AES_KEY decKey;
for(int c1=65; c1<=122; c1++){
for(int c2=65; c2<=122; c2++){
for(int c3=65; c3<=122; c3++){
if(c1==91)
c1=97;
userKey[29] = c1;
userKey[30] = c2;
userKey[31] = c3;
int flag=0;
char * ptr;
unsigned char out[32000];
for(int i=0; i<size; i+=16){//Descifra cada bloque
AES_set_decrypt_key(userKey, 256, &decKey);
AES_ecb_encrypt(&entrada[i], &out[i], &decKey, AES_DECRYPT);
if(!flag){
flag=1;
ptr = strstr((char*)&out[0], (char*)&userID[0]);
if(ptr<=0){
break;
}
}
}
out[size]=0;
ptr = strstr((char*)&out[0], (char*)&userID[0]);
if(ptr>0){
string dcp((char*)out);
string buf;
stringstream ss(dcp);
vector<string> tokens;
string uID((char*)userID);
while (ss >> buf)
tokens.push_back(buf);
for(int j=0; j<tokens.size(); j++){
if(tokens[j] == uID){
int timestamp = stoi(tokens[j+1]);
int event = stoi(tokens[j+2]);
pair<int,int> p = make_pair(timestamp, event);
events.push_back(p);
j+=2;
}
}
c1=122; c2=122; c3=122;
}
}
}
}
delete[] entrada;
}
}
sort(events.begin(), events.end());
vector<pair<int,int>>::iterator it;
int n=0;
for (it=events.end()-1; it>=events.begin()&&n<T; --it){
std::cout << it->second;
n++;
if(it-1>=events.begin()&&n<T)
cout << ' ';
}
cout << endl;
}
return 0;
}
Como veis, después realizo la ordenación de los eventID, en función de su timestamp, en orden descendente. Para ello utilizo un vector de pares de enteros, y la función sort() de la librería "algorithm" de STL.
Challenge 12 - Taxi Driver
Turno para el problema 12, en el que un joven Robert De Niro nos presenta un problema de encontrar la ruta más corta desde un origen a un destino, a través de un mapa de obstáculos. El problema que su taxi solo gira a la derecha (no me mezcles a 'Speed' con 'Taxi Driver primer aviso xd).
Es un programa de tipo laberinto (o eso pensaba yo) que intenté resolverlo haciendo uso de una búsqueda en anchura con el algoritmo de Lee http://en.wikipedia.org/wiki/Lee_algorithm y algunas modificaciones.
Finalmente no conseguí hacer que llegara a funcionar y me quedé sin tiempo para más. De todos modos os dejo el código para que os hagais una idea de lo que intentaba conseguir:
#define RIGHT 11
#define LEFT 22
#define DOWN 33
#define UP 44
class TaxiSolver{
private:
int M,N;
int Si,Sj; //Start
int Xi,Xj; //Destination
int casilla[101][101];
int distancia;
queue<pair<int, int>> cola;
queue<int> dir; //Direccion
queue<int> dist; //Distancia
public:
void readCity(){
cin >> M;
cin >> N;
//Realizamos la lectura del tablero
char input;
for(int n=0; n<N; n++){
for(int m=0; m<M; m++){
cin >> input;
if(input == '.'){
casilla[n][m] = 0;
}else if(input=='#'){
casilla[n][m] = 999999;
}else if(input=='S'){
Si = n;
Sj = m;
casilla[n][m] = 0;
}else if(input=='X'){
Xi = n;
Xj = m;
casilla[n][m] = -1;
}
}
}
}
void printCity(){
for(int n=0; n<N; n++){
for(int m=0; m<M; m++){
if(n==Si && m==Sj){
cout << 'S';
}else if(n==Xi&&m==Xj){
cout << 'X';
}else if(casilla[n][m] == 0){
cout << '.';
}else if(casilla[n][m]==999999){
cout << '#';
}else if(casilla[n][m]>0){
cout << casilla[n][m];
}
}
cout << endl;
}
cout << "\n" << endl;
}
// void printPath(){
// }
int insert_in(int i, int j, int num){
if(casilla[i][j]==-1){
pair<int,int> s = make_pair(i, j);
cola.push(s);
dist.push(num);
return 1;
}else if(i>=0 && j>=0 && i<N && j<M){
if(casilla[i][j]==0){
casilla[i][j]=num;
pair<int,int> s = make_pair(i, j);
cola.push(s);
dist.push(num);
return 1;
}else if(casilla[i][j]==999999){
return 999999;
}
}
return 0;
}
void insert_up(int i, int j, int num){
i--;
int r=insert_in(i,j,num);
if(r== 1){
dir.push(UP);
}else if(r == 999999){
//dir.push(RIGHT);
}
}
void insert_down(int i, int j, int num){
i++;
if(insert_in(i,j,num)==1)
dir.push(DOWN);
}
void insert_right(int i, int j, int num){
j++;
if(insert_in(i,j,num)==1)
dir.push(RIGHT);
}
void insert_left(int i, int j, int num){
j--;
if(insert_in(i,j,num)==1)
dir.push(LEFT);
}
int shortestPath(){
int distancia=1;
//Introducimos la posicion inicial
insert_up(Si,Sj,distancia);
insert_down(Si,Sj,distancia);
insert_right(Si,Sj,distancia);
insert_left(Si,Sj,distancia);
distancia++;
//printCity();
while (!cola.empty()){
distancia = dist.front()+1;
dist.pop();
int i = cola.front().first;
int j = cola.front().second;
cola.pop();
int direccion = dir.front();
dir.pop();
if(casilla[i][j]==-1){
return distancia-1+8;
}else{
if(direccion==UP){
insert_up(i,j,distancia);
insert_right(i,j,distancia);
}else if(direccion==DOWN){
insert_down(i,j,distancia);
insert_left(i,j,distancia);
}else if(direccion==RIGHT){
insert_down(i,j,distancia);
insert_right(i,j,distancia);
}else if(direccion==LEFT){
insert_up(i,j,distancia);
insert_left(i,j,distancia);
}
distancia++;
//printCity();
}
}
return -1;
}
};
int main(){
int T;
cin >> T;
for(int t=0; t<T; t++){
TaxiSolver mySolver;
mySolver.readCity();
//mySolver.printCity();
int path = mySolver.shortestPath();
if(path<0)
cout << "ERROR" << endl;
else
cout << "Case #" << t << ": " << path << endl;
}
return 0;
}
Creo que dadas las restricciones del problema mi planteamiento inicial fue erróneo, y si volviese a abordar el problema seguramente haría uso de mi algoritmo A* previamente programado. Además en este caso sería muy fácil programar una buena heurística para el problema y que fuera óptima (el propio algoritmo de Lee podría servir de base para una buena heurística).
Fin del juego, y conclusión
Desgraciadamente no me dio tiempo a más, y aquí terminó mi primera participación en el Tuenti Challenge. Mi posición provisional final fue cincuenta y algo (no la recuerdo exactamente), y si no hubiese perdido tanto tiempo en el problema 10 o al menos lo hubiese podido resolver, seguramente hubiese podido subir algún puesto más arriba.
El concurso la verdad es que me ha sorprendido positivamente, me lo esperaba más cutre (para ser honesto mucho más cutre), y me he llevado una verdadera sorpresa. Es más, durante estos días se celebran las primeras fases de la Codejam 2014 y los problemas de la Tuenti Challenge me han parecido mucho más logrados y originales (si bien es cierto que el de Google utiliza un formato de tiempo reducido), y creo que le falta algo más de difusión para lo currado que esta.
Si no recuerdo mal en su momento recibí un correo de la universidad, pero creo que esta labor de propaganda del desafío se puede mejorar, y que llegue a oídos de un montón de personas que de haberlo conocido se hubiesen interesado por él sin ninguna duda.
Por mi parte, el año que viene si las circunstancias laborales/personales me lo permiten espero estar nuevamente en la Tuenti Challenge 2015 y en esta ocasión para intentar llegar aún más arriba.
Nos vemos
Qué buena idea, no se me había ocurrido! En el 11, descifrar sólo los ficheros que sean necesarios, ya que solo por el timestamp ya podíamos ver que algunos no lo eran (la otra heurística sí la hice yo también). Ains, y yo convencido de que el truco era conocer cosas del AES...
ResponderEliminar