count-island.py

# -*- coding: utf-8 -*-
# https://codeiq.jp/ace/joboffer_apli/q377

import unittest

N = 6

def normalize(s, c):
    if c == u'○':
        s.append(-1)
    elif c == u'●':
        s.append(0)
    return s

def explore(m, i, v):
    m[i] = v
    x = i % N
    y = i // N
    if 0 < x and m[i - 1] == 0:
        explore(m, i - 1, v)
    if x < N - 1 and m[i + 1] == 0:
        explore(m, i + 1, v)
    if 0 < y and m[i - N] == 0:
        explore(m, i - N, v)
    if y < N - 1 and m[i + N] == 0:
        explore(m, i + N, v)

def count_island(field):
    m = reduce(normalize, field, [])
    if len(m) <> N * N:
        raise Exception('field size must be %dx%d' % (N, N))

    num_islands = 0
    while 0 in m:
        i = m.index(0)
        num_islands += 1
        explore(m, i, num_islands)
    return num_islands

class TestCountIsland(unittest.TestCase):
    def test(self):
        field = u'''
○○○○○○
○●●○○○
○○○○○○
○○○○●○
○○○●○○
○○○○○○
'''
        self.assertEqual(3, count_island(field))

        field = u'''
●○○○○○
○●○○○○
○○●○○○
○○○●○○
○○○○●○
○○○○○●
'''
        self.assertEqual(6, count_island(field))

        field = u'''
●●●●●●
○○○○○●
●●●●○●
●○○●○●
●○○○○●
●●●●●●
'''
        self.assertEqual(1, count_island(field))

if __name__ == '__main__':
    unittest.main()