{
 "metadata": {
  "name": "",
  "signature": "sha256:a59f3c8211a9e8fdf1291d37715fdc62e9305291e58b890b83d6dffba8ad977c"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The necessary modules, including SimpleAI for the AI problem solving"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from random import random\n",
      "from IPython.display import HTML\n",
      "from simpleai.search import SearchProblem, hill_climbing_random_restarts"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Simple Manhattan distance"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def distance(position1, position2):\n",
      "    x1, y1 = position1\n",
      "    x2, y2 = position2\n",
      "    return abs(x1 - x2) + abs(y1 - y2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We define the problem as a local search problem (optimization)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class CenterProblem(SearchProblem):\n",
      "    def __init__(self, precission, positions, special_importances):\n",
      "        super(CenterProblem, self).__init__(self)\n",
      "        self.precission = precission\n",
      "        self.positions = positions\n",
      "        self.special_importances = special_importances\n",
      "        \n",
      "        self.top = min(y for x, y in self.positions.values())\n",
      "        self.bottom = max(y for x, y in self.positions.values())\n",
      "        self.left = min(x for x, y in self.positions.values())\n",
      "        self.right = max(x for x, y in self.positions.values())\n",
      "\n",
      "        self.step_x = abs(self.top - self.bottom) / self.precission\n",
      "        self.step_y = abs(self.left - self.right) / self.precission\n",
      "        \n",
      "    def actions(self, state):\n",
      "        x, y = state\n",
      "        return ((x, y + self.step_y),\n",
      "                (x, y - self.step_y),\n",
      "                (x + self.step_x, y),\n",
      "                (x - self.step_x, y))\n",
      "\n",
      "    def result(self, state, action):\n",
      "        return action\n",
      "\n",
      "    def cost(self, state1, action, state2):\n",
      "        return 1\n",
      "\n",
      "    def value(self, state):\n",
      "        return -sum(distance(state, position) * self.special_importances.get(thing, 1) \n",
      "                    for thing, position in self.positions.items())\n",
      "\n",
      "    def generate_random_state(self):\n",
      "        return (self.left + random() * self.precission, \n",
      "                self.top + random() * self.precission)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Instantiate the problem with specific data, then solve it using hill climbing with random restarts"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "problem = CenterProblem(\n",
      "    precission = 100,  # higher is more precise\n",
      "    positions = {\n",
      "        'churi': (-34.581516, -58.578009),\n",
      "        'papacheese': (-34.572046, -58.494067),\n",
      "        'sirevanac': (-34.548862, -58.481364),\n",
      "        'blitz': (-34.511386, -58.496985),\n",
      "        'svin': (-34.762215, -58.248630),\n",
      "        'zild': (-34.112310, -59.029679),\n",
      "    },\n",
      "    special_importances = {\n",
      "        'svin': 0.15,\n",
      "        'zild': 0.15,\n",
      "    }\n",
      ")\n",
      "\n",
      "result = hill_climbing_random_restarts(problem, restarts_limit=100)\n",
      "\n",
      "print result.state, abs(result.value)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(-34.56296283235742, -58.49674475938182) 0.4075201\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Finally, plot the solution with google maps"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "template = \"\"\"<iframe \n",
      "                src=\"https://www.google.com/maps/embed/v1/place?key={maps_key}&q={position}\"\n",
      "                style=\"height: 500px; width: 100%\">\n",
      "              </iframe>\n",
      "           \"\"\"\n",
      "\n",
      "HTML(template.format(maps_key='AIzaSyBLX80To6RQE7BZwAf0ClVozv4MrZ2vwxI',\n",
      "                     position=','.join(map(str, result.state))))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<iframe \n",
        "                src=\"https://www.google.com/maps/embed/v1/place?key=AIzaSyBLX80To6RQE7BZwAf0ClVozv4MrZ2vwxI&q=-34.5629628324,-58.4967447594\"\n",
        "                style=\"height: 500px; width: 100%\">\n",
        "              </iframe>\n",
        "           "
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "<IPython.core.display.HTML at 0x7fa4d4184c50>"
       ]
      }
     ],
     "prompt_number": 6
    }
   ],
   "metadata": {}
  }
 ]
}