CareerCup

// Back_String_Comp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

class Back_string_Itter
{
public: 
	Back_string_Itter(string &s)
	{
		data = &s;
		index = s.size() - 1;
	} //------------------------------------------------------------------

	char pop()
	{
		if (index == -1)
		{
			return 0;
		}
		int back = 0;

		while (true)
		{
			while ((*data)[index] == '<') // count back spaces 
			{
				back++; 
				index--;
				if (index == -1)
				{
					return 0;
				}
			}

			do // drop letters 
			{
				back--;
				if (back == -1)
				{
					index--;
					return (*data)[index + 1];
				}				
				
				index--;
				if (index == -1)
				{
					return 0;
				}

			} while ((*data)[index] != '<');
		}
	} //------------------------------------------------------------------


private:
	string *data;
	int index;
	
}; //------------------------------------------------------------------

bool comp(string &a, string &b)
{
	Back_string_Itter i(a);
	Back_string_Itter j(b);

	while (true)
	{
		char x = i.pop();
		char y = j.pop();

		if (x != y)
		{
			return false;
		}

		if (x == 0 || y == 0)
		{
			if (x == y)
			{
				return true;
			}
			return false;
		}
	}
	return false; // make the compiler happy 
} //------------------------------------------------------------------


/*
int _tmain(int argc, _TCHAR* argv[])
{
	string s = "EDC<B<<Z";
	Back_string_Itter b(s);

	while (true)
	{
		char c = b.pop();

		while (c != 0)
		{
			cout << c;
			c = b.pop();
		}
	}


	return 0;
	}*/ //------------------------------------------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
	cout << comp(string("EDC<B<<Z"), string("EZ")) << "\n";  // t
	cout << comp(string("ED<C<B<<Z"), string("EZ")) << "\n"; // f
	cout << comp(string("ABC"), string("EZ")) << "\n"; // f
	cout << comp(string("ABC"), string("ABC")) << "\n"; // t
	cout << comp(string("ABC"), string("<ABC")) << "\n"; // t
	cout << comp(string("<ABC"), string("<ABC")) << "\n"; // t
	cout << comp(string("<ABC"), string("ABC")) << "\n"; // t
	cout << comp(string("Q<ABC"), string("ABC")) << "\n"; // t
	cout << comp(string("Q<ABC"), string("ABC<")) << "\n"; // f

} //------------------------------------------------------------------

sort
match every other one
{w[0], w[1]}
{w[2], w[3]}
...

If x+y-1 is odd you can make any pattern with row/column flips.
Else
If the exor of all cells is 0 then this is a valid pattern
However if it is 1 then you cannot make that pattern
Label all cells in the grid with capital letters
ABC
DEF

Let the lower case letter be true if it was the center of a flip
a= true
111
100

Write the equation for each cell
A = a exor b exor c exor d
B = a exor b exor c exor e
C…

Exor all capital letters
Simplify
z exor z -> 0
0 exor z -> z
…
When you flip a row / column you change x+y-1 cells
If(x+y-1) is even then the exor of all bits will = 0
If(x+y-1) is odd then exor of A….. = exor a…. so that does not matter

If someone can write a better explanation please do. It took me a long time to figure this out and I want to move on. It seems like a induction proof would be good for this.

#include "stdafx.h"
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

int count_crossings_after_sort(vector<int> in) // no depes aloud !
{
	unordered_map<int, int> value_to_old_index;

	for (int i = 0; i < in.size(); i++)
	{
		value_to_old_index[in[i]] = i;
	}

	sort(in.begin(), in.end());

	int c = 0;

	for (int i = 0; i < in.size() - 1; i++)
	{
		for (int j = i + 1; j < in.size(); j++)
		{
			if (value_to_old_index[in[i]] > value_to_old_index[in[j]])
			{
				c++;
			}
		}
	}


	return c;
}



int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> in = { 3, 5, 2, 1 };

	int r = count_crossings_after_sort(in);
	return 0;
}