# Code-Golf: Count Islands

A simple contest, inspired by this stackoverflow question:

You are given an image of a surface photographed by a satellite.The image is a bitmap where water is marked by '.' and land is marked by '*'. Adjacent group of '*'s form an island. (Two '*' are adjacent if they are horizontal, vertical or diagonal neighbours). Your task is to print the number of islands in the bitmap.

Sample Input:

.........**
**......***
...........
...*.......
*........*.
*.........*

Sample Output:

5

Winner is entry with smallest number of bytes in the code.

-
I don't understand the logic. Aren't 5 stars in the top right corner considered as one island? Then your example has 4 islands. – Artem Ice Aug 14 '12 at 4:42
the screen doesn't wrap. one island in each of the corners + the lone * island – Claudiu Aug 14 '12 at 4:59
But by your definition, an island is a group of '*' characters, implying more than one. – acolyte Aug 14 '12 at 20:09
oh fair point. stand-alone *s are also islands. – Claudiu Aug 16 '12 at 21:13

# Mathematica 188 185 170 115 130 45 chars

Explanation

In earlier versions, I made a graph of positions having a chessboard distance of 1 from each other. GraphComponents then revealed the number of islands, one per component.

The present version uses MorphologicalComponents to find and number clusters of ones in the array--regions where 1's are physically contiguous. Because graphing is unnecessary, this results in a huge economy of code.

Btw, -> ([Rule]) is actually a single, dedicated character in Mathematica

Code

Max@MorphologicalComponents@d/.{"."->0,"*"->1}

How it works

d holds the data. I assumed the data are a table of data; in Mathematica that is a list of lists:

d = {{".", ".", ".", ".", ".", ".", ".", ".", ".", "*", "*"}, {"*", "*", ".", ".", ".", ".", ".", ".", "*", "*", "*"}, {".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."}, {".", ".", ".", "*", ".", ".", ".", ".", ".", ".", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", "*", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", ".", "*"}}
<code from above goes here>
(* out *)
5

The input data, d, are converted to 1's and 0's by the replacement

/.{"."->0,"*"->1}

where /. is an infix form of ReplaceAll followed by replacement rules.

The picture below shows a some steps the approach uses. The input matrix contains only 1's and 0's. The output matrix labels each morphological cluster with a number. (I wrapped both the input and output matrices in MatrixForm to highlight their two dimensional structure.)

Max returns the largest value in the output matrix, which is the number of clusters (i.e. islands).

Displaying the Islands

Colorize will color each island uniquely.

-
 +1 Nicely done ;-) – Vitaliy Kaurov Aug 21 '12 at 5:09 This isn't working as written on v7 because MorphologicalComponents wants an Image, but even on v9 shouldn't this be Max@MorphologicalComponents[d/.{"."->0,"*"->1}]? That is, the replacement done first? Max would disappear before the replacement was done, would it not? – Mr.Wizard Apr 6 at 14:41

## Ruby 1.9 (134121113 110)

Takes the map on stdin or the file name of the map as the first command-line argument, and prints the number of islands to stdout. Using a basic recursive flood-fill. Improvements welcome as always!

c=0
gets\$!
c+=1while(f=->i{9.times{|o|\$_[i]=?.;f[o]if\$_[o=i+(o/3-1)*(~/\$/+1)+o%3-1]==?*&&o>0}if i})[~/\*/]
p c

Similar to David's colorize, you can also get it to display the different islands by changing \$_[i]=?. to \$_[i]=c.to_s and p c to puts\$_, which would give you something like this:

.........00
11......000
...........
...2.......
3........4.
3.........4

(at least until you run out of digits!)

Some test cases:

.........**
**......***
...........
...*.......
*........*.
*.........*

5

......*..**....*
**...*..***....*
....*..........*
...*.*.........*
*........***....
*.....*...***...
*.....*...*....*
****..........**
*.........*.....

9

*

1

****
****
....
****

2

**********
*........*
*.******.*
*.*....*.*
*.*.**.*.*
*.*.**.*.*
*.*....*.*
*.******.*
*........*
**********

3

-
I like the last test. Thinking inside the box! – Mr Lister Aug 14 '12 at 5:56

## C, 169 chars

Reads map from stdin. Had no luck improving the recursive flood-fill function r(j) although it looks like it could be.

c,g,x,w;char m[9999];r(j){if(m[j]==42)m[j]=c,r(j+1),r(j+w-1),r(j+w),r(j+w+1),c+=j==g;}main(){while((m[x++]=g=getchar())+1)w=g<11*!w?x:w;for(;g++<x;)r(g);printf("%i",c);}
-