{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "south-central",
   "metadata": {},
   "source": [
    "# Basic operations, control structure, operations (10/2-2021)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "pending-network",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Print numbers 1 to 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "latter-transparency",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# This is not the way to do it... If you copy paste code, there is likely a better way\n",
    "\n",
    "print(1)\n",
    "print(2)\n",
    "print(3)\n",
    "print(4)\n",
    "print(5)\n",
    "print(6)\n",
    "print(7)\n",
    "print(8)\n",
    "print(9)\n",
    "print(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "sticky-genetics",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 10 \n"
     ]
    }
   ],
   "source": [
    "# better, but perhaps 10 should not be hardcoded into the while loop\n",
    "\n",
    "i = 1\n",
    "while i <= 10:\n",
    "    print(i, end=' ')\n",
    "    i = i + 1\n",
    "print()\n",
    "# print('after the loop i =', i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "crazy-manual",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# better have constants defined as a variable somewhere\n",
    "\n",
    "n = 10\n",
    "\n",
    "i = 1\n",
    "while i <= n:\n",
    "    print(i)\n",
    "    i = i + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "polished-unemployment",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Print the sum of a list of values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "returning-interference",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40\n"
     ]
    }
   ],
   "source": [
    "# ok, this would be cheating for now...\n",
    "\n",
    "A = [3, 2, 6, 7, 10, 12]\n",
    "\n",
    "print(sum(A))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "objective-viking",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum is: 40\n"
     ]
    }
   ],
   "source": [
    "# loop over the values\n",
    "\n",
    "A = [3, 2, 6, 7, 10, 12]\n",
    "\n",
    "i = 0\n",
    "s = 0\n",
    "while i < len(A):\n",
    "    s = s + A[i]\n",
    "    # print(i,  A[i], s)\n",
    "    i = i + 1\n",
    "print('The sum is:', s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "opening-bahrain",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Print the maximum in a list of values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "preliminary-gregory",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n"
     ]
    }
   ],
   "source": [
    "# ok, cheating...\n",
    "\n",
    "A = [3, 2, 6, 12, 10, 7]\n",
    "\n",
    "print(max(A))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "rough-escape",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "max value = 12\n"
     ]
    }
   ],
   "source": [
    "# ok, a solution if there is a non-negative number - but what if all numbers are negative\n",
    "\n",
    "# A = [x, x, x, x, x, x, x, x, x, x, x, x, x, x, x]\n",
    "#      |                             |  |\n",
    "#      |------ max_value = max ------|  i\n",
    "\n",
    "A = [3, 2, 6, 12, 10, 7]\n",
    "\n",
    "i = 0\n",
    "max_value = 0\n",
    "while i < len(A):\n",
    "    #print(i, A[i])\n",
    "    if A[i] > max_value:\n",
    "        max_value = A[i]\n",
    "        #print('new maximum value', max_value)        \n",
    "    i = i + 1  # or i += 1\n",
    "print('max value =', max_value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "material-armor",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "max value = -2\n"
     ]
    }
   ],
   "source": [
    "# better initialize max_value to the first value\n",
    "\n",
    "A = [-5, -3, -10, -4, -2, -8]\n",
    "\n",
    "max_value = A[0]\n",
    "i = 1\n",
    "while i < len(A):\n",
    "    # print(i, A[i])\n",
    "    if A[i] > max_value:\n",
    "        max_value = A[i]\n",
    "        #print('new maximum value', max_value)        \n",
    "    i = i + 1  # or i += 1\n",
    "print('max value =', max_value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "distinct-recovery",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "max value = None\n"
     ]
    }
   ],
   "source": [
    "# in case list is empty, let the result be the special value None\n",
    "\n",
    "A = [-5, -3, -10, -4, -2, -8]\n",
    "#A = [3, 2, 7, 5]\n",
    "A = []\n",
    "\n",
    "if len(A) > 0:  # or \"if len(A):\" or just \"if A:\"\n",
    "    max_value = A[0]\n",
    "    i = 1\n",
    "    while i < len(A):\n",
    "        if A[i] > max_value:\n",
    "            max_value = A[i]\n",
    "        i += 1\n",
    "else:\n",
    "    max_value = None\n",
    "    \n",
    "print('max value =', max_value)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "induced-turner",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Count the number of occurrences of a character in a string, e.g. 'c' occours 4 times in 'abccbbacbabc'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "finite-crystal",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "there are 10 occurences of a in abaabababaaababab\n"
     ]
    }
   ],
   "source": [
    "c = 'a'\n",
    "s = 'abaabababaaababab'\n",
    "\n",
    "i = 0 \n",
    "occurences = 0\n",
    "while i < len(s):\n",
    "    if s[i] == c:\n",
    "        occurences += 1\n",
    "    # print(s[i], occurences)\n",
    "    i += 1\n",
    "print('there are', occurences, 'occurences of', c, 'in', s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "arabic-month",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Find the largest number of consecutive identical characters in a string, e.g. for 'abbacccbaa' the answer is 3 because of 'ccc'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "declared-supplier",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum block of identical characters is ccc with length 3\n"
     ]
    }
   ],
   "source": [
    "s = 'aabbccabaddddddabcccccddd'\n",
    "s = 'abbacccbaa'\n",
    "\n",
    "max_block = 0\n",
    "i = 0\n",
    "start = 0\n",
    "end = 0\n",
    "\n",
    "while i < len(s):\n",
    "    #print('i =', i)\n",
    "    j = i + 1\n",
    "    while j < len(s) and s[j] == s[i]:\n",
    "        #print('j =', j)\n",
    "        j = j + 1\n",
    "    #print(s[i:j])\n",
    "    length = j - i\n",
    "    if length > max_block:\n",
    "        max_block = length\n",
    "        start = i\n",
    "        end = j\n",
    "    i = j\n",
    "    \n",
    "print('Maximum block of identical characters is', s[start:end], 'with length', max_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "under-dealer",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Find the largest number of concecutive chars in a string that occure alphabetically, e.g. for 'abcxauefghvxuvw' the answer is 4 because of the substring 'efgh'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "biblical-visit",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "longest alphabetically increasing substring is efgh\n"
     ]
    }
   ],
   "source": [
    "s = 'abcxauefghvxuvw'\n",
    "\n",
    "#  s = xxxxxxdefghxxxxxxxx\n",
    "#            |   |        | \n",
    "#            i  i+k     len(s)\n",
    "\n",
    "i = 0\n",
    "\n",
    "longest = ''\n",
    "\n",
    "while i < len(s):\n",
    "    #print(i)\n",
    "    k = 1\n",
    "    while i + k < len(s) and ord(s[i + k - 1]) + 1 == ord(s[i + k]):\n",
    "        k += 1\n",
    "    #print(s[i:i+k])\n",
    "    if k > len(longest):\n",
    "        longest = s[i:i+k]\n",
    "    i += k\n",
    "    \n",
    "print('longest alphabetically increasing substring is', longest)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "honest-efficiency",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Find the position of an element in a sorted list, e.g. that 7 is at position 3 in [-2, 1, 3, 7, 10, 12]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "linear-findings",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "# cheating\n",
    "\n",
    "A = [1, 3, 5, 8, 10, 11, 13, 17, 20, 21]\n",
    "\n",
    "x = 13\n",
    "\n",
    "print(A.index(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "wanted-vacuum",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 is at position 6 in [1, 3, 5, 8, 10, 11, 13, 17, 20, 21]\n"
     ]
    }
   ],
   "source": [
    "# linear search\n",
    "\n",
    "A = [1, 3, 5, 8, 10, 11, 13, 17, 20, 21]\n",
    "\n",
    "x = 13\n",
    "\n",
    "position = None\n",
    "\n",
    "i = 0\n",
    "while i < len(A):\n",
    "    if A[i] == x:\n",
    "        position = i\n",
    "        break  # stop searching\n",
    "    i += 1\n",
    "\n",
    "if position == None:\n",
    "    print(x, 'is not in', A)\n",
    "else:\n",
    "    print(x, 'is at position', position, 'in', A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "bound-passing",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 is at position 2 in [1, 3, 5, 8, 10, 11, 13, 17, 20, 21]\n"
     ]
    }
   ],
   "source": [
    "# binary search\n",
    "\n",
    "A = [1, 3, 5, 8, 10, 11, 13, 17, 20, 21]\n",
    "\n",
    "x = 5\n",
    "\n",
    "#  A = [x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x]\n",
    "#                         |           |              |\n",
    "#                        low         mid            high\n",
    "#       ------- < x ---|                             |------ >= x ----\n",
    "\n",
    "low = -1\n",
    "high = len(A)\n",
    "\n",
    "while low < high:  # done when low == high\n",
    "    mid = (low + high) // 2\n",
    "\n",
    "    # print(low, mid, high)\n",
    "    \n",
    "    if A[mid] < x:\n",
    "        low = mid + 1\n",
    "    else:\n",
    "        high = mid\n",
    "\n",
    "if high < len(A) and A[high] == x:\n",
    "    print(x, 'is at position', high, 'in', A)\n",
    "else:\n",
    "    print(x, 'is not in', A)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "banned-worship",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linear search:\n",
      "333333 is not in A\n",
      "Search took 0.3958747386932373 seconds\n",
      "Binary search:\n",
      "333333 is not in A\n",
      "Search took 0.0 seconds\n"
     ]
    }
   ],
   "source": [
    "# timing comparison\n",
    "\n",
    "import random\n",
    "import time\n",
    "\n",
    "n = 1_000_000\n",
    "A = []\n",
    "\n",
    "i = 0\n",
    "while i < n:\n",
    "    r = random.randint(1, 2 * n)\n",
    "    A.append(r)\n",
    "    i = i + 1\n",
    "\n",
    "A.sort()\n",
    "\n",
    "x = n // 3\n",
    "\n",
    "print('Linear search:')\n",
    "\n",
    "position = None\n",
    "\n",
    "start = time.time()\n",
    "i = 0\n",
    "while i < len(A):\n",
    "    if A[i] == x:\n",
    "        position = i\n",
    "        break\n",
    "    i += 1\n",
    "end = time.time()\n",
    "\n",
    "if position == None:\n",
    "    print(x, 'is not in A')\n",
    "else:\n",
    "    print(x, 'is at position', position, 'in A')\n",
    "\n",
    "print('Search took', end - start, 'seconds')\n",
    "\n",
    "print('Binary search:')\n",
    "\n",
    "start = time.time()\n",
    "\n",
    "low = -1\n",
    "high = len(A)\n",
    "\n",
    "while low < high:  # done when low == high\n",
    "    mid = (low + high) // 2\n",
    "\n",
    "    # print(low, mid, high)\n",
    "    \n",
    "    if A[mid] < x:\n",
    "        low = mid + 1\n",
    "    else:\n",
    "        high = mid\n",
    "end = time.time()\n",
    "\n",
    "if high < len(A) and A[high] == x:\n",
    "    print(x, 'is at position', high, 'in A')\n",
    "else:\n",
    "    print(x, 'is not in A')\n",
    "\n",
    "print('Search took', end - start, 'seconds')"
   ]
  }
 ],
 "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}