kata/00_Sequence.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "200"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import requests\n",
    "\n",
    "url = 'https://kata.geosci.ai/challenge/sequence'  # <--- In week 2, you'll change the name.\n",
    "r = requests.get(url)\n",
    "r.status_code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Sequence\n",
       "\n",
       "You have a string of lithology codes, reading from the **bottom up** of a geological section. There is a sample every metre. There are three lithologies:\n",
       "\n",
       "- **M**udstone\n",
       "- **F**ine sandstone or siltstone\n",
       "- **S**andstone\n",
       "\n",
       "The strings look like this:\n",
       "\n",
       "      ...MFFSSFSSSS...\n",
       "\n",
       "Your data, when you receive it, will be much longer than this.\n",
       "\n",
       "We need to get some geological information from this string of codes. Specifically, you need to answer 3 questions:\n",
       "\n",
       "1. What is the total thickess in metres of sandstone (`S`)? Each sample represents one metre.\n",
       "2. How many sandstone beds are there? A bed is a contiguous group of one lithology, so `MMFFF` is 2 beds, one of `M` and one of `F`.\n",
       "3. How many times does the most common *upwards* bed transition occur? Do not include transitions from a lithology to itself.\n",
       "\n",
       "Remember that the sequence is given to you from the bottom up. So an upwards transition is equivalent to a transition to the right.\n",
       "\n",
       "\n",
       "## Example\n",
       "\n",
       "Here is some example input:\n",
       "\n",
       "      SSMMFFFFFFFFSSMFFSSFSSSSFMFSSSSFFSSFFFMM\n",
       "      ^^          ^^   ^^ ^^^^   ^^^^  ^^\n",
       "\n",
       "And the answers to the 3 questions:\n",
       "\n",
       "- In this example, the total thickess of sandstone is 16 m. So the required answer is: **16**\n",
       "- There are 6 sandstone beds in the sequence (marked above). The answer is: **6**\n",
       "- The most common bed transition is `F` to `S`, which occurs 5 times. So the answer is: **5**\n",
       "\n",
       "\n",
       "## A quick reminder how this works\n",
       "\n",
       "You can retrieve your data by choosing any Python string as a **`<KEY>`** and substituting here:\n",
       "    \n",
       "    https://kata.geosci.ai/challenge/sequence?key=<KEY>\n",
       "                                                  ^^^^^\n",
       "                                                  use your own string here\n",
       "\n",
       "To answer question 1, make a request like:\n",
       "\n",
       "    https://kata.geosci.ai/challenge/sequence?key=<KEY>&question=1&answer=1234\n",
       "                                                  ^^^^^          ^        ^^^^\n",
       "                                                  your key       Q        your answer\n",
       "\n",
       "[Complete instructions at kata.geosci.ai](https://kata.geosci.ai/challenge)\n",
       "\n",
       "----\n",
       "\n",
       "© 2020 Agile Scientific, licensed CC-BY"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Markdown\n",
    "Markdown(r.text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def net_thickness(section, facies):\n",
    "    \"\"\"Given a string representing a 'measured section' of facies, return the net thickness of the given facies.\n",
    "    \n",
    "    Example:\n",
    "    ---------\n",
    "    >>> net_thickness(section='MMSFM', facies='M')\n",
    "    \n",
    "    3\n",
    "    \"\"\"\n",
    "    c = Counter(section)\n",
    "    \n",
    "    return c[facies]\n",
    "\n",
    "assert net_thickness('MMSFM', 'M') == 3\n",
    "assert net_thickness('MMSFM', 'S') == 1\n",
    "assert net_thickness('MMSFM', 'C') == 0\n",
    "assert net_thickness('SSMMFFFFFFFFSSMFFSSFSSSSFMFSSSSFFSSFFFMM', 'S') == 16\n",
    "\n",
    "\n",
    "def split_section_into_beds(section):\n",
    "    \"\"\"Split a section up into a list of strings of contiguous facies\n",
    "    \n",
    "    Example:\n",
    "    ---------\n",
    "    >>> split_section_into_beds('MMMSSSFFM')\n",
    "    \n",
    "    ['MMM', 'SSS', 'FF', 'M']\n",
    "    \"\"\"\n",
    "    beds = list()\n",
    "    \n",
    "    i = 0\n",
    "    while i < len(section):\n",
    "        current_facies = section[i]\n",
    "        current_bed = ''\n",
    "\n",
    "        while i < len(section) and current_facies == section[i]:\n",
    "            current_bed += section[i]\n",
    "            i += 1            \n",
    "\n",
    "        beds.append(current_bed)\n",
    "    \n",
    "    return beds\n",
    "    \n",
    "     \n",
    "assert split_section_into_beds('MSF') == ['M', 'S', 'F']\n",
    "assert split_section_into_beds('MMSSFF') == ['MM', 'SS', 'FF']\n",
    "assert split_section_into_beds('MMSSFSF') == ['MM', 'SS', 'F', 'S', 'F']\n",
    "        \n",
    "\n",
    "def bed_count(section, facies):\n",
    "    \"\"\"Count the number of continuous beds of a given facies within a string representing a measured section\"\"\"\n",
    "    \n",
    "    # Split into beds\n",
    "    beds = split_section_into_beds(section)\n",
    "    # Filter by facies\n",
    "    facies_beds = [bed for bed in beds if facies in bed]\n",
    "    # Count beds\n",
    "    return len(facies_beds)\n",
    "\n",
    "assert bed_count('MMSSFSF', 'M') == 1\n",
    "assert bed_count('MMSSFSF', 'S') == 2\n",
    "assert bed_count('MMSSFSF', 'F') == 2\n",
    "assert bed_count('MMSSFSF', 'C') == 0\n",
    "\n",
    "def count_transitions(section):\n",
    "    \"Find all the transitions in a section\"\n",
    "    transitions = (pair for pair in zip(section[:-1], section[1:]) if pair[0] != pair[1])\n",
    "    return Counter(transitions)\n",
    "\n",
    "\n",
    "def most_common_transition_count(section):\n",
    "    \"\"\"Return the count of the most common transition in a section\"\"\"\n",
    "    return(count_transitions(section).most_common(1)[0][1])\n",
    "\n",
    "assert most_common_transition_count('SSMMFFFFFFFFSSMFFSSFSSSSFMFSSSSFFSSFFFMM') == 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# My Submission"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_key = \"MH - :)\"\n",
    "params = {'key': my_key}\n",
    "r = requests.get(url, params)\n",
    "section = r.text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer1 = net_thickness(section, 'S')\n",
    "answer2 = bed_count(section, 'S')\n",
    "answer3 = most_common_transition_count(section)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5741 2352 2263\n"
     ]
    }
   ],
   "source": [
    "print(answer1, answer2, answer3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answer 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Response [200]>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "params = {'key': my_key,\n",
    "          'question': 1,\n",
    "          'answer': answer1\n",
    "         }\n",
    "\n",
    "r = requests.get(url, params)\n",
    "r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Correct'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answer 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<Response [200]>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Correct'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "params['question'] = 2\n",
    "params['answer'] = answer2\n",
    "\n",
    "r = requests.get(url, params)\n",
    "print(r)\n",
    "r.text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answer 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<Response [200]>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Correct! The next challenge is: https://kata.geosci.ai/challenge/boreholes - good luck!'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "params['question'] = 3\n",
    "params['answer'] = answer3\n",
    "\n",
    "r = requests.get(url, params)\n",
    "print(r)\n",
    "r.text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alternate solution using numpy\n",
    "\n",
    "Using code from [this gist](https://gist.github.com/alimanfoo/c5977e87111abe8127453b21204c1065). I had to modify it slightly to use the `np.char` module for this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "def find_runs(x):\n",
    "    \"\"\"Find runs of consecutive items in an array.\"\"\"\n",
    "\n",
    "    # ensure array\n",
    "    x = np.asanyarray(x)\n",
    "    if x.ndim != 1:\n",
    "        raise ValueError('only 1D array supported')\n",
    "    n = x.shape[0]\n",
    "\n",
    "    # handle empty array\n",
    "    if n == 0:\n",
    "        return np.array([]), np.array([]), np.array([])\n",
    "\n",
    "    else:\n",
    "        # find run starts\n",
    "        loc_run_start = np.empty(n, dtype=bool)\n",
    "        loc_run_start[0] = True\n",
    "        np.not_equal(x[:-1], x[1:], out=loc_run_start[1:])\n",
    "        run_starts = np.nonzero(loc_run_start)[0]\n",
    "\n",
    "        # find run values\n",
    "        run_values = x[loc_run_start]\n",
    "\n",
    "        # find run lengths\n",
    "        run_lengths = np.diff(np.append(run_starts, n))\n",
    "\n",
    "        return run_values, run_starts, run_lengths\n",
    "    \n",
    "def find_char_runs(x):\n",
    "    \"\"\"Find runs of consecutive items in an array.\"\"\"\n",
    "\n",
    "    # ensure array\n",
    "    x = np.asanyarray(x)\n",
    "    if x.ndim != 1:\n",
    "        raise ValueError('only 1D array supported')\n",
    "    n = x.shape[0]\n",
    "\n",
    "    # handle empty array\n",
    "    if n == 0:\n",
    "        return np.array([]), np.array([]), np.array([])\n",
    "\n",
    "    else:\n",
    "        # find run starts\n",
    "        loc_run_start = np.empty(n, dtype=bool)\n",
    "        loc_run_start[0] = True\n",
    "        loc_run_start[1:] = np.char.not_equal(x[:-1], x[1:]) # this line had to be modified to work with np.char\n",
    "        run_starts = np.nonzero(loc_run_start)[0]\n",
    "\n",
    "        # find run values\n",
    "        run_values = x[loc_run_start]\n",
    "\n",
    "        # find run lengths\n",
    "        run_lengths = np.diff(np.append(run_starts, n))\n",
    "\n",
    "        return run_values, run_starts, run_lengths\n",
    "    \n",
    "def bed_count_np(section, facies):\n",
    "    values, _, _ = find_char_runs(np.array(list(section)))\n",
    "    return np.sum(values == facies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2352"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = np.array(list(section))\n",
    "values, starts, lengths = find_char_runs(a)\n",
    "\n",
    "np.sum(values == 'S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "51.6 µs ± 1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "assert bed_count('MMSSFSF', 'M') == 1\n",
    "assert bed_count('MMSSFSF', 'S') == 2\n",
    "assert bed_count('MMSSFSF', 'F') == 2\n",
    "assert bed_count('MMSSFSF', 'C') == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "730 µs ± 59.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "assert bed_count_np('MMSSFSF', 'M') == 1\n",
    "assert bed_count_np('MMSSFSF', 'S') == 2\n",
    "assert bed_count_np('MMSSFSF', 'F') == 2\n",
    "assert bed_count_np('MMSSFSF', 'C') == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27.5 ms ± 1.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "bed_count(section, 'S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.05 ms ± 204 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "bed_count_np(section, 'S')"
   ]
  }
 ],
 "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}