{ "cells": [ { "cell_type": "markdown", "id": "1c8bac27-fab9-4886-a81e-a1aa82cf4129", "metadata": {}, "source": [ "## Input Reading" ] }, { "cell_type": "code", "execution_count": 109, "id": "bf8c0849-ff45-40bb-bab2-832133c8df36", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "What is your name?\n" ] }, { "name": "stdin", "output_type": "stream", "text": [ " Zoe Paraskevopoulou\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "Hello Zoe Paraskevopoulou , how are you?\n" ] } ], "source": [ "print(\"What is your name?\")\n", "name = input()\n", "print(\"Hello\", name, \", how are you?\")" ] }, { "cell_type": "code", "execution_count": 2, "id": "f5f2246e-212a-4ee9-8e56-20555de6bb9e", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " Zoe Paraskevopoulou\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "['Zoe', 'Paraskevopoulou']\n" ] } ], "source": [ "name = input()\n", "print(name.split())" ] }, { "cell_type": "code", "execution_count": 110, "id": "08f8cc26-6b50-4b72-a634-d08ff1a8013c", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " Zoe Paraskevopoulou\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "First name: Zoe\n", "Last name: Paraskevopoulou\n" ] } ], "source": [ "name = input()\n", "name_list = name.split()\n", "first_name = name_list[0]\n", "last_name = name_list[1]\n", "print(\"First name:\", first_name)\n", "print(\"Last name:\", last_name)" ] }, { "cell_type": "code", "execution_count": 111, "id": "812ab24b-81b6-48b3-918d-d17d3313e65b", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 11 31\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "1131\n" ] } ], "source": [ "first, second = input().split()\n", "print(first + second)" ] }, { "cell_type": "code", "execution_count": 112, "id": "5016acb8-7399-41d7-a374-a6a309d2cf8c", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 11 31\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "42\n" ] } ], "source": [ "first, second = input().split()\n", "print(int(first) + int(second))" ] }, { "cell_type": "code", "execution_count": 113, "id": "47dc3744-cfb7-4456-bc4e-f12176504727", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3 4 5 6 \n" ] }, { "data": { "text/plain": [ "['1', '2', '3', '4', '5', '6']" ] }, "execution_count": 113, "metadata": {}, "output_type": "execute_result" } ], "source": [ "input().split()" ] }, { "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": 114, "id": "b1b3f11b-7eeb-47a3-987e-6fb00e84ee30", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3 4 5 6\n" ] }, { "data": { "text/plain": [ "[1, 2, 3, 4, 5, 6]" ] }, "execution_count": 114, "metadata": {}, "output_type": "execute_result" } ], "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", "l" ] }, { "cell_type": "code", "execution_count": 115, "id": "59878d63-87e4-4b26-9ff6-9104ea0fe24b", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3 4 5 6\n" ] }, { "data": { "text/plain": [ "[1, 2, 3, 4, 5, 6]" ] }, "execution_count": 115, "metadata": {}, "output_type": "execute_result" } ], "source": [ "inp = input().split()\n", "\n", "[int(x) for x in inp]" ] }, { "cell_type": "markdown", "id": "450b6555-54ec-45d0-8028-a7611e8e9da8", "metadata": {}, "source": [ "## Mapping Over Collections" ] }, { "cell_type": "code", "execution_count": 116, "id": "d7d1d522-8d76-41e7-8190-0ba4fb4bda04", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[10, 20, 30, 40]" ] }, "execution_count": 116, "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": 119, "id": "60e88bdf-7792-4a27-abc0-6a369b3eaffe", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "map" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(map(f, L))" ] }, { "cell_type": "code", "execution_count": 120, "id": "d2953c5f-f774-4d27-932b-6d393a32bed6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10" ] }, "execution_count": 120, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = map(f, L)\n", "next(m)" ] }, { "cell_type": "code", "execution_count": 121, "id": "fd1295d0-ed66-41bf-8747-4b7d1b199545", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "20" ] }, "execution_count": 121, "metadata": {}, "output_type": "execute_result" } ], "source": [ "next(m)" ] }, { "cell_type": "markdown", "id": "98fbdccf-977a-4ad8-8222-421d559153c9", "metadata": {}, "source": [ "Quiz: Can we write the same thing with a generator?" ] }, { "cell_type": "code", "execution_count": 124, "id": "b59d7264-b0d7-4ea2-82f8-4283e13e8db8", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3 4 5\n" ] }, { "data": { "text/plain": [ "[1, 2, 3, 4, 5]" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" } ], "source": [ "inp = input().split()\n", "list(map(int, inp))" ] }, { "cell_type": "code", "execution_count": 125, "id": "e741f412-fc3d-4352-a8c0-d6c5bd674505", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "first, second = map(int, input().split())\n", "print(first + second)" ] }, { "cell_type": "code", "execution_count": 126, "id": "49eeff95-da8d-4ac6-9b01-de03cf18ee31", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "6\n" ] } ], "source": [ "first, second, third = map(int, input().split())\n", "print(first + second + third)" ] }, { "cell_type": "code", "execution_count": 123, "id": "14861e3e-fb25-4f59-93d9-6c8b7ac3e953", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3 4 5 6 7\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "28\n" ] } ], "source": [ "L = list(map(int, input().split()))\n", "print(sum(L))" ] }, { "cell_type": "code", "execution_count": 23, "id": "06b07e71-5774-40a4-aa95-de8032486842", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3 4 5 6 7 7 8\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "43\n" ] } ], "source": [ "print(sum(list(map(int, input().split()))))" ] }, { "cell_type": "code", "execution_count": 127, "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(map(int, 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 \n", "10" ] }, { "cell_type": "code", "execution_count": 128, "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": 129, "id": "030e342c-0f7c-4c1b-872b-fe99613f7d89", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[4, 9, 5, 1, 10]" ] }, "execution_count": 129, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S1" ] }, { "cell_type": "code", "execution_count": 130, "id": "266a755f-4042-4864-b679-a934c5bd9b16", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[5, 7, 2, 4, 1]" ] }, "execution_count": 130, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S2" ] }, { "cell_type": "code", "execution_count": 132, "id": "70d710cd-dfd5-4907-82be-9ca17eba4bca", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "9\n", "10\n" ] } ], "source": [ "# naive solution, \n", "for x in S1: \n", " if x not in S2:\n", " print(x)" ] }, { "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": 134, "id": "a2c50d63-8f01-433b-9733-4c1759d0ed6f", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 4 9 5 1 10\n", " 5 7 2 4 1\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "9\n", "10\n" ] } ], "source": [ "S1 = map(int, input().split())\n", "S2 = set(map(int, input().split()))\n", "\n", "for x in S1:\n", " if x not in S2:\n", " print(x)" ] }, { "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": 135, "id": "ab9c116b-d685-46dd-a534-421fbcab019c", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 5 6 4 6 3 4 1\n" ] } ], "source": [ "a = list(map(int, input().split()))" ] }, { "cell_type": "code", "execution_count": 136, "id": "89178e57-7715-4cd1-9ecb-34393f15ed8a", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[5, 6, 4, 6, 3, 4, 1]\n" ] } ], "source": [ "print(a)" ] }, { "cell_type": "code", "execution_count": 138, "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": 139, "id": "f953eb9b-26e1-4e08-bef6-74bbf1bd08bf", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 139, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solve(a)" ] }, { "cell_type": "code", "execution_count": 140, "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": 141, "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": 142, "id": "5f6d774e-8eec-46c8-996d-5c2845e59ba7", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 142, "metadata": {}, "output_type": "execute_result" } ], "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": 143, "id": "9a9a9912-03d4-4dd4-ade3-b54affb8e633", "metadata": {}, "outputs": [], "source": [ "import random" ] }, { "cell_type": "code", "execution_count": 144, "id": "eb73302a-9fbe-426e-ac72-1e3b11a662f7", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 144, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random" ] }, { "cell_type": "code", "execution_count": 145, "id": "b41a3476-2ff0-4e4d-84bd-6f4a3a30ca37", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "module" ] }, "execution_count": 145, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(random)" ] }, { "cell_type": "code", "execution_count": 146, "id": "68c1bddb-5656-4972-813b-3c14dc9ce365", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "59" ] }, "execution_count": 146, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random.randrange(100)" ] }, { "cell_type": "code", "execution_count": 147, "id": "f3824cbb-d42e-4a09-acab-e13658d8b21b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "180" ] }, "execution_count": 147, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random.randrange(100, 199)" ] }, { "cell_type": "code", "execution_count": 151, "id": "b39cbe7b-8847-4aff-8844-568d7f0a94c5", "metadata": {}, "outputs": [], "source": [ "N = random.randrange(1,1000)" ] }, { "cell_type": "code", "execution_count": 152, "id": "4dfa75d3-8ece-43bc-8019-db716d68b0cd", "metadata": {}, "outputs": [], "source": [ "a = [random.randrange(1,100) for i in range(N)]" ] }, { "cell_type": "code", "execution_count": 153, "id": "54091c81-aba5-457b-b5fb-fa0a4542888c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "321\n" ] } ], "source": [ "print(N)" ] }, { "cell_type": "code", "execution_count": 154, "id": "1bdae67b-eae1-489c-8fd6-d55002539ab5", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[33, 31, 58, 10, 25, 4, 41, 1, 86, 70, 26, 82, 33, 37, 42, 57, 79, 18, 6, 64, 64, 10, 89, 2, 75, 96, 85, 16, 84, 7, 94, 92, 94, 2, 18, 40, 34, 20, 11, 76, 39, 94, 19, 60, 42, 65, 34, 42, 2, 46, 78, 2, 28, 87, 35, 88, 34, 54, 58, 58, 88, 43, 55, 11, 33, 42, 34, 41, 8, 87, 57, 49, 1, 55, 1, 52, 43, 84, 94, 8, 41, 75, 12, 75, 25, 24, 53, 27, 75, 42, 64, 72, 54, 11, 92, 3, 6, 73, 1, 44, 21, 98, 76, 16, 62, 47, 35, 48, 3, 70, 99, 8, 37, 20, 94, 63, 84, 22, 83, 47, 91, 13, 48, 91, 2, 41, 50, 19, 7, 37, 11, 7, 92, 84, 33, 98, 97, 91, 42, 15, 62, 59, 24, 55, 21, 55, 60, 59, 63, 18, 78, 89, 72, 49, 74, 3, 83, 94, 15, 95, 51, 85, 40, 9, 93, 6, 31, 79, 6, 40, 66, 19, 97, 62, 11, 78, 93, 76, 64, 52, 97, 25, 51, 37, 83, 98, 45, 91, 39, 67, 74, 24, 45, 74, 36, 34, 72, 50, 2, 32, 6, 77, 35, 78, 9, 36, 45, 25, 99, 28, 36, 87, 99, 55, 81, 94, 54, 98, 58, 5, 84, 35, 96, 67, 65, 76, 25, 17, 80, 53, 91, 11, 30, 17, 28, 88, 95, 50, 85, 99, 92, 80, 53, 67, 80, 55, 71, 78, 97, 88, 1, 48, 97, 13, 71, 36, 20, 3, 28, 41, 91, 93, 23, 29, 60, 19, 63, 2, 8, 35, 63, 94, 28, 43, 85, 92, 97, 91, 52, 47, 99, 69, 56, 3, 24, 7, 12, 40, 11, 53, 59, 29, 54, 12, 21, 24, 36, 81, 38, 12, 22, 5, 91, 2, 56, 10, 89, 50, 3, 52, 61, 56, 55, 11, 92, 36, 95, 90, 88, 2, 98]\n" ] } ], "source": [ "print(a)" ] }, { "cell_type": "code", "execution_count": 155, "id": "3e89db80-3181-47b7-8569-cdfc7ea5fa60", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 155, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solve(a)" ] }, { "cell_type": "code", "execution_count": 156, "id": "a23d2fe9-ddc5-4be1-a2dd-d504b603fb0e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 156, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solve_fast(a)" ] }, { "cell_type": "code", "execution_count": 157, "id": "ea280ca6-9ab8-4e3a-afe0-a63b784206d7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done!\n" ] } ], "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": 158, "id": "02c79cdf-d2b4-4080-93b7-8e22b3af5a91", "metadata": {}, "outputs": [], "source": [ "import itertools" ] }, { "cell_type": "code", "execution_count": 159, "id": "884db3bf-9560-4809-8ddc-39d497d4a38c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]" ] }, "execution_count": 159, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(itertools.permutations([1,2,3]))" ] }, { "cell_type": "code", "execution_count": 160, "id": "6025aeed-1734-4aa2-99e6-8f5637f8dd12", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(1, 2, 3)\n", "(1, 3, 2)\n", "(2, 1, 3)\n", "(2, 3, 1)\n", "(3, 1, 2)\n", "(3, 2, 1)\n" ] } ], "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": 161, "id": "268647c8-cf1a-4597-8f72-e402cb0c8d0f", "metadata": {}, "outputs": [], "source": [ "daltons = [\"Joe\", \"Jack\", \"William\", \"Averel\"]" ] }, { "cell_type": "code", "execution_count": 162, "id": "019bdaf5-9c6c-43ff-8731-72c90d31ecf1", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('Joe', 'Jack', 'William')\n", "('Joe', 'Jack', 'Averel')\n", "('Joe', 'William', 'Averel')\n", "('Jack', 'William', 'Averel')\n" ] } ], "source": [ "for x in itertools.combinations(daltons, 3):\n", " print(x)" ] }, { "cell_type": "code", "execution_count": 163, "id": "59e1b98f-6b7c-472c-a2b2-be6878c61e74", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(1, 2, 3, 4)]" ] }, "execution_count": 163, "metadata": {}, "output_type": "execute_result" } ], "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": 165, "id": "ffe32d8c-db98-44a2-911e-09c1c15e8f83", "metadata": {}, "outputs": [ { "name": "stdin", "output_type": "stream", "text": [ " 1 2 3 4 2\n" ] } ], "source": [ "L = list(map(int, input().split()))" ] }, { "cell_type": "code", "execution_count": 166, "id": "02883e2a-7fae-4fe1-91e7-8ff2402450e7", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 2]" ] }, "execution_count": 166, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L" ] }, { "cell_type": "code", "execution_count": 169, "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": 171, "id": "6e9fe9b0-1633-4d0f-9fb5-decdb6b0b481", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2, 4)" ] }, "execution_count": 171, "metadata": {}, "output_type": "execute_result" } ], "source": [ "partition(L)" ] }, { "cell_type": "code", "execution_count": 172, "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": 175, "id": "70ab65f3-e5ad-4d20-99a3-d05c71e55951", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 175, "metadata": {}, "output_type": "execute_result" } ], "source": [ "partition(L) == None # No solution for this input" ] }, { "cell_type": "code", "execution_count": 176, "id": "0c1b6889-ce56-454a-bffe-c7d6f5f0bf3e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2, 4)" ] }, "execution_count": 176, "metadata": {}, "output_type": "execute_result" } ], "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 }