day 24 - closest pair.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l1x = lambda a, b: abs(a[0] - b[0])\n",
    "l1y = lambda a, b: abs(a[1] - b[1])\n",
    "l2 = lambda a, b: np.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def merge(points_y, l, m, r):\n",
    "    i, j, aux = l, m, []\n",
    "    while i < m or j < r:\n",
    "        if i < m and j < r and points_y[i][1] > points_y[j][1]:\n",
    "            aux.append(points_y[j])\n",
    "            j += 1\n",
    "        elif i < m:\n",
    "            aux.append(points_y[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            aux.append(points_y[j])\n",
    "            j += 1\n",
    "    points_y[l:r] = aux"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def search(points_x, points_y, l, r):\n",
    "    if r - l < 2:\n",
    "        return np.inf\n",
    "\n",
    "    m = (l + r) // 2\n",
    "\n",
    "    # search inside partitions\n",
    "    delta1 = search(points_x, points_y, l, m)\n",
    "    delta2 = search(points_x, points_y, m, r)\n",
    "    delta = min(delta1, delta2)\n",
    "\n",
    "    # sort points by y\n",
    "    merge(points_y, l, m, r)\n",
    "\n",
    "    # find the middle band in delta of x\n",
    "    q = points[m]\n",
    "    band = [p for p in points_y[l:r] if l1x(p, q) < delta]\n",
    "\n",
    "    # search the middle band in delta of y\n",
    "    for i in range(len(band)):\n",
    "        p1 = band[i]\n",
    "        for j in range(i + 1, len(band)):\n",
    "            p2 = band[j]\n",
    "            if l1y(p1, p2) < delta:\n",
    "                delta = min(delta, l2(p1, p2))\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    # min distance\n",
    "    return delta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def closest_pair(points):\n",
    "    points = sorted(points)\n",
    "    return search(points, points[:], 0, len(points))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0.098408754012625277, 0.74280296333228502),\n",
       " (0.077086466963399936, 0.29657822643731369),\n",
       " (0.56160732190468798, 0.54675608365280715),\n",
       " (0.82076413876723719, 0.3014490061746683),\n",
       " (0.42758995432097113, 0.19199854966752694)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "points = [tuple(i) for i in np.random.rand(100, 2)]\n",
    "points[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.012360394883333799"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "closest_pair(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}