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?
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?)
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.
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
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.
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.
The code. There was no reason to introduce dynamic memory there. (And you don't delete anything you new.)
1 2
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.
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.)