Dynamic programming: Find largest diamond (rhombus)

Question

I have a small program to do in Java. I have a 2D array filled with 0 and 1, and I must find the largest rhombus (as in square rotated by 45 degrees) and their numbers.

Example:

0 1 0 0 0 1

1 0 1 1 1 0

1 0 1 1 1 1

0 1 1 1 1 1

0 0 1 1 1 1

1 1 1 1 1 1

Result:

The problem is similar to this SO question.

If you have any idea, post it here.

We probably have tons of idea's, but its not our homework to do. What have you accomplished? — Anthony Forloney, Apr 09 '10 at 13:52
By definition, a rhombus must have four sides of the same length, but doesn't necessarily have interior angles of 90 degrees. Do you need to find the largest rhombus of any kind, or __only__ the largest 45-degree-rotated square? (I assume you meant 45 degrees because of your sample result; a 90-degree-rotated square is identical to the original.) — Pops, Apr 09 '10 at 14:41
@Lord Torgamus: it's obviously, from the representation used to represent the "2D array", the largest 45-degrees rotated square... (I mean, otherwise good luck solving that problem due to line-drawing/intersection/precision issues ;) — SyntaxT3rr0r, Apr 09 '10 at 15:07
@Wizard, it's hardly obvious. Using other degrees is a more difficult problem, but certainly not an unsolvable one, if you treat all elements of the array as being of equal distance from neighbors, and don't count sides as being in the array. Consider 01000 / 01111 / 01110 / 11110 / 00010. Or 00100 / 11111 / 00100. — Pops, Apr 09 '10 at 15:18
@Lord Torgamus: In, say, your first example, 01000, what about the 'element' '-' at "01-00", how can you decide it's part (or not) of the rhombus? If you want to solve if for an arbitrary angle then we're not talking about a discrete problem anymore and I'm afraid that *a)* I don't have my less-than-15 lines solution (see my answer) and *b)* only approximate answer exist, due to the non-discrete nature that the problem would acquire :) — SyntaxT3rr0r, Apr 09 '10 at 15:31
@Wizard, that's why I said "don't count sides as being in the array." If you take out graph paper and plot the points (1, 4), (4, 3), (3, 0) and (0, 1), it's clearly a rhombus. The half-filled cells could be "don't cares," to borrow a term from Karnaugh maps. But since the OP isn't responding, I'm guessing that the easier interpretation of the problem, the one you solved, was the one he was assigned... which makes this whole comment thread off-topic and irrelevant. — Pops, Apr 09 '10 at 16:08
@Lord Torgamus: I see what you mean but my whole point is that precisely to *detect* which cells can be half-filled or not we're not talking about discrete math anymore. You have to take edges, you have to "draw a line" and you have to see if each cell is "inside" the rhombus. But you can't do that with a mechanical device: this is simply not a discrete problem anymore. It's similar to, say, using the Bresenham algorithm to draw lines: there **are** approximations going on. Write me an algo solving "your" version of the problem and I'll write you a test case breaking it. — SyntaxT3rr0r, Apr 09 '10 at 18:00
http://groups.google.com/group/comp.lang.c/msg/e105e5d339edec01?pli=1 ? — Zolomon, May 12 '10 at 13:49

SyntaxT3rr0r · Accepted Answer · 2010-04-09T15:21:43.983

3

This too long for a comment. I'll post my solution later on if you can't solve it but here's how I've done it (in less than 15 lines of code): I first created a second array (a little big bigger [n+2][n+2]) and did n/2 pass:

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 2 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 3 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0

Where a non-zero number x means "I'm the center of a rhombus of size x" (I'm expressing the size in relation with the length of the diagonals [which are both equal in your case] of the rhombus). You can find if you have the center of a rhombus of size (k+1) by checking if {top,right,down,left} are all the centers of rhombus of size k.

The advantage of first creating a bigger array is that it really simplifies your logic but I could do it in place, with a more convoluted logic, by modifying the original array or by using a second array of the same size as the input (once again, it's way easier to simply put a safe "fence" of all-zeroes around your input).

If you don't "surround" your array with a fence, you have a lot of additional if/else checks: this would be prone to errors, lead to bigger code and lead to uglier code.

edited Apr 09 '10 at 15:21

answered Apr 09 '10 at 14:55

SyntaxT3rr0r

27,745
21
87
120

3

If he really *needs* the code for his homework because its hard for him, then he really needs to do it himself to get the practice. – Beska Apr 09 '10 at 15:21
@WizardOfOdds thank you,elegant and brilliant ideea,i was thinking of that too,but my question is the following: When i start assign the numbers,i travel trough the array and where i find 1,i check min(up,down,left,right)+1 (which will be size 1 or to,in the first loop of the array-"traveling"). So i will have the new array made of 0,1 and 2.Then i have to loop it again,so i will have an array made of 0,1,2 and 3s.And so on, n-times.But...how would this work on a huge array? – Darksody Apr 10 '10 at 11:26
I'm testing it right now,i'll post after i do it,i'll tell you how it works. – Darksody Apr 10 '10 at 11:28
@Darksody: how big can the array be? You didn't tell anything about the requirements... a 3 000 x 3 000 square array containing 9 million elements can be solved in a few seconds. There *are* possible optimizations (like only checking on pass n+1 the squares that did actually get modified during pass n) and there *may* be faster solutions. I haven't looked more into it: what are the requirements? (ie how big can the square array be?) – SyntaxT3rr0r Apr 10 '10 at 13:24
@WizardOfOdds like 2^32... but it works pretty good,i tested it :) – Darksody Apr 11 '10 at 08:51

score 2 · Answer 2 · answered Apr 09 '10 at 13:59

2

Short tutorial:

How would you solve the problem if it was a 1x1-field?
How could you formulate the problem recursively?
How could you remember intermediate results and use them?
Do it.

answered Apr 09 '10 at 13:59

phimuemue

34,669
9
84
115

score 0 · Answer 3 · answered Apr 10 '10 at 11:58

void rhombus()
{
    maxr=0;
    for (int i=n-1;i>=0;i--)
    {
        for (int j=n-1;j>=0;j--)
        {
            if (b[i][j]>0)
            {
                if ((i==n-1) || (j==n-1) || (i==0) || (j==0)) b[i][j]=1;
                else {
                    b[i][j]=min4(b[i][j+1],b[i][j-1],b[i+1][j],b[i-1][j])+1;
                    if (b[i][j]==maxr) nrr++;
                    else if (b[i][j]>maxr) {
                        nrr=1;
                        maxr=b[i][j];
                    }
                }
            }
        }
    }
}

Did it,it works,this is my function,where maxr is the max size of the rhombus,and nrr is the number of max sized rhombus.Not sure how it works on huge arrays.(i loop this function n/2 times)

Thank you all for your help,especially WizardOfOdds,your ideea is really good.I didn't use that 0 border around my array,i just tested if the block is on the edge,felt more confortably with it.Again,thanks :) — Darksody, Apr 10 '10 at 12:01

Dynamic programming: Find largest diamond (rhombus)

3 Answers3

Linked