Learn how to program with Python #4 - Solving Puzzles from Advent of Code 2018

<hr /> <h4>Repository <p dir="auto"><span><a href="https://github.com/python" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">https://github.com/python <h4>What will I learn <ul> <li>What are defaultdicts? <li>Extracting arguments with re.search <li>Retrieving the max value of a dict <h4>Requirements <ul> <li>Python 3.7.2 <li><a href="https://pypi.org/project/pipenv/" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Pipenv <li>git <h4>Difficulty <ul> <li>basic <hr /> <h3>Tutorial <h4>Preface <p dir="auto">This tutorial is part of a course where solutions to puzzles from <a href="https://adventofcode.com/2018/" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Advent of Code 2018 are discussed to explain programming techniques using Python. Each puzzle contains two parts and comes with user specific inputs. It is recommended to try out the puzzle first before going over the tutorial. Puzzles are a great and fun way to learn about programming. <p dir="auto">While the puzzles start of relatively easy and get more difficult over time. Basic programming understanding is required. Such as the different type of variables, lists, dicts, functions and loops etc. A course like <a href="https://www.codecademy.com/learn/learn-python" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Learn Python2 from Codeacademy should be sufficient. Even though the course is for Python two, while Python 3 is used. <p dir="auto">This tutorial will look at <a href="https://adventofcode.com/2018/day/4" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">puzzle 4 <p dir="auto">The code for this tutorial can be found on <a href="https://github.com/Juless89/tutorials-aoc" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Github! <h4>Puzzle 4 <p dir="auto">This puzzle is about guards that are performing a shift and fall asleep during that shift. Somebody has spied on the guards and for each guard, the guard id, the moment the guard falls asleep and when the guard wakes up again are recorded. The idea is to analyse this information to think of a plan to circumvent the guard. <h4>Part one <blockquote> <p dir="auto">Strategy 1: Find the guard that has the most minutes asleep. What minute does that guard spend asleep the most? What is the ID of the guard you chose multiplied by the minute you chose? <p dir="auto">Taken from the puzzle question the total amount of <code>minutes and the <code>frequency per minute are needed to answer this question. To store this data <code>defaultdicts will be used. <h4>What are defaultdicts? <p dir="auto">Unlike normal dicts when creating a new <code>key, <code>value pair or asking for a <code>key that does not exist. Insteed of an error a default <code>value will be returned or set. In the case one wants to increment a <code>value inside the dict. If the key does not exist it will be added to the default <code>value. <pre><code>from collections import defaultdict # totals holds the total amount of minutes a guard has spent sleeping # frequency holds the frequency per minute (0-59) for each guard totals = defaultdict(int) frequency = defaultdict(lambda: defaultdict(int)) <p dir="auto"><br /><br /> In python <code>lamba is used to pass a function. In this case it creates a new <code>defaultdict when the default value is called. Thereby creating a nested dict structure. However, the nested dict is not created until the the first time a new key is called. <p dir="auto"><center><img src="https://images.hive.blog/0x0/https://cdn.steemitimages.com/DQme1pN49EAJNXB7LrXqvJTGoZikrjQmqr94R6JHtKabWWH/Apr-11-2019%2020-20-06.gif" alt="Apr-11-2019 20-20-06.gif" /> <h4>Extracting arguments with re.search <p dir="auto">The input for this puzzle has again become more complicated than seen so far. It is important to note that there is always only 1 guard on duty. The minute the guard falls asleep is included and the minute the guard wakes up is not. All guards only sleep between <code>0:00 and <code>0:59. <pre><code>[1518-11-01 00:00] Guard #10 begins shift [1518-11-01 00:05] falls asleep [1518-11-01 00:25] wakes up <p dir="auto">Each line contains a <code>timestamp and an action. There are three different actions. When a guard starts a shift, the guard ID has to be extraced. If <code>asleep or <code>wakes is inside the line the start and end minute can be extracted. <pre><code># sort lines by timestamp for line in sorted(lines): # parse minute minute = int(re.search(r':(\d+)', line).group(1)) if '#' in line: guard = int(re.search(r'#(\d+)', line).group(1)) # guards falls asleep, minute included elif 'asleep' in line: start = minute # guard wakes up, minute not included elif 'wakes' in line: end = minute # for each minute add to totals and frequency for m in range(start, end): totals[guard] += 1 frequency[guard][m] += 1 <p dir="auto">The input does not come <code>sorted. Python is clever enough to recognize the timestamp at the start of each line. To sort the input only <code>sorted() had to be applied to the list of lines. Extracting the <code>minute and <code>guard id is done by using <code>re.search(). Which requires a pattern and a string. <code>r':(\d+) takes all digits after the <code>: and <code>r'#(\d+)' does the same but after a <code>#. This functions returns a match object, to retrieve the value <code>group(1) has to be called on the object. <p dir="auto">When the input is <code>sorted, whenever a guard wakes up all data for this shift is done and the guard can be added to the dicts. This is done for the range <code>start, <code>end. Which included the start minute but excludes the end minute. <h4>Retrieving the max value of a dict <p dir="auto">To solve the first puzzle the guard that has the most minutes of sleep has to be found and the minute this guard has been asleep the most. Since the data is inside dicts using a <code>max() function is not as straight forward. <p dir="auto"><code>.items() returns the a list of tuples <code>(key, value). <pre><code>dict_items([(661, 498), (1663, 512), (419, 439), (859, 408), (2383, 216), (997, 466), (1367, 348), (61, 148), (3407, 385), (3391, 419), (739, 450), (2221, 253), (2297, 391), (2113, 198), (1163, 323), (3203, 337), (733, 570), (113, 151), (2609, 222), (2713, 194)]) <p dir="auto">To retrieve the max value for the value an <code>itemgetter can be used and passed as the key to the <code>max() function. <pre><code>from operator import itemgetter def part_1(totals, frequency): key = itemgetter(1) guard = max(totals.items(), key=key)[0] minute = max(frequency[guard].items(), key=key)[0] return guard * minute <p dir="auto"><code>itemgetter(1) sets the index to 1, that of the value. Since the actual max value is not required, it just needs to be sorted by this value. <code>[0] retrieves the first element. <blockquote> <p dir="auto">What is the ID of the guard you chose multiplied by the minute you chose? <p dir="auto">The answer can then be calculated with: <code>guard * minute <h4>Part two <blockquote> <p dir="auto">Strategy 2: Of all guards, which guard is most frequently asleep on the same minute? What is the ID of the guard you chose multiplied by the minute you chose? <p dir="auto">Solving this puzzle can be done by looping through all the <code>guards inside the <code>frequency dict. For each <code>guard retrieve the <code>minute with the heigest <code>frequency and store that with the <code>score (guard ID * minute). At the end sort the list and retrieve score associated with the highest <code>frequency. <pre><code>def part_2(frequency): items = [] key = itemgetter(1) # for each guard retrieve the minute with the highest # frequency. Store freq and score (guard * minute) for guard in frequency: minute, freq = max(frequency[guard].items(), key=key) items.append((freq, guard * minute)) # return by highest frequency return sorted(items)[-1][1] <p dir="auto">By default <code>sorted() will look at the first value inside the set to sort the list of sets. And sorts from low to high. <pre><code>before [(14, 21813), (14, 51553), (13, 14246), (12, 36937), (7, 69107), (19, 37886), (12, 58781), (7, 2196), (12, 126059), (13, 125467), (16, 35472), (8, 71072), (13, 84989), (5, 71842), (9, 38379), (10, 99293), (17, 35184), (5, 3164), (8, 62616), (7, 116659)] after sorted() [(5, 3164), (5, 71842), (7, 2196), (7, 69107), (7, 116659), (8, 62616), (8, 71072), (9, 38379), (10, 99293), (12, 36937), (12, 58781), (12, 126059), (13, 14246), (13, 84989), (13, 125467), (14, 21813), (14, 51553), (16, 35472), (17, 35184), (19, 37886)] <p dir="auto">The wanted value is at the end of the list, index <code>[-1] and is the 2nd item in the set, index <code>[1]. <h4>Running the code <p dir="auto">Run the code with: <code>python main.py <pre><code>if __name__ == "__main__": # parse input into totals and frequency dicts totals, frequency = parse_input() print(f'Part 1 Answer: {part_1(totals, frequency)}') print(f'Part 2 Answer: {part_2(frequency)}') <p dir="auto"><br /><br /> <center><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQme8hsQJ6oUFrCxX8oiVsfCJ3W8tXqamtvk4rASL92RM1q/Screenshot%202019-04-11%20at%2021.31.21.png" alt="Screenshot 2019-04-11 at 21.31.21.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQme8hsQJ6oUFrCxX8oiVsfCJ3W8tXqamtvk4rASL92RM1q/Screenshot%202019-04-11%20at%2021.31.21.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQme8hsQJ6oUFrCxX8oiVsfCJ3W8tXqamtvk4rASL92RM1q/Screenshot%202019-04-11%20at%2021.31.21.png 2x" /> <h4>Curriculum <p dir="auto"><a href="https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-1---solving-puzzles-from-advent-of-code-2018" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Part 1, <a href="https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-2---solving-puzzles-from-advent-of-code-2018" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Part 2, <a href="https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Part 3 <hr /> <p dir="auto">The code for this tutorial can be found on <a href="https://github.com/Juless89/tutorials-aoc" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Github! <p dir="auto"><span>This tutorial was written by <a href="/@juliank">@juliank.