Re: Math/Programming Algorithm Help
Jeff Higgins wrote:
Dasher wrote:
Hello -
I'm having trouble with an algorithm. Basically, the user is presented
with
a grid of toggle buttons (clicking on each button will change its color
from "inactive" to "active" and back). When the user is presented by a
grid of size NxN, they need to click to activate N number of squares, so
that all the activated squares are contiguous, ie, they each squares
shares
an edge with at least one other square. So, for instance, when N=5, the
user would need to activate 5 contiguous squares, like so (let 1=active,
and 0=inactive):
00000 00100
00100 00100
01110 or 00100 would be valid combinations
00100 00100
00000 00100
00110
00000
00000 would not be valid
00111
00000
So, basically, I'm trying to develop an algorithm for testing whether the
users selected a valid combination, for any size N>1. I was thinking
that
there might be some kind of mathematical solution, for instance, using
geometric properties, or matrices, but I haven't had any success going
that
route thus far. Does anyone have any pointers on how to go about doing
this?
Brute force.
import java.util.TreeSet;
public class ConnectednessTest
{
/*
4 | 0 0 0 0 0 4 | 0 0 0 0 0 4 | 0 1 1 1 0
3 | 0 0 1 0 0 3 | 0 1 1 0 0 3 | 0 1 0 1 0
2 | 0 1 1 1 0 2 | 0 0 1 0 0 2 | 0 0 0 0 0
1 | 0 0 1 0 0 1 | 0 1 1 0 0 1 | 0 0 0 0 0
0 | 0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 0 0 0
y ---------- y ---------- y ----------
T x 0 1 2 3 4 T x 0 1 2 3 4 T x 0 1 2 3 4
4 | 1 1 1 1 1 4 | 0 0 1 0 0 4 | 1 1 0 0 0
3 | 0 0 0 0 0 3 | 0 0 1 0 0 3 | 1 1 0 0 0
2 | 0 0 0 0 0 2 | 0 0 1 0 0 2 | 0 1 0 0 0
1 | 0 0 0 0 0 1 | 0 0 1 0 0 1 | 0 0 0 0 0
0 | 0 0 0 0 0 0 | 0 0 1 0 0 0 | 0 0 0 0 0
y ---------- y ---------- y ----------
T x 0 1 2 3 4 T x 0 1 2 3 4 T x 0 1 2 3 4
4 | 0 0 0 0 1 4 | 1 0 0 0 1 4 | 0 0 1 0 0
3 | 0 0 0 1 0 3 | 0 1 1 1 0 3 | 0 0 1 0 0
2 | 0 0 1 0 0 2 | 0 0 0 0 0 2 | 0 0 0 1 0
1 | 0 1 0 0 0 1 | 0 0 0 0 0 1 | 0 0 1 0 0
0 | 1 0 0 0 0 0 | 0 0 0 0 0 0 | 0 0 1 0 0
y ---------- y ---------- y ----------
F x 0 1 2 3 4 F x 0 1 2 3 4 F x 0 1 2 3 4
*/
public static void main(String[] args)
{
Cell[] a1 =
{
new Cell(2, 1),
new Cell(1, 2),
new Cell(2, 2),
new Cell(3, 2),
new Cell(2, 3)
};
Cell[] a2 =
{
new Cell(1, 1),
new Cell(2, 1),
new Cell(2, 2),
new Cell(2, 3),
new Cell(1, 3)
};
Cell[] a3 =
{
new Cell(1, 3),
new Cell(3, 3),
new Cell(1, 4),
new Cell(2, 4),
new Cell(3, 4)
};
Cell[] a4 =
{
new Cell(0, 4),
new Cell(1, 4),
new Cell(2, 4),
new Cell(3, 4),
new Cell(4, 4)
};
Cell[] a5 =
{
new Cell(2, 0),
new Cell(2, 1),
new Cell(2, 2),
new Cell(2, 3),
new Cell(2, 4)
};
Cell[] a6 =
{
new Cell(0, 4),
new Cell(1, 4),
new Cell(0, 3),
new Cell(1, 3),
new Cell(1, 2)
};
Cell[] a7 =
{
new Cell(0, 0),
new Cell(1, 1),
new Cell(2, 2),
new Cell(3, 3),
new Cell(4, 4)
};
Cell[] a8 =
{
new Cell(0, 4),
new Cell(4, 4),
new Cell(1, 3),
new Cell(2, 3),
new Cell(3, 3)
};
Cell[] a9 =
{
new Cell(2, 0),
new Cell(2, 1),
new Cell(2, 3),
new Cell(2, 4),
new Cell(3, 2)
};
Cell[][] list =
{a1,a2,a3,a4,a5,a6,a7,a8,a9};
for(Cell[] a : list)
{
System.out.println(test(a));
}
}
static boolean test(Cell[] CA)
{
TreeSet<Cell> ca = new TreeSet<Cell>();
for(int i = 0; i < CA.length; i++)
{
for(int j = 0; j < CA.length; j++)
{
if(CA[i].adjoins(CA[j]))
{
ca.add(CA[i]);
}
}
}
for(Cell c : CA)
{
if(ca.contains(c) == false)
return false;
}
return true;
}
static class Cell
implements Comparable<Cell>
{
int x; int y;
Cell(int X, int Y){
x = X; y = Y;
}
public boolean adjoins(Cell C){
if(((x-1)==C.x || (x+1)==C.x) && y==C.y)
return true;
else if(((y-1)==C.y || (y+1)==C.y) && x==C.x)
return true;
return false;
}
@Override
public int compareTo(Cell C){
if(x > C.x) return 1;
if(x < C.x) return -1;
if(y > C.y) return 1;
if(y < C.y) return -1;
return 0;
}
}
}