Intro
Link to problem statement. In short, we have a square grid. Each square contains a diagonal connecting two of its corners. We want to color the corners using at most 3 colors, in such a way that points connected by a line segment don't share a color. Is it possible?
This problem had multiple solutions. As usual some solutions need less analysis and others less code.
Simple analysis
This first solution is not difficult to think of or prove, but the code can be very complex.
Think of the setup of lattice points with N and Z patterns. It is actually a set of triangles:
Triangles have three vertexes and they are all connected to each other. Each vertex in the triangle must have a different color. Let us just pick the 3 colors for any of the triangles:
This triangle shares edges with other triangles. These triangles each have two new colors. The decision for the remaining color in each of these triangles is forced. We only have 3 available colors.
Each of these triangles have adjacent triangles of their own, once again we only have one option for the remaining color in each of these triangles:
We can go on... Note that some of the triangles that were adjacent to the previous ones are already completely colored. If this happens, we should verify that they have 3 different colors.
We have found two cases of a contradiction. In the bottom: If we fill one of the triangles, we will guess that the corner must be blue. If we fill the other triangle, it would tell us that the same corner must be red. Note that at the beginning, we just filled a triangle with three distinct colors. It wouldn't matter which order of colors we picked for this first triangle, the contradiction would still happen (but with different colors). Also, the triangle we picked must be colored eventually. So it must have three different colors. No matter what we do, we cannot use three colors to fill this setup.
If, instead, after visiting all of the triangles, we didn't find any inconsistency, then we would already know of one way to color the points. It is both necessary and sufficient that this coloring strategy works in order for it to be possible to use only three colors.
The complicated part about this approach is to implement it. We can pick any triangle to color in the first step. Let us just pick one of the triangles in the top-left cell. After filling one triangle we need to process the remaining triangles in such an order that each triangle shares an edge with at least one triangle that was processed before. Once we fill the two triangles in the top-left cell, we can take the second triangle in the top row, and so and so. If we process the cells in row-major order, we can be sure that at least one triangle in the cell shares an edge with a previously-processed triangle. However, it is not trivial to know which of the two triangles shares the edge, so we still have some potential issues to take care of:
// Each of the following functions returns true if it finds a contradiction.
// Verify/Complete the colors in triangle (a,b,c). Assume that at most one of
// them is unknown.
bool completeTriangle(int &a, int &b, int &c)
{
/* a
/|
/ |
b--c */
// Rotate vertices list until we are sure a, and b are known colors:
if ( a == -1 || b == -1) {
return completeTriangle(c,a,b);
}
if (c != -1) {
// All three colors are known, but we must verify that they are
// distinct:
return (a == b || b == c || c == a);
} else {
// c is the unknown, find a number from 0 to 2 that is different
// from a and b.
c = 0;
while ( (c == a || c == b) && (c < 2) ) {
c++;
}
return (a == b);
//this is not necessary, if a == b, then the contradiction
// would have been found before.
}
}
bool fillTwoTriangles(int &a, int &b, int &c, int &d)
{
/* a--b
Fill the two triangles: |\ |
| \|
c--d */
// Special case : all are unknown (The first cell)
if (a == -1 && b == -1 && c == -1 && d == -1) {
a = 0;
b = c = 1;
d = 2;
return false;
}
// Else either (a,b,d) or (a,c,d) has two assigned colors,
// the triangle with two assigned colors first.
int unknown = ( (a==-1) + (b==-1) + (d==-1) );
if (unknown > 1) {
// Too many unknowns in (a,b,d), begin with (a,c,d) instead.
return fillTwoTriangles(a,c,b,d);
}
// assume (a,b,d) is a good start:
return completeTriangle(a,b,d) || completeTriangle(a,c,d);
}
string isColorable(vector <string> cells)
{
int h = cells.size(), w = cells[0].size();
// Fill colors from top to bottom, left to right:
int colors[h+1][w+1];
memset(colors, -1, sizeof(colors));
for (int y=0; y<h; y++) {
for (int x=0; x<w; x++) {
int &a = colors[y][x] , &b = colors[y][x+1];
int &c = colors[y+1][x], &d = colors[y+1][x+1];
// Thanks to the order in which we fill the colors,
// either the cell is (0,0) or at least one of the triangles
// has two assigned colors.
bool contr = false;
if (cells[y][x] == 'N') {
/* a--b
|\ |
| \|
c--d */
contr = fillTwoTriangles(a,b,c,d);
} else {
/* a--b
| /|
|/ |
c--d */
contr = fillTwoTriangles(b,a,d,c);
}
if (contr) {
return "No";
}
}
}
return "Yes";
}
Simple code
There are actually two approaches worth naming that yield very simple codes.
One problem solving method is to try to find a pattern in boards that are solvable. To this effect, we can try and solve small setups. If you try any setup with only one row or only one column, you will see that they are always solvable. Let us better try setups with 2x2 cells. Of the 16 setups with 2x2 cells, the following 8 are 3-colorable:
There are two interesting ways to find a pattern in these. Perhaps it is clearer if we use 0 for Z an 1 for N:
00 00 01 01 00 11 01 10 10 10 11 11 01 10 00 11
Rule for 2x2 patterns a necessary rule in general
Each of those patterns has exactly an even number of N (and therefore an even number of Z) cells.
We can try to generalize this to larger setups. Perhaps the rule is that each 2x2 sub-rectangle of the setup needs to have an even number of N cells? It is easy to tell that this rules is necessary. We already know that a 2x2 sub-rectangle with an odd number of N cells cannot be colored. If at least one of those sub-rectangles exists, we cannot color it. If we cannot color a sub-rectangle in the setup, then we cannot color the setup itself.
Sufficient?
We need to show that the rule is also sufficient. If it was only necessary, then we wouldn't be able to guarantee that a setup that follows the rule is 3-colorable.
Assuming a setup follows the rule, can we prove that it is 3-colorable?
A new property
Back to the 2x2 setups, consider the 4 possible top rows: {00, 01, 10, 11}. Each has two valid values for the bottom rows. More interestingly, the valid values for the bottom rows are either the same as the top row, or the complete opposite. For example, if the top row is 01, then the two valid bottom rows are 01 and 10.
Now consider a larger row like 0100111101011010. We will pick the values for the row below it:
0100111101011010 ----------------
For the first two cells, we have two options 01 (equal) or 10 (opposite). Let us pick equal:
0100111101011010 01--------------
Consider the next 2x2 block. Its top row is 10, so the only two valid options for the row below are 10 and 01, however, the 1 is already chosen. We are forced to pick 10 (also equal). If we continue filling the row, we will always be forced to pick an equal cell:
0100111101011010 0100111101011010
What if in the first step we chose the opposite? The same will happen, this time the whole row has to be the opposite:
0100111101011010 1011000010100101
If a setup follows the 2x2 rule, then it is also true that it follows a new rule: Each row must be equal or the complete opposite of the previous row. This property is nice because it will make the code even simpler. It will also be useful if we intend to solve the division 1 hard version of this problem. It will also help us prove that the 2x2 property is sufficient.
Sufficient
Imagine we have chosen the colors for the top row. We have previously mentioned that it is always possible to use 3-colors to color a single row. If the next row is exactly equal to the top row, can we color it? If the next row is exactly the opposite, can we color it? If the answer for both questions is Yes, then we can use this argument in a proof by induction. Each of these questions will need a proof by induction of its own.
Equal row
For n=1. The number of columns is 1. We have colored the single cell in the top row. Can we color the row below it? This is a trivial case, because it is always possible to color a setup that has only one column.
Assume that the rule is true for n=k-1. We have colored the k cells in the top row. Can we color the k cells of the bottom row? Since the rule is true for n=k-1 we can assume that the first k-1 cells of the bottom can be colored correctly. There are 4 cases:
From the hypothesis, we know that the yellow points were colored in such a way that there are no contradictions in any of pink triangles. What we need to confirm if if the remaining white point can be given a color in such a way that there are no inconsistencies in the two white triangles. However, each of these 4 cases represents one of the 2x2 patterns that we already know can be colorable. If the colors for the vertices of the pink triangles are all valid, the remaining color and triangles will be valid too.
The proof for the opposite case is similar to this, it just uses the four 2x2 patterns we didn't use in this proof.
Code
For each row, verify if it is equal or completely opposite to the first row. This property is necessary and sufficient for the setup to be 3-colorable.
class ThreeColorabilityEasy:
def isColorable(self, cells):
# row 0
a = cells[0]
# the negative of row 0
b = string.join( ['Z' if ch == 'N' else 'Z' for ch in a], '')
# All rows must be equal to a or b:
return "Yes" if all( (row == a) or (row == b) for row in cells) else "No"
-------------------
Isn't that short python code beautiful?
You are now ready to solve the hard version.
No comments :
Post a Comment