UVa 213

Message Decoding.cpp

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define MAX_LENGTH 7

auto cipherTable = map<string, string>{};
auto cipherMessageLengthTable = map<string, int>{
	{ "001", 1 }, { "010", 2 }, { "011", 3 }, { "100", 4 }, { "101", 5 }, { "110", 6 }, { "111", 7 }
};
auto cipherMessageEndingTable = map<int, string>{
	{ 1, "1" },{ 2, "11" },{ 3, "111" },{ 4, "1111" },{ 5, "11111" },{ 6, "111111" },{ 7, "1111111" }
};

vector<string> makeCipherList()
{
	auto cipherList = vector<string>{};
	int powerOfTwoTable[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
	auto maxDecimalNumber = powerOfTwoTable[MAX_LENGTH] - 1;
	for (auto i = 0; i < maxDecimalNumber; i++)
	{
		auto number = i;
		auto binary = string{};
		for (auto digit = 0; digit < MAX_LENGTH; digit++)
		{
			binary = to_string(number % 2) + binary;
			number /= 2;
		}
		cipherList.insert(cipherList.begin(), binary);
	}

	for (auto i = MAX_LENGTH; i >= 1; i--)
	{
		auto stIndex = powerOfTwoTable[i - 1];
		auto edIndex = powerOfTwoTable[i] - 2;
		for (auto index = stIndex; index <= edIndex; index++)
		{
			auto cipher = cipherList[index];
			cipherList.push_back(cipher.substr(MAX_LENGTH - i + 1, cipher.size()));
		}
	}

	return cipherList;
}

void makeCipherTable(string &header, vector<string> &cipherList)
{
	cipherTable.clear();
	auto currentCipherPosition = cipherList.size() - 1;
	for (auto character : header)
	{
		auto cipher = cipherList[currentCipherPosition--];
		cipherTable[cipher] = character;
	}
}

bool fetchEncryptCharacterTo(string &encryptMessageQueue)
{
	auto encryptCharacter = ' ';
	while (true)
	{
		encryptCharacter = getchar();
		if (encryptCharacter == EOF)  return false;
		if (encryptCharacter == '\n') continue;

		break;
	}

	encryptMessageQueue.push_back(encryptCharacter);
	return true;
}

bool decrypt(bool &isEncryptLengthFetchable, int &encryptMessageLength, std::string &encryptMessageQueue)
{
	if (isEncryptLengthFetchable && encryptMessageQueue.size() == 3)
	{
		if (encryptMessageQueue == "000")
		{
			getchar();  //break line eater due to there is a break line after last 000
			cout << endl;
			return true;
		}

		encryptMessageLength = cipherMessageLengthTable[encryptMessageQueue];
		encryptMessageQueue.clear();
		isEncryptLengthFetchable = false;
	}
	else if (encryptMessageQueue.size() == encryptMessageLength)
	{
		if (cipherMessageEndingTable[encryptMessageQueue.size()] == encryptMessageQueue)
		{
			encryptMessageLength = -1;
			isEncryptLengthFetchable = true;
			encryptMessageQueue.clear();
			return false;
		}

		cout << cipherTable[encryptMessageQueue].c_str();
		encryptMessageQueue.clear();
	}

	return false;
}

int main()
{
	auto header = string{};
	auto cipherList = makeCipherList();
	while (getline(cin, header))
	{
		makeCipherTable(header, cipherList);

		auto encryptMessageLength = -1;
		auto isEncryptLengthFetchable = true;
		auto encryptMessageQueue = string{};
		while (fetchEncryptCharacterTo(encryptMessageQueue))
		{
			bool isDecryptFinished = decrypt(isEncryptLengthFetchable, encryptMessageLength, encryptMessageQueue);
			if (isDecryptFinished)
			{
				break;
			}
		}
	}
	return 0;
}