{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color='blue'>Data Science Academy - Python Fundamentos - Capítulo 7</font>\n",
    "\n",
    "## Download: http://github.com/dsacademybr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Missão: Implementar um algoritmo para mover um robô do canto superior esquerdo para o canto inferior direito de uma grade."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Nível de Dificuldade: Médio"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Premissas\n",
    "\n",
    "* Existem restrições de como o robô se move?\n",
    "     * O robô só pode se mover para a direita e para baixo\n",
    "* Algumas células são inválidas (fora dos limites)?\n",
    "     * Sim\n",
    "* Podemos supor que as células inicial e final são células válidas?\n",
    "     * Sim\n",
    "* Isso é uma grade retangular? ou seja, a grade não é irregular?\n",
    "     * Sim\n",
    "* Haverá sempre uma maneira válida para o robô chegar ao canto inferior direito?\n",
    "     * Não, retorno None\n",
    "* Podemos assumir que as entradas são válidas?\n",
    "     * Não\n",
    "* Podemos supor que isso se encaixa na memória?\n",
    "     * Sim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Teste Cases\n",
    "\n",
    "<pre>\n",
    "o = célula válida\n",
    "x = célula inválida\n",
    "\n",
    "   0  1  2  3\n",
    "0  o  o  o  o\n",
    "1  o  x  o  o\n",
    "2  o  o  x  o\n",
    "3  x  o  o  o\n",
    "4  o  o  x  o\n",
    "5  o  o  o  x\n",
    "6  o  x  o  x\n",
    "7  o  x  o  o\n",
    "</pre>\n",
    "\n",
    "* Caso geral\n",
    "\n",
    "```\n",
    "Saída esperada = [(0, 0), (1, 0), (2, 0),\n",
    "                  (2, 1), (3, 1), (4, 1),\n",
    "                  (5, 1), (5, 2), (6, 2), \n",
    "                  (7, 2), (7, 3)]\n",
    "```\n",
    "\n",
    "* Nenhum caminho válido, por exemplo, linha 7, col 2 é inválido\n",
    "* Nenhuma entrada\n",
    "* Matriz vazia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solução"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Grid(object):\n",
    "\n",
    "    def find_path(self, matrix):\n",
    "        # Implemente aqui sua solução"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Teste da Solução"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing missao3.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile missao3.py\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "\n",
    "class TestGridPath(object):\n",
    "\n",
    "    def test_grid_path(self):\n",
    "        grid = Grid()\n",
    "        assert_equal(grid.find_path(None), None)\n",
    "        assert_equal(grid.find_path([[]]), None)\n",
    "        max_rows = 8\n",
    "        max_cols = 4\n",
    "        matrix = [[1] * max_cols for _ in range(max_rows)]\n",
    "        matrix[1][1] = 0\n",
    "        matrix[2][2] = 0\n",
    "        matrix[3][0] = 0\n",
    "        matrix[4][2] = 0\n",
    "        matrix[5][3] = 0\n",
    "        matrix[6][1] = 0\n",
    "        matrix[6][3] = 0\n",
    "        matrix[7][1] = 0\n",
    "        result = grid.find_path(matrix)\n",
    "        expected = [(0, 0), (1, 0), (2, 0),\n",
    "                    (2, 1), (3, 1), (4, 1),\n",
    "                    (5, 1), (5, 2), (6, 2), \n",
    "                    (7, 2), (7, 3)]\n",
    "        assert_equal(result, expected)\n",
    "        matrix[7][2] = 0\n",
    "        result = grid.find_path(matrix)\n",
    "        assert_equal(result, None)\n",
    "        print('Sua solução foi executada com sucesso! Parabéns!')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestGridPath()\n",
    "    test.test_grid_path()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sua solução foi executada com sucesso! Parabéns!\n"
     ]
    }
   ],
   "source": [
    "%run -i missao3.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Obrigado - Data Science Academy - <a href=\"http://facebook.com/dsacademybr\">facebook.com/dsacademybr</a>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}