lake_area_problem.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3ZLqMhUapp4O"
      },
      "source": [
        "# Exercício Python no notebook Google Colab"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2RVMzCvAyQtB"
      },
      "source": [
        "ATENÇÃO: Primeiro copie esse notebook para sua área, resolva-o e retorne o seu link no formulário, não esquecendo de compartilhar o seu notebook Colab com qualquer pessoa que tenha acesso ao link."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oiBYTaycO4AS"
      },
      "source": [
        "## Preencha seu nome e email:\n",
        "\n",
        "Nome: Filipe de Castro Borges da Silveira\n",
        "\n",
        "Email: filipebcs8@gmail.com"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0Zj3u99uRFqI"
      },
      "source": [
        "## Enunciado\n",
        "Você receberá uma matriz (uma lista de listas) de, possivelmente, altura e largura diferentes contendo apenas `0`s e `1`s. Cada `0` representa terra e cada `1` representa água. Uma lagoa é composta por qualquer número de `1`s verticalmente ou horizontalmente adjacentes (mas não diagonalmente adjacentes). O número de `1`s adjacentes determina a área da lagoa.\n",
        "\n",
        "Escreva uma função que retorna uma lista com as áreas das lagoas contidas na matriz em ordem crescente."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MxEtZhVS1Q"
      },
      "source": [
        "Um exemplo é:\n",
        "\n",
        "Dada a matriz\n",
        "\n",
        "```\n",
        "matrix = [\n",
        "    [1, 1, 0, 1, 0],\n",
        "    [1, 0, 1, 0, 0],\n",
        "    [0, 0, 1, 0, 1],\n",
        "    [1, 0, 1, 0, 1],\n",
        "    [1, 0, 1, 1, 0]\n",
        "]\n",
        "```\n",
        "A resposta esperada é uma lista com os tamanhos dos rios\n",
        "\n",
        "```\n",
        "sizes = [1, 2, 2, 3, 5]\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JH3Ixn1AUu8O"
      },
      "source": [
        "Os critérios de avaliação são legibilidade do código e corretude do algoritmo, outros aspectos como performance e técnicas de programação não serão avaliados."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JgW3yfL5Sux1"
      },
      "source": [
        "Você pode usar qualquer função built-in do python, pode utilizar funções auxiliares, criar classes e etc. Deve-se apenas manter a assinatura da função `lake_areas`. Na dúvida, submeter sua melhor tentativa documentando seu raciocínio é melhor do que não submeter nada :)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "ZqixjszATBjE"
      },
      "outputs": [],
      "source": [
        "from typing import List\n",
        "\n",
        "def lake_areas(matrix: List[List[int]]) -> List[int]:\n",
        "    # Write your code here.\n",
        "    pass"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "np03iS0c0pyI"
      },
      "outputs": [],
      "source": [
        "matrix = [\n",
        "    [1, 1, 0, 1, 0],\n",
        "    [1, 0, 1, 0, 0],\n",
        "    [0, 0, 1, 0, 1],\n",
        "    [1, 0, 1, 0, 1],\n",
        "    [1, 0, 1, 1, 0]\n",
        "]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "a2ACOVHL1BvQ",
        "outputId": "02d01684-b184-475d-b485-7af9a3d7818c"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[[1, 1, 0, 1, 0],\n",
              " [1, 0, 1, 0, 0],\n",
              " [0, 0, 1, 0, 1],\n",
              " [1, 0, 1, 0, 1],\n",
              " [1, 0, 1, 1, 0]]"
            ]
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "matrix"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 30,
      "metadata": {
        "id": "VFDeOz_P1VTa"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "5 \n",
            "\n",
            "5 \n",
            "\n",
            "5 \n",
            "\n",
            "5 \n",
            "\n",
            "5 \n",
            "\n",
            "5 \n",
            "\n",
            "[[True, True, False, False, False, True], [False, True, False, False, True, False], [True, False, False, True, True, True], [False, False, False, False, False, False], [True, False, True, False, True, True], [True, False, False, True, False, True]]\n",
            "O número de lagos na área é: 8\n"
          ]
        }
      ],
      "source": [
        "\n",
        "# Classe que conta o número de lagos em uma determinada área\n",
        "class Area:\n",
        "\n",
        "    # Inicilializando as variáveis\n",
        "    def __init__(self, lin, col, area):\n",
        "        self.LIN = lin\n",
        "        self.COL = col\n",
        "        self.area = area\n",
        "        \n",
        "    # Função que verifica se os valores delinha e coluna são válidos para a posição e se essa posição já foi visitada\n",
        "    def dentroLimites(self, i, j, visitado):\n",
        "        # Linha e coluna não menores do que zero e não maiores do que o limite da área e se essa posição já foi\n",
        "        # visitada\n",
        "        return (i >= 0 and i < self.LIN and j >= 0 and j < self.COL and not visitado[i][j] and self.area[i][j])\n",
        "    \n",
        "    # Função que implementa o algoritmo 'depth-first search' para uma matriz 2D de booleanos. Apenas os 2 vizinhos\n",
        "    # na horizontal e os 2 vizinhos na vertical são considerados\n",
        "    def DFS(self, i, j, visitado):\n",
        "        \n",
        "        # Listas com os deslocamentos necessários para os 4 vizinhos considerados: 2 verticais e 2 horizontais\n",
        "        nLinha = [-1,  0, 0,  1];\n",
        "        nColuna = [ 0, -1, 1,  0];\n",
        "        \n",
        "        # Marcar posição como visitada\n",
        "        visitado[i][j] = True\n",
        "        \n",
        "        # Aplicar o algoritmo 'depth-first' search nos vizinhos da horizontal e da vertical\n",
        "        for k in range(4):\n",
        "            if self.dentroLimites(i + nLinha[k], j + nColuna[k], visitado):\n",
        "                self.DFS(i + nLinha[k], j + nColuna[k], visitado)\n",
        "\n",
        "    # Função que retorna o número de lagos em uma determinada área\n",
        "    def contarLagos(self):\n",
        "        # Criar um array booleano que registra as posições que foram visitadas (inicialmente, todas as células estão\n",
        "        # marcadas como NÃO-visitadas)\n",
        "        visitado = [[False for j in range(self.COL)]for i in range(self.LIN)]\n",
        "\n",
        "        # Inicializar o contador em zero e percorrer as posições da matriz\n",
        "        nLagos = 0\n",
        "        for i in range(self.LIN):\n",
        "            for j in range(self.COL):\n",
        "                # Checar se a posição contém o valor 1 e se ela ainda não foi visitada. Se ambas as condições forem\n",
        "                # cumpridas, conta-se mais um lago\n",
        "                if visitado[i][j] == False and self.area[i][j] == 1:\n",
        "                    # Visitar todas as células no lago e incrementar o contador de lagos\n",
        "                    self.DFS(i, j, visitado)\n",
        "                    nLagos += 1\n",
        "            print(j)\n",
        "\n",
        "        print(visitado)\n",
        "        return nLagos\n",
        "\n",
        "# Definir a área que será analisada onde:\n",
        "# - 0 representa terra\n",
        "# - 1 representa lago\n",
        "area = [\n",
        "    [1, 1, 0, 0, 0, 1],\n",
        "    [0, 1, 0, 0, 1, 0],\n",
        "    [1, 0, 0, 1, 1, 1],\n",
        "    [0, 0, 0, 0, 0, 0],\n",
        "    [1, 0, 1, 0, 1, 1],\n",
        "    [1, 0, 0, 1, 0, 1]\n",
        "]\n",
        "\n",
        "# Extrair o número de linha e colunas na matriz que representa a área\n",
        "lin = len(area)\n",
        "col = len(area[0])\n",
        "\n",
        "# Chamar a classe 'Area'\n",
        "area = Area(lin, col, area)\n",
        "\n",
        "# Identificar o número de lagos na área designada\n",
        "print (\"O número de lagos na área é:\", area.contarLagos())"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 101,
      "metadata": {},
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "\n",
        "area = [\n",
        "    [1, 1, 0, 0, 0, 1],\n",
        "    [0, 1, 0, 0, 1, 0],\n",
        "    [1, 0, 0, 1, 1, 1],\n",
        "    [0, 0, 0, 0, 0, 0],\n",
        "    [1, 0, 1, 0, 1, 1]\n",
        "]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 133,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1 1\n",
            "[[1, 1, 0, 0, 0, 1], [0, 1, 0, 0, 1, 0], [1, 0, 0, 1, 1, 1], [0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 1, 1]]\n",
            "[[ 1.  1.  0.  0.  0.  2.]\n",
            " [ 0.  3.  0.  0.  4.  0.]\n",
            " [ 5.  0.  0.  6.  7.  7.]\n",
            " [ 0.  0.  0.  0.  0.  0.]\n",
            " [ 8.  0.  9.  0. 10. 10.]]\n"
          ]
        }
      ],
      "source": [
        "numberingIslands = np.zeros(np.shape(area))\n",
        "labelCont = 1\n",
        "labels = []\n",
        "\n",
        "for i in range(len(area)):\n",
        "    \n",
        "    for j in range(len(area[0])):\n",
        "    \n",
        "        if area[i][j] == 1:\n",
        "    \n",
        "            if i == 0 and j == 0:\n",
        "                numberingIslands[i][j] = labelCont\n",
        "                labels.append(labelCont)\n",
        "                labelCont += 1\n",
        "        \n",
        "            if i == 0 and j > 0:\n",
        "                \n",
        "                if j == len(area[0]):\n",
        "                    continue\n",
        "        \n",
        "                if area[i][j-1] == 1:\n",
        "                    numberingIslands[i][j] = numberingIslands[i][j-1]\n",
        "        \n",
        "                if not area[i][j-1] == 1:\n",
        "                    numberingIslands[i][j] = labelCont\n",
        "                    labels.append(labelCont)\n",
        "                    labelCont += 1\n",
        "        \n",
        "            if i > 0 and j == 0:\n",
        "                \n",
        "                if area[i-1][j] == 1:\n",
        "                    numberingIslands[i][j] = numberingIslands[i-1][j]\n",
        "                \n",
        "                else:\n",
        "                    numberingIslands[i][j] =  labelCont\n",
        "                    labels.append(labelCont)\n",
        "                    labelCont += 1\n",
        "        \n",
        "            if i > 0 and j > 0:\n",
        "        \n",
        "                if area[i-1][j] == 1 and area[i][j-1] == 1:\n",
        "                    numberingIslands[i][j] = numberingIslands[i-1][j]\n",
        "        \n",
        "                if area[i-1][j] == 1 and area[i][j-1] == 0:\n",
        "                    numberingIslands[i][j] = numberingIslands[i-1][j]\n",
        "        \n",
        "                if area[i-1][j] == 0 and area[i][j-1] == 1:\n",
        "                    numberingIslands[i][j] = numberingIslands[i][j-1]\n",
        "                    \n",
        "                else:\n",
        "                    numberingIslands[i][j] = labelCont\n",
        "                    labels.append(labelCont)\n",
        "                    labelCont += 1\n",
        "                    \n",
        "                \n",
        "        \n",
        "        else:\n",
        "            continue\n",
        "            \n",
        "    #if i == 2:\n",
        "    #    break\n",
        "        \n",
        "print(area)\n",
        "print(numberingIslands)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 118,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "execution_count": 118,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "area"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 76,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "5\n",
            "6\n"
          ]
        }
      ],
      "source": [
        "print(len(area))\n",
        "print(len(area[0]))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "name": "lake_area_problem.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.10.2"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}