2_Buscas_Sem_Informação.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Semana_2_BuscasSemInformacao.ipynb",
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/franconoronha/treinamento-h2ia/blob/main/2_Buscas_Sem_Informa%C3%A7%C3%A3o.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "21uUELma0562"
      },
      "source": [
        "# O Problema\n",
        "Sliding Puzzle - Bloco Deslizante"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 218
        },
        "id": "duRbJW3rz01L",
        "outputId": "e1049773-9cf4-4b39-e026-e220c566311f"
      },
      "source": [
        "# !wget -qq https://miro.medium.com/max/700/1*W7jg4GmEjGBypd9WPktasQ.gif\n",
        "from IPython.display import Image\n",
        "Image(url='https://miro.medium.com/max/700/1*W7jg4GmEjGBypd9WPktasQ.gif',width=200)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<img src=\"https://miro.medium.com/max/700/1*W7jg4GmEjGBypd9WPktasQ.gif\" width=\"200\"/>"
            ],
            "text/plain": [
              "<IPython.core.display.Image object>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "f6TPxqB-1Cwx"
      },
      "source": [
        "# Resolver o quebra-cabeças usando Buscas"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Acabei por não utilizar o numpy, pois na minha cabeça fazia mais sentido representar os estados utilizando strings, já que pelos meus testes ocuparia menos memória. Porém não sei se vale a pena, visto que os arrays do numpy foram feitos para ter boa perfomance, e as strings do python são imutáveis e por isso dificultam um pouquinho a manipulação (ou seja provavelmente mais lento), no fim acho que o ganho na memória não foi tão significativo, quem sabe para tamanhos maiores de quebra-cabeças. \n",
        "\n",
        "Também optei por fazer tudo de forma iterativa e não recursiva, o python não curtiu muito a recursão, mas não sei se isso é algo que deveria ignorar no futuro.\n",
        "\n",
        "Comparação de memória:"
      ],
      "metadata": {
        "id": "8pj_2nyZcHdh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "from sys import getsizeof\n",
        "string = \"123456789\"\n",
        "np_array = np.array([[1,2,3],[4,5,6],[7,8,9]])\n",
        "\n",
        "print(\"Tamanho de um string de 9 char: {} bytes\".format(getsizeof(string)))\n",
        "print(\"Tamanho de uma matriz numpy 3x3: {} bytes\".format(getsizeof(np_array)))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "q6lLxHLpXdXh",
        "outputId": "66fbe55e-c6c1-4547-d91d-41d504337889"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Tamanho de um string de 9 char: 58 bytes\n",
            "Tamanho de uma matriz numpy 3x3: 192 bytes\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Importação de bibliotecas, definição de funções auxiliares e geração de um puzzle \"aleatório\"."
      ],
      "metadata": {
        "id": "gqGs1ZAgdBFt"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import deque\n",
        "from random import seed, randint\n",
        " \n",
        "# Comentar a seed para ter um puzzle aleatório\n",
        "seed(101)\n",
        "\n",
        "class Tree:\n",
        "    def __init__(self, data, parent, move):\n",
        "        self.children = []\n",
        "        self.data = data\n",
        "        self.parent = parent\n",
        "        self.move = move\n",
        "\n",
        "\"\"\" Representando o puzzle como uma string\n",
        "* representa o espaço vazio\n",
        "Movimentos possíveis\n",
        "(considerando que quem se move é o * e ele troca de lugar com a peça pra onde tá indo)\n",
        "- pra cima: -3 posições\n",
        "- pra baixo: +3 \n",
        "- pra direita: +1\n",
        "- pra esquerda: -1\n",
        "\n",
        "1.só é possível se (pos_atual + movimento) for maior ou igual a 0 e menor que len(puzzle)  \n",
        "2.não é possível mexer para esquerda na coluna da esquerda (posições 0, 3, 6 % 3 == 0)\n",
        "3.não é possível mexer para direita na coluna da direita (posições 2, 5, 8 % 3 == 2)\n",
        "\"\"\"\n",
        "\n",
        "def gerar_puzzle():\n",
        "  puzzle = \"\"\n",
        "  numeros = [\"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\"]\n",
        "  for x in range(0, len(numeros)):\n",
        "    char = numeros.pop(randint(0, len(numeros) - 1))\n",
        "    puzzle += char\n",
        "  puzzle += '*'\n",
        "  return puzzle\n",
        "\n",
        "def get_movimentos_legais(puzzle):\n",
        "  ind = puzzle.find(\"*\")\n",
        "  moves = []\n",
        "  for x in [3, -3, 1, -1]:\n",
        "    if x == -1 and ind % 3 == 0:\n",
        "      continue\n",
        "    elif x == 1 and ind % 3 == 2:\n",
        "      continue\n",
        "    if((ind + x) < len(puzzle) and (ind + x) >= 0):\n",
        "      moves.append(x)\n",
        "  return moves\n",
        "\n",
        "def swap(puzzle, move):\n",
        "  index = puzzle.find('*')\n",
        "  move += index\n",
        "  p = list(puzzle)\n",
        "  p[index], p[move] = p[move], p[index]\n",
        "  return ''.join(p)\n",
        "\n",
        "def aplica_resultado(puzzle, resultado):\n",
        "  if resultado == -1:\n",
        "    return puzzle\n",
        "  for move in resultado:\n",
        "    puzzle = swap(puzzle, move)\n",
        "  return puzzle\n",
        "  \n",
        "def nodos_arvore(arvore):\n",
        "  contador = 0\n",
        "  fila = deque()\n",
        "  fila.append(arvore)\n",
        "  while len(fila) > 0:\n",
        "    atual = fila.popleft()\n",
        "    fila += atual.children\n",
        "    contador += 1\n",
        "  return contador\n",
        "\n",
        "solucao = \"12345678*\"\n",
        "puzzle = gerar_puzzle()\n",
        "puzzle = \"8672543*1\"\n",
        "print(\"Puzzle gerado: {}\".format(puzzle))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NHbUpOJpXc6i",
        "outputId": "a6b4e580-2676-488a-f4bf-ffd5d3379cc4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Puzzle gerado: 8672543*1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o6ZClGCC1RxB"
      },
      "source": [
        "## Busca em largura"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cmJfg8CF0Jwc",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "de0d3195-e79f-4a3e-9957-27cc2351fcb5"
      },
      "source": [
        "def busca_largura(puzzle):\n",
        "  global solucao\n",
        "  borda = deque()\n",
        "  visitados = set()\n",
        "  contador = 0\n",
        "\n",
        "  arvore = Tree(puzzle, None, None) # arvore de busca\n",
        "  visitados.add(puzzle)             # estados gerados/\"visitados\"\n",
        "  borda.append(arvore)\n",
        "\n",
        "  while len(borda) > 0:\n",
        "      atual = borda.popleft()\n",
        "      if atual.data == solucao:\n",
        "          break\n",
        "\n",
        "      moves = get_movimentos_legais(atual.data) \n",
        "      novos_estados = [(swap(atual.data, x), x) for x in moves]\n",
        "\n",
        "      for estado in novos_estados:\n",
        "          if estado[0] not in visitados:\n",
        "              contador += 1\n",
        "              novo_nodo = Tree(estado[0], atual, estado[1])\n",
        "              #arvore.children.append(novo_nodo) \n",
        "              borda.append(novo_nodo)\n",
        "              visitados.add(estado[0]) \n",
        "\n",
        "  print(\"Estados gerados: {}\".format(contador))\n",
        "  if atual.data == solucao:\n",
        "      print(\"Solucionado.\")\n",
        "      #print(\"Nodos na árvore: {}\".format(nodos_arvore(arvore)))\n",
        "      # N de nodos vai ser sempre igual aos estados\n",
        "      moves_solucao = []\n",
        "      while atual.move != None:\n",
        "        moves_solucao.append(atual.move)\n",
        "        atual = atual.parent\n",
        "      return moves_solucao[::-1]\n",
        "  else:\n",
        "      print(\"Não existe uma solução\")\n",
        "      return -1\n",
        "\n",
        "resultado_largura = busca_largura(puzzle)\n",
        "print(resultado_largura)\n",
        "print(aplica_resultado(puzzle, resultado_largura))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Estados gerados: 181439\n",
            "Solucionado.\n",
            "[-3, -3, 1, 3, -1, -1, 3, 1, 1, -3, -1, -1, -3, 1, 1, 3, -1, 3, -1, -3, -3, 1, 3, 3, -1, -3, -3, 1, 1, 3, 3]\n",
            "12345678*\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zCCoey-J1U5t"
      },
      "source": [
        "## Busca em Profundidade"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Acho que a parte de corte não funcionou corretamente. Ele tira a relação de pai/filho dos nós (já que a função de contar os nodo retorna um número bem menor que os estados gerados), mas pelo jeito não deleta os nós de fato, não sei se é pela minha falta de familiaridade com python, mas ao meu ver parece correto, a não ser que eu esteja apenas deletando a referência para o objeto e não o objeto de fato.\n",
        "\n",
        "((Acho que o problema era o getsizeof mesmo, pelo jeito tá funcionando... eu acho))"
      ],
      "metadata": {
        "id": "qGPv4izvbtGr"
      }
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XJkS_j3m8A4x",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c5d20ecd-3a02-4f31-9567-4af43e57cb24"
      },
      "source": [
        "def busca_profundidade(puzzle):\n",
        "  global solucao\n",
        "  contador = 0\n",
        "  borda = deque()\n",
        "  visitados = set()\n",
        "\n",
        "  arvore = Tree(puzzle, None, None) # arvore de busca\n",
        "  visitados.add(puzzle)       # estados gerados/\"visitados\"\n",
        "  borda.append(arvore)\n",
        "\n",
        "  while len(borda) > 0:\n",
        "      atual = borda.pop()     # pop ao inves de popleft\n",
        "      if atual.data == solucao:\n",
        "          break\n",
        "\n",
        "      moves = get_movimentos_legais(atual.data) \n",
        "      novos_estados = [(swap(atual.data, x), x) for x in moves]\n",
        "      estados_validos = [x for x in novos_estados if x[0] not in visitados]\n",
        "\n",
        "      if len(estados_validos) == 0: # Apaga os caminhos fechados\n",
        "        prev = atual\n",
        "        atual = atual.parent\n",
        "        atual.children.remove(prev)\n",
        "        del prev\n",
        "        while len(atual.children) == 0 and atual.parent != None:\n",
        "          prev = atual\n",
        "          atual = atual.parent\n",
        "          atual.children.remove(prev)\n",
        "          del prev\n",
        "      \n",
        "      for estado in estados_validos:\n",
        "        contador += 1\n",
        "        novo_nodo = Tree(estado[0], atual, estado[1])\n",
        "        atual.children.append(novo_nodo)\n",
        "        borda.append(novo_nodo)\n",
        "        visitados.add(estado[0])  \n",
        "\n",
        "  print(\"Estados gerados: {}\".format(contador))\n",
        "  if atual.data == solucao:\n",
        "      print(\"Solucionado.\")\n",
        "      print(\"Nodos na árvore: {}\".format(nodos_arvore(arvore)))\n",
        "      moves_solucao = []\n",
        "      while atual.move != None:\n",
        "        moves_solucao.append(atual.move)\n",
        "        atual = atual.parent\n",
        "      return moves_solucao[::-1]\n",
        "  else:\n",
        "      print(\"Não existe uma solução\")\n",
        "      return -1\n",
        "\n",
        "resultado_profundidade = busca_profundidade(puzzle)\n",
        "#print(resultado_profundidade)\n",
        "print(len(resultado_profundidade))\n",
        "print(aplica_resultado(puzzle, resultado_profundidade))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Estados gerados: 179094\n",
            "Solucionado.\n",
            "Nodos na árvore: 53165\n",
            "30280\n",
            "12345678*\n"
          ]
        }
      ]
    }
  ]
}