Polyominoes (sp?)

[Lithium]

This was one of the problems from programming competition I won this year.

A polyominoe is a connected patch of the same letters, they must be connected directly verticaly or horizontally

A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

the bold A's are an example of a polyominoe

You must write a program to count the number of polyominoes in a grid of letters

you take input from a text file (must be test.dat), i.e:

the first number in the file, x, will be the x size of the grid, the second, y, will be the y size. the next x*y data entrys will be upper case letters (the data for the grid)

Code:

5, 5
A, A, A, B, B
A, B, B, B, C
A, A, B, C, C
D, D, D, D, C
D, D, D, A, B

the output for this data would be 6

your program should be able to handle grids of capital letters only, with a size maximum of 32x32

the fastest program will win

[Blitz]

You're going to have to be more specific, why is output 6? There are 6 connected As, what about the other letters? There are more connections between them. Is it supposed to count the connections or the number of connected letter? Does a series of connections of the same letter but in two different places count as number of connections or just the first one?

[Z!re]

A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

Thats 7..

D, Up
D, Right
D, Down
D, Right
D, Up
D, Right
D

[Meg]

He means that if you connect all adjacent,matching letters with lines, you would end up with 6 separate groups of connected nodes. Hence, output 6.

[Lithium]

Yeah I didn't word that very well, so just go by what meg said.

Here are all the polyominoes in this grid:

1.
A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

2.
A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

3.
A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

4.
A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

5.
A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

6.
A A A B B
A B B B C
A A B C C
D D D D C
D D D A B

since there are 6 polyominoes here your program should output 6

[Neo]

I made this in a few minutes:

(it's FreeBasic code)
[syntax="FreeBasic"]'Program for counting Polyominoes in a small grid
'Not very fast or efficient, but working
'- Neo

'#define DEBUG

'$dynamic

Declare Sub LoadData ()
Declare Sub Calculate ()
Declare Sub RecursiveScan (ByVal Object As Integer, ByVal X As Integer, ByVal Y As Integer)

Dim Shared Grid(0, 0) As Integer, gWidth As Integer, gHeight As Integer
Dim Shared NoPatches As Integer = 0

Call LoadData
Call Calculate

#ifdef DEBUG
For y = 0 To gHeight - 1
For x = 0 To gWidth - 1
Print Grid(x, y);
Next x
Print
Next y

Print: Print
#endif
Print "Number of Polyominoes in Grid:"; NoPatches
Sleep
End

Private Sub Calculate
For y = 0 To gHeight - 1
For x = 0 To gWidth - 1
If Grid(x, y) <> -1 Then
NoPatches+=1
RecursiveScan(Grid(x, y), x, y)
End If
Next x
Next y
End Sub

Private Sub RecursiveScan (ByVal Object As Integer, ByVal X As Integer, ByVal Y As Integer)
Grid(X, Y) = -1
If X - 1 >= 0 Then If Grid(X - 1, Y) = Object Then RecursiveScan(Object, X - 1, Y)
If X + 1 < gWidth Then If Grid(X + 1, Y) = Object Then RecursiveScan(Object, X + 1, Y)
If Y - 1 >= 0 Then If Grid(X, Y - 1) = Object Then RecursiveScan(Object, X, Y - 1)
If Y + 1 < gHeight Then If Grid(X, Y + 1) = Object Then RecursiveScan(Object, X, Y + 1)
End Sub

Private Sub LoadData
FF = FreeFile
Open "test.dat" For Input As #FF
'width and height
Input #FF, gWidth
Input #FF, gHeight

#ifdef DEBUG
Print "Width:"; gWidth
Print "Height:"; gHeight
#endif

Redim Grid(gWidth - 1, gHeight - 1) As Integer

#ifdef DEBUG
Print Chr$(13) + "Grid:"
#endif
For y = 0 To gHeight - 1
For x = 0 To gWidth - 1
Input #FF, letter$
Grid(x, y) = Asc(letter$) - Asc("A")
#ifdef DEBUG
Print Grid(x, y);
#endif
Next y
#ifdef DEBUG
Print
#endif
Next x
#ifdef DEBUG
Print
#endif

Close #FF
End Sub
[/syntax]

Tested it a few times and seems to work It might not be fast, but I'm glad it works.

Wish they allowed FB on the programming competitions I did.

[Lithium]

That's exactly how I did it at the competition

And it's not that slow, just a little bit slower than x_grid_size * y_grid_size

[Neo]

Hehe wow =) Me making the program in the same way as you did... hehe. I guess people who do competitions are most likely to do this

I'm glad it works, was a nice challenge (although I met some terribly more difficult ones in my competitions... and you probably too).

I'm glad you won it though, I never did. Once again shows your class and understanding about things =)

[Lithium]

This was just a highschool programming competition, third time in a row I've won it though

I spent a lot of time preparing for it, in the process I did around 30 problems from university competitions, including 3 from last years ACM word finals

My goal now is to go to the world finals... but I'll have to get out of highschool first

[Pyrokid]

What are these programming competitions. ive never heard of them