{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 03 - Lists and Tuples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Jupyter notebooks\n",
    "\n",
    "This is a space where text and code come together to form a coherent document. Throughout the course, we will make use of Jupyter notebooks for illustration purposes and for experimentation. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "After the second set of slides, you should be able to write **straight-line** programs and programs that allow for **branching** and **repetition** based on an expression's truth value. What we have learned so far is fundamental, useful, but not enough. In particular, programming often requires storing in memory user inputs or copying existing elements and storing them in an object with some internal structure. \n",
    "\n",
    "For example, given a sequence of numbers entered by user, how to:\n",
    "\n",
    "1) Print them in reverse order?\n",
    "\n",
    "2) Check if they are distinct?\n",
    "\n",
    "3) Sort them in (reverse) order?\n",
    "\n",
    "This is where we will make use of the `list` data structure, which is built-in in Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List\n",
    "### `list` initialization\n",
    "In Python, we use brackets `[]` to initialize a `list`, where elements are separated by commas. For example, the below objects are two different lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "L1 = [1, 2, 3, 4, 5]\n",
    "L2 = [\"hello\", 2.0, 'CSC243', -1, True]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Python `list` is either:\n",
    "\n",
    "1) Homogeneous, thus containing objects of the same data-type (like `L1`)\n",
    "\n",
    "2) Heterogeneous, containing objects of mixed data-type (like `L2`)\n",
    "\n",
    "Like in `str`, the built-in `len()` function gives the length of a list. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "n = len(L2)\n",
    "print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `list` indexing\n",
    "The `list` elements can be accessed by specifying the index:\n",
    "\n",
    "1) Non-negative indices: start at `0`, end at `len()-1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "first element of L2: hello\n",
      "last element of L2: True\n"
     ]
    }
   ],
   "source": [
    "# illustrating positive indices\n",
    "first_element = L2[0]\n",
    "last_element = L2[n-1]\n",
    "\n",
    "print(\"first element of L2:\", first_element)\n",
    "print(\"last element of L2:\", last_element)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) **Negative indices** work from right to left (reverse order)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "first element from the right True\n",
      "third element from the right CSC243\n"
     ]
    }
   ],
   "source": [
    "# illustrating negative indices\n",
    "# n = len(L2)\n",
    "first_element_right = L2[-1] # L2[n-1]\n",
    "third_element_right = L2[-3] # L3[n-3]\n",
    "\n",
    "print(\"first element from the right\", first_element_right)\n",
    "print(\"third element from the right\", third_element_right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists are **mutable** data-structures (i.e., can be modified). We not only have read-access, but also write-access. Let's modify elements from L2 at different indices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "L2 (before): ['hello', 2.0, 'CSC243', -1, True]\n",
      "L2 (after): ['goodbye', 4.0, 'CSC243', -1, True]\n"
     ]
    }
   ],
   "source": [
    "print(\"L2 (before):\", L2)\n",
    "L2[1] = L2[1] + 2\n",
    "L2[0] = \"goodbye\"\n",
    "print(\"L2 (after):\", L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `list` slicing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition to single-element access, we can slice a `list` using the `L[start:end]` syntax, which slices the list at index `i=start, start + 1, start+2, .... , end-1`. Notice that as in the `stop` parameter in the `range`, the `end` is exclusive as well. The default values are `start=0` and `end=n` where `n=len(L)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "slice 1 [1, 2, 3, 4, 5, 6]\n",
      "slice 2 [2, 3]\n",
      "slice 3 [1, 2, 3]\n",
      "slice 4 [4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "L = [1, 2, 3, 4, 5, 6]\n",
    "print(\"slice 1\", L[:]) # without any paramters\n",
    "print(\"slice 2\", L[1:3]) # start = 1, stop =3\n",
    "print(\"slice 3\", L[:3]) # without the start parameter\n",
    "print(\"slice 4\", L[3:]) # without the stop paremeter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also specify a `step` for the slicing, using `L[start:stop:step]`. This will extract values at indices `i = start, start+step, start + 2*step,  … , start + c*step`, where `c` is an integer such that `start + c*step <= n-1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "odd entries of L [1, 3, 5]\n",
      "even entries of L [2, 4, 6]\n"
     ]
    }
   ],
   "source": [
    "print(\"odd entries of L\", L[::2])\n",
    "print(\"even entries of L\", L[1::2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "### Low-level implementation\n",
    "List are stored in memory block  consisting of contiguous memory cells (called arrays in other languages such as `C/C++`). This gives the indexing operator `[]` direct access: given index `i`, we can directly go to `L[i]` (compared to starting from the beginning of the list and moving `i` steps, which is not efficient). Direct access is very fast."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Homogeneous list initialization (via `*` operator)\n",
    "Using the `*` operator, we can initialize a list with an element repeated multiple times. General syntax: `L = [value]*n`, where `n` is an integer. \n",
    "\n",
    "Examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "['test', 'test', 'test']\n",
      "[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]\n",
      "[True, True, True, True, True]\n"
     ]
    }
   ],
   "source": [
    "L = ['test']*3\n",
    "print(L)\n",
    "L = [-1]*10\n",
    "print(L)\n",
    "L = [True]*5\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Homogeneous list initialization via user input (method 1)\n",
    "Also, we can retrieve input from a user to initialize a `list` of, say, `float`. When the number of elements is known, the method uses a `for` loop (or a counter-controlled `while` loop) with the following steps:\n",
    "\n",
    "1) We take the number of integers `n` and convert to int (as usual).\n",
    "\n",
    "2) We initialize a list to `n` zeros using: `L = [0]*n`.\n",
    "\n",
    "3) We loop `n` times and insert each new integer at index `i`, i.e. at `L[i]`, where `i` is the loop counter.\n",
    "\n",
    "Code illustration:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter the number of integers: 3\n",
      "enter a real number: 1.5\n",
      "enter a real number: 2.5\n",
      "enter a real number: 3.5\n",
      "[1.5, 2.5, 3.5]\n"
     ]
    }
   ],
   "source": [
    "n = int(input(\"Enter the number of integers: \"))\n",
    "L = [0]*n\n",
    "\n",
    "for i in range(n):\n",
    "    L[i] = float(input(\"enter a real number: \"))\n",
    "\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Homogeneous list initialization via user input (method 2)\n",
    "If the number of elements is not known ahead of time (as with method 1), we can enter the elements separated by a particular separator -- like the whitespace ` ` -- as a string. The approach will **split** the string using the `.split` method. Finally, we convert each entry in the resulting `list` from string to `int` or `float`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter a separator: ,\n",
      "Enter numbers seperated by a ',': 1,2,3.5\n",
      "L before conversion: ['1', '2', '3.5']\n",
      "L after conversion: [1.0, 2.0, 3.5]\n"
     ]
    }
   ],
   "source": [
    "sep = input(\"Enter a separator: \")\n",
    "st = input(\"Enter numbers seperated by a \\'\" + str(sep) + \"\\': \")\n",
    "L = st.split(sep)\n",
    "print(\"L before conversion:\", L)\n",
    "\n",
    "n = len(L)\n",
    "for i in range(n):\n",
    "    L[i] = float(L[i])\n",
    "    \n",
    "print(\"L after conversion:\", L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: printing a list in reverse order\n",
    "Using repetition, we can print in reverse order of elements in a `list`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "printing in reverse (method 1):\n",
      "3.5\n",
      "2.0\n",
      "1.0\n",
      "printing in reverse (method 2):\n",
      "3.5\n",
      "2.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "print(\"printing in reverse (method 1):\")\n",
    "for i in range(1, n+1):\n",
    "    print(L[n-i])\n",
    "\n",
    "print(\"printing in reverse (method 2):\")\n",
    "for i in range(n-1, -1, -1):\n",
    "    print(L[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: element distinctness problem\n",
    "Using repetition, we can check if the elements of a `list` are distinct. First, store user input in length-`n` list `L`. The, we need to check if there exists distinct indices `i` and `j` between (inclusive)  `0` and `n-1` such that `L[i] == L[j]`.\n",
    "\n",
    "We make use of the “True-until-proven-False” pattern: \n",
    "\n",
    "1) Assume `list` consists of distinct elements: use a boolean variable `distinct`, initialized to `True`.\n",
    "\n",
    "2) Look for evidence of **non-distinctness**: use nested loops, an outer loop on `i` and inner loop on `j`.\n",
    "\n",
    "3) If `i!=j` and `L[i]==L[j]`, set `distinct` to `False` and `break` **both loops**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter integers separated by whitespaces: 3 1 4 1 5\n",
      "elements are not distinct\n"
     ]
    }
   ],
   "source": [
    "# user-input\n",
    "st = input(\"Enter integers separated by whitespaces: \")\n",
    "L = st.split(\" \")\n",
    "n = len(L)\n",
    "for i in range(n):\n",
    "    L[i] = int(L[i])\n",
    "\n",
    "# main work: true-until-false pattern\n",
    "distinct = True\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        if i == j:\n",
    "            continue\n",
    "        elif L[i] == L[j]:\n",
    "            distinct = False\n",
    "            break # from inner loop\n",
    "    if not distinct:\n",
    "        break # from outer loop\n",
    "\n",
    "# display of result\n",
    "if distinct:\n",
    "    output_message = \"elements in L are distinct\"\n",
    "else:\n",
    "    output_message = \"elements are not distinct\"\n",
    "print(output_message)            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can do it faster by assuming without loss of generality that `i < j`. The checks `L[i] == L[j]` and `L[j] == L[i]` are redundant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "elements are not distinct\n"
     ]
    }
   ],
   "source": [
    "# main algorithm: true-until-proven-false\n",
    "distinct = True\n",
    "for i in range(n):\n",
    "    for j in range(i+1, n):\n",
    "        if L[i] == L[j]:\n",
    "            distinct = False\n",
    "            break # from inner loop\n",
    "    if not distinct:\n",
    "        break # from outer loop\n",
    "\n",
    "# display of result\n",
    "if distinct:\n",
    "    print(\"elements in L are distinct\")\n",
    "else:\n",
    "    print(\"elements are not distinct\") "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The `in` operator\n",
    "To check if an element exists in a list, can use the regular looping mechanism to do so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "enter an integer: 5\n",
      "5 is in the list [1, 2, 5, -1, 0]\n"
     ]
    }
   ],
   "source": [
    "x = int(input(\"enter an integer: \"))\n",
    "L = [1, 2, 5, -1, 0]\n",
    "n = len(L)\n",
    "\n",
    "found = False\n",
    "for i in range(n):\n",
    "    if L[i] == x:\n",
    "        found = True\n",
    "        break\n",
    "\n",
    "if found:\n",
    "    print(x, \"is in the list\", L)\n",
    "else:\n",
    "    print(x, \"is not in the list\", L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An alternative (and simpler) way, is the use of `in` operator. Note that it is equivalent to a for loop, since the code needs to check all elements to confirm if `x` is in `L`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "enter an integer: 3\n",
      "3 is not in the list: [1, 2, 5, -1, 'CSC243']\n"
     ]
    }
   ],
   "source": [
    "x = int(input(\"enter an integer: \"))\n",
    "L = [1, 2, 5, -1, \"CSC243\"]\n",
    "\n",
    "if x in L:\n",
    "    print(x, \"is in the list:\", L)\n",
    "else:\n",
    "    print(x, \"is not in the list:\", L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example: element distincness problem (revisited using slicing and `in`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter integers separated by whitespaces: 1 2 3 4\n",
      "elements in L are distinct\n"
     ]
    }
   ],
   "source": [
    "# user-input\n",
    "st = input(\"Enter integers separated by whitespaces: \")\n",
    "L = st.split(\" \")\n",
    "n = len(L)\n",
    "for i in range(n):\n",
    "    L[i] = int(L[i])\n",
    "\n",
    "# main work: true-until-false pattern\n",
    "distinct = True\n",
    "for i in range(n):\n",
    "    if L[i] in L[i+1:n]:\n",
    "        distinct = False\n",
    "        break # from loop (controller by i)\n",
    "\n",
    "# display of result\n",
    "if distinct:\n",
    "    print(\"elements in L are distinct\")\n",
    "else:\n",
    "    print(\"elements are not distinct\") "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a version that relies on the while-loop to break automatically when `distinct` changes to `False`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter integers separated by whitespaces: 1 2 3 4\n",
      "elements in L are distinct\n"
     ]
    }
   ],
   "source": [
    "# user-input\n",
    "st = input(\"Enter integers separated by whitespaces: \")\n",
    "L = st.split(\" \")\n",
    "n = len(L)\n",
    "for i in range(n):\n",
    "    L[i] = int(L[i])\n",
    "\n",
    "# main work: true-until-false pattern\n",
    "distinct = True\n",
    "i = 0\n",
    "while i < n and distinct:\n",
    "    if L[i] in L[i+1:n]:\n",
    "        distinct = False\n",
    "    i += 1\n",
    "\n",
    "# display of result\n",
    "if distinct:\n",
    "    print(\"elements in L are distinct\")\n",
    "else:\n",
    "    print(\"elements are not distinct\") "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `list` copying\n",
    "To copy the contents of a list called `L1` into another list, we must: \n",
    "\n",
    "1) Declare a new list of the **same size** and initialize it (example, call it `L2`).\n",
    "\n",
    "2) Loop over the contents of the original list `L1`.\n",
    "\n",
    "3) Set the first element of `L2` equal to the first element of `L1`, the second element of `L2` equal to the second in `L1`, and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter integers separated by whitespaces: 1 2 3\n",
      "L1 is: [1, 2, 3]\n",
      "L2 is: [1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "st = input(\"Enter integers separated by whitespaces: \")\n",
    "L1 = st.split(\" \")\n",
    "\n",
    "L2 = [0]*len(L1)\n",
    "for i in range(len(L1)):\n",
    "    L1[i] = int(L1[i])\n",
    "    L2[i] = L1[i]\n",
    "    \n",
    "print(\"L1 is:\", L1)\n",
    "print(\"L2 is:\", L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another, simpler way, is to use the `.copy()` method which is associated with the `list` object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "L2 = L1.copy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Note: the built-in `id` function\n",
    "The `id` function returns a **unique identifier** for each object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "True\n",
      "4484194368\n",
      "4484184384\n"
     ]
    }
   ],
   "source": [
    "truthValue = L1 == L2\n",
    "print(truthValue)\n",
    "print(id(L1))\n",
    "print(id(L2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note how, while the two objects contain the same elements, each list is a **unique** object with its own identifier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `list` aliasing\n",
    "What if we write `L2 = L1`? This will result in **aliasing**. In fact, the assignment operator `=` will NOT perform a value copy (unlike for scalar types); `L2` is simply another name (alias) for `L1`. What are the consequences for this? Changes in the values of `L2` affect `L1` as well, and vice-versa.\n",
    "\n",
    "If we don’t want this, we use the `.copy()` or we process by looping, as done in the previous two methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter integers separed by whitespaces: 1 2 3\n",
      "L1 is (before assignment): [1, 2, 3]\n",
      "L1 is now: ['X', 2, 3]\n",
      "L2 is: ['X', 2, 3]\n"
     ]
    }
   ],
   "source": [
    "st = input(\"Enter integers separed by whitespaces: \")\n",
    "L1 = st.split(\" \")\n",
    "for i in range(len(L1)):\n",
    "    L1[i] = int(L1[i])\n",
    "    \n",
    "L2 = L1\n",
    "print(\"L1 is (before assignment):\", L1)\n",
    "L2[0] = 'X'\n",
    "print(\"L1 is now:\", L1)\n",
    "print(\"L2 is:\", L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: checking if two lists are equal\n",
    "This is another example of “True-until-proven-False” pattern. We initialize a bool to `True`. Then we check each element in the lists and compare them against each other to find a counter-example. This is the classical way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "lists are equal.\n"
     ]
    }
   ],
   "source": [
    "are_equal = True\n",
    "for i in range(len(L1)):\n",
    "    if L1[i] != L2[i]:\n",
    "        are_equal = False\n",
    "        break\n",
    "\n",
    "if are_equal:\n",
    "    print(\"lists are equal.\")\n",
    "else:\n",
    "    print(\"lists NOT equal.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Python, there exists a simpler way via the equality-check `==` operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "lists are equal.\n"
     ]
    }
   ],
   "source": [
    "if L1 == L2:\n",
    "    print(\"lists are equal.\")\n",
    "else:\n",
    "    print(\"lists are NOT equal.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `list` concatenation\n",
    "We can join two lists together using the `+` operator. This is similar to string concatenation, as we have seen before. We cannot concatenate a `list` with another data type, such as a `str` or an `int`. The `+=` augmented assignment operator can also be used to concatenate lists. \n",
    "\n",
    "Here is an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[1, 2, 3, 4, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "L1 = [1,2,3,4]\n",
    "L2 = [6,7,8,9]\n",
    "L = L1 + L2\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note here how the `+` operator did not result in element-by-element addition. Instead, it added the one list to another. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Two-dimensional `list`\n",
    "The list elements can be lists themselves. In this case, it is useful to think of the list as rows and columns. Processing the list in this scenario requires nested-loops and the use of **two indices**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "first row: [1, 2, 3]\n",
      "last row: [7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "L = [[1,2,3], [4,5,6], [7,8,9]]\n",
    "print(\"first row:\", L[0])\n",
    "print(\"last row:\", L[-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example: printing a `list` in matrix form"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1 2 3 \n",
      "4 5 6 \n",
      "7 8 9 \n"
     ]
    }
   ],
   "source": [
    "rows = len(L)\n",
    "for i in range(rows):\n",
    "    cols = len(L[i])\n",
    "    for j in range(cols):\n",
    "        print(L[i][j], end=\" \")\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `tuple` data-structure\n",
    "Use parentheses `( )` to initialize a `tuple` in Python. The elements are separated by commas, as in the case of `list`. \n",
    "\n",
    "Examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "T1 = (1, 2, 3)\n",
    "T2 = (\"hello\", 2.0, \"CSC243\", -1, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A `tuple` is either:\n",
    "\n",
    "1) Homogeneous: same data-type (like `T1`) \n",
    "\n",
    "2) Heterogeneous: mixed data-type (like `T2`)\n",
    "\n",
    "Like in `str` and `list`, the built-in `len()` function gives the length of a `tuple`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "3\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "print(len(T1))\n",
    "print(len(T2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Besides the method of initializaion, the difference is that tuples are immutable lists. Once initialized, they cannot be changed, i.e., we have read-only access. To read the `i`-th element, use the indexing operator `[]` as in lists.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "hello CSC243\n"
     ]
    }
   ],
   "source": [
    "print(T2[0] + \" \" + T2[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also compare tuples using the `==` operator. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Are T1 and T2 equal?\n",
      "No.\n"
     ]
    }
   ],
   "source": [
    "print(\"Are T1 and T2 equal?\")\n",
    "if T1 == T2:\n",
    "    print(\"Yes!\")\n",
    "else:\n",
    "    print(\"No.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To initialize a `tuple` consisting of a single object `x`, use `T = (x,)` not `T = (x)`. Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "('CSC243',)\n"
     ]
    }
   ],
   "source": [
    "x = \"CSC243\"\n",
    "T = (x,)\n",
    "print(T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quick `tuple` example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "33.89311\n",
      "33.89311\n",
      "35.47782\n",
      "35.47782\n"
     ]
    }
   ],
   "source": [
    "location = (33.89311, 35.47782)\n",
    "\n",
    "(lat, lon) = location\n",
    "print(lat)\n",
    "print(location[0])\n",
    "print(lon)\n",
    "print(location[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "(1, 2, 3, 4, 5, 6)\n"
     ]
    }
   ],
   "source": [
    "T1 = (1,2,3)\n",
    "(fd, sd, td) = T1\n",
    "\n",
    "T2 = (4, 5, 6)\n",
    "T = T1 + T2\n",
    "\n",
    "print(T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `list` and `tuple` objects with or without mutable objects\n",
    "In this section, we will examine what happens when a `list` or a `tuple` are themselves consisting of (im)mutable objects:\n",
    "\n",
    "For a `list` which does not contain mutable objects, e.g., `L = [1,20,10]`, the assignment operator `L2 = L` creates an alias, and `L2 = L.copy()` creates a clone."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "L's ID: 4484363392\n",
      "L2's ID: 4484363392\n",
      "L2's ID: 4484363328\n"
     ]
    }
   ],
   "source": [
    "L = [1,20,10]\n",
    "L2 = L\n",
    "\n",
    "print(\"L's ID:\", id(L))\n",
    "print(\"L2's ID:\", id(L2))\n",
    "\n",
    "L2 = L.copy()\n",
    "print(\"L2's ID:\", id(L2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a `tuple` which does not contain  mutable objects, e.g., `T = (1,20,10)`, we only need the assignment operator `T2 = T` since anyways we cannot change `T` (there is no `copy()` member function associated with the type `tuple`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a `list` containing mutable objects, e.g., `L = [1, [3,6], 10]`, the assignment operator `L2 = L` creates an alias, and `L2 = L.copy()` creates a clone **whose mutable objects are aliases**. For instance, `L2` using the `.copy()` method will create a new object, with its own unique identifier, but such that the **mutable** list `[3,6]` is aliasing the original one in `L`.\n",
    "\n",
    "Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "L after modifying the first element of L2: [1, [3, 6], 10]\n",
      "L after modifying the mutable object in L2: [1, ['X', 6], 10]\n",
      "L2 after both modifications: ['0', ['X', 6], 10]\n"
     ]
    }
   ],
   "source": [
    "L = [1, [3,6], 10]\n",
    "L2 = L.copy()\n",
    "\n",
    "L2[0] = \"0\"\n",
    "print(\"L after modifying the first element of L2:\", L)\n",
    "\n",
    "L2[1][0] = \"X\"\n",
    "print(\"L after modifying the mutable object in L2:\", L)\n",
    "print(\"L2 after both modifications:\", L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a `tuple` containing mutable objects, e.g. `T = (1,[3,6], 10)` , `T2 = T` creates an alias."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deep copy\n",
    "What if we are interested in a **deep copy** of a `list` or `tuple` containing mutable objects? We need to clone all mutable **and** immutable objects all the way (i.e., recursively). We make use of the `deepcopy()` function from the `copy` module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "L after modifying the first element of L2: [1, [3, 6], 10]\n",
      "L after modifying the mutable object in L2: [1, [3, 6], 10]\n",
      "L2 after both modifications: ['0', ['X', 6], 10]\n"
     ]
    }
   ],
   "source": [
    "from copy import deepcopy\n",
    "\n",
    "L = [1, [3,6], 10]\n",
    "L2 = deepcopy(L)\n",
    "L2[0] = \"0\"\n",
    "print(\"L after modifying the first element of L2:\", L)\n",
    "L2[1][0] = \"X\"\n",
    "print(\"L after modifying the mutable object in L2:\", L)\n",
    "print(\"L2 after both modifications:\", L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, modifying `L2` in this case did not affect the original list `L`, thanks to deep copy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `list`, `string`, and `tuple` as iterables and looping mechanisms\n",
    "In Python, a `list`, `str` and `tuple` are all **sequences**. Hence, we can loop over them using cleaner syntax than the one using an index. The general syntax to do so is the following:\n",
    "\n",
    "`for variable in sequence:\n",
    "    block of code`\n",
    "    \n",
    "Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "10 -8 1 -2.2 3.0 \n",
      "10 -8 1 -2.2 3.0 "
     ]
    }
   ],
   "source": [
    "L = [10, -8, 1, -2.2, 3.0] # L is a sequence\n",
    "\n",
    "for i in range(len(L)):\n",
    "    print(L[i], end=\" \")\n",
    "\n",
    "print(\"\\n\", end=\"\")\n",
    "\n",
    "for x in L:\n",
    "    print(x, end=\" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "C\n",
      "S\n",
      "C\n",
      " \n",
      "2\n",
      "4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "my_string = \"CSC 243\"\n",
    "for character in my_string:\n",
    "    print(character, end=\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that in the above, the variable `character` is simply a placeholder for the element that loops over the list. It does not hold actual meaning and consequently we could have named it anything we like."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "C\n",
      "S\n",
      "C\n",
      " \n",
      "2\n",
      "4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "my_string = \"CSC 243\"\n",
    "for c in my_string:\n",
    "    print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `list` comprehension"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Python, we can initialize a `list` using the following syntax: \n",
    "\n",
    "`L = [function_of(x) for x in sequence]`\n",
    "\n",
    "This is called list comprehension. The `sequence` in the above is any iterable, such as a `list`, a `str`, or a `tuple`. Also, `function_of(x)` is an expression, which is a function of `x`, as the name indicates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "L1 is: [1.0, 1.4142135623730951, 1.7320508075688772, 2.0, 2.23606797749979, 2.449489742783178, 2.6457513110645907, 2.8284271247461903, 3.0, 3.1622776601683795, 3.3166247903554, 3.4641016151377544, 3.605551275463989, 3.7416573867739413, 3.872983346207417, 4.0, 4.123105625617661, 4.242640687119285, 4.358898943540674]\n",
      "\n",
      "L2 is: [10, 8, 6, 4, 2]\n",
      "\n",
      "L3 is: [0, 1, 4, 9, 16]\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "L1 = [math.sqrt(x) for x in range(1, 20)] # function_of(x) is sqrt(x)\n",
    "print(\"L1 is:\", L1)\n",
    "\n",
    "print()\n",
    "L2 = [i for i in range(10, 0, -2)] # function_of(x) is x\n",
    "print(\"L2 is:\", L2)\n",
    "\n",
    "print()\n",
    "L3 = [x*x for x in range(0, 5)] # function_of(x) is x**2\n",
    "print(\"L3 is:\", L3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an example to achieve type-casting via list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter integers (separated by whitespaces): 4 8 15 16 23 42\n",
      "['4', '8', '15', '16', '23', '42']\n",
      "[4, 8, 15, 16, 23, 42]\n"
     ]
    }
   ],
   "source": [
    "L = input(\"Enter integers (separated by whitespaces): \").split(\" \")\n",
    "print(L)\n",
    "L = [int(x) for x in L]\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Advanced `list` comprehension\n",
    "A more advanced way to initialize a `list` is to add a condition for the previous syntax:\n",
    "\n",
    "`L = [function_of(x) for x in sequence if condition]`\n",
    "\n",
    "Example: filtering out the integers from a list with mixed elements (heterogeneous list)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "mixed list: [1, '-2', 2, True, (18, 25), False, 'CSC243', -5]\n",
      "L (filtered list): [1, 2, -5]\n"
     ]
    }
   ],
   "source": [
    "mixed_list = [1, \"-2\", 2, True, (18,25), False, \"CSC243\", -5]\n",
    "print(\"mixed list:\", mixed_list)\n",
    "L = [x for x in mixed_list if type(x)==int]\n",
    "print(\"L (filtered list):\", L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
