4 "cell_type": "markdown",
7 "# Summer of Code: Problem 0 worked solution\n",
9 "How to go about solving this problem? This post is a worked example of how to go about it.\n",
11 "If you've not done so already, [have a look at the problem](https://learn2.open.ac.uk/mod/quiz/view.php?id=1352295).\n",
13 "In summary, we're given an input file that looks like this…\n",
15 "Tilly, Daisy-May, Tori\n",
16 "Iona, Deniz, Kobe, Grayson, Luka\n",
17 "Demi, Reanne, Tori\n",
18 "Dafydd, Reanne, Rohit, Kai, Iona, Nojus\n",
19 "Tommy, Rosa, Demi\n",
20 "Daisy-May, Tilly, Grayson, Deniz, Kobe, Tommy, Rohit\n",
21 "Sultan, Iona, Dafydd, Rosa, Kobe, Devan\n",
22 "Tilly, Rohit, Tori, Deniz, Kobe, Jennie\n",
23 "Luka, Tori, Tommy\n",
26 "…and have to solve some tasks with it. \n",
28 "I'll implement this solution in Python 3, but the ideas should translate across to any other programming language. \n",
31 "I'll only think about the first task first. I'll deal with the second part once I've got the first part working.\n",
33 "In summary, the task is to find the maximum number of names on any one line.\n",
35 "## Where to start\n",
36 "Let's think about the overall shape of a solution to this task: the **algorithm**. We're given a text file of invitations and we have to read it. Once we've read the file, we have to split it into lines and then split each line into names, and then do something about counting names on a line.\n",
38 "So, the subtasks are:\n",
39 "1. Read the text file.\n",
40 "2. Split the file into lines.\n",
41 "3. For each line, split the line into names.\n",
42 "4. Count the number of names on each line.\n",
43 "5. Find the highest count.\n",
45 "That doesn't seem anything particularly complicated. There's lots of repetition, but no really complex logic to deal with. \n",
47 "Next, let's think about the **data structures** we'll need. I find that often, once the data structures are sorted, the rest of the program follows. When choosing data structures, I find it helpful to think about what's stored and what operations we need to perform on that data. \n",
49 "In this case, we need to store a bunch of lines and a bunch of names within each line.\n",
51 "We don't do anything with a _name_ apart from count it, so storing it as a simple `string` should be sufficient.\n",
53 "A _line_ is a group of names. All we need to do is count how many names are in a line, so a simple container should do. Let's keep it simple and just just a `list` of names (a `list` of `string`s).\n",
55 "We also need to store the whole set of lines. We'll call that the _invitations_. All we need to do is process all the lines in the invitations to get the answer. Again, a simple container such as a `list` of lines will do. \n",
57 "Let's now take each of these subtasks in turn."
61 "cell_type": "markdown",
64 "## Steps 1 and 2: read a text file\n",
65 "In Python, the `open()` built-in command reads a file. By default, it reads the file as text. It also conveniently allows us to process the file line-by-line. The standard Python idiom for this is:\n",
68 "for line in open('path/to/file'):\n",
69 " # do some processing\n",
71 "As this datafile is in a strange place, store the path in a variable for reuse."
80 "invitation_filename = '../../data/00-invites.txt'"
84 "cell_type": "markdown",
87 "However, Python leaves the trailing newline character on the end of each line. We can get rid of that with the `str.strip()` method.\n",
89 "We also need to create the _invitations_ to store the lines in. This starts as an empty list, and we `append()` lines to it as they're read.\n",
91 "Note that the line-as-read is just a long `string` of all the names."
105 "execution_count": 2,
107 "output_type": "execute_result"
111 "# Create the empty list\n",
112 "invitation_lines = []\n",
114 "# Iterate over all the lines in the file\n",
115 "for line in open(invitation_filename):\n",
116 " invitation_lines.append(line.strip())\n",
118 "# Finish by saying how many lines we've read\n",
119 "len(invitation_lines)"
123 "cell_type": "markdown",
126 "## Step 3: split the invitation lines into names\n",
127 "Now we have the list of invitation lines, we can process each line and split it into names. Luckily for us, the built-in `str.split()` method does this for us. It works like this:"
132 "execution_count": 3,
138 "['Tom', 'Dick', 'Harry']"
141 "execution_count": 3,
143 "output_type": "execute_result"
147 "'Tom, Dick, Harry'.split(', ')"
151 "cell_type": "markdown",
154 "This splits a string into parts, using the given delimiter. \n",
156 "We can use that to `split` each instruction line into names. We follow the same overall pattern as above, creating an empty list lf `invitations` and `append`ing to it as we process each line."
161 "execution_count": 4,
198 "execution_count": 4,
200 "output_type": "execute_result"
204 "# Create the empty list\n",
205 "invitations = []\n",
207 "# Iterate over all the invitations\n",
208 "for line in invitation_lines:\n",
209 " invitations.append(line.split(', '))\n",
211 "# Finish by saying how many lines we've processed, and the first split invitation\n",
212 "len(invitations), invitations[0]"
216 "cell_type": "markdown",
219 "## Step 4: count the names in each line\n",
220 "The built-in `len()` function counts the number of items in a list. As we have a bunch of name lists, we can use `len()` to count the number of names in each line. \n",
222 "Again, we'll use the same pattern of iterating over all the lines in the invitations."
227 "execution_count": 5,
233 "[28, 13, 20, 20, 22]"
236 "execution_count": 5,
238 "output_type": "execute_result"
242 "# Create the empty list\n",
243 "invitation_lengths = []\n",
245 "# Iterate over all the invitations\n",
246 "for line in invitations:\n",
247 " invitation_lengths.append(len(line))\n",
249 "# Finish by giving the first few counts\n",
250 "invitation_lengths[:5]"
254 "cell_type": "markdown",
257 "## Step 5: find the highest count\n",
258 "There's a couple of ways we can go here. The built-in `max()` function, when passed a list of numbers, finds the maximum value in that list. That means the solution is easy:"
263 "execution_count": 6,
272 "execution_count": 6,
274 "output_type": "execute_result"
278 "max(invitation_lengths)"
282 "cell_type": "markdown",
285 "But there's a more general pattern for when `max()` isn't applicable. It uses an _accumulator_ which starts off at some initial value and is updated as each item is processed. The accumulator could be something like a running total when going through a list of amounts. In this case, the accumulator is the most names we've seen on a line so far. If we see a longer line than any we've seen before, we update the most names accumulator.\n",
287 "That gives this pattern:"
292 "execution_count": 7,
301 "execution_count": 7,
303 "output_type": "execute_result"
307 "# Set the accumulator to some initial value\n",
310 "# Iterate over all the invitation lengths\n",
311 "for name_count in invitation_lengths:\n",
312 " if name_count > most_names:\n",
313 " most_names = name_count\n",
315 "# Finish by giving the highest name\n",
320 "cell_type": "markdown",
324 "We have a working solution, but it's rather repetitive. Can we make it simpler? In particular, do we really need to walk over the list of invitations so many times?\n",
326 "_Refactoring_ is the process of tidying up and simplifiying an already-working solution into something better.\n",
328 "Here's the solution we have."
333 "execution_count": 8,
342 "execution_count": 8,
344 "output_type": "execute_result"
348 "# Create the empty list\n",
349 "invitation_lines = []\n",
351 "# Iterate over all the lines in the file\n",
352 "for line in open(invitation_filename):\n",
353 " invitation_lines.append(line.strip())\n",
355 "invitations = []\n",
357 "# Iterate over all the invitations\n",
358 "for line in invitation_lines:\n",
359 " invitations.append(line.split(', '))\n",
361 "invitation_lengths = []\n",
363 "# Iterate over all the invitations\n",
364 "for line in invitations:\n",
365 " invitation_lengths.append(len(line))\n",
367 "# Give the solution\n",
368 "max(invitation_lengths)"
372 "cell_type": "markdown",
375 "As you can see, each stage involves cycling over the list of all invitations. As each stage just transforms individual lines, we can do all of the operations within one loop."
380 "execution_count": 9,
389 "execution_count": 9,
391 "output_type": "execute_result"
395 "# Create the empty list\n",
396 "invitation_lengths = []\n",
398 "# Iterate over all the lines in the file\n",
399 "for line in open(invitation_filename):\n",
400 " stripped_line = line.strip()\n",
401 " names = stripped_line.split(', ')\n",
402 " name_count = len(names)\n",
403 " invitation_lengths.append(name_count)\n",
405 "# Give the solution\n",
406 "max(invitation_lengths)"
410 "cell_type": "markdown",
413 "If we include the \"accumulator\" version of finding the longest line, we don't need to store any of the invitation lines at all, like this:"
418 "execution_count": 10,
427 "execution_count": 10,
429 "output_type": "execute_result"
433 "# Set the accumulator to some initial value\n",
436 "# Iterate over all the lines in the file\n",
437 "for line in open(invitation_filename):\n",
438 " stripped_line = line.strip()\n",
439 " names = stripped_line.split(', ')\n",
440 " name_count = len(names)\n",
441 " if name_count > most_names:\n",
442 " most_names = name_count\n",
444 "# Finish by giving the highest name\n",
449 "cell_type": "markdown",
452 "## A more Pythonic approach\n",
453 "If you're interested, a more \"Pythonic\" approach (using idiomatic Python) to this problem is to use _list comprehensions_ rather than lots of `append` calls. \n",
455 "We can find `invitation_lines` like this:"
460 "execution_count": 11,
464 "invitation_lines = [line.strip() for line in open(invitation_filename)]"
468 "cell_type": "markdown",
471 "and then find the `invitations` from `invitation_lines`"
476 "execution_count": 12,
480 "invitations = [line.split(', ') for line in invitation_lines]"
484 "cell_type": "markdown",
487 "Or even combine the two steps in one call:"
492 "execution_count": 13,
496 "invitations = [line.strip().split(', ') for line in open(invitation_filename)]"
500 "cell_type": "markdown",
503 "From `invitations`, we can find the number of names on each line with another comprehension:"
508 "execution_count": 14,
512 "invitation_lengths = [len(names) for names in invitations]"
516 "cell_type": "markdown",
519 "and then find the maximum length:"
524 "execution_count": 15,
533 "execution_count": 15,
535 "output_type": "execute_result"
539 "max(invitation_lengths)"
543 "cell_type": "markdown",
546 "If you really want to go to town, you can combine all these steps into a one-liner:"
551 "execution_count": 16,
560 "execution_count": 16,
562 "output_type": "execute_result"
566 "max(len(line.strip().split(', ')) for line in open(invitation_filename))"
570 "cell_type": "markdown",
574 "Now to look at the second part. This is a bit more complex. We have to _count_ the number of times each name appears anywhere in the file, and then count how many names appear more than once.\n",
576 "The first chunk of the algorithm is the same as before. In summary, my approach is:\n",
578 "So, the subtasks are:\n",
579 "1. Read the text file.\n",
580 "2. Split the file into lines.\n",
581 "3. For each line, split the line into names.\n",
582 "4. _Something something count names in whole input._\n",
583 "5. Count how many names appear more than once.\n",
585 "The first three steps are the same as before.\n",
587 "Note the detail about step 4. \n",
589 "Perhaps things will be clearer if we think about the **data structure** for keeping track of the counts of all the names.\n",
591 "What we want is a data structure that holds a bunch of names, and associates each name with the number of times we've seen that name so far. When we first see a name in the file, we want to include it in the data structure. When we see a name _again_, we want to incremement the number times we've seen it.\n",
593 "In subtask 5, we can look at that data structure and pick out all the names with a count of two or more.\n",
595 "This association of a _name_ and a _number_ is a classic use of a _key-value store_, which crops up all over computing. In this case, the name is the key and the number of occurrences is the value. A simple built-in key-value store is called a `dict` in Python, a `Hash` in Ruby, and a `Map` in Java (and an `object` in JavaScript, but… well, [JavaScript](https://www.destroyallsoftware.com/talks/wat)).\n",
597 "That seems like a useful thing to use. Going back to the problem, we have the updated list of subtasks:\n",
599 "1. Read the text file.\n",
600 "2. Split the file into lines.\n",
601 "3. For each line, split the line into names.\n",
602 "4. For each name in the input:\n",
603 " 1. If it's in the name counts, increase its count by 1\n",
604 " 2. Otherwise, include the name in the name counts with a count of 1\n",
605 "5. Count how many names appear more than once.\n",
607 "This is a slightly more complex algorithm as it includes both loops and conditionals, but it's not too bad.\n",
609 "We can reuse the first three subtasks from Part 1, and assume the `invitations` list-of-lists-of-names already exists. "
613 "cell_type": "markdown",
617 "When we implement step 4 using the logic above, the Python code looks like this:"
622 "execution_count": 17,
627 "name_counts = {}\n",
629 "# for each name in the input\n",
630 "for invite in invitations:\n",
631 " for name in invite:\n",
632 " # record how many times we've now seen this name\n",
633 " if name in name_counts:\n",
634 " name_counts[name] += 1\n",
636 " name_counts[name] = 1"
640 "cell_type": "markdown",
643 "If you squint, you can see something like the \"accumulator\" pattern again, with the `name_counts` `dict` being the accumulator.\n",
645 "(If you want a more Pythonic approach, take a look at the [`defaultdict`](https://docs.python.org/3/library/collections.html#defaultdict-objects) and [`Counter`](https://docs.python.org/3/library/collections.html#counter-objects) objects in the [`collections`](https://docs.python.org/3/library/collections.html) standard library.)"
649 "cell_type": "markdown",
653 "Talking of accumulators, we use that pattern again to do step 5, but this time we're iterating over the `name_counts` rather than the input. In this case, the accumulator of the number of people invited. "
658 "execution_count": 18,
667 "execution_count": 18,
669 "output_type": "execute_result"
673 "number_invited = 0\n",
674 "for name in name_counts:\n",
675 " if name_counts[name] > 1:\n",
676 " number_invited += 1\n",
682 "cell_type": "markdown",
685 "## An alternative way\n",
686 "There's another way of solving this task. As we only need to record the names we've seen twice or more, we can walk over the input building that list of invitiations directly. \n",
688 "The trick is to maintain two lists of names: one is the list of names to invite, and one is a list of names we've seen in the input. \n",
690 "When we see a name for the first time, we add it to the list of seen names. When we see a name again, it's already in the seen names so we know to add it ot the list of invited people. \n",
692 "In both cases, we don't want to add a name to either list if it's already there. That implementation gets easier if we use `set`s, which don't allow duplicate items. That means we don't use `list`s for `seen` and `invited`, but use `set`s instead. \n",
694 "That gives the algorithm of:\n",
695 "1. For each name in the input\n",
696 " 1. If the name is in the seen set\n",
697 " 1. Add it to the invited set\n",
698 " 2. Add the name to the seen set\n",
700 "Note that the order of these steps is important: we want to check for inviting a person _before_ recording that we've seen them at all."
705 "execution_count": 19,
714 "execution_count": 19,
716 "output_type": "execute_result"
720 "# create empty sets\n",
721 "seen = set() # all the names we've seen\n",
722 "invited = set() # the people to invite\n",
724 "# for each name in the input\n",
725 "for invite in invitations:\n",
726 " for name in invite:\n",
727 " # invite this person if we've seen them before\n",
728 " if name in seen:\n",
729 " invited.add(name)\n",
730 " # record that we've now seen this person\n",
737 "cell_type": "markdown",
740 "## Which is better?\n",
741 "Which of these two ways is better? It depends a lot on what you mean by \"better\". \n",
743 "The approach with the `dict` of counts is perhaps easier to follow as a _process_. It's also more easily extendable to other conditions and tasks, such as different thresholds for getting an invite or finding the most popular person (i.e. the person who was mentioned the most).\n",
745 "The approach with `set`s of names is perhaps closer to a description of the _conditions_ the solution must fulfil: `invited` is the `set` of names we've `seen` and `seen` again. But it's less flexible: how would you use that approach to ensure you only invited people who were mentioned at least three times, or ten times?\n",
747 "But as a learning exercise, the main thing is seeing many different ways of solving problems so you have a range of alternatives to choose from when you come across fresh challenges."
752 "execution_count": null,
760 "display_name": "Python 3",
761 "language": "python",
769 "file_extension": ".py",
770 "mimetype": "text/x-python",
772 "nbconvert_exporter": "python",
773 "pygments_lexer": "ipython3",
projects / summerofcode2018soln.git / blob