Flip Five - Competition Problem

[LB]

I just got back from a 3-hour competitive programming competition. There were 7 problems, my team mate solved 1, and I solved 5. That took 2 hours - we had an hour left to solve the first problem, the problem we had skipped. We couldn't solve it - only first place beginners and the first three places of advanced division solved all seven problems. (We got 7th place)

I still have no idea how to even go about the problem at all - I know from past experience that the host of the competition likes problems that require dynamic programming - that is, a naive approach will exceed the time limit whereas the intended simpler solution will work. The time limit for this problem was 3 seconds, so brute force was not an option.

You have a 3x3 grid of cells that are each initially either black or white, and you have to output the number of the least flips it takes to make all the cells white, where flipping one cells causes the adjacent (but not diagonal) cells to flip with it.

I figured out that the order didn't matter, and it didn't matter if you went from given to all white or all white to given, you just had to output the least number of flips for the solution. There was one requirement I could not understand, and it was that we could not rotate the grid - as far as we could tell it would make no difference, and they wouldn't be able to tell if we did that in our code anyway.

There were two given sample input and outputs:
■□□
■■□
■□□
Output 1 (just flip the left center tile)

■■■
■□□
□□■
Output 3 (flip the top center, left bottom, and bottom center)

We did actually spend our whole remaining hour working on this one, trying to understand the mechanics of the puzzles - we had 9 ripped square papers with scribbles on one side and nothing on the other that we were using to play with. We figured out some techniques but nothing got us close to solving the puzzle in programming.

As for the title "Flip Five", I am sure it is relevant but I don't know how - I think, but have not made sure, that the most number of moves a puzzle will ever take is five (at least we could not find a puzzle that took 6 moves or more).

I'm still stumped on this one, and my coach and the other teams' coaches were stumped too. Several teams did solve it though, so it has a solution. (One team in the advanced division even solved all 7 problems during the first hour of the competition).

I want to know how to solve this puzzle the correct way, could I get some help?

[m4ster r0shi]

What if you used something like A* with the number of black tiles as a heuristic? Did you have the option to run programs and view the output without submitting them? If yes, you could just brute force every possible configuration (a little more than 128 (2^9 / 4)) and then hardcode the results into your final program. What access to resources did you have in general (e.g. were you allowed to use google or wikipedia?)

Something relevant -> http://www.newgrounds.com/portal/view/438701

[cire]

Just an idea.

Begin with the solution (all squares the same color.) Flip the top left square. Record the pattern generated and the square flipped. If this pattern in encountered again, it can be solved with one flip of the recorded square.

Revert back to the solution. Flip the top middle square. Record the pattern generated and the square flipped. If this pattern is encountered again, it can be solved with one flip of the recorded square.

Revert back to the solution. Flip the top right square. Record the pattern generated and the square flipped. If this pattern is encountered again, it can be solved with one flip of the recorded square.

At this point, one may check against the patterns generated by rotating the grid so that each side is interpreted as the top one, but the requirements are that you not do that, so you need to repeat the steps for all of the squares in the grid.

Once that's done, begin with the first pattern that required one flip to solve. Do as above, but instead of reverting back to the solution, revert back to the first pattern that required one flip to solve. Patterns generated that require one flip to solve (we already know what all those are right?) or result in a solution should be ignored. All patterns so recorded will require two flips to solve.

Repeat for each pattern that required one flip to solve.

I think you can see how this goes. You eventually catalog every pattern that can occur and at that point you can stop further processing and just look up the pattern to see the smallest number of flips a particular pattern requires for a solution.

[Catfish3]

You have to take advantage of the fact that the given input is solvable, because it appears that not all inputs are.

[ne555]

> The time limit for this problem was 3 seconds, so brute force was not an option.
3 seconds for checking 512 movements seems viable.

[LB]

m4ster r0shi wrote:

What if you used something like A* with the number of black tiles as a heuristic? Did you have the option to run programs and view the output without submitting them? If yes, you could just brute force every possible configuration (a little more than 128 (2^9 / 4)) and then hardcode the results into your final program. What access to resources did you have in general (e.g. were you allowed to use google or wikipedia?)

We were only allowed to use the internet for documentation.

@ne555 I forgot to mention, the competition was in unoptimized Java, which is why brute forcing takes too long.

@Catfish3 we could not find a puzzle that could not be solved in 5 moves or less.

@cire @m4ster r0shi I will check that out and think on it, thanks

[cire]

I put together a quick (almost entirely untested) implementation. It does report puzzles that take 6 moves to solve. I wonder if I goofed something up. I don't have the patience to do it manually. These are some of the puzzles:

■□■
■■■
□□□


■■■
■□□
■□□


■■□
■■■
□■■

I believe the rest are all rotated or inverted versions of these three.

Code at: http://gist.github.com/cire3791/5381142

[Script Coder]

Interesting problem.
@L B would you mind sharing the other problems please? (I feel like doing some of them)

[Script Coder]

My solution, might not be correct, test data returns correct results.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int hash(int **A) {	//Creats unique hash of grid
	int h=0;
	for(int i=0; i<3; ++i)
		for(int j=0; j<3; ++j) 
			h+=(A[i][j]==1 ? (1<<((3*i)+j)) : 0);
	return(h);
}

void dehash(int h, int** A) {	//Creates a grid from a hash
	for(int i=0; i<3; ++i) {
		for(int j=0; j<3; ++j) {
			A[i][j]=h%2;
			h>>=1;
		}
	}
}

inline int alt(int i) {	// 1 becomes 0 and vice versa (probably a better way to do this)
	return(i==0 ? 1 : 0);
}
void flip(int **A, int **B, int x, int y) {							//Flips the (i;j) cell, leaving the origional in tact and putting the flipped in B
	for(int i=0; i<3; ++i) for(int j=0; j<3; ++j) B[i][j]=A[i][j]; //Copies A to B
	B[x][y]=alt(B[x][y]);
	if(x-1>=0) B[x-1][y]=alt(B[x-1][y]);
	if(x+1<3) B[x+1][y]=alt(B[x+1][y]);
	if(y-1>=0) B[x][y-1]=alt(B[x][y-1]);
	if(y+1<3) B[x][y+1]=alt(B[x][y+1]);
}
	
int main() {
	int **A=new int*[3], **B=new int*[3];		//Create space for working out arrays
	for(int i=0; i<3; ++i) {
		A[i]=new int[3];
		B[i]=new int[3];
	}
	
	for(int i=0; i<3; ++i) for(int j=0; j<3; ++j) cin>>A[i][j];	//get target grid for user
	
	int p=hash(A);			//create target hash
	int keys[512]; for(int i=1; i<512;++i) keys[i]=513; keys[0]=0;		//stores the steps required to get to a hash
	bool done[512]; for(int i=1; i<512;++i) done[i]=false; done[0]=true;	//stores weather or not a hash has been done
	queue<int> st; st.push(0);

	while(!(st.empty())) {			//I believe this algorithm mimics distrika's algorithm
		int a=st.front(); st.pop();
		dehash(a,A);
		for(int i=0; i<3; ++i) {
			for(int j=0; j<3; ++j) {
				flip(A, B, i, j);
				int h=hash(B);
				if(!done[h]) {
					st.push(h);
					done[h]=true;
				}
				keys[h]= (keys[h]<keys[a] ? keys[h] : keys[a]+1);					
			}
		}
	}
	cout<<keys[p]<<'\n';		//output result
}

[LB]

Based on the complexity of the 'harder' problems and what the competition host said, I am pretty sure there is a very simple solution. I do very much enjoy reading your solutions, though :)

The judges' solutions will be emailed to our coaches soon, so I'll post that when we get it.

[cire]

ScriptCoder wrote:

My solution, might not be correct, test data returns correct results.

Your solution reports 7 flips needed for the ones I mentioned above which required 6.

	int **A=new int*[3], **B=new int*[3];		//Create space for working out arrays
	for(int i=0; i<3; ++i) {
		A[i]=new int[3];
		B[i]=new int[3];
	}

Really? =P

I also had to rename hash since your using namespace std; directive brought std::hash into the global namespace and made the calls to hash ambiguous.

L B wrote:

I am pretty sure there is a very simple solution.

I thought mine was pretty simple. I have a tendency to avoid recursion or it would look quite a bit simpler.

[Script Coder]

@L B please try and get all the problems

cire wrote:

Really? =P

Was that towards my code or my comment?

cire wrote:

I also had to rename hash since your using namespace std; directive brought std::hash into the global namespace and made the calls to hash ambiguous.

Dutifully noted and I will try not to do it again in the future. (I blame my Overly Helpful Compiler for not reporting this to me).

cire wrote:

Your solution reports 7 flips needed for the ones I mentioned above which required 6.

Would you (or anyone else) mind helping me find the error in my code?

[cire]

Was that towards my code or my comment?

The code. There was no reason to introduce dynamic memory there. (And you don't delete anything you new.)

int A[3][3] ;
int B[3][3] ;

And changing function parameter types to match would've sufficed.

Would you (or anyone else) mind helping me find the error in my code?

I don't have time at the moment and it's not necessarily an error in your code, as I haven't spent any time verifying mine is correct. Just noting an inconsistency between the two.

[Script Coder]

There was no reason to introduce dynamic memory there

I tried not to and I did change the functions, but ran into problems when I had to declar the queue.

And you don't delete anything you new.

Terribly bad habit, sorry and thank you.

Also, I was more referring to the semantics of my code, rather than the code itself.

[LB]

We've got the explanations!

All 7 problems were explained across a total of 3 pages. This problem took over a whole page to explain.

Problem set:
https://www.dropbox.com/s/u0nerz0vw2j1hwd/HScontest_4_13_13.pdf
Explanations:
https://www.dropbox.com/s/bja1wy5of5pkqss/Explanation.pdf

My team solved all but this problem (Problem A) of which I solved 5 and my partner solved Empress Cindy.

[cire]

The explanation provided for that particular problem is roughly what I coded, except I didn't store the click pattern required to achieve a particular pattern, only the minimum number of clicks to get there. (And of course, it doesn't solve the problem, but that would be easy enough to do once the solutions are mapped out.)

[Script Coder]

I only just noticed your links now, thanks L B :)