SuperFluousLettersSolver.cpp

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#ifdef _WIN32
#include <intrin.h>
#define __builtin_popcount(x) __popcnt(x)
#endif
using namespace std;
#define lowbit(n) ((n)&-(n))
int bitmap[7][105] = {
	{ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 },
	{ 1,0,0,0,1,0,1,1,1,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1 },
	{ 1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1 },
	{ 1,0,0,0,1,0,0,0,1,0,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,1,1,1,0,1,0,0,1,1,0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,1,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,1,0,1,1 },
	{ 1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,1,0,1,1,1 },
	{ 1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,1,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,1,0,1,0,1,0,1,1,0,1,1,0,0,0,1 },
	{ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 }
};
const int n = 26;
int templates[n][5][3];
short compdata[n]; // Stores binary representation of each letter
short compsum[1 << n]; // Stores xor sum of compdata
int pre[1 << n];
int routes[1 << n];
vector<int> myv; // Stores all x where compsum[x] = 0
queue<int> myq;
bool visit[1 << n]; // Stores all possible solutions
void printshortest(int id)
{
	int iz = 1 << id;
	int best = 0;
	for (int route : myv)
	{
		if (route&iz)
		{
			if (best == 0 || __builtin_popcount(best) > __builtin_popcount(route^iz))
			{
				best = route^iz;
			}
		}
	}
	vector<int> allbest;
	for (int route : myv)
	{
		if (route&iz)
		{
			if (__builtin_popcount(best) == __builtin_popcount(route^iz))
			{
				allbest.push_back(route^iz);
			}
		}
	}
	if (best == 0)
	{
		cout << "No solution for " << char(id + 'A') << endl;
	}
	else
	{
		cout << "Shortest sequence for " << char(id + 'A') << ": ";
		bool first = true;
		for (int route : allbest)
		{
			if (first)
				first = false;
			else
				cout << " | ";
			for (int i = 0; i<n; ++i)
			{
				if (route & 1 << i)
				{
					cout << char(i + 'A');
				}
			}
		}
		cout << endl;
	}
}
int main()
{
	for (int i = 0; i<n; ++i)
	{
		for (int x = 4; x >= 0; --x)
		{
			for (int y = 2; y >= 0; --y)
			{
				templates[i][x][y] = !bitmap[x + 1][y + 1 + i * 4];
				compdata[i] = (compdata[i] << 1) | templates[i][x][y];
			}
		}
		compsum[1 << i] = compdata[i];
	}
	int nz = 1 << n;
	for (int iz = 1; iz <= nz; ++iz)
	{
		if (lowbit(iz) != iz)
		{
			compsum[iz] = compsum[iz^lowbit(iz)] ^ compsum[lowbit(iz)];
			if (compsum[iz] == 0)
			{
				myv.push_back(iz);
			}
		}
	}
	myq.push(0);
	visit[0] = true;
	int tcount = 1;
	while (!myq.empty())
	{
		int state = myq.front();
		myq.pop();
		for (int route : myv)
		{
			int coll = route&state;
			if (coll == 0)
			{
				for (int ic = route; ic; ic ^= lowbit(ic))
				{
					int ib = lowbit(ic);
					int newstate = state | ib;
					int newroute = route^ib;
					if (!visit[newstate])
					{
						visit[newstate] = true;
						++tcount;
						myq.push(newstate);
						routes[newstate] = newroute;
						pre[newstate] = state;
						if (tcount % 1000000 == 0)
						{
							printf("%d\n", tcount);
						}
					}
					/*else if(__builtin_popcount(newroute)<__builtin_popcount(routes[newstate]))
					{
					routes[newstate]=newroute;
					pre[newstate]=state;
					}*/
				}
			}
		}
	}
	int tmax = 0;
	for (int iz = 0; iz<nz; ++iz)
	{
		if (visit[iz] && __builtin_popcount(iz)>__builtin_popcount(tmax))
			tmax = iz;
	}
	printf("Best: %d\n", __builtin_popcount(tmax));
	vector<string> solution;
	while (tmax)
	{
		int route = routes[tmax];
		int killed = pre[tmax] ^ tmax;
		string result = "Remove ";
		result += char((int)log2(killed) + 'A');
		result += ": ";
		for (int i = 0; i<n; ++i)
		{
			if (route & 1 << i)
			{
				result += char(i + 'A');
			}
		}
		solution.push_back(result);
		tmax ^= killed;
	}
	reverse(solution.begin(), solution.end());
	for (string s : solution)
	{
		cout << s << endl;
	}
	system("pause");
}