{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Grid Domain\n",
    "\n",
    "Many games are played on a two-dimensional grid. We should represent two-dimensional points, and grids:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Point(x, y): \"Two-dimensional (x, y) point.\"; return (x, y)\n",
    "    \n",
    "def X(point): \"X coordinate of a point\"; return point[0]\n",
    "\n",
    "def Y(point): \"Y coordinate of a point\"; return point[1]\n",
    "\n",
    "class Grid(dict): \n",
    "    \"A mapping of {point: contents}; also has width and height methods.\"\n",
    "    def __init__(self, data):\n",
    "        if isinstance(data, str):\n",
    "            data = grid_from_picture(data)\n",
    "        self.update(data)\n",
    "        \n",
    "    def width(self):  return max(X(p) for p in self) + 1\n",
    "    def height(self): return max(Y(p) for p in self) + 1\n",
    "          \n",
    "    def __str__(self):\n",
    "        return '\\n'.join(''.join(self[Point(x, y)] \n",
    "                                 for x in range(self.width()))\n",
    "                         for y in range(self.height()))\n",
    "    __repr__ = __str__\n",
    "    \n",
    "def grid_from_picture(text):\n",
    "    lines = text.strip().splitlines()\n",
    "    return {Point(x, y): ch\n",
    "            for (y, line) in enumerate(lines)\n",
    "            for (x, ch) in enumerate(line)}\n",
    "\n",
    "def add_sequence(grid, seq, marker='*'):\n",
    "    for point in seq:\n",
    "        grid[point] = marker\n",
    "    return grid\n",
    "\n",
    "g = Grid(\"\"\"\n",
    "S...|.G\n",
    "....|.-\n",
    ".---+..\n",
    ".......\n",
    "\"\"\")\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def depth_first_search(problem):\n",
    "    return recursive_depth_first_search(problem, Node(problem.initial), set())\n",
    "\n",
    "def recursive_depth_first_search(problem, node, explored):\n",
    "    if problem.is_goal(node.state):\n",
    "        return node.action_sequence()\n",
    "    else:\n",
    "        for action in problem.actions(node.state):\n",
    "            child = node.child(problem, action)\n",
    "            if child.state not in explored:\n",
    "                explored.add(child.state)\n",
    "                result = recursive_depth_first_search(problem, child, explored)\n",
    "                if result is not None:\n",
    "                    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GPX - Coyote Century\n",
    "\n",
    "I have tracks from the 2012 Century Juliet and I did, but for some reason I didn't get time stamps (nor elevation), just lat/lon. I need timestamps to import into Strava or Garmin. \n",
    "\n",
    "So I'll take my average speed (12.3 mph) and start time (6/14/2012 8:12) and assign time stamps, assuming (incorrectly) a constant speed. Then I'll write the whole thing as a file in GPX format:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import time\n",
    "import re\n",
    "import math\n",
    "import re\n",
    "\n",
    "text = open('/Users/pnorvig/Downloads/vrp9cybkx_Coyote-Century-Juliet-and-Peter.gpx').read()\n",
    "points = re.findall('<trkpt lat=\"(.*?)\" lon=\"(.*?)\">', text)\n",
    "\n",
    "gpx_template = \"\"\"\n",
    "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"yes\"?>\n",
    "<gpx xmlns=\"http://www.topografix.com/GPX/1/1\"  \n",
    "     creator=\"KML2GPX.COM\" version=\"1.1\" \n",
    "     xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" \n",
    "     xsi:schemaLocation=\"http://www.topografix.com/GPX/1/1 http://www.topografix.com/GPX/1/1/gpx.xsd\">\n",
    "  <trk><name>Track 1</name><number>1</number>\n",
    "    <name>Coyote Creek Century, Peter and Juliet</name>\n",
    "    <trkseg>\n",
    "    {}\n",
    "    </trkseg>\n",
    "  </trk>\n",
    "</gpx>\n",
    "</xml>\n",
    "\"\"\"\n",
    "\n",
    "trkpt_template = \"\"\"<trkpt lat=\"{}\" lon=\"{}\"><time>2012-06-14T{}Z</time></trkpt>\"\"\"\n",
    "\n",
    "speed = 12.3 # Overall speed of 12.3 MPH\n",
    "\n",
    "start = time.mktime((2012, 6, 14, 8, 12, 0, -1, -1, -1))\n",
    "\n",
    "def hms(t): return time.strftime('%H:%M:%S', time.localtime(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2816, ('37.310427', '-121.843023'), ('37.310474', '-121.843086'))"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(points), points[0], points[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1339686720.0, 'Thu Jun 14 08:12:00 2012', '08:12:00')"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(start, \n",
    " time.asctime(time.localtime(start)), \n",
    " hms(start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from math import radians, cos, sin, asin, sqrt\n",
    "def haversine(lat1, lon1, lat2, lon2):\n",
    "    \"\"\"\n",
    "    Calculate the great circle distance between two points \n",
    "    on the earth (specified in decimal degrees)\n",
    "    \"\"\"\n",
    "    # convert decimal degrees to radians \n",
    "    lon1, lat1, lon2, lat2 = [radians(float(x)) for x in [lon1, lat1, lon2, lat2]]\n",
    "    # haversine formula \n",
    "    dlon = lon2 - lon1 \n",
    "    dlat = lat2 - lat1 \n",
    "    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2\n",
    "    c = 2 * asin(sqrt(a)) \n",
    "    return 3963.1676 * c # Radius of Earth in miles\n",
    "\n",
    "def pairs(sequence):\n",
    "    return [sequence[i:i+2] for i in range(len(sequence) - 1)]\n",
    "\n",
    "assert pairs('abcd') == ['ab', 'bc', 'cd']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.005787321233984945"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = haversine(\"37.310427\", \"-121.843023\", \"37.31041\", \"-121.843126\")\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100.09224214050319"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(haversine(a, b, c, d) for ((a, b), (c, d)) in pairs(points))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.693850117263886"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d / speed * 60 * 60"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'08:14:49'"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hms(start + d / speed * 60 * 60)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def insert_times(points):\n",
    "    (lat, lon), time = points[0], start\n",
    "    for (lat2, lon2) in points:\n",
    "        d = haversine(lat, lon, lat2, lon2) \n",
    "        time += d / speed * 60 * 60\n",
    "        yield trkpt_template.format(lat2, lon2, hms(time))\n",
    "        lat, lon = lat2, lon2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"yes\"?>\n",
      "<gpx xmlns=\"http://www.topografix.com/GPX/1/1\"  \n",
      "     creator=\"KML2GPX.COM\" version=\"1.1\" \n",
      "     xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" \n",
      "     xsi:schemaLocation=\"http://www.topografix.com/GPX/1/1 http://www.topografix.com/GPX/1/1/gpx.xsd\">\n",
      "  <trk><name>Track 1</name><number>1</number>\n",
      "    <name>Coyote Creek Century, Peter and Juliet</name>\n",
      "    <trkseg>\n",
      "    <trkpt lat=\"37.310427\" lon=\"-121.843023\"><time>2012-06-14T08:12:00Z</time></trkpt>\n",
      "    <trkpt lat=\"37.31041\" lon=\"-121.843126\"><time>2012-06-14T08:12:01Z</time></trkpt>\n",
      "    <trkpt lat=\"37.310461\" lon=\"-121.84309700000001\"><time>2012-06-14T08:12:02Z</time></trkpt>\n",
      "    <trkpt lat=\"37.310313\" lon=\"-121.84318\"><time>2012-06-14T08:12:06Z</time></trkpt>\n",
      "    <trkpt lat=\"37.310198\" lon=\"-121.843346\"><time>2012-06-14T08:12:09Z</time></trkpt>\n",
      "    </trkseg>\n",
      "  </trk>\n",
      "</gpx>\n",
      "</xml>\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def convert(points):\n",
    "    records = '\\n    '.join(insert_times(points))\n",
    "    return gpx_template.format(records)\n",
    "    \n",
    "print(convert(points[:5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "256252"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open('coyote_creek_century.gpx', 'w').write(convert(points))"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "REVISE       amendment = re + sight\n",
    "RESEARCH     analysis = re + find                         \n",
    "REFRACT      bending light = re + portion\n",
    "RELIABLE     dependable = re + susceptible\n",
    "RENEG        do something again = re + plea\n",
    "REDO         echo = re + action word\n",
    "RENOUNCE     give up = re + endorse\n",
    "RESOURCE     good = re + origin\n",
    "RECONSTITUTE make whole = re + health\n",
    "RELOCATE     move = re + find\n",
    "REVEAL       find again = re + hide\n",
    "REPAIR       fix = re + two things\n",
    "RECREATION   pastime = re + bringing into existence\n",
    "REFINE       purify = re + exact\n",
    "REPERCUSSION ramification = re + impact\n",
    "RECYCLE      salvage = re + periodicity\n",
    "REPURPOSE    sell = re + end\n",
    "RESUBMIT     state briefly = re + surrender\n",
    "RECOLLECT    summon a memory = re + amass\n",
    "REMEMBER     summon a memory = re + section\n",
    "RECALL       summon a memory = re + shout\n",
    "REPRESENT    symbolize = re + give\n",
    "RELATE       tell = re + tardy"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
