#include "message.h"
#include <cassert>
#include <iostream>
using namespace std;
constexpr int PACKET_SIZE = 31, LOG_P_SIZE = 5;
constexpr int LOG_MAX_MSG_SIZE_MINUS_ONE = 10;
void send_message(vector<bool> msg, vector<bool> controlled) {
int witness_bit = 0, size_msg = msg.size();
while (controlled[witness_bit])
++witness_bit;
for (int i_pw = 0; i_pw < LOG_P_SIZE; ++i_pw) {
bool val = (witness_bit >> i_pw) & 1;
send_packet(vector<bool>(PACKET_SIZE, val));
}
vector<int> avail;
for (int i_bit = 0; i_bit < PACKET_SIZE; ++i_bit) {
if (!controlled[i_bit] && i_bit != witness_bit)
avail.push_back(i_bit);
}
vector<bool> testimonies;
for (bool ctr : controlled)
testimonies.push_back(ctr); // wasting 1 bit for controlled[witness]
for (int i_pw = 0; i_pw < LOG_MAX_MSG_SIZE_MINUS_ONE; ++i_pw) {
bool val = ((size_msg-1) >> i_pw) & 1;
testimonies.push_back(val);
}
int nb_testimonies = testimonies.size();
int next_msg_bit = 0, next_testimony = 0;
while (next_msg_bit < (int)msg.size() || next_testimony < nb_testimonies) {
vector<bool> packet(PACKET_SIZE);
if (next_testimony < nb_testimonies) {
packet[witness_bit] = testimonies[next_testimony++];
} else if (avail.back() != witness_bit) {
avail.push_back(witness_bit);
}
for (int bit : avail) {
if (next_msg_bit < (int)msg.size()) {
packet[bit] = msg[next_msg_bit++];
}
}
send_packet(packet);
}
}
bool maj_element(vector<bool> &a) {
int cnt = count(a.begin(), a.end(), true);
return 2*cnt >= (int)a.size();
}
vector<bool> receive_message(vector<vector<bool>> packets) {
int witness_bit = 0;
for (int i_pack = 0; i_pack < LOG_P_SIZE; ++i_pack) {
if (maj_element(packets[i_pack]))
witness_bit += (1 << i_pack);
}
packets.erase(packets.begin(), packets.begin() + LOG_P_SIZE);
vector<int> avail;
for (int i_packet = 0; i_packet < PACKET_SIZE; ++i_packet) {
int observed_bit = i_packet; // small waste
bool control = packets[i_packet][witness_bit];
if (!control && observed_bit != witness_bit) // not controlled
avail.push_back(observed_bit);
}
int size_msg = 1; // then add binary encoding of size-1
for (int delta = 0; delta < LOG_MAX_MSG_SIZE_MINUS_ONE; ++delta) {
int i_pack = PACKET_SIZE+delta;
if (packets[i_pack][witness_bit])
size_msg += (1 << delta);
}
vector<bool> msg;
for (int i_packet = 0; i_packet < (int)packets.size(); ++i_packet) {
if (i_packet == PACKET_SIZE + LOG_MAX_MSG_SIZE_MINUS_ONE)
avail.push_back(witness_bit);
for (int bit : avail) if ((int)msg.size() < size_msg) {
msg.push_back(packets[i_packet][bit]);
}
}
return msg;
}
