{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1c8bac27-fab9-4886-a81e-a1aa82cf4129",
   "metadata": {},
   "source": [
    "## Input Reading"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3e3838b6-5e85-4f62-bd97-fedb719c8039",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " Hello, world!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Hello, world!'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4b2740c8-deb4-4631-8f9a-c2eeadcb9009",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " Hello, world!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['Hello,', 'world!']"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input().split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "72cf06ca-ea69-43f0-af2f-666a92ab08e1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " Zoe Paraskevopoulou\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First name: Zoe and last name: Paraskevopoulou\n"
     ]
    }
   ],
   "source": [
    "name = input()\n",
    "name_list = name.split()\n",
    "first = name_list[0]\n",
    "last = name_list[1]\n",
    "print(\"First name:\", first, \"and last name:\", last)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "211dd94c-27c5-487e-b751-2fb14675475e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " Zoe Paraskevopoulou\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First name: Zoe and last name: Paraskevopoulou\n"
     ]
    }
   ],
   "source": [
    "first, last = input().split()\n",
    "print(\"First name:\", first, \"and last name:\", last)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "16559bd6-6072-4391-8a0b-8f4a2f2faa5e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 17 42\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1742\n"
     ]
    }
   ],
   "source": [
    "n1, n2 = input().split()\n",
    "print(n1 + n2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9e62d8e6-e7cb-4ba9-a953-e1ea0d8dcb0b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 17 42\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "59\n"
     ]
    }
   ],
   "source": [
    "n1, n2 = input().split()\n",
    "print(int(n1) + int(n2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5016acb8-7399-41d7-a374-a6a309d2cf8c",
   "metadata": {},
   "outputs": [],
   "source": [
    "first, second = input().split()\n",
    "print(int(first) + int(second))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "daf4c19e-3118-4f4c-b642-815aa0044d19",
   "metadata": {},
   "source": [
    "This works, but it is not idiomatic Python. Also, it doesn't generalize for more than two numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a89c7b48-11bb-45d6-93b7-28cebf70242f",
   "metadata": {},
   "source": [
    "How can we convert a list of strings arbitrary length to a list of integers?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b1b3f11b-7eeb-47a3-987e-6fb00e84ee30",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3 4\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "# this works but it is not very \"Pythonic\"\n",
    "l = [] \n",
    "\n",
    "inp = input().split()\n",
    "\n",
    "for x in inp: l.append(int(x))\n",
    "\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "59878d63-87e4-4b26-9ff6-9104ea0fe24b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3 4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[int(x) for x in input().split()]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "450b6555-54ec-45d0-8028-a7611e8e9da8",
   "metadata": {},
   "source": [
    "## Mapping Over Collections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d7d1d522-8d76-41e7-8190-0ba4fb4bda04",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20, 30, 40]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = [1, 2, 3, 4]\n",
    "\n",
    "def f(x):\n",
    "    return x*10\n",
    "    \n",
    "list(map(f, L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "788aecfb-e3cc-45d2-aefe-1ed283a51d99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20, 30, 40]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda x: x * 10, L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "60e88bdf-7792-4a27-abc0-6a369b3eaffe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "map"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(map(f, L))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc2a8526-7566-43da-b2d0-d104dec0c893",
   "metadata": {},
   "source": [
    "Map objects are similar to generators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d2953c5f-f774-4d27-932b-6d393a32bed6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = map(f, L)\n",
    "next(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "fd1295d0-ed66-41bf-8747-4b7d1b199545",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98fbdccf-977a-4ad8-8222-421d559153c9",
   "metadata": {},
   "source": [
    "Quiz: How can we write the same thing with a generator?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87d51175-78a1-4fcf-8720-889589713159",
   "metadata": {},
   "source": [
    "Both of the following programs read a list of integers from the standard input and print them to the standard output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "b6c11f44-9691-480c-9ec3-ccdda4438761",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3 4 5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "print(sum(map(int, input().split())))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "b9eb99c7-d9ba-4412-944d-73f5de40f6a7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3 4 5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "print(sum(int(x) for x in input().split()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7a93db3-b6f5-4e56-9685-99adb64d5f02",
   "metadata": {},
   "source": [
    "## Exercise 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43f459c7-706c-4d41-b0d1-793fa8df7d32",
   "metadata": {},
   "source": [
    "Given two sequences of numbers, print all the numbers that belong to the first sequence but not the second one, in the order they appear in the first list. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ceadd491-5c9e-4f4f-9fb8-75867d5ff1ce",
   "metadata": {},
   "source": [
    "**Example Input**\n",
    "\n",
    "4 9 5 1 10\n",
    "\n",
    "5 7 2 4 1\n",
    "\n",
    "**Example Output**\n",
    "\n",
    "9 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "58f142ce-c16c-48c0-adc4-b3fd436ee0c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 4 9 5 1 10\n",
      " 5 7 2 4 1\n"
     ]
    }
   ],
   "source": [
    "S1 = list(map(int, input().split()))\n",
    "S2 = list(map(int, input().split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "030e342c-0f7c-4c1b-872b-fe99613f7d89",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 9, 5, 1, 10]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "266a755f-4042-4864-b679-a934c5bd9b16",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 7, 2, 4, 1]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "fe9685d5-7cfa-486f-98c6-49b5202264da",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "for x in S1:\n",
    "    if x not in S2:\n",
    "        print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "3bfedbdd-098f-4212-a316-098bdf0ec85b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 10]\n"
     ]
    }
   ],
   "source": [
    "L = []\n",
    "\n",
    "for x in S1:\n",
    "    if not x in S2:\n",
    "        L.append(x)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "4da0dfb2-6222-45f9-97d4-58ad1c1b7f6e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 10]\n"
     ]
    }
   ],
   "source": [
    "# similar, but more Pythonic\n",
    "L = [x for x in S1 if not x in S2]\n",
    "\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "28d4499b-7341-4f29-a35f-2388d8da4b5f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hi there'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\" \".join([\"hi\", \"there\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "ffc51353-e028-4345-a902-6de782332e2a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 10\n"
     ]
    }
   ],
   "source": [
    "print(\" \".join(str(x) for x in S1 if not x in S2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "9a393a7f-9036-4499-8686-fe57fd6ebb87",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 10\n"
     ]
    }
   ],
   "source": [
    "print(*(str(x) for x in S1 if not x in S2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db95f6b6-36a1-41c8-813f-d3b2c7d326b3",
   "metadata": {},
   "source": [
    "What is the running time of the above code?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "485d8cae-c552-4b74-bb29-94be8d28b27a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "  4 9 5 1 10\n",
      " 5 7 2 4 1\n"
     ]
    }
   ],
   "source": [
    "S1 = list(map(int, input().split()))\n",
    "S2 = set(map(int, input().split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "a2c50d63-8f01-433b-9733-4c1759d0ed6f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 10\n"
     ]
    }
   ],
   "source": [
    "print(*(str(x) for x in S1 if x not in S2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d949ab14-4fc3-435c-bfb1-7f4f0a59ef43",
   "metadata": {},
   "source": [
    "## Exercise 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fa189e9-1804-4928-a888-276a760a86bb",
   "metadata": {},
   "source": [
    "Ένα πρόβλημα από τον Πανελλήνιο Διαγωνισμό Πληροφορικής:\n",
    "\n",
    "Μια ομάδα παιδιών στέκονται σε μια ευθεία γραμμή, το ένα πίσω από το άλλο, περιμένοντας\n",
    "τη σειρά τους στο κυλικείο του σχολείου. Το πρώτο παιδί προφανώς βλέπει την είσοδο του\n",
    "κυλικείου, όσα παιδιά όμως στέκονται πίσω του δεν είναι σίγουρο ότι και αυτά τη βλέπουν.\n",
    "Για να βλέπει ένα παιδί την είσοδο του κυλικείου πρέπει όλα τα παιδιά που στέκονται\n",
    "μπροστά του να είναι κοντύτερα από αυτό.\n",
    "\n",
    "Να αναπτύξετε ένα πρόγραμμα το οποίο, αφού διαβάσει ένα αρχείο με τη λίστα των υψών των \n",
    "παιδιών, θα εκτυπώνει πόσα παιδιά βλέπουν την είσοδο."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9453f78-525c-4876-82c6-65dc07055a11",
   "metadata": {},
   "source": [
    "**Example Input:**\n",
    "5 6 4 6 3 4 1\n",
    "\n",
    "**Example Output:**\n",
    "3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab9c116b-d685-46dd-a534-421fbcab019c",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = list(map(int, input().split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "89178e57-7715-4cd1-9ecb-34393f15ed8a",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61a57877-7a2f-449c-aba0-bc9e71a50f88",
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(a):\n",
    "    N = len(a)\n",
    "    count = 0\n",
    "    for i in range(N):\n",
    "        tallest = True\n",
    "        for j in range (i+1, N):\n",
    "            if a[i] <= a[j]:\n",
    "                tallest = False\n",
    "                break\n",
    "        if tallest: count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f953eb9b-26e1-4e08-bef6-74bbf1bd08bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "solve(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "18de4230-041d-4533-a78e-a2120bf89ee0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_fast(a):\n",
    "    N = len(a)\n",
    "    tallest = 0\n",
    "    count = 0\n",
    "\n",
    "    for x in (a):                \n",
    "        if tallest < x:\n",
    "            tallest = x\n",
    "            count += 1\n",
    "\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2397ddc1-0f55-4f00-b078-cd49400cafe4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_fast(a):\n",
    "    N = len(a)\n",
    "    tallest = 0\n",
    "    count = 0\n",
    "\n",
    "    for x in reversed(a):                \n",
    "        if tallest < x:\n",
    "            tallest = x\n",
    "            count += 1\n",
    "    \n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f6d774e-8eec-46c8-996d-5c2845e59ba7",
   "metadata": {},
   "outputs": [],
   "source": [
    "solve_fast(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f61d518f-0a56-42d6-8bc5-61cfb58e255d",
   "metadata": {},
   "source": [
    "Let's test that the two solutions compute the same result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9a9a9912-03d4-4dd4-ade3-b54affb8e633",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb73302a-9fbe-426e-ac72-1e3b11a662f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b41a3476-2ff0-4e4d-84bd-6f4a3a30ca37",
   "metadata": {},
   "outputs": [],
   "source": [
    "type(random)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68c1bddb-5656-4972-813b-3c14dc9ce365",
   "metadata": {},
   "outputs": [],
   "source": [
    "random.randrange(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3824cbb-d42e-4a09-acab-e13658d8b21b",
   "metadata": {},
   "outputs": [],
   "source": [
    "random.randrange(100, 199)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b39cbe7b-8847-4aff-8844-568d7f0a94c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "N = random.randrange(1,1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4dfa75d3-8ece-43bc-8019-db716d68b0cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [random.randrange(1,100) for i in range(N)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "54091c81-aba5-457b-b5fb-fa0a4542888c",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1bdae67b-eae1-489c-8fd6-d55002539ab5",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e89db80-3181-47b7-8569-cdfc7ea5fa60",
   "metadata": {},
   "outputs": [],
   "source": [
    "solve(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a23d2fe9-ddc5-4be1-a2dd-d504b603fb0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "solve_fast(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea280ca6-9ab8-4e3a-afe0-a63b784206d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "for _ in range(1000):\n",
    "    N = random.randrange(1,100)\n",
    "    a = [random.randrange(1,100) for i in range(N)]\n",
    "    if solve_fast(a) != solve(a): print(\"BOOM!\", a)\n",
    "print(\"Done!\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "872ca8ef-6196-4421-bb89-7a9bd17005f8",
   "metadata": {},
   "source": [
    "## Itertools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02c79cdf-d2b4-4080-93b7-8e22b3af5a91",
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "884db3bf-9560-4809-8ddc-39d497d4a38c",
   "metadata": {},
   "outputs": [],
   "source": [
    "list(itertools.permutations([1,2,3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6025aeed-1734-4aa2-99e6-8f5637f8dd12",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Iterate through all permutations of a collection\n",
    "\n",
    "for x in itertools.permutations([1,2,3]):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "268647c8-cf1a-4597-8f72-e402cb0c8d0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "daltons = [\"Joe\", \"Jack\", \"William\", \"Averel\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "019bdaf5-9c6c-43ff-8731-72c90d31ecf1",
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in itertools.combinations(daltons, 3):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59e1b98f-6b7c-472c-a2b2-be6878c61e74",
   "metadata": {},
   "outputs": [],
   "source": [
    "list(itertools.combinations([1,2,3,4], 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3d1885a-09df-46e6-84db-19fe447a6fa9",
   "metadata": {},
   "source": [
    "These are helpful for bruteforce solutions, but be careful as they can be very slow."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dddb4ce5-017f-4703-8f3d-0e89a5112b09",
   "metadata": {},
   "source": [
    "## Exercise 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e67eb439-f8bc-4f00-8bff-f63c2d854bfa",
   "metadata": {},
   "source": [
    "Given a set of elements, partition it into two subsets such that the sum of the two subsets is the same.\n",
    "\n",
    "**Example Input**\n",
    "\n",
    "1 2 3 4 2\n",
    "\n",
    "**Example Output**\n",
    "\n",
    "2 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ffe32d8c-db98-44a2-911e-09c1c15e8f83",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = list(map(int, input().split()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02883e2a-7fae-4fe1-91e7-8ff2402450e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "023d159c-a279-4225-abe2-9421e29bb21b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(l):\n",
    "    S = sum(l)\n",
    "\n",
    "    for n in range(1, len(l)//2 + 1):\n",
    "        for candidate_sol in itertools.combinations(l, n):\n",
    "            if 2*sum(candidate_sol) == S:\n",
    "                return candidate_sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e9fe9b0-1633-4d0f-9fb5-decdb6b0b481",
   "metadata": {},
   "outputs": [],
   "source": [
    "partition(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19373d77-f5bb-40f7-8550-11fce2fc07e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [1, 4, 3, 8, 19, 12, 27]\n",
    "partition(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70ab65f3-e5ad-4d20-99a3-d05c71e55951",
   "metadata": {},
   "outputs": [],
   "source": [
    "partition(L) == None # No solution for this input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c1b6889-ce56-454a-bffe-c7d6f5f0bf3e",
   "metadata": {},
   "outputs": [],
   "source": [
    "partition([1, 2, 3, 4, 2])"
   ]
  }
 ],
 "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.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}