Session1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8c360760-cb7f-40cf-a428-bdb3f3e2f2a3",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Algorithms\n",
    "https://fituska.eu/viewtopic.php?f=2066&t=25692\n",
    "\n",
    "https://fituska.eu/viewtopic.php?f=1859&t=25402\n",
    "\n",
    "https://visualgo.net/en\n",
    "\n",
    "https://algorithm-visualizer.org/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "ea33d3f2-6ee2-4e88-a23e-cbb3f623765c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import jp_flowchart_nocairo\n",
    "# %%pyflowchart_magic "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42fad55c-4051-4578-9909-6a3e15f2fa15",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Simple algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2be7a292-4d74-4507-9024-11adc7c9d56d",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Factorial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "b721db43-ebac-4ba9-83f8-f0255aa8784c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1! = 1\n",
    "# n! = n * (n - 1)!\n",
    "\n",
    "# 1! = 1\n",
    "# 3! = 1*2*3\n",
    "# 6! = 1*2*3*4*5*6\n",
    "\n",
    "def factorial_recursive(n: int) -> int:\n",
    "    if n <= 1:\n",
    "        return 1\n",
    "    return n * factorial_recursive(n - 1)\n",
    "\n",
    "def factorial_iterative(n: int) -> int:\n",
    "    x = 1\n",
    "    while n > 1:\n",
    "        x *= n\n",
    "        n -= 1\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e85c18f-de0f-4d9a-ba70-f51e5b929f85",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Fibonacci"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "21808186-6b2d-40db-b573-18604c332354",
   "metadata": {},
   "outputs": [],
   "source": [
    "# F(0) = 0\n",
    "# F(1) = 1\n",
    "# F(n) = F(n - 1) + F(n - 2)\n",
    "\n",
    "# F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144\n",
    "\n",
    "# F(2) = F(1) + F(0) = 0 + 1 = 1\n",
    "# F(3) = F(2) + F(1) = F(2) + F(1) + 0 = 1 + 1 + 0 = 2\n",
    "# F(4) = F(3) + F(2) = 2 + 1 = 3\n",
    "# F(5) = F(4) + F(3) = 3 + 2 = 5\n",
    "\n",
    "def fibonacci_recursive(n: int) -> int:\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)\n",
    "\n",
    "# Problem with recursive implementation, certain values calculated multiple times:\n",
    "#    F(5)\n",
    "#      F(4)\n",
    "#        F(3)\n",
    "#          F(2)\n",
    "#            F(1)\n",
    "#            F(0)\n",
    "#          F(1)\n",
    "#        F(2)\n",
    "#          F(1)\n",
    "#          F(0)\n",
    "#      F(3)\n",
    "#        F(2)\n",
    "#          F(1)\n",
    "#          F(0)\n",
    "#        F(1)\n",
    "\n",
    "# Solution: Memoization (Dynamic programming)\n",
    "# Saving already calculated values to a cache for further reference\n",
    "def fibonacci_memo(n: int, cache={0: 0, 1: 1}) -> int:\n",
    "    if n in cache:\n",
    "        return cache[n]\n",
    "    result = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)\n",
    "    cache[n] = result\n",
    "    return result\n",
    "\n",
    "# Using implicit lru_cache from functools\n",
    "from functools import lru_cache\n",
    "@lru_cache\n",
    "def fibonacci_lru(n: int) -> int:\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)\n",
    "\n",
    "# n=0, a=0, b=1\n",
    "# n=1, a=1, b=1\n",
    "# n=2, a=1, b=2\n",
    "# n=3, a=2, b=3\n",
    "# n=4, a=3, b=5\n",
    "def fibonacci_iterative(n):\n",
    "    a, b = 0, 1\n",
    "    for i in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42e8091e-41b3-44c7-920a-03a0cd9f483c",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Ackermann"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "2a34c3cc-714b-4ebb-9590-eb6c478e407a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# A(0, n) = n + 1\n",
    "# A(m, 0) = A(m - 1, 1)\n",
    "# A(m, n) = A(m - 1, A(m, n - 1))\n",
    "\n",
    "def ackermann(m: int, n: int) -> int:\n",
    "    if m == 0:\n",
    "        return n + 1\n",
    "    elif n == 0:  # and m != 0\n",
    "        return ackermann(m - 1, 1)\n",
    "    else:  # m != 0 and n != 0\n",
    "        return ackermann(m - 1, ackermann(m, n - 1))\n",
    "\n",
    "assert(ackermann(2, 1) == 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdfa1466-dc44-4ce1-ba1c-4d33af153c25",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Sum of digits of a number"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c21ce056-dc74-477b-a7f9-e1e0d91abbe7",
   "metadata": {},
   "source": [
    "- Inputs: the number N (N_0 + 10 * N_1 + 100 * N_2 + ...)\n",
    "- Outputs: N_0 + N_1 + N_2 + ...\n",
    "- Examples:\n",
    "  - f(345) = 3+4+5 = 12\n",
    "  - f(12) = 1+2 = 3\n",
    "  - f(3) = 3 = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "facedc72-adf4-4c41-91b5-bfa24b91c4e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# % (modulo) = \"zbytek po dělění\"\n",
    "# 123 // 10 = 12\n",
    "#   5 // 10 = 0\n",
    "# 123  % 10 = 3\n",
    "\n",
    "def sum_digits_recursive(n: int) -> int:\n",
    "    if n < 10:\n",
    "        return n\n",
    "    return (n % 10) + sum_digits_recursive(n // 10)\n",
    "\n",
    "def sum_digits_iterative(n: int) -> int:\n",
    "    x = 0\n",
    "    while n > 0:\n",
    "        x = x + n % 10\n",
    "        n = n // 10\n",
    "    return x\n",
    "\n",
    "def banned(num: int) -> int:\n",
    "    return sum(int(x) for x in str(num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "391faa8e-670d-4e6b-af67-98783f6c56ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert(sum_digits_recursive(345) == 12)\n",
    "assert(sum_digits_iterative(345) == 12)\n",
    "assert(banned(345) == 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f863311d-963a-447a-8d1f-b82752db111d",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## String representation of a number in a base"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1ffca66-aa47-4ce8-b042-dff689a65fd5",
   "metadata": {},
   "source": [
    "- Inputs: number N, base B\n",
    "- Outputs: string representing N in base B (`B * N_0 + B*B * N_1 + B*B*B * N_2 + ...`)\n",
    "- Numeric base:\n",
    "  - base 10, decimal system, 0123456789\n",
    "       0d123 = 1 * 10^2 + 2 * 10^1 + 3 * 10^0\n",
    "       0d123 = 1 * 100  + 2 * 10   + 3 * 1      = 123\n",
    "  - base 2, binary system, 01\n",
    "       0b101 = 1 * 2^2  + 0 * 2^1  + 1 * 2^0\n",
    "       0b101 = 1 * 4    + 0 * 2    + 1 * 1      = 5\n",
    "  - base 8, octal system, 01234567\n",
    "       0o123 = 1 * 8^2 + 2 * 8^1 + 3 * 8^0\n",
    "       0o123 = 1 * 64  + 2 * 8   + 3 * 1        = 75\n",
    "  - base 16, hexadecimal system, 0123456789abcdef\n",
    "       0xabc = 10 * 16^2 + 11 * 16^1 + 12 * 16^0\n",
    "       0xabc = 10 * 256  + 11 * 16   + 12 * 1   = 2748"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "abbd657c-170d-4e8b-b737-ec7baaf4947e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Examples:\n",
    "#   number_in_base(2748, 16) = \"abc\"\n",
    "#   number_in_base(75,    8) = \"123\"\n",
    "#   number_in_base(5,     2) = \"101\"\n",
    "#   number_in_base(123,  10) = \"123\"\n",
    "\n",
    "# 123 // 10 = 12  ;  123  % 10 = 3\n",
    "\n",
    "digits = \"0123456789abcdefghijklmnopqrstuvwxyz\"  # digits[10] == \"a\"\n",
    "def number_in_base_recursive(n: int, base: int) -> str:\n",
    "    assert(base < len(digits))\n",
    "    if n <= 0:\n",
    "        return \"\"\n",
    "    return number_in_base_recursive(n // base, base) + digits[n % base]\n",
    "\n",
    "def number_in_base_iterative(n: int, base: int) -> str:\n",
    "    assert(base < len(digits))\n",
    "    result = \"\"\n",
    "    while n > 0:  \n",
    "        result = digits[n % base] + result\n",
    "        n = n // base\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "2b59cd2b-ec89-4bb5-9e82-f736179fd9d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'10'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "number_in_base_iterative(30,30)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd17bb45-d679-4353-b81d-381aa1a799b7",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Nth power of X (n-tá mocnina čísla)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b330368e-af40-459c-942b-1a881ddc56bf",
   "metadata": {},
   "source": [
    "- Inputs: the base A, the power B\n",
    "- Outputs: A^B"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25f94e3c-9ba7-4a14-b3ad-fca748dbbd36",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "# Search"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96390ef7-90c4-4c01-bea5-1192475f38d4",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## GenericSearch(L, X):"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aaa1618b-9d8f-4588-a299-33626ac34b62",
   "metadata": {},
   "source": [
    "\n",
    "- Inputs: list L of items, item X to find\n",
    "- Output: index of item X in list L\n",
    "- General search algorithm (unknown list)\n",
    "- \"I need to look at each item individually\"\n",
    "- time complexity: O(n) ~ linear\n",
    "\n",
    "      xs = [1, 5, 9, 2, 8, 3, 4, ..., 9]\n",
    "      x = 8\n",
    "      ix = ?  =>  ix = 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "fc78fbfa-5b68-49f3-82a0-7570efefad8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "def generic_search(l: List[int], n: int) -> int:\n",
    "    for i in range(len(l)):\n",
    "        if l[i] == n:\n",
    "            return i\n",
    "\n",
    "def generic_search_v2(l: List[int], n: int) -> int:\n",
    "    for i, x in enumerate(l):\n",
    "        if x == n:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a7b5f4f-7937-49c9-ad2f-d4fc58fafb6d",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## OrderedSearch(L, X)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70c4060b-ddc7-402d-8baa-173da2b7cb36",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "- Inputs: ordeded list L of items, item X to find\n",
    "- Output: index of item X in list L\n",
    "- Binary search\n",
    "- \"At each step, I need to only look at the half of the list\"\n",
    "- time complexity: O(log_2(n)) ~ logarithmic\n",
    "\n",
    "      xs = [1, 2, 3, 4, 5, 8, 9, 9]\n",
    "      x = 8\n",
    "      n = ?  =>  n = 4\n",
    "\n",
    "      1) xs = [1, 2, 3, 5, 8, 9, 9]\n",
    "                        \\\n",
    "                        x?\n",
    "                        \n",
    "      2) xs = [----------, 8, 9, 9]\n",
    "                              \\\n",
    "                              x?\n",
    "                              \n",
    "      2) xs = [----------, 8, ----]\n",
    "                           \\\n",
    "                           x?\n",
    "                           \n",
    "      Equivalent:\n",
    "         xs = [1, 2, 3, 5, 8, 9, 9]\n",
    "\n",
    "         xs =           5,\n",
    "                  2,          9,\n",
    "              [1,    3,    8,    9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "d2c149f5-4a4e-4389-91c0-9e4c36e21bb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ordered_search(l: List[int], x: int) -> int:\n",
    "    assert(l == sorted(l))\n",
    "    pass"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}