본문 바로가기

Python_Matter/Solve

Python Learn the basics Quiz 97

반응형

Q>

The Robots have found a chain of islands in the middle of the Ocean.

(로봇은 대양의 한가운데에 일련의 섬들을 발견했습니다.)

They would like to explore these islands and have asked for your help calculating the areas of each island.

(그들은이 섬을 탐험하고 각 섬의 면적을 계산하는 데 도움을 요청했습니다.)

They have given you a map of the territory.

(그들은 당신에게 영토지도를주었습니다.)

The map is a 2D array, where 0 is water, 1 is land. An island is a group of land cells surround by water.

(지도는 2D 배열이며 0은 물, 1은 땅입니다. 섬은 물로 둘러싸인 땅 세포 그룹입니다.)

Cells are connected by their edges and corners.

(세포는 모서리와 모서리로 연결됩니다.)

You should calculate the areas for each of the islands and return a list of sizes (quantity of cells) in ascending order.

(각 섬의 면적을 계산하고 크기 목록 (셀 수량)을 오름차순으로 반환해야합니다.)

All of the cells outside the map are considered to be water.

(지도 외부의 모든 셀은 물로 간주됩니다.)

 

Input: A map as a list of lists with 1 or 0.

        (1 또는 0이있는 목록의지도.)

 

Output: The sizes of island as a list of integers.

           (섬의 크기는 정수 목록입니다.)

 

Example:

checkio([
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]]) == [1, 3]
checkio([
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 0, 0]]) == [5]
checkio([
    [0, 0, 0, 0, 0, 0],
    [1, 0, 0, 1, 1, 1],
    [1, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0]]) == [2, 3, 3, 4]

 

How it is used: This task is an example of a disjoint-set data structure.

                     (이 작업은 분리 된 데이터 구조의 예입니다.)

                     Disjoint-set data structures model the partitioning of a set;

                     (불연속 집합 데이터 구조는 집합의 분할을 모델링합니다.)

                     for example, it helps with keeping track of the connected components in an undirected graph

                     (예를 들어, 연결되지 않은 그래프에서 연결된 구성 요소를 추적하는 데 도움이됩니다.  )                    

                     (networks).

 

Precondition: 0 < len(land_map) < 10

                   all(len(land_map[0]) == len(row) for row in land_map)

                   any(any(row) for row in land_map)

 

A>

# itertools :  자신만의 반복자를 만드는 모듈
import itertools

def checkio1(x, y, water, land):
    a = [x + i for i in range(-1, 2) if x + i in range(0, water)]
    b = [y + i for i in range(-1, 2) if y + i in range(0, land)]
    # itertools.product : 곱집합
    return list(itertools.product(a, b))

def checkio(land_map):
    water = len(land_map)
    land = len(land_map[0])
    u = [(x, y) for x in range(water) for y in range(land)]
    c = []

    while u:
        x, y = u.pop(0)
        if land_map[x][y]:
            n = 1
            k = checkio1(x, y, water, land)
            while k:
                i = k.pop(0)
                if i in u:
                    u.remove(i)
                    if land_map[i[0]][i[1]]:
                        n = n + 1
                        k.extend(checkio1(i[0], i[1], water, land))
            c.append(n)
    c.sort()

    return c

#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    print("Example:")
    print(checkio([[0, 0, 0, 0, 0],
                   [0, 0, 1, 1, 0],
                   [0, 0, 0, 1, 0],
                   [0, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0]]))

    assert checkio([[0, 0, 0, 0, 0],
                    [0, 0, 1, 1, 0],
                    [0, 0, 0, 1, 0],
                    [0, 1, 0, 0, 0],
                    [0, 0, 0, 0, 0]]) == [1, 3], "1st example"
    assert checkio([[0, 0, 0, 0, 0],
                    [0, 0, 1, 1, 0],
                    [0, 0, 0, 1, 0],
                    [0, 1, 1, 0, 0]]) == [5], "2nd example"
    assert checkio([[0, 0, 0, 0, 0, 0],
                    [1, 0, 0, 1, 1, 1],
                    [1, 0, 0, 0, 0, 0],
                    [0, 0, 1, 1, 1, 0],
                    [0, 0, 0, 0, 0, 0],
                    [0, 1, 1, 1, 1, 0],
                    [0, 0, 0, 0, 0, 0]]) == [2, 3, 3, 4], "3rd example"
    print("Coding complete? Click 'Check' to earn cool rewards!")

 

O>

Example:
[1, 3]
Coding complete? Click 'Check' to earn cool rewards!

Process finished with exit code 0

 

S>

https://py.checkio.org

반응형

'Python_Matter > Solve' 카테고리의 다른 글

Python Learn the basics Quiz 99  (0) 2019.06.25
Python Learn the basics Quiz 98  (0) 2019.06.25
Python Learn the basics Quiz 97  (0) 2019.06.24
Python Learn the basics Quiz 96  (0) 2019.06.24
Python Learn the basics Quiz 95  (0) 2019.06.24
Python Learn the basics Quiz 94  (0) 2019.06.24