#include "grader.h"
#include "encoder.h"
#include <queue>
#include <vector>
using namespace std;
vector<int> shortest_path_to_all_cities(int source, vector<vector<int>> & adjacency) {
// Calculate length of shortest path from source to all cities in graph.
int num_cities = (int) adjacency.size();
vector<int> distances(num_cities, num_cities + 1);
distances[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: adjacency[city]) {
if (distances[neighbour] > distances[city] + 1) {
distances[neighbour] = distances[city] + 1;
bfs_queue.push(neighbour);
}
}
}
return distances;
}
vector<vector<int>> calculate_distances_to_hubs(
vector<vector<int>> & adjacency, int num_hubs
) {
// Calculate length of shortest paths from all hubs to all cities in graph.
vector<vector<int>> distances(num_hubs);
for (int i = 0; i < num_hubs; i++) {
distances[i] = shortest_path_to_all_cities(i, adjacency);
}
return distances;
}
vector<int> define_parent(vector<vector<int>> & adjacency) {
// Run BFS from city 0 to define BFS tree for the graph.
vector<int> parent(adjacency.size(), -1);
queue<int> bfs_queue;
bfs_queue.push(0);
parent[0] = -2;
while (!bfs_queue.empty()) {
int city = bfs_queue.front();
bfs_queue.pop();
for (int & neighbour: adjacency[city]) {
if (parent[neighbour] == -1) {
parent[neighbour] = city;
bfs_queue.push(neighbour);
}
}
}
parent[0] = -1;
return parent;
}
void encode_in_bits(int number, int num_bits) {
// Encode a decimal number in num_bits binary columns.
vector<int> bits(num_bits);
for (int idx = num_bits - 1; idx >= 0; idx--) {
bits[num_bits - idx - 1] = number / (1 << idx);
number %= (1 << idx);
}
for (int i = 0; i < num_bits; i++) {
encode_bit((bool) bits[i]);
}
}
void encode(int num_cities, int num_hubs, int num_hops, int *v1, int *v2){
vector<vector<int>> adjacency(num_cities);
for (int i = 0; i < num_hops; i++) {
adjacency[v1[i]].push_back(v2[i]);
adjacency[v2[i]].push_back(v1[i]);
}
vector<vector<int>> distances = calculate_distances_to_hubs(adjacency, num_hubs);
vector<int> parent = define_parent(adjacency);
for (int i = 1; i < num_cities; i++) {
encode_in_bits(parent[i], 10);
}
for (int hub_idx = 0; hub_idx < num_hubs; hub_idx++) {
encode_in_bits(distances[hub_idx][0], 10);
for (int city = 1; city < num_cities; city++) {
int distances_delta = distances[hub_idx][parent[city]] - distances[hub_idx][city] + 1;
encode_in_bits(distances_delta, 2);
}
}
}
#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_distance, vector<vector<int>> & tree_adjacency, vector<int> & deltas) {
vector<int> distance(tree_adjacency.size());
distance[0] = source_distance;
queue<int> bfs_queue;
bfs_queue.push(0);
while (!bfs_queue.empty()) {
int city = bfs_queue.front();
bfs_queue.pop();
for (int & neighbour: tree_adjacency[city]) {
distance[neighbour] = distance[city] + deltas[neighbour];
bfs_queue.push(neighbour);
}
}
return distance;
}
void decode(int num_cities, int num_hubs) {
vector<vector<int>> tree_adjacency(num_cities);
for (int i = 1; i < num_cities; i++) {
int parent = decode_in_bits(10);
tree_adjacency[parent].push_back(i);
}
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 source_distance = decode_in_bits(10);
for (int i = 1; i < num_cities; i++) {
deltas[i] = decode_in_bits(2) - 1;
}
distances[hub_idx] = find_distances(source_distance, tree_adjacency, deltas);
}
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]);
}
}
}
