Practice Problems

If you’d like some extra practice in preparation for the timed exercises or the final exam, we have compiled a list of interesting problems from Advent of Code, a yearly set of programming puzzles that are released in an advent calendar schedule.

To test whether your solutions are correct, you will need to submit your solution through the Advent of Code website. Please note that Advent of Code won’t ask you for your code: instead, each problem will ask you to compute a value based on some inputs (you can think of it as there being a single automated test that determines whether your solution is correct or not)

Additionally, each problem is divided into two tasks, and their website will not reveal the second (typically more difficult) task until you solve the first one. Unless we suggest otherwise, we encourage you to try to complete both tasks. Also, while not required by Advent of Code, we encourage you to think about how to define a specific function that will solve each of the tasks, potentially with some additional helper functions, instead of just throwing some code together in IPython.

We have also provided links to possible solutions for each problem. That said, we encourage you to first attempt solving the problem on your own before looking at the solution. Furthermore, Advent of Code is a popular event where participants are encouraged to share their solutions broadly; looking at other published solutions online can be a great way to learn about the different ways of approaching a problem. Advent of Code also has a very active subreddit with lots of information about solutions, strategies, etc.

List/Loops

2019: Day #1

• Problem

• Solution

2020: Day #1

• Problem

• Solution

2020: Day #2

• Problem

• Solution

Note: this problem also involves some string processing.

2019: Day #4

• Problem

• Solution

Note: This is a slightly challenging problem, but one that can really help you gain a solid understanding of lists. You may want to start by first implementing an “is_valid_password” function.

2020: Day #13 [Task 1 only]

• Problem

• Solution

Note: Task 2 involves higher math that we would not expect you to know in this class.

Sets

2020: Day #6

• Problem

• Solution

Dictionaries

2020: Day #10 [Task 1 only]

• Problem

• Solution

Note: Task 2 is much more challenging and involves recursion.

Problem Solving

2019: Day #3

• Problem

• Solution

Hint: Despite how the problem is stated, you should avoid approaching it as a list-of-lists problem. Instead of creating a grid to “draw” the wires on, think instead about how you could keep track of the coordinates that a wire goes through.

2020: Day #9

• Problem

• Solution

2020: Day #15

• Problem

• Solution

Recursion

2020: Day #10 [Task 2 only]

• Problem

• Solution

We encourage you to approach this task as simply writing a recursive function to recursively generating the “arrangement of jolts”, as that is representative of the kinds of problems we could assign in CS 121.

However, while you will be able to test your solution with the smaller test cases shown in the problem, writing a function that generates the arrangements won’t work for the larger test cases, which involve trillions of arrangements. This requires a much more clever solution focused on counting the arrangements without generating them. We encourage you to think about how to do this as well, and it should be possible for you to come up with a recursive counting algorithm that works for the small test cases. However, solving the problem fully requires applying concepts and skills we have not covered in CS 121, so don’t be discouraged if you can’t figure it out.

2020: Day #7

• Problem

• Solution

This is a pretty challenging problem, but which can provide good practice once you feel like you’re getting comfortable with recursion.

Parsing the input is non-trivial, so we provide a function that will do this for you:

import re

def read_rules(lines):
    """
    Parses the string representation of the rules.

    Input:
      - lines (list of strings): Each string is one rule (one line
        in the input, as specificed in the problem)

    Returns: Dictionary where the keys are colors, and the values are
        lists of (color, amount) tuples. This represents the number
        of bags of other colors that can be contained in a bag of a
        given color.
    """

    rules = {}

    for line in lines:
        m = re.match("(.*) bags contain (.*)\.", line)
        container_bag, contained_bags = m.groups()

        if contained_bags == "no other bags":
            bags = []
        else:
            bags = []
            bag_strs = contained_bags.split(", ")
            for bag in bag_strs:
                amount, color1, color2, _ = bag.split()
                bags.append((f"{color1} {color2}", int(amount)))

        rules[container_bag] = bags

    return rules

Hint: the relationship between the bags may feel like it is a tree, but it is not (i.e., don’t use a Tree data structure!) You should be able to solve the problem using just the dictionary returned by the above function, without needing any additional data structures. You can also assume that there are no “cycles” in the bag rules; for example, suppose that color A can contain color B, and that color B can contain color C. You will never encounter a rule that says that color C can contain color A.