Pure-Python-Exercises_Kaggle_Final-UPDATED-REGULARLY.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "### In this Notebook I shall cover the following most common Python challenges for Data Science Interviews.\n",
    "\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">1.Product of two matrices<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">2.Proportional Probability Sampling<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">3.Closest points (based on cosine distance)<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">4.Fast way to list all primes number below n<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">5.Find all prime factors of a number<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">6.Implement formulae of permutations and combinations.<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">7.Converts a decimal number to binary number<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">8. Find whether a given line (equation in x and y ) is able to separate the two lists of points (tuples) successfully<a id=\"1\"></a></h2>\n",
    "<h2 style=\"font-size:150%; font-family:cursive; color:#ff6666;\">9. Implement Log-Loss Function<a id=\"1\"></a></h2>\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "# Q: Product of two matrices\n",
    "\n",
    "Given two matrices print the product of those two matrices\n",
    "\n",
    "### Solution with Explanations and Theory\n",
    "\n",
    "### Basics of Matrix Multiplication\n",
    "\n",
    "Multiplication rule to remember - Here also the flow is Row and then Column\n",
    "\n",
    "1. Sum-Product of First Row \\* 1st Column => Becomes the 1-st_Row-1-st_Column of the resultant Matrix\n",
    "\n",
    "2. Sum-Product of 1st Row \\* 2-nd Column => Becomes the 1-st_Row-2-nd_Column of the resultant Matrix\n",
    "\n",
    "### There are four simple rules that will help us in multiplying matrices, listed here:\n",
    "\n",
    "#### 1. Firstly, we can only multiply two matrices when the number of columns in matrix A is equal to the number of rows in matrix B.\n",
    "\n",
    "#### 2. Secondly, the first row of matrix A multiplied by the first column of matrix B gives us the first element in the matrix AB, and so on.\n",
    "\n",
    "#### 3. Thirdly, when multiplying, order matters—specifically, AB ≠ BA.\n",
    "\n",
    "#### 4. Lastly, the element at row i, column j is the product of the ith row of matrix A and the jth column of matrix B.\n",
    "\n",
    "Further read through [this](https://www.mathsisfun.com/algebra/matrix-multiplying.html) for a very nice visual flow of Matrix Multiplication.\n",
    "\n",
    "![img](https://i.imgur.com/9IETtIo.png)"
   ],
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "source": [
    "import math\n",
    "import numpy as np\n",
    "import random\n",
    "import pandas as pd\n",
    "\n",
    "# This works in O(n^3)\n",
    "def multiply_matrix(matrix1,matrix2):\n",
    "    results = []\n",
    "    try:\n",
    "        for i in range(len(matrix1)):\n",
    "            rows = []\n",
    "            for j in range(len(matrix2[0])):\n",
    "                item = 0\n",
    "                for k in range(len(matrix1[0])):\n",
    "                    item += matrix1[i][k] * matrix2[k][j]\n",
    "                rows.append(item)\n",
    "            results.append(rows)\n",
    "        return results\n",
    "    except:\n",
    "        return \"These matrices aren't compatible.\"\n",
    "\n",
    "\n",
    "\n",
    "A1 = [[1, 2],\n",
    "      [3, 4]]\n",
    "\n",
    "B1 = [[1, 2, 3, 4, 5],\n",
    "      [5, 6, 7, 8, 9]]\n",
    "\n",
    "\n",
    "print(multiply_matrix(A1, B1))\n",
    "\n",
    "# [[11, 14, 17, 20, 23], [23, 30, 37, 44, 51]]"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[[1, 3, 4], [2, 5, 7], [5, 9, 6]]\n",
      "[[11, 14, 17, 20, 23], [23, 30, 37, 44, 51]]\n",
      "Matrix multiplication of two arguments not possible as number of columns in first Matrix is NOT equal to the number of rows in second Matrix\n",
      "None\n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: proportional Probability Sampling\n",
    "\n",
    "Select a number randomly with probability proportional to its magnitude from the given array of n elements\n",
    "\n",
    "consider an experiment, selecting an element from the list A randomly with probability proportional to its magnitude. assume we are doing the same experiment for 100 times with replacement, in each experiment you will print a number that is selected randomly from A.\n",
    "\n",
    "Ex 1:\n",
    "A = [1, 5, 27, 6, 13, 28, 100, 45, 10, 79]\n",
    "let f(x) denote the number of times x getting selected in 100 experiments.\n",
    "f(100) > f(79) > f(45) > f(28) > f(27) > f(13) > f(10) > f(6) > f(5) > f(0)\n",
    "\n",
    "\n",
    "### Solution and Explanations and Notes on methods, steps, algorithms\n",
    "\n",
    "The below solution is inspired by the explanations given in [this Stackoverflow](https://stackoverflow.com/questions/16489449/select-element-from-array-with-probability-proportional-to-its-value) question.com\n",
    "\n",
    "**To explain further on the question** -\n",
    "\n",
    "I have an array of doubles and I want to select a value from it with the probability of each value being selected being proportional to its value. For example:\n",
    "\n",
    "```\n",
    "arr[0] = 100\n",
    "arr[1] = 200\n",
    "```\n",
    "\n",
    "In this example, element 0 would have a 66% of being selected and element 1 a 33% chance.\n",
    "\n",
    "### The general algorithm is\n",
    "\n",
    " - sum the array\n",
    " - Pick a random number between 0 and the sum\n",
    " - Accumulate the values starting from the beginning of the array until you are >= to the random value.\n",
    "\n",
    "**Note: All values must be positive for this to work.**\n",
    "\n",
    "The usual technique is to transform the array into an array of cumulative sums:\n",
    "\n",
    "     [10 60 5 25]  --> [10 70 75 100]\n",
    "\n",
    "Pick a random number in the range from zero up to the cumulative total (in the example: ``0 <= x < 100``).  Then, use [bisection][1] on the cumulative array to locate the index into the original array:\n",
    "\n",
    "\n",
    "    Random variable x      Index in the Cumulative Array      Value in Original Array\n",
    "    -----------------      -----------------------------      ----------------------\n",
    "     0 <= x < 10                      0                            10\n",
    "    10 <= x < 70                      1                            60\n",
    "    70 <= x < 75                      2                             5\n",
    "    75 <= x < 100                     3                            25\n",
    "\n",
    "For example, if the random variable *x* is 4, bisecting the cumulative array gives a position index of 0 which corresponds to 10 in the original array.\n",
    "\n",
    "And, if the random variable *x* is 72, bisecting the cumulative array gives a position index of 2 which corresponds to 5 in the original array.\n",
    "\n",
    "For an inverse proportion, the technique is exactly the same except you perform an initial transformation of the array into its reciprocals and then build the cumulative sum array:\n",
    "\n",
    "    [10 60 5 25]  -->  [1/10  1/60  1/5  1/25]  -->  [1/10  7/60  19/60  107/300]\n",
    "\n",
    "  [1]: http://en.wikipedia.org/wiki/Binary_search_algorithm"
   ],
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "source": [
    "import random\n",
    "\n",
    "def pick_a_number_from_list(A):\n",
    "    sum=0\n",
    "    cum_sum=[]\n",
    "    for i in range(len(A)):\n",
    "        sum = sum + A[i]\n",
    "        cum_sum.append(sum)\n",
    "    #print(cum_sum)\n",
    "    r = int(random.uniform(0,sum))\n",
    "    print(r)\n",
    "    number=0\n",
    "    for index in range(len(cum_sum)):\n",
    "        if(r>=cum_sum[index] and r<cum_sum[index+1]):\n",
    "            return A[index+1]\n",
    "    return number\n",
    "\n",
    "def sampling_based_on_magnitued():\n",
    "    # A = [0,5,27,6,13,28,100,45,10,79]\n",
    "    A = [1, 5, 27, 6, 13, 28, 100, 45, 10, 79]\n",
    "    a = dict()\n",
    "    #A.sort()\n",
    "    print(A,sum(A))\n",
    "    for i in range(1,100):\n",
    "        number = pick_a_number_from_list(A)\n",
    "        #print(number)\n",
    "        if number not in a:\n",
    "            a[number] = 1\n",
    "        else:\n",
    "            a[number]+=1\n",
    "    print(a)\n",
    "\n",
    "\n",
    "sampling_based_on_magnitued()"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "' Would print like below\\n\\n[100, 5, 79, 100, 100, 100, 100, 27, 45, 28, 79, 79, 100, 100, 28, 27, 100, 79, 6, 28, 27, 13, 13, 45, 45, 100, 13, 6, 27, 100, 6, 79, 100, 27, 10, 100, 79, 45, 28, 13, 5, 28, 45, 45, 28, 45, 79, 79, 6, 79, 5, 45, 79, 6, 45, 79, 100, 45, 100, 27, 79, 13, 45, 28, 79, 100, 100, 79, 28, 100, 100, 100, 100, 45, 13, 79, 79, 79, 28, 27, 27, 100, 79, 45, 100, 79, 45, 100, 45, 28, 100, 100, 45, 79, 100, 100, 45, 45, 79, 100]\\n[79, 100, 45, 100, 79, 45, 79, 100, 27, 100, 100, 10, 100, 79, 79, 79, 100, 10, 45, 79, 45, 100, 100, 27, 100, 100, 13, 45, 100, 45, 79, 13, 45, 79, 27, 100, 45, 100, 45, 100, 45, 45, 100, 100, 100, 79, 45, 100, 100, 79, 100, 100, 100, 100, 79, 28, 79, 79, 100, 45, 100, 79, 100, 79, 79, 45, 45, 100, 28, 100, 45, 79, 13, 100, 79, 100, 100, 79, 100, 6, 27, 79, 100, 79, 100, 45, 79, 79, 28, 79, 28, 100, 28, 45, 10, 27, 79, 79, 13, 100]\\n...\\n'"
      ]
     },
     "metadata": {},
     "execution_count": 2
    }
   ],
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: Closest points (based on cosine distance)\n",
    "\n",
    "Find the closest points (based on cosine distance) in S (which is n data points in the form of list of tuples) from P (which is a point `P=(p,q)` )\n",
    "\n",
    "Consider you have given n data points in the form of list of tuples like\n",
    "\n",
    "`S=[(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),..,(xn,yn)]` and a point `P=(p,q)`\n",
    "\n",
    "Your task is to find 5 closest points(based on cosine distance) in S from P\n",
    "\n",
    "cosine distance between two points (x,y) and (p,q) is defined as\n",
    "\n",
    "### $cos^{-1}(\\frac{(x\\cdot p+y\\cdot q)}{\\sqrt(x^2+y^2)\\cdot\\sqrt(p^2+q^2)})$\n",
    "\n",
    "Ex:\n",
    "\n",
    "S= [(1,2),(3,4),(-1,1),(6,-7),(0, 6),(-5,-8),(-1,-1)(6,0),(1,-1)]\n",
    "P= (3,-4)\n",
    "\n",
    "![img](https://i.imgur.com/vIFPOcG.jpg)\n",
    "\n",
    "Output:\n",
    "(6,-7)\n",
    "(1,-1)\n",
    "(6,0)\n",
    "(-5,-8)\n",
    "(-1,-1)\n",
    "\n",
    "### Solution and Explanations and Notes on methods, steps, algorithms\n",
    "\n",
    "Cosine Similarity and Cosine Distance is heavily used in recommendation systems to recommend products to the users based on there likes and dislikes. For example, Amazon, Flipkart and similar Companies use it to recommend items to customers for personalized experience,Movies rating and recommendation etc.\n",
    "\n",
    "### Notes on Cosine-Distance concept\n",
    "\n",
    "The cosine distance measures the angular cosine distance between vectors a and b.\n",
    "While cosine similarity measures the similarity between two vectors of an inner product space. It is measured by the cosine of the angle between two vectors and determines whether two vectors are pointing in roughly the same direction.\n",
    "\n",
    "### A comparison between euclidean distance (d) and cosine similarity (θ).\n",
    "\n",
    "![img](https://i.imgur.com/LuKJMvT.png)\n",
    "\n",
    "The distance d above is euclidean distance. Which can be measured as below\n",
    "\n",
    "### √{(x2-x1)^2 + (y2-y1)^2}\n",
    "\n",
    "But cosine considers the angle between vectors (thus not taking into regard their weight or magnitude).\n",
    "\n",
    "![img](https://i.imgur.com/U8vIZja.png)\n",
    "\n",
    "[Source of above image](https://medium.com/datadriveninvestor/cosine-similarity-cosine-distance-6571387f9bf8)\n",
    "\n",
    "For two vectors that are completely identical, the cosine similarity will be 1. For vectors that are completely unrelated, this value will be 0. If there is an opposite relationship between the two vectors, this time the cosine similarity value will be -1. (cos0 = 1, cos90 = 0, cos180 = -1)\n",
    "\n",
    "![img](https://i.imgur.com/KuBcMCg.png)"
   ],
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "source": [
    "def clst_pts(S, P):\n",
    "    clst_pts = []\n",
    "    final_list = []\n",
    "\n",
    "    for point in S:\n",
    "        dnmntr = math.sqrt((point[0] ** 2) + (point[1] ** 2)) * math.sqrt((P[0] ** 2) + (P[1] ** 2))\n",
    "        nmrtr = point[0] * P[0] + point[1] * P[1]\n",
    "\n",
    "        if dnmntr != 0:\n",
    "            cosine_distance_for_this_point = math.acos(nmrtr / dnmntr)\n",
    "            clst_pts.append((cosine_distance_for_this_point, point))\n",
    "\n",
    "    for item in sorted(clst_pts, key=lambda x: x[0])[:5]:\n",
    "        final_list.append(item[1])\n",
    "\n",
    "    return final_list\n",
    "\n",
    "\n",
    "S = [(1, 2), (3, 4), (-1, 1), (6, -7), (0, 6), (-5, -8), (-1, -1), (6, 0), (1, -1)]\n",
    "P = (3, -4)\n",
    "\n",
    "clst_pts = clst_pts(S, P)\n",
    "print(\"Closest point-cosine-distance - top 5:\", *[point for point in clst_pts], sep=\"\\n\")\n"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "5 Closest point to P based on cosine-distance:\n",
      "(6, -7)\n",
      "(1, -1)\n",
      "(6, 0)\n",
      "(-5, -8)\n",
      "(-1, -1)\n"
     ]
    }
   ],
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q:  Fast way to list all primes number below n\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "import itertools\n",
    "def erat2( ):\n",
    "    D = {  }\n",
    "    yield 2\n",
    "    for q in itertools.islice(itertools.count(3), 0, None, 2):\n",
    "        p = D.pop(q, None)\n",
    "        if p is None:\n",
    "            D[q*q] = q\n",
    "            yield q\n",
    "        else:\n",
    "            x = p + q\n",
    "            while x in D or not (x&1):\n",
    "                x += p\n",
    "            D[x] = p\n",
    "\n",
    "def get_primes_erat(n):\n",
    "  return list(itertools.takewhile(lambda p: p < n, erat2()))\n",
    "\n",
    "print(get_primes_erat(30))"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: Find all prime factors of a number.\n",
    "\n",
    "Example: prime factors of 56 are\n",
    "\n",
    "2, 2, 2, 7\n",
    "\n"
   ],
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "source": [
    "import math\n",
    "\n",
    "def generate_prime_factors(n):\n",
    "    p_factors_list = []\n",
    "\n",
    "    while n % 2 == 0:\n",
    "        p_factors_list.append(2)\n",
    "        n = n / 2\n",
    "\n",
    "    for i in range(3, int(math.sqrt(n)) + 1, 2):\n",
    "        while n % i == 0:\n",
    "            p_factors_list.append(int(i))\n",
    "            n = n / i\n",
    "\n",
    "    if n > 1:\n",
    "        p_factors_list.append(int(n))\n",
    "\n",
    "    return p_factors_list\n",
    "\n",
    "\n",
    "print(generate_prime_factors(84))"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[2, 2, 3, 7]\n"
     ]
    }
   ],
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: Implement formulae of permutations and combinations.\n",
    "\n",
    "Number of permutations of n objects taken r at a time: p(n, r) = n! / (n-r)!"
   ],
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "source": [
    "from math import factorial\n",
    "\n",
    "def p(n, r):\n",
    "    return int(factorial(n) / factorial(n - r))\n",
    "\n",
    "\n",
    "def c(n, r):\n",
    "    return int(factorial(n) / (factorial(r) * factorial(n - r)))\n",
    "\n",
    "\n",
    "print(p(7, 3))\n",
    "print(c(7, 3))\n",
    "\n",
    "\n",
    "# Without using math.factorial\n",
    "\n",
    "def generate_factrl(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * factorial(n - 1)\n",
    "\n",
    "\n",
    "def permutation(n, r):\n",
    "    return int(generate_factrl(n) / generate_factrl(n - r))\n",
    "\n",
    "\n",
    "def combination(n, r):\n",
    "    return int(factorial(n) / (factorial(r) * factorial(n-r)))\n",
    "\n",
    "\n",
    "print(permutation(7, 3))\n",
    "print(combination(7, 3))"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "210\n",
      "35\n",
      "210\n",
      "35\n"
     ]
    }
   ],
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: Converts a decimal number to binary number\n",
    "\n",
    "\n",
    "Performing Short Division by Two with Remainder (For integer part)\n",
    "\n",
    "This is a straightforward method which involve dividing the number to be converted. Let decimal number is N then divide this number from 2 because base of binary number system is 2. Note down the value of remainder, which will be either 0 or 1. Again divide remaining decimal number till it became 0 and note every remainder of every step. Then write remainders from bottom to up (or in reverse order), which will be equivalent binary number of given decimal number. This is procedure for converting an integer decimal number, algorithm is given below.\n",
    "\n",
    "Take decimal number as dividend.\n",
    "\n",
    "Divide this number by 2 (2 is base of binary so divisor here).\n",
    "\n",
    "Store the remainder in an array (it will be either 0 or 1 because of divisor 2).\n",
    "\n",
    "Repeat the above two steps until the number is greater than zero.\n",
    "\n",
    "Print the array in reverse order (which will be equivalent binary number of given decimal number).\n",
    "\n",
    "Note that dividend (here given decimal number) is the number being divided, the divisor (here base of binary, i.e., 2) in the number by which the dividend is divided, and quotient (remaining divided decimal number) is the result of the division.\n",
    "\n",
    "Example for number = 112\n",
    "\n",
    "Divisision Remainder (R) 112 / 2 = 56 Remainder-0 56 / 2 = Remainder-28 0 28 / 2 = Remainder-14 0 14 / 2 = Remainder-7 0 7 / 2 = 3 Remainder-1 3 / 2 = 1 Remainder-1 1 / 2 = 0 Remainder-1\n",
    "\n",
    "Now, write remainder from bottom to up (in reverse order), this will be 1110000 which is equivalent binary number of decimal integer 112."
   ],
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "source": [
    "def decimal_to_binary(number):\n",
    "    if number == 0:\n",
    "        return ''\n",
    "    else:\n",
    "        return decimal_to_binary(number // 2) + str(number % 2)\n",
    "\n",
    "print(decimal_to_binary(112))"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1110000\n"
     ]
    }
   ],
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: Find whether a given line (equation in x and y ) is able to separate the two lists of points (tuples) successfully\n",
    "\n",
    "consider you have given two set of data points in the form of list of tuples like\n",
    "\n",
    "```\n",
    "Red =[(R11,R12),(R21,R22),(R31,R32),(R41,R42),(R51,R52),..,(Rn1,Rn2)]\n",
    "\n",
    "Blue=[(B11,B12),(B21,B22),(B31,B32),(B41,B42),(B51,B52),..,(Bm1,Bm2)]\n",
    "```\n",
    "\n",
    "and set of line equations(in the string format, i.e list of strings)\n",
    "\n",
    "```\n",
    "Lines = [a1x+b1y+c1, a2x+b2y+c2, a3x+b3y+c3, a4x+b4y+c4,.., K lines]\n",
    "```\n",
    "Note: you need to do string parsing here and get the coefficients of x,y and intercept\n",
    "\n",
    "your task is for each line that is given print \"YES\"/\"NO\", you will print yes, if all the red points are one side of the line and blue points are other side of the line, otherwise no\n",
    "\n",
    "Example :-\n",
    "\n",
    "Red= [(1,1),(2,1),(4,2),(2,4), (-1,4)]\n",
    "Blue= [(-2,-1),(-1,-2),(-3,-2),(-3,-1),(1,-3)]\n",
    "\n",
    "Lines=[\"1x+1y+0\",\"1x-1y+0\",\"1x+0y-3\",\"0x+1y-0.5\"]\n",
    "\n",
    "![img](https://i.imgur.com/DoQf7mE.jpg)\n",
    "\n",
    "#### Output:\n",
    "\n",
    "YES\n",
    "NO\n",
    "NO\n",
    "YES\n",
    "\n",
    "### Solution and Explanations and Notes on methods, steps, algorithms\n",
    "\n",
    "Math Theory - If the line equation is $y=ax+b$ and the coordinates of a point is $(x_0,y_0)$ then compare $y_0$ and $ax_0+b$, for example if $y_0>ax_0+b$ then the point is above the line, etc.\n",
    "\n",
    "In this particular case - Mathematically to find if 2 points lie on the opposite side of a line -\n",
    "\n",
    "### Mathematics to determine if 2 points are on opposite sides of a line\n",
    "\n",
    "#### Find the equation of the line. It should be of the form $ax + by + c = 0$. Given two points $(x_1, y_2)$ and $(x_2, y_2)$, plug these into that equation. They are on opposite side of the line if $ax_1 + by_1 + c < 0$ and $ax_2 + by_2 + c > 0$, or visa-versa.\n",
    "\n",
    "[Source](https://math.stackexchange.com/a/162730/517433)\n",
    "\n",
    "\n",
    "So I take the equation of the line, say \"1x+1y+0\"\n",
    "\n",
    "Now consider 2 points (1,1) and (-6,-1)\n",
    "\n",
    "For point (1, 1) => 1(1)+ 1(1) = 2 which is > 0\n",
    "\n",
    "For point (-6, -1) = 1(-6)+(1)(-1) = -7 which is < 0\n",
    "\n",
    "Therefore, we can conclude that (1,1) and (-6,-1) lie on different sides of the line S.\n",
    "\n",
    "Now in the given problem, given an equation - all red should be on one side of the equation and blue on the other side.\n",
    "\n",
    "#### General Mathematical Principle\n",
    "\n",
    "\n",
    "### Here's the Algorithm I will follow for the below Python Implementation\n",
    "\n",
    "- The question already mentioned - \"you need to do string parsing here and get the coefficients of x,y and intercept\"\n",
    "- I know the string in the Equation will be of the form `some_number*x` and `some_number*y`, where the 'some_number' is the coefficients of x and y. So I need to break the string up in such a way that I am only left with just the numbers, and then replace the value of x and y in the equation with the value of the points that I am evaluating.\n",
    "- Initiate a variable `sign_of_equation_with_red_point_tuple` to be minus 1 (-1)\n",
    "- Take the first tuple of the Red_side list (i.e.  red[0][0] and red[0][1] )  and replace then into the Equation. If sign of Equation becomes  positive with this, then change `sign_of_equation_with_red_point_tuple` to be plus 1 ( 1 )\n",
    "- Now assuming `sign_of_equation_with_red_point_tuple` to be plus one ( 1 ) do the below step\n",
    "- One by one, check for all the Red side's tuples (points) - if Equation sign becomes negative for any point > That means that single point is on the other side of the Line Equation.\n",
    "- So in that case, then return 'NO' from the function.\n",
    "- Similarly in the next step, assuming `sign_of_equation_with_red_point_tuple` to be negaive 1 (-1), do the below step\n",
    "- Ony by one, check for all the Red side's tuples (points) - if Equation sign becomes positive for any point > That means that single point is on the other side of the Line Equation.\n",
    "- So in that case, then return 'NO' from the function.\n",
    "- Do both the above steps for the Blue side as well.\n",
    "- And if none of the above 4 steps returns a 'NO' ans, then finally return 'YES' from the function.\n"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "source": [
    "import math\n",
    "\n",
    "\n",
    "def find_who(red, blue, line):\n",
    "    sign_of_r_pts_eq = -1\n",
    "\n",
    "    if eval(line.replace('x', '*%s' % red[0][0]).replace('y', '*%s' % red[0][1])) > 0:\n",
    "        sign_of_r_pts_eq = 1\n",
    "\n",
    "    for r_pt in red:\n",
    "        if sign_of_r_pts_eq == 1 and eval(\n",
    "                line.replace('x', '*%s' % r_pt[0]).replace('y', '*%s' % r_pt[1])) < 0:\n",
    "            return 'NO'\n",
    "\n",
    "        if sign_of_r_pts_eq == -1 and eval(\n",
    "                line.replace('x', '*%s' % r_pt[0]).replace('y', '*%s' % r_pt[1])) > 0:\n",
    "            return 'NO'\n",
    "\n",
    "\n",
    "    sign_of_b_pts_eq = -1 * sign_of_r_pts_eq\n",
    "\n",
    "    for b_pts in blue:\n",
    "        if sign_of_b_pts_eq == 1 and eval(\n",
    "                line.replace('x', '*%s' % b_pts[0]).replace('y', '*%s' % b_pts[1])) < 0:\n",
    "            return 'NO'\n",
    "\n",
    "        if sign_of_b_pts_eq == -1 and eval(\n",
    "                line.replace('x', '*%s' % b_pts[0]).replace('y', '*%s' % b_pts[1])) > 0:\n",
    "            return 'NO'\n",
    "\n",
    "    return 'YES'\n",
    "\n",
    "\n",
    "Red = [(1, 1), (2, 1), (4, 2), (2, 4), (-1, 4)]\n",
    "Blue = [(-2, -1), (-1, -2), (-3, -2), (-3, -1), (1, -3)]\n",
    "\n",
    "Lines = [\"1x+1y+0\", \"1x-1y+0\", \"1x+0y-3\", \"0x+1y-0.5\"]\n",
    "\n",
    "for i in Lines:\n",
    "    yes_or_no = find_who(Red, Blue, i)\n",
    "    print(yes_or_no)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "YES\n",
      "NO\n",
      "NO\n",
      "YES\n"
     ]
    }
   ],
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: Implement Log-Loss Function in Plain Python\n",
    "\n",
    "You will be given a list of lists, each sublist will be of length 2 i.e. [[x,y],[p,q],[l,m]..[r,s]]\n",
    "consider its like a matrix of n rows and two columns\n",
    "\n",
    "- a. the first column Y will contain integer values\n",
    "- b. the second column $Y_{score}$ will be having float values <br>\n",
    "\n",
    "Your task is to find the value of the below\n",
    "\n",
    "![img](https://i.imgur.com/de0qTf4.png)\n",
    "\n",
    "Ex:\n",
    "[[1, 0.4], [0, 0.5], [0, 0.9], [0, 0.3], [0, 0.6], [1, 0.1], [1, 0.9], [1, 0.8]]\n",
    "output:\n",
    "0.4243099\n",
    "\n",
    "### Explanations and Notes on Log Loss\n",
    "\n",
    "Logarithmic Loss (i.e. Log Loss and also same as Cross Entropy Loss), is a classification loss function. Log Loss quantifies the accuracy of a classifier by penalising false classifications. Minimising the Log Loss is basically equivalent to maximising the accuracy of the classifier.\n",
    "\n",
    "Log loss is used when we have {0,1} response. In these cases, the best models give us values in terms of probabilities. The log loss function is simply the objective function to minimize, in order to fit a log linear probability model to a set of binary labeled examples.\n",
    "\n",
    "![img](https://i.imgur.com/IVGQ307.png)\n",
    "\n",
    "In slightly different form Log is expressed as\n",
    "\n",
    "![img](https://i.imgur.com/DmdC21x.png)\n",
    "\n",
    "Log Loss is a slight modification on the Likelihood Function. In fact, Log Loss is -1 * the log of the likelihood function.\n",
    "\n",
    "Log Loss measures the accuracy of a classifier. It is used when the model outputs a probability for each class, rather than just the most likely class.\n",
    "\n",
    "In simple words, log loss measures the UNCERTAINTY of the probabilities of your model by comparing them to the true labels. Let us look closely at its formula and see how it measures the UNCERTAINTY.\n",
    "\n",
    "Now the question is, your training labels are 0 and 1 but your training predictions are 0.4, 0.6, 0.89, 0.1122 etc.. So how do we calculate a measure of the error of our model ? If we directly classify all the observations having values > 0.5 into 1 then we are at a high risk of increasing the miss-classification. This is because it may so happen that many values having probabilities 0.4, 0.45, 0.49 can have a true value of 1.\n",
    "\n",
    "**This is where logLoss comes into picture.**\n",
    "\n",
    "Log-loss is a “soft” measurement of accuracy that incorporates the idea of probabilistic confidence. It is intimately tied to information theory: log-loss is the cross entropy between the distribution of the true labels and the predictions. Intuitively speaking, entropy measures the unpredictability of something. Cross entropy incorporate the entropy of the true distribution, plus the extra unpredictability when one assumes a different distribution than the true distribution. So log-loss is an information-theoretic measure to gauge the “extra noise” that comes from using a predictor as opposed to the true labels. By minimizing the cross entropy, one maximizes the accuracy of the classifier.\n",
    "\n",
    "\n",
    "### Cases where Log-Loss function can be mostly used\n",
    "\n",
    "The log loss function is used as evaluation metric of the ML classifier models. This is an important metric as it is only metric which uses the actual predicted probability for evaluating the model ( ROC - AUC uses the order of the values but not the actual values). This is very useful as this penalizes the model heavily if it is very confident in predicting the wrong class(please check the plot of -log(x)). We optimize our model to minimize the log loss. Hence this metric is very useful in the cases where the cost of predicting wrong class is very high. Hence model tries to reduce the probabilities of belonging to wrong class and we can choose the higher threshold of probability to predict the class label. This metric can be used for both binary and multi class classifications. The value of log loss lies between 0 ( including) and infinity. This is the only disadvantage of log loss as it is not very interpretable. We know that the best case would be 0 value of log loss however we can not interpret other values of log loss. For some cases log loss of 1 can be good while for other it may not be good enough. One hack is that we can measure the log loss of random model and try to reduce log-loss of our actual model from this value as much as possible without increasing variance much.\n",
    "\n",
    "Please note that this metric can only be used if our model can predict the probability of each class. Hence for calculating the log loss for the models which don't provide the probability score, probability calibration methods can be used on top of the base classifier to predict the probability score for each class.\n",
    "\n",
    "### An use-case of Logloss\n",
    "\n",
    "Say, I am predicting Cancer from my ML Model. And Suppose you have 5 cases. 2 cases were cancer (y1 = y2 = 1) and 3 cases were benign (y3 = y4 = y5 = 0). Say your model predicted each model has 0.5 probability of cancer. In this case, what we have for log loss is…\n",
    "\n",
    "−1/5∗(log(0.5)+log(0.5)+(1−0)∗log(1−0.5)+(1−0)∗log(1−0.5)+(1−0)∗log(1−0.5))\n",
    "\n",
    "Essentially, y_i and (1 - y_i) determines which term is to be dropped depending on the ground truth label. Depending on ground truth, either the log (y_hat) or log(1-y_hat) will be selected to determines how far away from truth your model’s generated probability is.\n",
    "\n",
    "We can use the log_loss function from scikit-learn, with documentation found [here](http://scikit-learn.org/stable/modules/generated/sklearn.metrics.log_loss.html): But here we will implement a pure-python version"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "source": [
    "from math import log\n",
    "\n",
    "\n",
    "def get_loss_log(matrix):\n",
    "    logistic_loss = 0\n",
    "    for row in matrix:\n",
    "        logistic_loss += (row[0] * log(row[1], 10) + ((1 - row[0]) * log(1 - row[1], 10)))\n",
    "\n",
    "    log_loss = -1 * logistic_loss / len(matrix)\n",
    "    return log_loss\n",
    "\n",
    "\n",
    "A = [[1, 0.4], [0, 0.5], [0, 0.9], [0, 0.3], [0, 0.6], [1, 0.1], [1, 0.9], [1, 0.8]]\n",
    "print(get_loss_log(A))"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "0.42430993457031635\n"
     ]
    }
   ],
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q: Average Words Length\n",
    "\n",
    "For a given sentence, return the average word length.\n",
    "Note: Remember to remove punctuation first."
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "sentence1 = \"Hello, its a beautiful morning, today.\"\n",
    "sentence2 = \"I love algorithms in Python!\"\n",
    "\n",
    "def solution(sentence):\n",
    "    for p in \"!?',;.\":\n",
    "        sentence = sentence.replace(p, '')\n",
    "    words = sentence.split()\n",
    "    return round(sum(len(word) for word in words)/len(words),2)\n",
    "\n",
    "print(solution(sentence1))\n",
    "print(solution(sentence2))"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q:  Gradient Descent in Python from scratch without using any library"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "'''\n",
    "  Gradient Descent for a single feature\n",
    "  It will NOT work for multiple feature\n",
    "'''\n",
    "\n",
    "number_of_data_points = 50\n",
    "\n",
    "# For predictor x, generate a Numpy array containing number betwen 2 and 9\n",
    "x = np.random.randint(2, 9, number_of_data_points)\n",
    "\n",
    "# print('x before dataframe ', x)\n",
    "x = pd.DataFrame(x)\n",
    "# print('df ', x)\n",
    "\n",
    "# Standardize x\n",
    "x = (x - x.mean()) / x.std()\n",
    "\n",
    "# ***************************************************************\n",
    "\n",
    "# Add one column for gradient-descent\n",
    "x = np.c_[np.ones(x.shape[0]), x]\n",
    "# print('x after adding one column ', x)\n",
    "\n",
    "# For the target variable y, generate a Numpy array containing number betwen 1 and 26\n",
    "y = np.random.randint(1, 26, number_of_data_points )\n",
    "y = pd.DataFrame(y, columns = ['Y-Value'])\n",
    "y = y['Y-Value']\n",
    "\n",
    "# ********* Now the Gradient descent formulae implementation **********\n",
    "\n",
    "alpha = 0.01 # Learning Step size\n",
    "iterations = 100 #No. of iterations\n",
    "np.random.seed(123) #Set the seed\n",
    "theta = np.random.rand(2) #Pick some random values to start with\n",
    "\n",
    "\n",
    "#GRADIENT DESCENT\n",
    "def gradient_descent(x, y, theta, iterations, alpha):\n",
    "    prev_cost = []\n",
    "    prev_thetas = [theta]\n",
    "    for i in range(iterations):\n",
    "        prediction = np.dot(x, theta)\n",
    "        error = prediction - y\n",
    "\n",
    "        cost = 1/(2*number_of_data_points) * np.dot(error.T, error)\n",
    "        prev_cost.append(cost)\n",
    "        theta = theta - (alpha * (1/number_of_data_points) * np.dot(x.T, error))\n",
    "        prev_thetas.append(theta)\n",
    "\n",
    "    return prev_thetas, prev_cost\n",
    "\n",
    "prev_thetas, prev_cost = gradient_descent(x, y, theta, iterations, alpha)\n",
    "theta = prev_thetas[-1]\n",
    "\n",
    "print(\"Gradient Descent: {:.2f}, {:.2f}\".format(theta[0], theta[1]))"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "# Q:  Check if one string is a rotation of other string\n",
    "\n",
    "Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?\n",
    "\n",
    "Example:\n",
    "\n",
    "If s1 = \"stackoverflow\" then the following are some of its rotated versions:\n",
    "\n",
    "```\n",
    "\"tackoverflows\"\n",
    "\"ackoverflowst\"\n",
    "\"overflowstack\"\n",
    "```\n",
    "\n",
    "Where as \"stackoverflwo\" is not a rotated version.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "First make sure s1 and s2 are of the same length. Then check to see if s2 is a substring of s1 concatenated with s1:\n",
    "\n",
    "Joining of two or more strings into a single one is called concatenation.\n",
    "\n",
    "The + operator does this in Python. Simply writing two string literals together also concatenates them.\n",
    "\n",
    "The * operator can be used to repeat the string for a given number of times.\n",
    "\n",
    "str1 = 'Hello'\n",
    "str2 ='World!'\n",
    "\n",
    "#### using +\n",
    "print('str1 + str2 = ', str1 + str2)\n",
    "\n",
    "#### using *\n",
    "print('str1 * 3 =', str1 * 3)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def is_rotation(s1, s2):\n",
    "    if s1 is None or s2 is None:\n",
    "        return False\n",
    "    if len(s1) != len(s2):\n",
    "        return False\n",
    "    return s1 in (s2+s2)\n",
    "\n",
    "s1 = \"stackoverflow\"\n",
    "\n",
    "s2 = \"stackoverflwo\" # Should return False\n",
    "# s2 = \"tackoverflows\" # Should return True\n",
    "# s2 = \"ackoverflowst\" # Should return True\n",
    "# s2 = \"overflowstack\" # Should return True\n",
    "\n",
    "print(is_rotation(s1, s2))\n",
    "\n",
    "### Alternative version\n",
    "\n",
    "def is_rotation_alternative(s1, s2):\n",
    "  return len(s1) ==len(s2) and s1 in 2*s2"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "In above in operator : The ‘in’ operator is used to check if a value exists in a sequence or not. Evaluates to true if it finds a variable in the specified sequence and false otherwise.\n",
    "\n",
    "---\n",
    "\n",
    "# Q: Some useful and tricky Python script\n",
    "\n",
    "### Q:  Get laptops charging value\n",
    "\n",
    "```python\n",
    "\n",
    "import  psutil\n",
    "\n",
    "print (\"battery charge left: \" + str(psutil.sensors_battery()[0]) + \"%\")\n",
    "\n",
    "# battery charge left: 25.0%\n",
    "\n",
    "\"\"\" If I run the above function in a desktop machine will get\n",
    "\n",
    "TypeError: 'NoneType' object is not subscriptable\n",
    "\n",
    "\"\"\"\n",
    "# And alternative way to get the above along with\n",
    "# how many minutes of charging left\n",
    "\n",
    "import psutil as ps\n",
    "\n",
    "batterystats = dict(ps.sensors_battery()._asdict())\n",
    "print(batterystats)\n",
    "timeleft = batterystats.get('secsleft')\n",
    "percent = batterystats.get('percent')\n",
    "\n",
    "print('battery percent : '+str(percent)+'%')\n",
    "print('time left (secs) : '+str(timeleft)+' secs')\n",
    "\n",
    "\"\"\"\n",
    "{'percent': 25.0, 'secsleft': <BatteryTime.POWER_TIME_UNLIMITED: -2>, 'power_plugged': True}\n",
    "battery percent : 25.0%\n",
    "time left (secs) : 680 secs\n",
    "\"\"\"\n",
    "\n",
    "```\n",
    "## Get high precision time\n",
    "\n",
    "Say, I need to print a message right at 08:00:00.000000. Hence, I tried to get the current time of my system with microsecond precision. To do so, I used datetime.datetime.now(). But, I found something weird, that made me think it is not that accurate. When I run the following code on a system with Intel (R) Corei7-8550U CPU @ 1.80GHz 1.99GHz and Windows 10:\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "import datetime\n",
    "import time\n",
    "\n",
    "x = datetime.datetime.now()\n",
    "t=2**10000\n",
    "y = datetime.datetime.now()\n",
    "print(x, '\\n', y)"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Will give you get exact same times, e.g.:\n",
    "\n",
    "2020-07-13 02:28:28.763578 2020-07-13 02:28:28.763602\n",
    "\n",
    "So to resolve the above lack of precision, we can depend onf time.time_ns() - which was introduced in Python 3.7 as new functions to the time module providing higher resolution:\n",
    "\n",
    "https://docs.python.org/3/library/time.html - Similar to time() but returns time as an integer number of nanoseconds since the epoch."
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "time1 = time.time_ns()\n",
    "print(time1)\n",
    "\n",
    "\n",
    "time2 = time.time_ns() / (10 ** 9)\n",
    "# The above will convert to floating-point seconds\n",
    "print(time2)"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Replace characters from file name in local Machine's Directory\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "import os\n",
    "import shutil\n",
    "import sys\n",
    "import re\n",
    "\n",
    "# REPLACE ALL SPACES - MOST USED ONE\n",
    "for root, dirs, files in os.walk(sys.argv[1], topdown=False):\n",
    "    for f in files:\n",
    "        shutil.move(\n",
    "            os.path.join(root, f), os.path.join(root, f.replace(\"some random characters\", \"\").strip())\n",
    "        )\n",
    "    for dr in dirs:\n",
    "        shutil.move(\n",
    "            os.path.join(root, dr),  os.path.join(root, dr.replace(\"some random characters\", \"\").strip())\n",
    "        )"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Execute the above code file like below\n",
    "\n",
    "python name-of-this-python-file.py path-of-directory-where-you-want-to-replace-this-character\n",
    "\n",
    "---\n",
    "\n",
    "## Implement 1-D Random Walk and show the plotting with matplotlib.pyplot :\n",
    "\n",
    "The number of steps that we require is the only argument that the function will take\n",
    "\n",
    "For a 1D random walk, we consider that the motion is going to be in just two directions i.e. either up or down, or left or right.\n",
    "\n",
    "#### Lets implement following rules in the Random Walk\n",
    "\n",
    "- a. if step is less than 0.5 we move up\n",
    "- b. if step is greater than 0.5 we move down\n",
    "\n",
    "### Some note on Random walk\n",
    "\n",
    "The random walk is central to statistical physics.  It is essential in predicting how fast one gas will diffuse into another, how fast heat will spread in a solid, how big fluctuations in pressure will be in a small container, and many other statistical phenomena.\n",
    "\n",
    "Einstein used the random walk to find the size of atoms from the Brownian motion. The movement is also known as drunkard's walk. You may have experienced this after a very wet night on a pub: you step forward and backward in a random fashion.  What may come as a surprise is the following fact: even when there is equal probability of going forward and backward, one can prove mathematically that the drunkard will always reach his home. Or more precisely, he will get home in finite time\n",
    "\n",
    "One-dimensional random walk An elementary example of a random walk is the random walk on the integer number line, which starts at 0 and at each step moves +1 or ?1 with equal probability."
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def random_walk_1d(num):\n",
    "    x = 0\n",
    "    y = 0\n",
    "\n",
    "    # the random walk will start from origin (0,0)\n",
    "    # Create an array of positions for the walker.  And initialize the first position\n",
    "    #to be the origin (zero).  The array will be the same size as the number of steps.\n",
    "    x_position = [0]\n",
    "    y_position = [0]\n",
    "\n",
    "    for i in range(1, num + 1):\n",
    "        random_step = np.random.uniform(0, 1)\n",
    "        if random_step < 0.5: # if step is less than 0.5 we move up\n",
    "            x += 1\n",
    "            y += 1\n",
    "        if random_step >= 0.5: # if step is greater than 0.5 we move down\n",
    "            x += 1\n",
    "            y -= 1\n",
    "\n",
    "        x_position.append(x)\n",
    "        y_position.append(y)\n",
    "\n",
    "    return [x_position, y_position]\n",
    "\n",
    "random_walk = random_walk_1d(1000)\n",
    "plt.plot(random_walk[0], random_walk[1], 'r-', label='Random walk 1D')\n",
    "# 'r-' for making the color of the path red\n",
    "plt.title('Plotting 1-D Random walk')\n",
    "plt.show()"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Find Sum of Digits / Digital Root\n",
    "\n",
    "[Digital root](https://en.wikipedia.org/wiki/Digital_root) is the recursive sum of all the digits in a number.\n",
    "\n",
    "Given n, take the sum of the digits of n. If that value has more than one digit, continue reducing in this way until a single-digit number is produced. The input will be a non-negative integer.\n",
    "\n",
    "Examples\n",
    "\n",
    "```\n",
    "    16  -->  1 + 6 = 7\n",
    "   942  -->  9 + 4 + 2 = 15  -->  1 + 5 = 6\n",
    "132189  -->  1 + 3 + 2 + 1 + 8 + 9 = 24  -->  2 + 4 = 6\n",
    "493193  -->  4 + 9 + 3 + 1 + 9 + 3 = 29  -->  2 + 9 = 11  -->  1 + 1 = 2\n",
    "\n",
    "```\n",
    "From [Wikipedia](https://en.wikipedia.org/wiki/Digital_root)\n",
    "\n",
    "![Imgur](https://imgur.com/z1qFSHv.png)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "def digital_root(n):\n",
    "    i = 1\n",
    "    temp = 1\n",
    "    root_sum = 0\n",
    "\n",
    "    while n > 9:\n",
    "        root_sum = 0\n",
    "        temp = str(n)\n",
    "        for j in range(len(temp)):\n",
    "            root_sum += int(temp[j])\n",
    "            # the above will sum all the elements of the value of n at this poin\n",
    "            # e.g. if n is 456 for the first run of this while loop\n",
    "            # root_sum will be 15\n",
    "\n",
    "        # now after each for loop, update n by reducing it\n",
    "        n = root_sum\n",
    "\n",
    "    return root_sum\n",
    "\n",
    "print(digital_root(456))\n",
    "# 6\n"
   ],
   "outputs": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}