#include "grader.h"
#include "encoder.h"
#include <queue>
#include <vector>
using namespace std;
// Calcula la longitud del camino mas corto desde la fuente al resto de ciudades.
vector<int> caminoMasCortoATodasLasCiudades(int fuente, vector<vector<int>> & listaAdyacencia) {
int numCiudades = (int) listaAdyacencia.size();
vector<int> distancias(numCiudades, numCiudades + 1);
distancias[fuente] = 0;
queue<int> colaBfs;
colaBfs.push(fuente);
while (!colaBfs.empty()) {
int ciudad = colaBfs.front();
colaBfs.pop();
for (int & vecina: listaAdyacencia[ciudad]) {
if (distancias[vecina] > distancias[ciudad] + 1) {
distancias[vecina] = distancias[ciudad] + 1;
colaBfs.push(vecina);
}
}
}
return distancias;
}
// Calcula la distancia entre todos los centros de actividades y todas las ciudades.
vector<vector<int>> todasLasDistancias(
vector<vector<int>> & listaAdyacencia, int numCentros
) {
vector<vector<int>> distancias(numCentros);
for (int i = 0; i < numCentros; i++) {
distancias[i] = caminoMasCortoATodasLasCiudades(i, listaAdyacencia);
}
return distancias;
}
// Encuentra el arbol BFS del grafo y saber el padre de cada ciudad.
vector<int> definePadres(vector<vector<int>> & listaAdyacencia) {
vector<int> padre(listaAdyacencia.size(), -1);
queue<int> colaBfs;
colaBfs.push(0);
padre[0] = -2;
while (!colaBfs.empty()) {
int ciudad = colaBfs.front();
colaBfs.pop();
for (int & vecina: listaAdyacencia[ciudad]) {
if (padre[vecina] == -1) {
padre[vecina] = ciudad;
colaBfs.push(vecina);
}
}
}
padre[0] = -1;
return padre;
}
// Codifica un numero decimal en numBits columnas binarias.
void codificaEnBits(int numero, int numBits) {
vector<int> bits(numBits);
for (int idx = numBits - 1; idx >= 0; idx--) {
bits[numBits - idx - 1] = numero / (1 << idx);
numero %= (1 << idx);
}
for (int i = 0; i < numBits; i++) {
encode_bit((bool) bits[i]);
}
}
void encode(int numCiudades, int numCentros, int numConexiones, int * v1, int * v2) {
vector<vector<int>> listaAdyacencia(numCiudades);
for (int i = 0; i < numConexiones; i++) {
listaAdyacencia[v1[i]].push_back(v2[i]);
listaAdyacencia[v2[i]].push_back(v1[i]);
}
vector<vector<int>> distancias = todasLasDistancias(listaAdyacencia, numCentros);
vector<int> padre = definePadres(listaAdyacencia);
for (int i = 1; i < numCiudades; i++) {
codificaEnBits(padre[i], 10);
}
int ciudad, diferenciaDistancias, diferenciasAgregadas;
for (int hub_idx = 0; hub_idx < numCentros; hub_idx++) {
ciudad = 1;
while (ciudad + 2 < numCiudades) {
diferenciasAgregadas = 0;
for (int diff = 0; diff < 3; diff++) {
diferenciaDistancias = distancias[hub_idx][ciudad + diff] - distancias[hub_idx][padre[ciudad + diff]] + 1;
diferenciasAgregadas = 3 * diferenciasAgregadas + diferenciaDistancias;
}
codificaEnBits(diferenciasAgregadas, 5);
ciudad += 3;
}
while (ciudad < numCiudades) {
diferenciaDistancias = distancias[hub_idx][ciudad] - distancias[hub_idx][padre[ciudad]] + 1;
codificaEnBits(diferenciaDistancias, 2);
ciudad++;
}
}
}
#include "grader.h"
#include "decoder.h"
#include <queue>
#include <vector>
using namespace std;
int decode_in_bits(int num_bits) {
// Decode a number received in num_bits bits to decimal.
vector<int> bits(num_bits);
for (int i = 0; i < num_bits; i++) {
bits[i] = (int) decode_bit();
}
int number = 0;
for (int idx = num_bits - 1; idx >= 0; idx--) {
number += bits[num_bits - idx - 1] * (1 << idx);
}
return number;
}
vector<int> find_distances(
int source,
vector<vector<int>> & tree_adjacency,
vector<int> & deltas,
vector<int> & parent
) {
vector<int> distance(tree_adjacency.size(), -1);
distance[source] = 0;
queue<int> bfs_queue;
bfs_queue.push(source);
while (!bfs_queue.empty()) {
int city = bfs_queue.front();
bfs_queue.pop();
for (int & neighbour: tree_adjacency[city]) {
if (distance[neighbour] != -1) {
continue;
}
if (parent[neighbour] == city) {
distance[neighbour] = distance[city] + deltas[neighbour];
} else {
distance[neighbour] = distance[city] - deltas[city];
}
bfs_queue.push(neighbour);
}
}
return distance;
}
void decode(int num_cities, int num_hubs) {
vector<vector<int>> tree_adjacency(num_cities);
vector<int> parent(num_cities, -1);
for (int i = 1; i < num_cities; i++) {
int p = decode_in_bits(10);
tree_adjacency[p].push_back(i);
tree_adjacency[i].push_back(p);
parent[i] = p;
}
vector<vector<int>> distances(num_hubs, vector<int>(num_cities));
vector<int> deltas(num_cities);
for (int hub_idx = 0; hub_idx < num_hubs; hub_idx++) {
int city = 1, aggregate_distance;
while (city + 2 < num_cities) {
aggregate_distance = decode_in_bits(5);
for (int diff = 2; diff >= 0; diff--) {
deltas[city + diff] = (aggregate_distance % 3) - 1;
aggregate_distance /= 3;
}
city += 3;
}
while (city < num_cities) {
deltas[city] = decode_in_bits(2) - 1;
city++;
}
distances[hub_idx] = find_distances(hub_idx, tree_adjacency, deltas, parent);
}
for (int hub_idx = 0; hub_idx < num_hubs; hub_idx++){
for (int city = 0; city < num_cities; city++){
hops(hub_idx, city, distances[hub_idx][city]);
}
}
}
