UVa 1590

IP Networks.cpp

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <regex>
#include <limits>
#include <algorithm>

using namespace std;

unsigned int compressIPTextAsNumber(const string &ipText)
{
	auto splitContent = vector<string>{};
	regex patern(R"(\d+)");
	copy(sregex_token_iterator(ipText.begin(), ipText.end(), patern), sregex_token_iterator(), back_inserter(splitContent));

	auto result = 0u;
	auto baseNumber = 16777216u;  //256^3
	for (const auto& ipTextInParts : splitContent)
	{
		auto singleIP = atoi(ipTextInParts.c_str());
		result += baseNumber * singleIP;
		baseNumber /= 256;
	}
	return result;
}

string decompressedIPNumberAsText(unsigned int ipInNumber)
{
	auto result = string{};
	for (auto i = 0; i < 4; i++)
	{
		auto ipInParts = ipInNumber % 256;
		auto appendString = to_string(ipInParts) + (result.empty() ? "" : ".");
		result = appendString + result;
		ipInNumber /= 256;
	}
	return result;
}

std::pair<unsigned int, unsigned int> retrieveMinMaxIP(const vector<string> &ipList)
{
	auto maxNumber = numeric_limits<unsigned int>::min();
	auto minNumber = numeric_limits<unsigned int>::max();
	for (const auto& ip : ipList)
	{
		auto number = compressIPTextAsNumber(ip);
		maxNumber = max(maxNumber, number);
		minNumber = min(minNumber, number);
	}
	return make_pair(minNumber, maxNumber);
}

int calculateSameDigitFromMSB(unsigned int num1, unsigned int num2)
{
	auto resultDigit = 0;
	auto redundantNum = num1 ^ num2;
	while (redundantNum > 0)
	{
		redundantNum /= 2;
		resultDigit++;
	}
	return 32 - resultDigit;
}

unsigned int calculateSubMaskInNumber(int totalDigitFromMSB)
{
	auto result = 0u;
	for (auto digit = 32 - totalDigitFromMSB; digit < 32; digit++)
	{
		result += (1 << digit);
	}
	return result;
}

void solve(const vector<string> &ipList)
{
	auto minMaxIP = retrieveMinMaxIP(ipList);
	auto continousSameDigitFromMSB = calculateSameDigitFromMSB(minMaxIP.first, minMaxIP.second);
	auto submaskNumber = calculateSubMaskInNumber(continousSameDigitFromMSB);
	auto resultMinIPInNumber = minMaxIP.first & submaskNumber;

	cout << decompressedIPNumberAsText(resultMinIPInNumber) << endl;
	cout << decompressedIPNumberAsText(submaskNumber) << endl;
}

int main()
{
	auto m = 0;
	while (~scanf("%d", &m))
	{
		auto ipTextList = vector<string>(m);
		for (auto i = 0; i < m; i++)
		{
			cin >> ipTextList[i];
		}

		solve(ipTextList);
	}
	return 0;
}