lake_area_problem_4.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": 1,
      "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": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "a2ACOVHL1BvQ",
        "outputId": "02d01684-b184-475d-b485-7af9a3d7818c"
      },
      "outputs": [],
      "source": [
        "# Importar bibliotecas relevantes\n",
        "import numpy as np\n",
        "import itertools\n",
        "import pandas as pd"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Definir a matriz de lagos original\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",
        "matrix = np.array(matrix)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Definir a matriz de lagos de teste\n",
        "matrix_2 = [\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_2 = np.array(matrix_2)\n",
        "#lastRow = len(matrix_2) - 1\n",
        "#lastColumn = len(matrix_2[0]) - 1\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Inicializar os rótulos dos grupos\n",
        "grupo = 1\n",
        "\n",
        "# Inicializar arrays vazios\n",
        "colunas = []\n",
        "linhas = []\n",
        "posicoes = []"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Identificar as respectivas linhas e colunas de cada entrada '1' na matriz\n",
        "for i in range(matrix_2.shape[0]):\n",
        "    \n",
        "    for j in range(matrix_2.shape[1]):\n",
        "    \n",
        "        if matrix_2[i][j] == 1:\n",
        "            #entradas.append([i, j])\n",
        "            linhas.append(i)\n",
        "            colunas.append(j)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[0, 0],\n",
              "       [0, 1],\n",
              "       [0, 3],\n",
              "       [1, 0],\n",
              "       [1, 2],\n",
              "       [1, 5],\n",
              "       [2, 1],\n",
              "       [2, 2],\n",
              "       [2, 4],\n",
              "       [3, 0],\n",
              "       [3, 2],\n",
              "       [3, 4],\n",
              "       [4, 0],\n",
              "       [4, 2],\n",
              "       [4, 3],\n",
              "       [4, 5]])"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# Monta um array com as posições das entradas '1' no formato \"['linha', 'coluna']\"\n",
        "posicoes = np.column_stack((np.array(linhas), np.array(colunas)))\n",
        "posicoes"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])"
            ]
          },
          "execution_count": 8,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "posicoesGrupo = np.zeros(len(posicoes))\n",
        "posicoesGrupo[0] = 1\n",
        "posicoesGrupo"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0\n",
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n",
            "6\n",
            "7\n",
            "8\n",
            "9\n",
            "10\n",
            "11\n",
            "12\n",
            "13\n",
            "14\n",
            "15\n"
          ]
        }
      ],
      "source": [
        "# Montar matriz cujas colunas 0 e 1 são o ponto de referência e coluna 2 e 3 são o ponto comparador\n",
        "for referencia in range(posicoes.shape[0]):\n",
        "    print(referencia)\n",
        "    \n",
        "    for comparador in range(referencia+1, posicoes.shape[0]):\n",
        "        \n",
        "        if posicoesGrupo[referencia] == 0:\n",
        "            posicoesGrupo[referencia] = max(posicoesGrupo)+1\n",
        "        \n",
        "        # Calcular a distância entre o ponto de referência e o ponto comparador\n",
        "        posicaoRelativa = np.sum(abs(posicoes[referencia] - posicoes[comparador]))\n",
        "        \n",
        "        if posicaoRelativa <= 1:\n",
        "            \n",
        "            if posicoesGrupo[comparador] == 0:\n",
        "                posicoesGrupo[comparador] = posicoesGrupo[referencia]\n",
        "                \n",
        "            if posicoesGrupo[comparador] != posicoesGrupo[referencia]:\n",
        "                posicoesGrupo[referencia] = min(posicoesGrupo[referencia], posicoesGrupo[comparador])\n",
        "        \n",
        "    if referencia == len(posicoesGrupo)-1:\n",
        "        posicoesGrupo[-1] = max(posicoesGrupo)+1"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([1., 1., 2., 1., 3., 4., 3., 3., 5., 6., 3., 5., 6., 3., 3., 7.])"
            ]
          },
          "execution_count": 10,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "posicoesGrupo"
      ]
    }
  ],
  "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
}