# 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 '*'. Groups of adjacent '*'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.

A single * also counts as an island.

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. Commented Aug 14, 2012 at 4:42
• the screen doesn't wrap. one island in each of the corners + the lone * island Commented Aug 14, 2012 at 4:59
• But by your definition, an island is a group of '*' characters, implying more than one. Commented Aug 14, 2012 at 20:09
• oh fair point. stand-alone *s are also islands. Commented Aug 16, 2012 at 21:13

# Mathematica 188 185 170 115 130 46 48 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.

Code

Max@MorphologicalComponents[#/.{"."->0,"*"->1}]&


## Example

Max@MorphologicalComponents[#/.{"."->0,"*"->1}]&[{{".", ".", ".", ".", ".", ".", ".", ".", ".", "*", "*"}, {"*", "*", ".", ".", ".", ".", ".", ".", "*", "*", "*"}, {".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."}, {".", ".", ".", "*", ".", ".", ".", ".", ".", ".", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", "*", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", ".", "*"}}]


5

How it works

Data are input as an array; in Mathematica, this is a list of lists.

In the input array, data are converted to 1's and 0's by the replacement

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


where /. is an infix form of ReplaceAll followed by replacement rules. This essentially converts the array into a black and white image. All we need to do is apply the function, Image.

Image[{{".", ".", ".", ".", ".", ".", ".", ".", ".", "*", "*"}, {"*", "*", ".", ".", ".", ".", ".", ".", "*", "*", "*"}, {".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."}, {".", ".", ".", "*", ".", ".", ".", ".", ".", ".", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", "*", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", ".", "*"}} /. {"." -> 0, "*" -> 1}]


The white squares correspond to the cells having the value, 1.

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.)

MorphologicalComponents replaces 1s with an integer corresponding to the cluster number of each cell.

Max returns the largest cluster number.

Displaying the Islands

Colorize will color each island uniquely.

• 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? Commented Apr 6, 2013 at 14:41
• I have V9, @Mr.Wizard is right. 46 characters is the right number. Commented Dec 28, 2013 at 21:19
• @Mr.Wizard The replacement is carried out before the application of MorphologicalComponents. Must be a precedence thing. Commented Dec 28, 2013 at 22:50
• Hi @DavidCarraher, my point is not about "->" but that the expression Max@MorphologicalComponents@d/.{"."->0,"*"->1} do not work, what make sense is Max@MorphologicalComponents[d /. {"." -> 0, "*" -> 1}], so you have one more character. Commented Dec 29, 2013 at 11:42

## 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! Commented Aug 14, 2012 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);}  # Python 2, 223 203 Bytes Thank you to Step Hen and Arnold Palmer for shaving off 20 characters of spaces and unnecessary parenthesis! s=input() c=[(s.index(l),i)for l in s for i,v in enumerate(l)if'*'==v] n=[set([d for d in c if-2<d[0]-v[0]<2and-2<d[1]-v[1]<2])for v in c] f=lambda x,p=0:p if x&n[p]else f(x,p+1) print len(set(map(f,n)))  I thought that using list comprehensions might decrease the number of bytes, but it didn't provide any significant improvement. Try it here. I keep trying to trim it around the n (neighbors) list, but I haven't been successful. Maybe someone else will have some ideas for that section. • Welcome to PPCG! Here's 217 bytes by removing some spaces. The Python parser is really lenient :P Commented Aug 9, 2017 at 2:04 • You have more whitespace than needed. Remove the spaces between (s.index(l),i) and for, enumerate(l) and if, -v[0])<2 and and, p=0: and p, and bool(x&n[p]) and else. You also have more parenthesis than needed in your print statement, since you have 2 groups surrounding set. Edit: Beat by StepHen cause doing stuff on mobile isn't ideal. Commented Aug 9, 2017 at 2:07 • 203 bytes combining @StepHen's and my suggestions, plus changing the conditionals a bit. Commented Aug 9, 2017 at 2:14 • Thank you both for the help! Python's leniency keeps surprising me : ) Commented Aug 9, 2017 at 14:33 # Perl 5, 100 bytes 98 bytes of code + 2 bytes for -p0 flags. /.*/;$@="@+"-1;$~="(.?.?.{$@})?";(s/X$~\*/X$1X/s||s/\*$~X/X$1X/s)&&redo;s/\*/X/&&++$\&&redo}{$\|=0


Try it online!

An adaptation (or rather a simplification) of my answer to the challenge How Many Holes?. You can find explanations of how this code works on this other answer (it's a bit long to explain, so I prefer not to retype the entire explanations).

## Python 2, 233 bytes

Too long, compared to other answers. Port of my answer to this question.
Try it online

A=input()
c=0
X=len(A[0])-1
Y=len(A)-1
def C(T):
x,y=T
if A[y][x]<'.':A[y][x]='.';map(C,zip([x]*3+[min(x+1,X)]*3+[max(x-1,0)]*3,[y,min(y+1,Y),max(y-1,0)]*3))
while'*'in sum(A,[]):i=sum(A,[]).index('*');c+=1;C((i%-~X,i/-~X))
print c


## JavaScript, 158 bytes

function f(s){w=s.search('\n');t=s.replace(RegExp('([*@])([^]{'+w+','+(w+2)+'})?(?!\\1)[*@]'),'@$2@');return t!=s?f(t):/\*/.test(s)?f(s.replace('*','@'))+1:0}  Noncompeting ES6 answer (language postdates challenge) for 132 bytes: f=s=>s!=(s=s.replace(RegExp(([*@])([^]{${w=s.search
},${w+2}})?(?!\\1)[*@]),@$2@))?f(s):/\*/.test(s)?f(s.replace(*,@))+1:0


Port of my answer to How Many Holes? (yes I'm jumping on the bandwagon, now that I've seen two other people port their answers).

# Python 2, 225 bytes

g=map(list,input())
q,w,t,r=len(g),len(g[0]),0,range
def l(i,j):
if 0<=i<q and 0<=j<w and g[i][j]=='1':g[i][j]=0;l(i+1,j);l(i-1,j);l(i,j+1);l(i,j-1)
return 1
print sum(l(i,j)if g[i][j]=='1'else 0 for j in r(w)for i in r(q))


Try it online!

• -1 bytes, suggested by an anonymous user Commented Jan 18, 2021 at 20:59

# Python 3, 133 bytes

I,*g=input(),
w=i=I.find(',')
for c in I:
q={k for k in g if{i-1,i,i+1,i+w}&{*k}};i+=1
if','>c:g={*g,sum(q,(i+w,))}-q
print(len(g))


Try it online!

Takes a comma-separated grid on a single line as input