lake_area_problem._1ipynb.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": 3,
      "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": 4,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "a2ACOVHL1BvQ",
        "outputId": "02d01684-b184-475d-b485-7af9a3d7818c"
      },
      "outputs": [
        {
          "ename": "NameError",
          "evalue": "name 'np' is not defined",
          "output_type": "error",
          "traceback": [
            "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[1;32md:\\OneDrive\\Documentos\\pythonworkspace\\src\\github.com\\problems\\lake_area_problem._1ipynb.ipynb Cell 9'\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/OneDrive/Documentos/pythonworkspace/src/github.com/problems/lake_area_problem._1ipynb.ipynb#ch0000008?line=0'>1</a>\u001b[0m matrix \u001b[39m=\u001b[39m [\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/OneDrive/Documentos/pythonworkspace/src/github.com/problems/lake_area_problem._1ipynb.ipynb#ch0000008?line=1'>2</a>\u001b[0m     [\u001b[39m1\u001b[39m, \u001b[39m1\u001b[39m, \u001b[39m0\u001b[39m, \u001b[39m1\u001b[39m, \u001b[39m0\u001b[39m],\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/OneDrive/Documentos/pythonworkspace/src/github.com/problems/lake_area_problem._1ipynb.ipynb#ch0000008?line=2'>3</a>\u001b[0m     [\u001b[39m1\u001b[39m, \u001b[39m0\u001b[39m, \u001b[39m1\u001b[39m, \u001b[39m0\u001b[39m, \u001b[39m0\u001b[39m],\n\u001b[1;32m   (...)\u001b[0m\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/OneDrive/Documentos/pythonworkspace/src/github.com/problems/lake_area_problem._1ipynb.ipynb#ch0000008?line=5'>6</a>\u001b[0m     [\u001b[39m1\u001b[39m, \u001b[39m0\u001b[39m, \u001b[39m1\u001b[39m, \u001b[39m1\u001b[39m, \u001b[39m0\u001b[39m]\n\u001b[0;32m      <a href='vscode-notebook-cell:/d%3A/OneDrive/Documentos/pythonworkspace/src/github.com/problems/lake_area_problem._1ipynb.ipynb#ch0000008?line=6'>7</a>\u001b[0m ]\n\u001b[1;32m----> <a href='vscode-notebook-cell:/d%3A/OneDrive/Documentos/pythonworkspace/src/github.com/problems/lake_area_problem._1ipynb.ipynb#ch0000008?line=7'>8</a>\u001b[0m matrix \u001b[39m=\u001b[39m np\u001b[39m.\u001b[39marray(matrix)\n",
            "\u001b[1;31mNameError\u001b[0m: name 'np' is not defined"
          ]
        }
      ],
      "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",
        "]\n",
        "matrix = np.array(matrix)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "matrix = [\n",
        "    [1, 1, 0, 1, 0, 0],\n",
        "    [1, 0, 1, 0, 0, 1],\n",
        "    [0, 1, 1, 0, 1, 0],\n",
        "    [1, 0, 1, 0, 1, 0],\n",
        "    [1, 0, 1, 1, 0, 1]\n",
        "]\n",
        "matrix = np.array(matrix)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "VFDeOz_P1VTa"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "5\n",
            "5\n",
            "5\n",
            "5\n",
            "5\n",
            "5\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": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Inicilizar as biliotecas\n",
        "import numpy as np"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Inicializar a matriz com as posições dos rios\n",
        "area = [\n",
        "    [0, 1, 1, 0, 1, 0],\n",
        "    [0, 0, 0, 1, 0, 1],\n",
        "    [1, 1, 1, 0, 1, 1],\n",
        "    [0, 0, 0, 0, 1, 0],\n",
        "    [1, 1, 0, 0, 1, 1],\n",
        "    [0, 1, 1, 0, 0, 1]\n",
        "]\n",
        "area = np.array(area)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "area = np.array(area)\n",
        "cluster = np.zeros(np.shape(area))\n",
        "label = 0"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "for i in range(len(area)):\n",
        "    \n",
        "    for j in range(len(area[0])):\n",
        "        \n",
        "        # Pegar as posições em que foi identificado um lago\n",
        "        if area[i][j] == 1:\n",
        "            \n",
        "            # Análise Linha 1, Coluna 1\n",
        "            if i == 0 and j == 0:\n",
        "                cluster[i][j] = label\n",
        "\n",
        "            # Análise Linha 1, Coluna 2 em diante\n",
        "            elif i == 0 and j != 0:\n",
        "                \n",
        "                if area[i][j-1] == 1:\n",
        "                    cluster[i][j] = cluster[i][j-1]\n",
        "                else:\n",
        "                    label += 1\n",
        "                    cluster[i][j] = label\n",
        "            \n",
        "            # Análise Linha 2 em diante, Coluna 1\n",
        "            elif i != 0 and j == 0:\n",
        "                \n",
        "                if area[i-1][j] == 1:\n",
        "                    cluster[i][j] = cluster[i-1][j]\n",
        "                    \n",
        "                else:\n",
        "                    label += 1\n",
        "                    cluster[i][j] = label\n",
        "            \n",
        "            # Análise Linha 2 em diante, Coluna 2 em diante        \n",
        "            else:\n",
        "                \n",
        "                if area[i-1][j] == 1:\n",
        "                    cluster[i][j] = cluster[i-1][j]\n",
        "                \n",
        "                elif area[i][j-1] == 1:\n",
        "                    cluster[i][j] = cluster[i][j-1]\n",
        "                \n",
        "                else:\n",
        "                    label += 1\n",
        "                    cluster[i][j] = label"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[0., 1., 1., 0., 2., 0.],\n",
              "       [0., 0., 0., 3., 0., 4.],\n",
              "       [5., 5., 5., 0., 6., 4.],\n",
              "       [0., 0., 0., 0., 6., 0.],\n",
              "       [7., 7., 0., 0., 6., 6.],\n",
              "       [0., 7., 7., 0., 0., 6.]])"
            ]
          },
          "execution_count": 516,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "cluster"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Percorrer a matriz dos lagos classificando aqueles que possuem adjacências verticais e horizontais\n",
        "for i in range(len(cluster)-1):\n",
        "    \n",
        "    for j in range(len(cluster[0])-1):\n",
        "        \n",
        "        if cluster[i][j] != 0:\n",
        "            \n",
        "            if (cluster[i][j] != cluster[i][j+1]) and cluster[i][j+1] != 0:\n",
        "                minimo = min(cluster[i][j], cluster[i][j+1])\n",
        "                maximo = max(cluster[i][j], cluster[i][j+1])\n",
        "                cluster[i][j] = minimo\n",
        "                cluster[i][j+1] = minimo\n",
        "\n",
        "for i in range(int(maximo), int(np.amax(cluster))):\n",
        "    cluster = np.where(cluster == i+1, i, cluster)\n",
        "                "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "val_unique, counts = np.unique(cluster, return_counts=True)\n",
        "sizes = np.sort(counts[1:]).tolist()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[1, 1, 2, 3, 3, 8]"
            ]
          },
          "execution_count": 519,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "sizes"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[0., 1., 1., 0., 2., 0.],\n",
              "       [0., 0., 0., 3., 0., 4.],\n",
              "       [5., 5., 5., 0., 4., 4.],\n",
              "       [0., 0., 0., 0., 6., 0.],\n",
              "       [6., 6., 0., 0., 6., 6.],\n",
              "       [0., 6., 6., 0., 0., 6.]])"
            ]
          },
          "execution_count": 520,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "cluster"
      ]
    }
  ],
  "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
}