UVa 509

RAID!.cpp

#include <bitset>
#include <iostream>
#include <sstream>

using namespace std;

int DiskNumber;
int BlockDigit;
int BlockNumber;
char ParityCharacter;
string Raid[100][6];

string getExclusiveOrResult(const string &diskInfo, int parityPos)
{
	auto parity = diskInfo[parityPos] - '0';
	auto exclusiveResult = (ParityCharacter == 'E') ? parity : (1 - parity);
	for (auto index = 0; index < diskInfo.size(); index++)
	{
		if (index == parityPos || diskInfo[index] == 'x')
		{
			continue;
		}
		exclusiveResult = exclusiveResult ^ (diskInfo[index] - '0');
	}
	return to_string(exclusiveResult);
}

bool repair()
{
	for (auto digit = 0; digit < BlockDigit; digit++)
	{
		for (auto block = 0; block < BlockNumber; block++)
		{
			auto missingDigitCount = 0;
			auto missingDigitPos = -1;
			auto diskInfo = string {};
			for (auto disk = 0; disk < DiskNumber; disk++)
			{
				auto dataBit = Raid[block][disk].substr(digit, 1);
				if (dataBit == "x")
				{
					missingDigitCount++;
					missingDigitPos = disk;
				}
				diskInfo += dataBit;
			}

			auto parityPos = block % DiskNumber;
			string result = getExclusiveOrResult(diskInfo, parityPos);
			if (missingDigitCount >= 2 || (missingDigitCount == 0 && result != "0"))
			{
				return false;
			}
			if (missingDigitCount == 1 && diskInfo[parityPos] != 'x')
			{
				Raid[block][missingDigitPos].replace(digit, 1, result);
			}
		}
	}
	return true;
}

string recoveryData()
{
	auto dataString = string {};
	for (auto block = 0; block < BlockNumber; block++)
	{
		for (auto disk = 0; disk < DiskNumber; disk++)
		{
			if (block % DiskNumber != disk)
			{
				dataString += Raid[block][disk];
			}
		}
	}

	auto redudantDigit = dataString.size() % 4;
	dataString.append(string(redudantDigit == 0 ? 0 : (4 - redudantDigit), '0'));

	auto result = string {};
	for (auto index = 0; index < dataString.size(); index += 4)
	{
		auto hexStringStream = stringstream();
		auto bitList = bitset<4>(dataString.substr(index, 4));
		hexStringStream << uppercase << hex << bitList.to_ullong();
		result += hexStringStream.str();
	}

	return result;
}

bool inputData()
{
	auto validInput = scanf("%d", &DiskNumber);
	if (DiskNumber == 0 || validInput == -1)
	{
		return false;
	}

	scanf("%d%d\n%c ", &BlockDigit, &BlockNumber, &ParityCharacter);
	for (auto disk = 0; disk < DiskNumber; disk++)
	{
		auto diskInfo = string {};
		getline(cin, diskInfo);

		for (auto index = 0, block = 0; index < diskInfo.size(); index += BlockDigit)
		{
			Raid[block++][disk] = diskInfo.substr(index, BlockDigit);
		}
	}
	return true;
}

int main()
{
	auto T = 1;
	while (inputData())
	{
		if (repair())
		{
			printf("Disk set %d is valid, contents are: %s\n", T++, recoveryData().c_str());
		}
		else
		{
			printf("Disk set %d is invalid.\n", T++);
		}
	}
	return 0;
}