Category: Programming

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 3 of Advent of Code, a.k.a. “The Toboggan Puzzle”.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 3 challenge.

The Day 3 challenge, part one

The challenge

Here’s the text from part one of the challenge:

With the toboggan login problems resolved, you set off toward the airport. While travel by toboggan might be easy, it’s certainly not safe: there’s very minimal steering and the area is covered in trees. You’ll need to see which angles will take you near the fewest trees.

Due to the local geology, trees in this area only grow on exact integer coordinates in a grid. You make a map (your puzzle input) of the open squares (.) and trees (#) you can see. For example:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

These aren’t the only trees, though; due to something you read about once involving arboreal genetics and biome stability, the same pattern repeats to the right many times:

..##.........##.........##.........##.........##.........##.......  --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

You start on the open square (.) in the top-left corner and need to reach the bottom (below the bottom-most row on your map).

The toboggan can only follow a few specific slopes (you opted for a cheaper model that prefers rational numbers); start by counting all the trees you would encounter for the slope right 3, down 1:

From your starting position at the top-left, check the position that is right 3 and down 1. Then, check the position that is right 3 and down 1 from there, and so on until you go past the bottom of the map.

The locations you’d check in the above example are marked here with O where there was an open square and X where there was a tree:

..##.........##.........##.........##.........##.........##.......  --->
#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........X.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...#X....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

In this example, traversing the map using this slope would cause you to encounter 7 trees.

Starting at the top-left corner of your map and following a slope of right 3 and down 1, how many trees would you encounter?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into Python. This involves pasting it into a triple-quoted string and assigning it to the variable raw_input.

raw_input = """...#...###......##.#..#.....##.
..#.#.#....#.##.#......#.#....#
......#.....#......#....#...##.
...#.....##.#..#........##.....
...##...##...#...#....###....#.
...##...##.......#....#...#.#..
..............##..#..#........#
#.#....#.........#...##.#.#.#.#
.#..##......#.#......#...#....#
#....#..#.#.....#..#...#...#...
#.#.#.....##.....#.........#...
......###..#....#..#..#.#....#.
##.####...#.............#.##..#
....#....#..#......#.......#...
...#.......#.#..#.........##.#.
......#.#.....###.###..###..#..
##..##.......#.#.....#..#....#.
..##.#..#....#.............##.#
....#.#.#..#..#........##....#.
.....####..#..#.###..#....##..#
#.#.......#...##.##.##..#....#.
.#..#..##...####.#......#..#...
#...##.......#...####......##..
...#.####....#.#...###.#.#...#.
....#...........#.##.##.#......
.....##...#.######.#..#....#..#
.#....#...##....#..######....#.
...#.....#...#####.##...#..#.#.
.....#...##........##.##.##.###
#.#..#....##....#......#....#.#
......##...#.........#....#.#..
###..#..##......##.#####.###.##
#.....#..##.##....#...........#
##..#.#..##..#.#.....#......#..
.#.##.#..#.#....##..#..#....#..
.#......##..##.#...#..#.......#
#....##.##..###..###......##.#.
....###..##.......#.###.#....#.
..##........#........##.....#..
.#..#.....#...####.##...##.....
....#.#.#.....#.##..##.....#..#
..............#.....#...#.....#
.#.....#......###...........#.#
.....#.#......#.##..#..........
.#......###............#.#.##..
.#.#....##.#..###.....#.##..#.#
.......#.#.#..#..#..#...##..#.#
.#.###...##.#.#.####.#.#...#...
...#.#....#......##.##.#.......
#...#.....##....#........##....
.....###...#.##.#......##.#..#.
..#...##.##.###..#..#......####
.#.##.#..#.##..##..........##..
..#.#.#..#.#.....#...###.....#.
..#..#.#....#.##.............##
.......#..###..#.#...#.....##.#
####.#.#......#..#.##.........#
..........#.....#..##......###.
..#..............#...#..##.....
......#.#.#..#.##.....####..##.
.##.#..#.#....#.......#..#.....
..#..#..#.##.#....###.#.#.#.#.#
.....#....#......###..#........
#.#.#..#...###.....#......#.##.
...#.#....#.#......#........#..
..#...###.#...#..#....##...#..#
.###.##..#..#...###.#..#.####..
#....#..##..##..#......#...##..
#.#..#...#..#...###..#.#.##....
##....#....##.####...#.#.###...
##.#...#.......#.##.##....#...#
..#.#..........#..#.#.#....#..#
..#........#...#....#....#....#
..#..#....#.......#........#...
......#....#....##.#....#.#.##.
.##...###.##.##....##.#...###..
.....##..#.#.....###..#.....###
....##.#.##...##..##........#..
#...#..##.#.#....#......#...#..
.###.##.#........#.####....#...
#.##.....#..#...#..##.##..#.#..
.....#.#..#....#..#...##.##.#..
.#......#####...##...#.#.###.#.
#......##....#.....#......##.#.
#.#.##.###.#......#####..#.....
........###.#...#..#.#........#
....#....###..#.##.#...#....#..
..........#..#.#....#...#.#...#
#.##......###.#.#.#....####...#
...#.#....#........##.#.....##.
.....##..#.#.#..###...##...#...
#...#...#....#....##........#..
.....#.........##.#......#..#..
#.....##..#.###.....#....##.##.
...#..#..#.#........##...##.#.#
..#..##.###.....#.#.....###.##.
..###.........#...##.....###...
...###...##.#...##....##.......
.#.#..#...###..#.#....#....#...
##..#.......#....#.#...#..#..#.
..#......#....####..##..#.###.#
..#.......##........#.#.#..#...
.#.......#.##.#.##.#.......#..#
###...#...#...#...#..#...#...##
..#..........#..###........##..
.##..#....##......##........#.#
......#.##......#......##...#.#
.#.#....#.#.#........#......#..
.#.#..#....####..##...##....#..
.#...##..#..#..#####....##.#...
.##.#.#...#...#.#...#.##.#...#.
###.#...##..#.###.#.....#.##.#.
#.....#.###.#.#...#..#....#.#..
..##..#....#......#.........###
.#...#...##......#...#.####....
..#.##...##..............#.#..#
..#......#..##...........#..#.#
..#####...#..#.......##...###..
..##..#....#.#...###.#...#.....
..#....#..#.#.......#..#.#.#...
.##..#.#.....##....#.......#...
...#.#..###...##....#....##..#.
.....##..#...##.####....##...#.
.......#.........#...#.##..####
........###..#..#.##.###..#....
.#.#..#.##.##.........#...#....
.###......#.....#....##....####
.##..##...........#.....#.....#
#.#.#.#.#.#.##..#.#.#..#.##....
.##.##...##..#....##..###..####
#..##.#......#...###.........#.
#..#...#..##..#..##.....##...#.
#...##..#...##.#.###.#...#.....
.###.....#.......#...#.##.###.#
..........#.#......#...###...##
..##....#.#..#....#.###...#..##
#.#..#....##.##..##.........##.
#.....#.##.###.#..#....##...#..
...#........##...#..###..######
#..#.#.#.#...#....#....###.#..#
...##.##.##.....##..#........#.
..#.#....#..#.......#...##.##.#
###.##.......##..#.####...#.#..
....#.#.....##.....#.#.##...#..
.#..##..#.....#.#..#...#..#..#.
.###....##...#......#.....#....
##.##.###......#...#...###.#...
#...#.##...#.#....##.....####..
#.#.#.#...###...##.............
..#....#.....##.#...#......#...
....#...#......#...#..#...#.#..
.###..#.....#..#...#....#...#..
..#...#.#..###.......#..#.#...#
#...###.##.....#....#..#.#..##.
...#.##.#.##......#.#.#.##.....
........####...##...##..#....#.
.#.#....#....#.#...##.###...##.
#.#...###.#.#.#....#....#.#....
.####.#..#.#....#..#.#..#..#...
#####...#...#...#....#.#.#..##.
..###.##.###...#..........#.##.
##.....#...#....###..###.#.#.#.
#..##.#..#..#..#...#.#...###..#
##....#.#...##......#.#...#...#
.##..........#.#....#...#.##..#
....#....####.#.####......#.###
..##.#.....####.#.####.......#.
#.##.##.#.....#.##......##...#.
......###..#.....#.....##......
..#..#....#.#...#.....#......##
##..#..#..###.#.#..#..##.....#.
#....#.#.....#####...#.#.......
.....#..#....#.#.#..#...#...#..
............#.##......##.##.#.#
....#...#.#........###....#....
..#..#...###.#....##..#..###.##
#.##....#...#.....##..#.##.#...
...##..###...#.#.....##.#......
.#..#.##.#####..#.......#..###.
...#.##...###.....####.#.#.....
.#......##.#.#.#.#.##.#.....#..
..#.##.#..##.......#.#.....##..
..................#....#...#...
.##.#..#.#.#..#.......#.#..##.#
....#........#......#..####..#.
#...#...##..##.#..#.......##...
#..#..#..#..#........####..#.#.
..#.#......#..#.##.##.#.#...#.#
...#..#......#.#.###.#.##..##..
..#...##.....#..#...##..#.#....
#.........#....#..#....##.##..#
..#..#.#....#..#...#.##.....#..
...#..#...#.#.....#..##..#.#...
....#........#.#....##..##..#..
#.....#.#..#.......#.##.....#..
.#.###.###...##...##..###...#..
.##.##.......#.#......#.....#.#
...#....##....#..#..........#.#
..#.##.........#.#.....#.....#.
...#.##..##.......##..##...#...
#.##......##.##..#.....##...##.
#.#.#..##...#.#............#.#.
....#.....#......##...#.#.....#
...#.#......#.#...###.......#..
......##..###....#.#...#.#####.
..#..#.#.#...##.#...###..##..#.
##.##.#.#.##.#..#....#...#...#.
#..#....######.##.#...#...#.#..
.#..#.##....#..#.#.......#....#
....#....#......##....##.#.#...
.###......#..#..#.......####..#
.#.#.....#..###...........##...
.##..##.##.....####..#..#..##..
..#..##.#......#...###.##..#.#.
....##..#.....###..#.##....##.#
#..#......#....#.........#.....
.#...#.....#.#..#..##....#.....
.##..#...#..##.#..#...........#
..#..##........##.......#..#...
#.....#....#....#.#.#...##.#...
...#...#.#.#..#.##.#.#...#.....
..#..#.#....#....###....#.#.#..
...###..#...#..#....#.....#....
...#...#.#..#.....#...###......
##......#..........#.#.#..#.#.#
....#.....#.....#..#..#.#.#.#..
...####...#.##...#.#..#....#.#.
#.##........##.............#.##
#.#.#.#.#.....................#
.#.###....#..##.##.##....#.....
#.#...#.####.###...#..#..#.#...
.##...#..###.......##..#.#.....
#.#.#.#...#...#.##.....#.......
.##.#.#.#......####..#.#.......
###..........#......#...##...#.
.........##...#.##...#.#.......
...#.#.....#...#..#...#..##..#.
.#..###...#.#.........###....#.
##..#...#........#.........##..
.....#...#.#...#.#.#...........
..#....##...#.#..#..#.##....##.
.##....#.#.....##.#..#..#...##.
..##......#.#...#.#.......##.#.
##...#..#...##.#........#.##...
#......#.##..#.#..#.###.......#
#.#...#.....#.#......#.#.#.....
#.....#..#.......#....##.#.#..#
###.#....#..##.#.##....#....#..
#.##.##....#.#..#.#...#....#...
####...#####...#.....#....##.#.
....#.#...#.#.##.#.#.##.#.#.###
#.....##.#.....#.#......#.#..#.
.#....##.#..#........#...##.#..
......#...#....##....##....##..
..###.....#....##.#...#..#.....
#....##...##.##..##.#...#...#..
#..#...#...#.#....##..#.#....#.
......................#.....#..
.#..#...#.........#....##...###
.##.#.#...##...#...#...#..#....
.#.###....#.#............##..#.
###..##.#.#.#.#....##...#......
.##................####...##.##
.#.#.........##....#.#.##.##.#.
....#...#...#...##...#.##.#..#.
.#.#........#..##.....#..#....#
##.#..#.#....#.....#...#...#...
.#...##....#.....##....#..#.#.#
####.....#..#....#......###.##.
##..##.#....###.....#...#......
.##.#...#.....#.#..#.#..#.#...#
.....#.#..#..#..###.#...###.#..
.#.#.##.#..#.#..#...#..#.......
..#.....#....#.##.##.##.......#
.#..##....###...#..............
#....#...#.#.......#....##.#...
....#.#..##.#....#..#.#....#.#.
#.........##...#.#.............
#.#.......##.....#...##..##.#.#
.......#....#..##...#..#######.
.#.#...##........#..#.....#.#..
.#.......#..#......#.##.##...##
.........#............#....#..#
.#......#...##...##...#....###.
.........#...#.#.###.......#...
###.#..#.#.#.#......##...#.#...
.#.........##.#....###....#.#..
#.#....#..#.##.#..#....##...#..
###.#...#..#..##........#.###..
.....#....#..#........#..#.##.#
..#.....##......#....#..#.#.#..
.#.........#.....#.....#.......
......#....#.###..#.#....#....#
..#.#..#.#.###.........#..#..#.
..#..#.#.#.........#....##.#.#.
#.......#........##...##....#..
##..#..#...###...#..##..#..#.#.
##..#..#....#.#..##..#..#.#..#.
..##.....##.#..#.#........###..
..#.#..#..##........#...#....##
.##..#....##..#..#..#..#.#....#
#....#.....##........#.....#.##
......#....#.#..#......#.##....
.......#..#..#......##.........
......#...#..##.....#......#..#
#..#..#....##....#........##..#
##....#...#.#.....#####........
...#.#..#.#.##.#.##..##...#....
..#..#..#..#..#....#..#..##...#
.#.....#....##.##....##.....#..
#...#.....#.....#.#...#.#....#.
.###...#..##....#..#...#.###...
....#..##..#.......#.##.##..###
#.......##.....#.......#.#...##
#.....#.#.#....#.#......#.#.#..
..##.....#..###......##........
.....#...#..##....#......#.....
#..#..#....#.#...#..###.......#
.....#.....#....#..#...#.#..##.
#####........#...#..#..##..#.#.
.#..#...#.##....#.#..#......###
#.###.#..#.....##..##....#...#.
.#...#.#####....##..........##."""

I then split() the string into a list, using the newline character as the delimiter. I named the resulting list map_basis, since it’s the basis for a complete map of the hill:

map_basis = raw_input.split("\n")

I did a quick len(map_basis) check to see how long a list I was dealing with. It had 323 items.

Strategy

Looking at the question, it became clear to me that the most important problem was to come up with the answer to this question:

Given a set of coordinates, is there a tree at that location?

First, let’s consider the coordinate system of the problem. It’s not unlike screen coordinates, with the origin — (0, 0) — located at the upper left corner of the screen. x increases as you go right, and y increases as you go down:

All the strings in map_basis are 31 characters wide, and the actual map repeats itself in the x-direction starting at character index 31. This means that for any given line:

• The character at index 31 is the same as the character at index 0.
• The character at index 32 is the same as the character at index 1.
• The character at index 33 is the same as the character at index 2.
• The character at index 34 is the same as the character at index 3.
• And so on…

This means that for any x-coordinate on the actual hill (let’s call it x_hill_coordinate), its corresponding x-coordinate on the map (let’s call it x_map_coordinate) can be defined by:

x_map_coordinate = x_hill_coordinate mod 31

The map doesn’t repeat itself in the y-direction. Any y-coordinate on the actual hill has the same corresponding y-coordinate on the map.

With that in mind, I defined this function:

def is_tree_at_coordinates(hill_x, hill_y):
    map_x = hill_x % 31
    return map_basis[hill_y][map_x] == "#"

This function should return True if and only if there is a tree at the coordinates (hill_x, hill_y).

Going down the hill

Now that I had a function that could tell me where the trees were, it was time to go down the hill! I wrote this function, which takes arguments for rightward and downward movement for each “step”. It then “travels” down the hill, counting trees along the way:

def tree_count_for_slope(right_increment, down_increment):
    right_coordinate = 0
    down_coordinate = 0
    tree_count = 0

    while down_coordinate < len(map_basis):
        if is_tree_at_coordinates(right_coordinate, down_coordinate):
            tree_count += 1
        right_coordinate += right_increment
        down_coordinate += down_increment

    return tree_count

For my input data, the tree count was 230.

The Day 3 challenge, part two

The challenge

Here’s the text of part two:

Time to check the rest of the slopes – you need to minimize the probability of a sudden arboreal stop, after all.

Determine the number of trees you would encounter if, for each of the following slopes, you start at the top-left corner and traverse the map all the way to the bottom:

• Right 1, down 1.
• Right 3, down 1. (This is the slope you already checked.)
• Right 5, down 1.
• Right 7, down 1.
• Right 1, down 2.

In the above example, these slopes would find 2, 7, 3, 4, and 2 tree(s) respectively; multiplied together, these produce the answer 336.

What do you get if you multiply together the number of trees encountered on each of the listed slopes?

In completing part one, I had also completed the crucial piece of part two! Let this be a lesson to Advent of Code participants: Creating a good data structure or interface for the input data will make coming up with the answers that much easier.

The solution was simply to plug in the values above into my tree_count_for_slope() function and multiply the results together:

print(
    tree_count_for_slope(1, 1) * 
    tree_count_for_slope(3, 1) * 
    tree_count_for_slope(5, 1) * 
    tree_count_for_slope(7, 1) * 
    tree_count_for_slope(1, 2)
)

This gave me the solution for my data: 9533698720.

And with that, I had completed Day 3!

If you have any questions, feel free to post them in the comments.

Solutions for other days in Advent of Code 2020

Solutions for other days in Advent of Code 2020

• Day 1: Report Repair
• Day 2: Password Philosophy
• Day 4: Passport Processing
• Day 5: Binary boarding
• Day 6: Custom Customs
• Day 7: Handy Haversacks
• Day 8: Handheld Halting

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

For those of you not familiar with Advent of Code, here’s a quick description, taken straight from their “About” page…

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.

You don’t need a computer science background to participate – just a little programming knowledge and some problem solving skills will get you pretty far. Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.

Advent of Code has been around since 2015, and each year, its puzzles have all been centered around a “Save Christmas” theme. Over the past five holidays seasons, programmers all over the world have solved problems using code in order to:

• Helping Santa with various tasks (2015)
• Assisting Santa with his rivalry with the Easter Bunny (2016)
• Debugging the “Naughty or Nice” system (2017)
• Saving Santa from evil time travelers who are altering history to erase him from existence (2018)
• Rescuing Santa, who’s stranded at the edge of the solar system (2019)

This year’s puzzles are about saving the well-earned vacation you’re taking, after having saved Christmas five years in a row. Day 1’s puzzles had you fix an expense report that you had to deal with before you could go on vacation, and I posted my Python solution yesterday.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 2 challenge.

The Day 2 challenge, part one

Here’s the text from part one of the challenge:

Day 2: Password Philosophy

Your flight departs in a few days from the coastal airport; the easiest way down to the coast from here is via toboggan.

The shopkeeper at the North Pole Toboggan Rental Shop is having a bad day. “Something’s wrong with our computers; we can’t log in!” You ask if you can take a look.

Their password database seems to be a little corrupted: some of the passwords wouldn’t have been allowed by the Official Toboggan Corporate Policy that was in effect when they were chosen.

To try to debug the problem, they have created a list (your puzzle input) of passwords (according to the corrupted database) and the corporate policy when that password was set.

For example, suppose you have the following list:

1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc

Each line gives the password policy and then the password. The password policy indicates the lowest and highest number of times a given letter must appear for the password to be valid. For example, 1-3 a means that the password must contain a at least 1 time and at most 3 times.

In the above example, 2 passwords are valid. The middle password, cdefg, is not; it contains no instances of b, but needs at least 1. The first and third passwords are valid: they contain one a or nine c, both within the limits of their respective policies.

How many passwords are valid according to their policies?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through the usual process of bringing it into Python by pasting it into a triple-quoted string and assigning it to the variable raw_input.

I then split the string into an array, using the newline character as the delimiter. I named the array split_input.

Here’s the code, with the data abridged for brevity:

raw_input = """3-5 f: fgfff
6-20 n: qlzsnnnndwnlhwnxhvjn
6-7 j: jjjjjwrj
8-10 g: gggggggggg
5-6 t: ttttttft
6-11 h: khmchszhmzm
4-6 q: qqbjqqqj

...

3-6 h: hdhjhhhhchh
11-12 r: zrrkcrrrrrlh
7-9 v: vhqvlvwvzqwqvrxvjnf
1-5 r: rvmjr"""

split_input = raw_input.split("\n")

Formatting the data

One of the best things you can do while taking on an Advent of Code puzzle is to convert the data set you’re given into a format that will make it easier to solve the problem. The second part of the puzzle is usually based on the same data, and having it already in a helpful format will save you a lot of time.

With that in mind, my next step was to define a function that would convert each line in split_input into a dictionary. For example, when given the following line…

6-11 h: khmchszhmzm

…the function would produce the following dictionary:

{
"min": 6,
"max": 11,
"char": h,
"password": khmchszhmzm
}

Here’s the function:

def convert_to_password_and_policy_dict(line):
    password_and_policy_dict = {}
    password_and_policy_list = line.split()
    
    min_max = password_and_policy_list[0].split("-")
    password_and_policy_dict["min"] = int(min_max[0])
    password_and_policy_dict["max"] = int(min_max[1])
    
    password_and_policy_dict["char"] = password_and_policy_list[1][0]
    
    password_and_policy_dict["password"] = password_and_policy_list[2]
    
    return password_and_policy_dict

I used convert_to_password_and_policy_dict() in a list comprehension to convert split_input into a list of “password and policy” dictionaries named passwords_and_policies:

passwords_and_policies = [convert_to_password_and_policy_dict(password_and_policy) for password_and_policy in split_input]

Here’s a peek at passwords_and_policies’ contents:

>>> passwords_and_policies
[{'min': 3, 'max': 5, 'char': 'f', 'password': 'fgfff'},
 {'min': 6, 'max': 20, 'char': 'n', 'password': 'qlzsnnnndwnlhwnxhvjn'},
 {'min': 6, 'max': 7, 'char': 'j', 'password': 'jjjjjwrj'},
 {'min': 8, 'max': 10, 'char': 'g', 'password': 'gggggggggg'},
 {'min': 5, 'max': 6, 'char': 't', 'password': 'ttttttft'},

...

 {'min': 6, 'max': 12, 'char': 'g', 'password': 'dmgggpgggwczggghggm'},
 {'min': 3, 'max': 6, 'char': 'h', 'password': 'hdhjhhhhchh'},
 {'min': 11, 'max': 12, 'char': 'r', 'password': 'zrrkcrrrrrlh'},
 {'min': 7, 'max': 9, 'char': 'v', 'password': 'vhqvlvwvzqwqvrxvjnf'},
 {'min': 1, 'max': 5, 'char': 'r', 'password': 'rvmjr'}]

I then wrote a function that takes a “password and policy” dictionary and returns True if the dictionary’s password meets its policy:

def meets_password_policy(password_and_policy):
    char_count_in_password = password_and_policy["password"].count(password_and_policy["char"])
    return password_and_policy["min"] <= char_count_in_password <= password_and_policy["max"]

I used that function as the criteria for a filter() to create a list of only “password and policy” dictionaries whose passwords met their policies:

valid_passwords = list(filter(meets_password_policy, passwords_and_policies))

The solution to the first puzzle is the number of dictionaries in the resulting list, valid_passwords:

>>> len(valid_passwords)
564

I entered this result and completed the first challenge.

The Day 2 challenge, part two

Here’s the text from part two of the challenge:

While it appears you validated the passwords correctly, they don’t seem to be what the Official Toboggan Corporate Authentication System is expecting.

The shopkeeper suddenly realizes that he just accidentally explained the password policy rules from his old job at the sled rental place down the street! The Official Toboggan Corporate Policy actually works a little differently.

Each policy actually describes two positions in the password, where 1 means the first character, 2 means the second character, and so on. (Be careful; Toboggan Corporate Policies have no concept of “index zero”!) Exactly one of these positions must contain the given letter. Other occurrences of the letter are irrelevant for the purposes of policy enforcement.

Given the same example list from above:

• 1-3 a: abcde is valid: position 1 contains a and position 3 does not.
• 1-3 b: cdefg is invalid: neither position 1 nor position 3 contains b.
• 2-9 c: ccccccccc is invalid: both position 2 and position 9 contain c.

How many passwords are valid according to the new interpretation of the policies?

Since I already had the data in a nice, usable format, solving part two of the puzzle was easy. I simply wrote a new function that takes a “password and policy” dictionary and returns True if the dictionary’s password meets the policy described in part two:

def meets_new_password_policy(password_and_policy):
    first_position = password_and_policy["min"]
    char_in_first_position = password_and_policy["password"][first_position - 1] == password_and_policy["char"]
    
    second_position = password_and_policy["max"]
    char_in_second_position = password_and_policy["password"][second_position - 1] == password_and_policy["char"]

    return char_in_first_position ^ char_in_second_position

Note the return statement. While Python has the and and or keywords for logical and and or, it uses the ^ character for logical exclusive or.

I used that function as the criteria for a filter() to create a list of only “password and policy” dictionaries whose passwords met their policies, according to the new rules:

new_valid_passwords = list(filter(meets_new_password_policy, passwords_and_policies))

The solution to the second puzzle is the number of dictionaries in the resulting list, new_valid_passwords:

>>> len(new_valid_passwords)
325

Upon entering that result, the Day 2 challenge was complete!

Other days’ solutions:

Here are my solutions for other days in Advent of Code 2020:

• My solution to Advent of Code 2020’s Day 1 challenge, in Python
• My solution to Advent of Code 2020’s Day 3 challenge, in Python

 

December has arrived, and so has the great programming exercise known as the Advent of Code!

Think of it as an Advent calendar, but chocolates (or cheese, or wine), you’re presented with a new programming puzzle every day between the start of December and Christmas Day, in which you try to save Santa’s mission. You can use whatever programming language you want, and you don’t need to be an expert — as the site says, “just a little programming knowledge and some problem solving skills will get you pretty far.”

Advent of Code started in 2015, and has been taking place every year ever since. The 2020 edition began on Tuesday, December 1st at 12:00 midnight Eastern time (UTC-5).

Not only do I plan on participating in this year’s Advent of Code, but I might even use a couple of the challenges in the Python class I’m currently teaching on behalf of Computer Coach.

You have to sign in to play

In order to take on Advent of Code’s challenges, you have to sign in using an account from one of these popular “federated ID” services:

• Github
• Google
• Twitter
• Reddit

This is for a couple of reasons:

• Signing in makes it easier for the site to keep track of your progress. Advent of Code is structures so that you must successfully complete challenge n before taking on challenge (n+1).
• While everyone has to solve the same problem, each user gets their own (presumably) unique data set.

Once you’ve signed in, you can start on the first challenge…

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 1 challenge.

The Day 1 challenge, part one

Here’s the text from part one of the challenge:

Day 1: Report Repair

After saving Christmas five years in a row, you’ve decided to take a vacation at a nice resort on a tropical island. Surely, Christmas will go on without you.

The tropical island has its own currency and is entirely cash-only. The gold coins used there have a little picture of a starfish; the locals just call them stars. None of the currency exchanges seem to have heard of them, but somehow, you’ll need to find fifty of these coins by the time you arrive so you can pay the deposit on your room.

To save your vacation, you need to get all fifty stars by December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn’t quite adding up.

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.

For example, suppose your expense report contained the following:

1721
979
366
299
675
1456

In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579.

Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?

Here are the expense numbers that were provided for my account:

1140
1736
1711
1803
1825
1268
1651
2007
1923
1661
1788
1876
2003
1752
1988
1955
1568
1478
1699
1717
1828
1636
1387
1870
1658
1572
1703
1185
1569
1515
1142
1407
1587
1608
1827
1546
1808
1937
1815
1957
1401
1763
1970
1960
1853
1987
1865
1567
1664
1961
1771
1846
1971
1416
1897
633
1708
1606
515
1397
1873
1374
1969
1918
1170
1660
1494
1764
2002
1938
1396
1926
1714
1659
1805
1593
1899
1850
1644
1877
1561
1895
1985
1353
395
1919
1522
1745
1721
901
1765
1939
2009
1949
1852
1792
1749
1675
1883
1240
1868
1615
1693
1720
1388
1325
1337
867
1751
1408
1715
1942
1706
1894
1260
1945
1700
1148
1373
351
1790
1861
1755
1155
1622
1743
1872
1979
1262
1789
1305
1311
1729
1929
823
1623
2005
1932
1814
1909
1728
1592
1712
1363
1338
1804
1402
1198
264
1117
1791
1419
1229
1924
1838
1785
1982
1683
1950
1199
1984
1830
1921
1980
1834
1341
1282
1989
1854
1395
1847
1900
1913
1777
1779
1333
1800
1966
1543
1882
1375
1811
1673
1679
889
1670
1879
1312
1741
1772
1663
1776
1642
1674
1472
1580
1264
1738
1999
1637

I decided to use a Jupyter notebook running a Python kernel solve the problem.

Importing the data

My first step was to copy the numbers above, paste them into a triple-quoted string, and assign that string to the variable raw_input:

raw_input = """1140
1736
1711
1803
1825
1268
1651
2007
1923
1661
1788
1876
2003
1752
1988
1955
1568
1478
1699
1717
1828
1636
1387
1870
1658
1572
1703
1185
1569
1515
1142
1407
1587
1608
1827
1546
1808
1937
1815
1957
1401
1763
1970
1960
1853
1987
1865
1567
1664
1961
1771
1846
1971
1416
1897
633
1708
1606
515
1397
1873
1374
1969
1918
1170
1660
1494
1764
2002
1938
1396
1926
1714
1659
1805
1593
1899
1850
1644
1877
1561
1895
1985
1353
395
1919
1522
1745
1721
901
1765
1939
2009
1949
1852
1792
1749
1675
1883
1240
1868
1615
1693
1720
1388
1325
1337
867
1751
1408
1715
1942
1706
1894
1260
1945
1700
1148
1373
351
1790
1861
1755
1155
1622
1743
1872
1979
1262
1789
1305
1311
1729
1929
823
1623
2005
1932
1814
1909
1728
1592
1712
1363
1338
1804
1402
1198
264
1117
1791
1419
1229
1924
1838
1785
1982
1683
1950
1199
1984
1830
1921
1980
1834
1341
1282
1989
1854
1395
1847
1900
1913
1777
1779
1333
1800
1966
1543
1882
1375
1811
1673
1679
889
1670
1879
1312
1741
1772
1663
1776
1642
1674
1472
1580
1264
1738
1999
1637"""

Now that I had the data in a string, I could split the string into an array, using the newline character as the delimiter. I named the array split_input:

>>> split_input = raw_input.split("\n")
>>> split_input
['1140', '1736', '1711', '1803', '1825', '1268', '1651', '2007', '1923', '1661', '1788', '1876', '2003', '1752', '1988', '1955', '1568', '1478', '1699', '1717', '1828', '1636', '1387', '1870', '1658', '1572', '1703', '1185', '1569', '1515', '1142', '1407', '1587', '1608', '1827', '1546', '1808', '1937', '1815', '1957', '1401', '1763', '1970', '1960', '1853', '1987', '1865', '1567', '1664', '1961', '1771', '1846', '1971', '1416', '1897', '633', '1708', '1606', '515', '1397', '1873', '1374', '1969', '1918', '1170', '1660', '1494', '1764', '2002', '1938', '1396', '1926', '1714', '1659', '1805', '1593', '1899', '1850', '1644', '1877', '1561', '1895', '1985', '1353', '395', '1919', '1522', '1745', '1721', '901', '1765', '1939', '2009', '1949', '1852', '1792', '1749', '1675', '1883', '1240', '1868', '1615', '1693', '1720', '1388', '1325', '1337', '867', '1751', '1408', '1715', '1942', '1706', '1894', '1260', '1945', '1700', '1148', '1373', '351', '1790', '1861', '1755', '1155', '1622', '1743', '1872', '1979', '1262', '1789', '1305', '1311', '1729', '1929', '823', '1623', '2005', '1932', '1814', '1909', '1728', '1592', '1712', '1363', '1338', '1804', '1402', '1198', '264', '1117', '1791', '1419', '1229', '1924', '1838', '1785', '1982', '1683', '1950', '1199', '1984', '1830', '1921', '1980', '1834', '1341', '1282', '1989', '1854', '1395', '1847', '1900', '1913', '1777', '1779', '1333', '1800', '1966', '1543', '1882', '1375', '1811', '1673', '1679', '889', '1670', '1879', '1312', '1741', '1772', '1663', '1776', '1642', '1674', '1472', '1580', '1264', '1738', '1999', '1637']

split_input is an array of strings which needed to be converted into integer values.

In many other languages, I’d do this by using the map function to apply a “convert a string to its integer value” function to every item in the array, creating a resulting array called expenses. Here’s the Python version of that approach:

>>> expenses = list(map(int, split_input))
>>> expenses
[1140, 1736, 1711, 1803, 1825, 1268, 1651, 2007, 1923, 1661, 1788, 1876, 2003, 1752, 1988, 1955, 1568, 1478, 1699, 1717, 1828, 1636, 1387, 1870, 1658, 1572, 1703, 1185, 1569, 1515, 1142, 1407, 1587, 1608, 1827, 1546, 1808, 1937, 1815, 1957, 1401, 1763, 1970, 1960, 1853, 1987, 1865, 1567, 1664, 1961, 1771, 1846, 1971, 1416, 1897, 633, 1708, 1606, 515, 1397, 1873, 1374, 1969, 1918, 1170, 1660, 1494, 1764, 2002, 1938, 1396, 1926, 1714, 1659, 1805, 1593, 1899, 1850, 1644, 1877, 1561, 1895, 1985, 1353, 395, 1919, 1522, 1745, 1721, 901, 1765, 1939, 2009, 1949, 1852, 1792, 1749, 1675, 1883, 1240, 1868, 1615, 1693, 1720, 1388, 1325, 1337, 867, 1751, 1408, 1715, 1942, 1706, 1894, 1260, 1945, 1700, 1148, 1373, 351, 1790, 1861, 1755, 1155, 1622, 1743, 1872, 1979, 1262, 1789, 1305, 1311, 1729, 1929, 823, 1623, 2005, 1932, 1814, 1909, 1728, 1592, 1712, 1363, 1338, 1804, 1402, 1198, 264, 1117, 1791, 1419, 1229, 1924, 1838, 1785, 1982, 1683, 1950, 1199, 1984, 1830, 1921, 1980, 1834, 1341, 1282, 1989, 1854, 1395, 1847, 1900, 1913, 1777, 1779, 1333, 1800, 1966, 1543, 1882, 1375, 1811, 1673, 1679, 889, 1670, 1879, 1312, 1741, 1772, 1663, 1776, 1642, 1674, 1472, 1580, 1264, 1738, 1999, 1637]

It works, but from a Python programming point of view, it just doesn’t feel right.

The Pythonic approach would involve using a list comprehension instead of map (and then using the resulting iterator into a list). It just seems more readable:

>>> expenses = [int(string) for string in split_input]
>>> expenses
[1140, 1736, 1711, 1803, 1825, 1268, 1651, 2007, 1923, 1661, 1788, 1876, 2003, 1752, 1988, 1955, 1568, 1478, 1699, 1717, 1828, 1636, 1387, 1870, 1658, 1572, 1703, 1185, 1569, 1515, 1142, 1407, 1587, 1608, 1827, 1546, 1808, 1937, 1815, 1957, 1401, 1763, 1970, 1960, 1853, 1987, 1865, 1567, 1664, 1961, 1771, 1846, 1971, 1416, 1897, 633, 1708, 1606, 515, 1397, 1873, 1374, 1969, 1918, 1170, 1660, 1494, 1764, 2002, 1938, 1396, 1926, 1714, 1659, 1805, 1593, 1899, 1850, 1644, 1877, 1561, 1895, 1985, 1353, 395, 1919, 1522, 1745, 1721, 901, 1765, 1939, 2009, 1949, 1852, 1792, 1749, 1675, 1883, 1240, 1868, 1615, 1693, 1720, 1388, 1325, 1337, 867, 1751, 1408, 1715, 1942, 1706, 1894, 1260, 1945, 1700, 1148, 1373, 351, 1790, 1861, 1755, 1155, 1622, 1743, 1872, 1979, 1262, 1789, 1305, 1311, 1729, 1929, 823, 1623, 2005, 1932, 1814, 1909, 1728, 1592, 1712, 1363, 1338, 1804, 1402, 1198, 264, 1117, 1791, 1419, 1229, 1924, 1838, 1785, 1982, 1683, 1950, 1199, 1984, 1830, 1921, 1980, 1834, 1341, 1282, 1989, 1854, 1395, 1847, 1900, 1913, 1777, 1779, 1333, 1800, 1966, 1543, 1882, 1375, 1811, 1673, 1679, 889, 1670, 1879, 1312, 1741, 1772, 1663, 1776, 1642, 1674, 1472, 1580, 1264, 1738, 1999, 1637]

Now that I had the expenses in a Python list (that’s Pythonese for “array”), I could work with them.

Combinations to the rescue!

Once again, the goal of the challenge was to find the two numbers in the expense report whose sum was 2020.

To solve this problem, we need a way to generate all the possible combinations of two numbers taken from the list. I could write this code, but Python’s itertools module has a combinations() method that can do just that.

Here’s a quick demo of combinations() in action. Given a list containing a small number of integers, it generates a list of the possible 2-number combinations you can get from the list, without repetition (that is, a number can’t appear more than once in any combination):

>>> from itertools import *
>>> simple_list = [1, 3, 5, 7, 9]
>>> list(combinations(simple_list, 2))
[(1, 3), (1, 5), (1, 7), (1, 9), (3, 5), (3, 7), (3, 9), (5, 7), (5, 9), (7, 9)]

itertools also has a combinations_with_replacement() method. Rather than tell you what it does, let me show you:

>>> list(combinations_with_replacement(simple_list, 2))
[(1, 1), (1, 3), (1, 5), (1, 7), (1, 9), (3, 3), (3, 5), (3, 7), (3, 9), (5, 5), (5, 7), (5, 9), (7, 7), (7, 9), (9, 9)]

With that in mind, I used combinations() to generate a list of all the possible two-number combinations in expenses, which I assigned to a variable named all_expense_pairs:

>>> all_expense_pairs = list(combinations(expenses, 2))
>>> len(all_expense_pairs)
19900

Now that we have all the possible two-number combinations from the expense report, we can try to find the one(s) whose numbers add up to 2020.

Any time you’re in a situation where you need to find values in an array that match some criteria, you should think about applying a filter() function. I did just that: I used a filter() to extract a list of only those pairs summed to 2020…

def sums_to_2020(values):
    return sum(values) == 2020

>>> result = list(filter(sums_to_2020, all_expense_pairs))
>>> result
[(1387, 633)]

The resulting list had one tuple, (1387, 633), whose values sum to 2020. I entered the product of these two numbers — 877971 — and completed the first challenge.

The Day 1 challenge, part two

Here’s the text from part two:

The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.

Using the above example again, the three entries that sum to 2020 are 979, 366, and 675. Multiplying them together produces the answer, 241861950.

In your expense report, what is the product of the three entries that sum to 2020?

Had I solved the problem from first principles, the solution might have taken a lot of extra work. Thanks to the use of itertools.combinations(), the solution for part two took three lines of code:

>>> all_expense_triplets = list(combinations(expenses, 3))
>>> result2 = list(filter(sums_to_2020, all_expense_triplets))
>>> result2
[(867, 264, 889)]

Once again, the resulting list had one tuple, (867, 264, 889), and its values, added up, were 2020. I entered the product of these three numbers — 203481432 — and completed the second challenge.

Feeling simultaneously proud and soiled

Thanks to Python (and remembering that it had a library that could do combinations and permutations),  I made a personal best in solving the Day 1 puzzles. I’m pretty pleased, but at the same time, I did so little work that it feels as if I’ve cheated. I may have to try solving the problem from first principles — if I have the time.

Other days’ solutions:

Here are my solutions for other days in Advent of Code 2020:

• My solution to Advent of Code 2020’s Day 2 challenge, in Python
• My solution to Advent of Code 2020’s Day 3 challenge, in Python