Tips and Tricks for Solving Advent of Code's Puzzles

What is Advent of Code?

Advent of Code is an annual event featuring Christmas-themed puzzles that are meant to be solved with code. Since 2015, tens of thousands of programmers have tackled the new puzzles that appear every day from December 1 through 25 at the stroke of midnight (U.S. Eastern standard time). For the past five years, the site’s puzzles have been centered around imaginative storylines where you have to save Christmas through coding. This year, you’ve earned a break after five years of holiday heroics.

This year’s Advent of Code story and puzzles are all about saving your well-deserved vacation. While the story is meant to draw you in, the coding challenges aren’t meant to scare you away. Advent of Code creator Eric Wastl says that he takes great care to make the challenges not require advanced knowledge of algorithms (“You don’t need to know what a red-black tree is,” he’s fond of saying).

The puzzles are designed to maintain a balance between friendliness to entry-level developers and presenting a challenge. If you have a decent understanding of branching, loops, arrays, and hash tables in at least one programming language, you should be able to solve most of its puzzles. You may have to do the occasional web search for an algorithm, but in doing so, you’ll broaden your programming repertoire.

Each puzzle comes with input data that is custom-generated for each participant. To solve the puzzle, the participant must write code that uses the input to produce a matching answer. While all the participants have to come up with the same general solution, everyone’s answer is different.

Completing the day’s first puzzle reveals the second one. That puzzle uses the same data, but often features some kind of twist or change to the first puzzle’s requirements. This is intentional; it’s meant to mirror real-life software development, where such changes are painfully all too common.

At the time of writing, it’s Day 17 of Advent of Code. Participants around the world have submitted a million correct answers to the puzzles over the past 16 days. Coders have established online communities around sharing puzzle solutions and hints, with some even live streaming their screens as they attempt to solve the latest puzzle. Advent of Code puzzles have been used in all sorts of ways: As job interview questions, programming course assignments, as a way to brush up on a familiar programming language, or to learn a new one.

With so many people making plans to stay home this holiday season, you might find yourself looking for something to do. If you like playing games and solving puzzles and want to test your coding skills (or even learn how to code), you should try the 2020 edition of Advent of Code. I’ve assembled this list of tips and tricks to help you succeed and find solutions to its challenges. You may find that they apply to other coding contests, too!

Before Starting

Here are some things to keep in mind before taking on Advent of Code’s challenges.

Read the problem. Then read it again.

This may seem like obvious advice to you, but it will serve you well. Between the impreciseness of English and the fact the puzzles are in story form, it’s quite easy to misunderstand the requirements and waste a lot of time chasing after the wrong solution.

Eric takes great care and does a fair bit of user testing to ensure that the text of the puzzles is as clear and unambiguous as possible, but it’s up to you to make sure that you understand the problem. Read it carefully.

Know how the puzzle creator thinks

You should always keep in mind that Advent of Code puzzles were meant to be solved. The many considerations that go into making an Advent of Code puzzle include:

• For a given input (remember, every participant has their own unique input), there is one and only one correct answer.
• Avoiding expectations of domain-specific knowledge, including computer science. The puzzles aren’t made with the assumption that you’ve taken a data structures course or even any computer science course. You are expected to know how to do a little coding.
• Trying not to make the reader make any assumptions. In fact, the text of the puzzle often repeats and highlights important details. Eric has observed that “for every sentence, there’s a user that skipped only that sentence.”
• Every day has two puzzles, with the end of the first puzzle acting as a kind of checkpoint. The second puzzle is always a twist on the first, and it’s meant to simulate the real-world experience of changing requirements.
• Generally, the later in the month, the more challenging the puzzle. They throw in the occasional “off-difficulty” puzzle to control pacing and to keep participants from burning out.
• Some earlier puzzles may be simpler versions of more difficult puzzles that appear later. This is Advent of Code’s way of preparing you.
• The puzzles vary in type from day to day to keep things interesting, and weekend puzzles are more involved than weekday puzzles.
• Using a compiled language to solve the puzzles won’t give you any noticeable speed advantage over using an interpreted language. If your code is still working on a solution after about a minute, you’re probably taking the wrong approach. To quote the “About” page, “every problem has a solution that completes in at most 15 seconds on ten-year-old hardware”.

Ignore the leaderboard

Even though Advent of Code has a leaderboard that lists the participants who solved the puzzles in the fastest time, even Eric Wastl recommends that you don’t pay any attention to it. The people on the leaderboard participate in programming competitions all the time, and have the experience and an arsenal of code that helps them produce solutions in minutes, and sometimes, even seconds. They’re not worth worrying about.

It’s better by far to make sure that you’re getting a good mental workout from puzzles than to worry about a high score.

Use programming languages and tools that can give you immediate feedback

If possible, use a programming language with an “interactive mode”, REPL (read-eval-print-loop), or “code playground” that gives you immediate feedback when you enter code. This makes it easier to experiment and ask “what if?” questions, which in turn often makes it easier to find a solution. It’s especially useful when trying out language features or libraries that you don’t use often.

I write my Advent of Code solutions in Python using a Jupyter Notebook. It’s a web app that runs on your local machine, and its documents consist of “cells” (like the cells in a spreadsheet) that can contain either text in Markdown form, or code. Jupyter Notebook typically supports Python by default, but it supports over 40 languages, including JavaScript, PHP, C#, F#, R, Ruby, Scala, Lua, and more. The Jupyter Notebook page-and-cell structure makes it possible to break your code into distinct pieces while sharing the same variables. I’ve found this useful for experimenting with different approaches to a problem; it allows me to fall back to an earlier solution if an idea doesn’t work out.

Consider pair programming

I’ve done this in person in previous years and via Zoom this year. Not only does it expose you to different ways of thinking and different problem-solving styles, but it’s also fun!

Try out your solutions on the example data first

Every puzzle features example data and the solution for that data. The example data is much smaller than the input data you have to use to submit your answer, and therefore easier to work with.

Don’t submit an answer without first testing your code with the sample data. There’s a mandatory waiting period after submitting a wrong answer, and it gets longer as you submit more wrong answers.

What You’ll Need to Know

Know the basics: Branching, looping, strings, and data structures

If you’re using Advent of Code in order to learn a programming language or to learn how to code, you should be able to solve most of its puzzles with these basics: branching, looping, strings, and a couple of data structures that most modern programming languages have.

I mention branching and looping primarily for those of you who are new to programming. Most programs that do even just a little more than Hello, World! make use of decision-making and repetition, and you should know how to perform those tasks in your programming language.

Every Advent of Code puzzle comes with input data, and you will need to either copy and paste it directly into your code or save it to a file that your code will read. Either way, you’ll need to do some string processing, and you should be familiar with your programming language’s string processing functions.

Computer science is rife will all sorts of data structures, but you don’t need to know all of them to succeed in Advent of Code. The two that you need to know to tackle most, if not all, of the puzzles are:

• Arrays (some programming languages, such as Python, call them lists)
• Hash tables (these go by many other names — for example, they’re called hashes in Ruby, objects in JavaScript, dictionaries in Python and Swift, and Maps in Kotlin.)

If you’re familiar with these, you should be able to solve most of the puzzles without any help.

You might want to read up on a couple of algorithms

Historically, there’s always been a puzzle or two that makes use of breadth-first and depth-first searches. You can probably derive how to do these from first principles, but they’re a key part of programming, so why not make sure you’ve learned them?

map(), filter(), and reduce() — or their equivalents — are your friends

The individualized input data that Advent of Code gives you will often consist of hundreds of items of data that will likely end up in an array or similar data structure. You can save a lot of time and lines of code by taking advantage of your programming language’s equivalent of the map(), filter(), and reduce() to process that data:

Do you need to perform some operation on every item in a collection of data to create a new collection? Use map():

# Python

numbers = [1, 2, 3, 4, 5]
squares_of_numbers = list(map(lambda number: number**2, numbers))
print(squares_of_numbers) # [1, 4, 9, 16, 25]

Do you need to choose only those items in a collection of data that meet certain criteria to create a new collection? Use filter():

# Python

numbers = [1, 2, 3, 4, 5]
even_numbers = list(filter(lambda number: number % 2 == 0, numbers))
print(even_numbers) # [2, 4]

Do you need to use all the items in a collection of data to perform a calculation that provides a single-value result? You might find reduce() useful. In Python, you’ll need to import it from the functools module first:

# Python

from functools import reduce
numbers = [1, 2, 3, 4, 5]
sum = reduce(lambda accumulator, current_value: accumulator + current_value, numbers)
print(sum) # 15

You can use map() and filter() in Python, but it’s more Pythonic to use list comprehensions to get the same effect.

Here’s how you get the map() effect using a list comprehension:

# Python

numbers = [1, 2, 3, 4, 5]
squares_of_numbers = [number**2 for number in numbers]
print(squares_of_numbers)  # [1, 4, 9, 16, 25]

Here’s how you get the filter() effect:

# Python

numbers = [1, 2, 3, 4, 5]
even_numbers = [number for number in numbers if number % 2 == 0]
print(even_numbers) # [2, 4]

And here’s how you combine both map() and filter() in a list comprehension:

# Python

numbers = [1, 2, 3, 4, 5]
squares_of_even_numbers = [number**2 for number in numbers if number % 2 == 0]
print(squares_of_even_numbers) # [4, 16]

Examples to Explore

Here are some example solutions from the Advent of Code 2020’s earlier days. They highlight techniques that you’ll find useful for solving its puzzles.

Spoiler alert! These examples, while they don’t present complete solutions, give away the key to solving the puzzles for days 1, 3, 5, 6 and 7. I’ve marked each example so that you can avoid “spoiling” any puzzles that you might be working on.

Look for useful libraries (Day 1)

Day 1, Report Repair, presents you with a list of 200 numbers, ranging from the low hundreds to the low thousands. The goal of the first puzzle is to find the two numbers in that list that add up to the magic number 2020.

I decided to solve that puzzle by repeatedly popping the last item from the list and iterating through the remaining part, testing to see if there was a number that could be added to the popped number to form 2020:

# Python

# `expenses` is the list of numbers.

still_searching = True
results = []

while still_searching:
    last_expense_in_list = expenses.pop()
    
    if len(expenses) < 1:
        break
    
    for expense in expenses:
        if expense + last_expense_in_list == 2020:
            results += [expense, last_expense_in_list]
            still_searching = False
            break
            
if still_searching:
    print("Can't find the two numbers whose sum is 2020!")
else:
    print(f"The two numbers whose sum is 2020 are {results[0]} and {results[1]}.")

For the second puzzle, the goal was to find the three numbers in the list whose sum is 2020.

These two thoughts came to my mind, in the order presented:

1. This definitely calls for a nested loop.
2. Wow, do I not want to do that.

My solution to the first puzzle effectively tries to add every combination of two numbers from the list. To solve the second puzzle, I would need to use a three-number combination.

That’s when I decided to use Python’s itertools, a “utility belt” of useful functions for processing lists of data. It’s a library that I need to spend more time researching, but I do know about its combinations() function. Given a list of items and a number n, it returns all the possible n-length combinations of items from that list.

Thanks to combinations(), my second puzzle solution was shorter than my first:

# Python

from itertools import combinations

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

all_expense_triplets = list(combinations(expenses, 3))
result_triplet = list(filter(sums_to_2020, all_expense_triplets))[0]
print(f"The three numbers whose sum is 2020 are {result_triplet[0]}, {result_triplet[1]} and {result_triplet[2]}.")

Make sure that you research your programming language for libraries that provide additional functions for array/list processing. You’ll save a lot of time, and you may end up using them in less trivial programming tasks!

Master modulo math (Day 3)

The Day 3 challenge, Toboggan Trajectory, features a character-based map that looks like this:

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

(...there’s another 318 lines)

The . characters represent open space, and the # characters represent trees. The puzzle involves counting the number of trees you encounter while traveling through the map on various downward/rightward slopes.

The map is 323 lines high and 31 characters wide, but it repeats forever horizontally. This means that the 32nd is the same as the 1st, the 33rd character is the same as the 2nd, the 34th character is the same as the 3rd, and so on.

Any time you see this kind of repetition, you should think of the modulo operator. In most programming languages, it’s represented by the % character, and the result of x % y is the remainder of the integer division operation x / y.

The modulo operator may not seem very useful until you realize that remainders and repeating cycles are related. Consider the days of the week:

• 0: Sunday
• 1: Monday
• 2: Tuesday
• 3: Wednesday
• 4: Thursday
• 5: Friday
• 6: Saturday

What day will it be 5 days after Wednesday, which is day 3? It will be day (3 + 5), or day 8. There isn’t a day 8 in the week, but the days of the week repeat every 7 days, so day 8 is actually day (8 % 7), or day 1: Monday.

Modulo math makes it possible to write a function to determine if there is a tree at an (x, y) coordinate for any value of x and any legal (between 0 and 323 inclusive) value of y:

# Python

# Hill map is a list of strings, each one representing
# one row (the y-coordinate) of the map.

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

This function made it easy for me to write a function that solved both of the day’s puzzles:

# Python

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

Sharpen your regular expression skills (Day 7)

You’ve probably heard the joke about regular expressions:

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

There is a grain of truth to it, and I’m sure I’m not alone in saying that I spent the first couple of years in my programming career avoiding regular expressions and simply relying on “regular” string functions. I’ve since become more comfortable with regex work, and I’ve even surprised myself a couple of times.

Regular expressions are often useful in Advent of Code problems, especially when the input data you’re given needs to be “massaged” into something that you can actually use with an algorithm.

Consider the case of the Day 7 puzzle for 2020, Handy Haversacks. In this puzzle, the airline has unusual rules for baggage. Bags must be color-coded and must contain specific quantities of other color-coded bags. The rules are encoded in your input data, and I’ve included a sample below:

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.

(...this goes on for a few hundred lines)

You can parse this data with regular string methods, but you might find that some well-placed regular expressions can do the job more concisely. With the examples above, I needed to split each line into two parts: one for the color of each containing bag, and one for the phrase listing its contained bags. Here’s how I did it:

# Python

bag_and_contents_regex = r"^(\w+ \w+) bags contain (.*)"
bag_and_contents = re.search(bag_and_contents_regex, item)

After executing that code, bag_and_contents[1] now contains the color of the containing bag, and bag_and_contents[2] contains the phrase listing the contained bags. I could’ve written it in one line, but given the choice between clarity and conciseness, I’ll take clarity every time.

The next task is to parse the phrase listing the contained bags. Here’s an example of such a phrase:

1 bright white bag, 2 muted yellow bags.

Here’s the code I used to parse it:

# Python

contents_regex = r"([0-9] )*(\w+ \w+) bags*"
contents_tuples = re.findall(contents_regex, bag_and_contents[2] )

The result is that contents_tuples now contains something that I can more easily turn into a data structure:

[('1 ', 'bright white'), ('2 ', 'muted yellow')]

And speaking of data structures...

Spend some time thinking about the data structures that you want to use (Day 7)

Many programmers have heard of Brooks’ Law: Adding people to a late software project make it later. There’s a lesser-known quote of his from his 1975 book, The Mythical Man-Month:

Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.

To a modern programmer, it makes more sense if you replace flowcharts with code and tables with data structures. Using the right data structure often makes it easier to solve a puzzle. In fact, the right data structure sometimes makes the solution easier to find.

I spent most of my time on the Day 7 puzzles working on building a data structure to represent this input data, which is a list of bags and the bags they must contain. Once again, here’s a sample:

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.

I needed a data structure that would accurately model what was specified in the input data and would also be easy to process. I decided to use a Python dictionary where:

• the keys were the name of the containing bags
• the corresponding values contained a list of the contained bags, where each contained bag type was represented by a dictionary with two keys/value pairs that specified:
  • The name of bag type
  • The number of that type of bag

Here’s the resulting data structure, which uses the input data above:

{
  "light red": [
    {
      "count": 1,
      "type": "bright white"
    },
    {
      "count": 2,
      "type": "muted yellow"
    },  
  ],
  "dark orange": [
    {
      "count": 3,
      "type": "bright white"
    },
    {
      "count": 4,
      "type": "muted yellow"
    }
  ],
  "bright white": [
    {
      "count": 1,
      "type": "shiny gold"
    }
  ],
  "muted yellow": [
    {
      "count": 2,
      "type": "shiny gold"
    },
        {
      "count": 9,
      "type": "faded blue"
    }
  ]

# ... and so on...

}

This data structure made it simple for me to solve both of Day 7’s puzzles.

Here’s my solution to the first puzzle, which asks: How many bag colors can eventually contain at least one shiny gold bag?

# Python

# The data structure is contained in the variable bags_and_contents.

def shiny_gold_bag_count(bag_name):
    count = 0
    bag = bags_and_contents[bag_name]
    
    if len(bag) == 0:
        return 0
    else:
        for sub_bag in bag:
            if sub_bag["type"] == "shiny gold":
                count += 1
            count += shiny_gold_bag_count(sub_bag["type"])
        
    return count


total = 0
for bag_name in bags_and_contents.keys():
    if shiny_gold_bag_count(bag_name) > 0:
        print(f"{bag_name} eventually contains a shiny gold bag!")
        total += 1
        
print(f"{total} bags eventually contain a shiny gold bag.")

Notice that the function shiny_gold_bag_count() calls itself. That brings me to the next topic...

Get comfortable with recursion (Day 7)

There will be at least two or three Advent of Code puzzles for which recursion will come in handy. The problem above, Handy Haversacks, is an obvious candidate since it involves counting bags inside bags, which in turn may contain more bags.

Any time you see a problem with this sort of “snake eating its own tail” quality, you should consider using a recursive solution.

If recursion makes you uncomfortable, keep in mind that a recursive function has two key parts:

1. The base case, where the function can immediately return a value
2. The recursive case, where the function needs to call itself using a simpler version of the current data

Here’s a simple, not-so-scary example of a recursive function, isEven(), which returns True if passed an even number and False otherwise:

Python

def isEven(number):
    
    # Ensure that the function works with negative numbers.
    value = abs(number) 
    
    if value == 0 or value == 1:
    # Base case: 0 is even, 1 is odd.
    return value == 0
  else:
    # Recursive case: A number n is even if (n - 2) is even.
    return isEven(value - 2)

Here’s my solution to the second Handy Haversacks puzzle, which asks: How many individual bags are required inside your single shiny gold bag?

The code’s a little more complex than the recursion example above, but the general principles are the same:

# Python

def bag_count(bag_collection, bag_name):
    count = 0
    top_level_bag = bag_collection[bag_name]
    print(f"Currently counting bags inside {bag_name}.")
    
    if len(top_level_bag) == 0:
        # Base case: There are no bags inside the current bag.
        # Stop counting.
        return 0
    else:
             # Recursive case: There are bags inside the current bag.
             # Count them, and their contents.
        for current_bag in top_level_bag:
            print(f"There are {current_bag['count']} of {current_bag['type']} inside {bag_name}.")
            # Add the number of bags of the current type
            # to the count.
            current_bag_type_count = current_bag['count']
            count += current_bag_type_count
            # Count the bags inside each bag of the current type,
            # multiply it by the number of the current type,
            # then add it to the count.
            bags_inside_current_bag_type_count = bag_count(bag_collection, current_bag["type"])
            count += bags_inside_current_bag_type_count * current_bag_type_count
        
    return count
    
    
print(f"One gold bag contains {bag_count(bags_and_contents, 'shiny gold')} other bags.")

Don’t over-process your input data (Day 6)

It can be tempting to over-process your input data, especially when working on the first puzzle. For example, consider the Day 6 puzzle, Custom Customs, where passengers on your plane are answering “yes/no” questions on their custom forms. Your input data is in this format:

abc
cde
fgh
 
v
v
v
v
v

This data represents two groups of passengers:

1. The first group is made up of 3 people:
   • Person 1 answered “yes” to questions a, b, and c
   • Person 2 answered “yes” to questions c, d, and e
   • Person 3 answered “yes” to questions f, g, and h
2. The second group is made up of 5 people, all of whom answered “yes” to question v.

In the first puzzle, you’re told that a group is considered to have answered “yes” to a question if any member of the group answered “yes” to it. This means that:

1. Group 1 answered “yes” to questions a, b, c, d, e, f, g, and h.
2. Group 2 answered “yes” to question v.

In my initial conversion of the data, I eliminated duplicate answers from each group. For the data shown above, my resulting data structure would look like this:

[
  "abcdefgh",
  "v"
]

This worked for the first puzzle, where the goal was to get the sum of all the questions to which anyone answered "yes". It failed for the next puzzle, where the goal was to count only the questions to which *everyone in each group answered “yes”*.

Under the new requirements:

1. Group 1 did not answer any questions, as there is no question for which all three of them answered “yes”.
2. Group 2 answered “yes” to one question: v.

By eliminating duplicate answers for each group in my data structure, I discarded information that I didn’t need for the first puzzle but absolutely needed for the second.

This is the sort of trap that Advent of Code likes to set. Just as with real-world projects, requirements can change, and over-optimizing for a specific set of requirements can cost you time and effort.

In the end, I refactored my data structure to look like this:

[
  ['abc', 'cde', 'fgh'],
  ['v', 'v', 'v', 'v', 'v']
]

Watch for data that are actually another kind of data in disguise (Day 5)

The Day 5 puzzle, Binary Boarding, requires you to work with airplane seats whose designations look like this:

FBFBBFFRLR

The first seven letters represent the seat rows, of which there are 128, ranging from 0 to 127. This is what they represent:

• Each letter can either be F for “front” or B for “back”.
• If the first letter is F, the seat is in the front half of the plane. If the first letter is B, the seat is in the back half of the plane.
• If the second letter is F, the seat is in the front half of the plane section specified by the first letter. If the second letter is B, the seat is in the back half of the plane section specified by the first letter.
• The pattern continues for the remaining letters. Each letter position further divides the plane into smaller sections until you reach the last character, narrowing the possibilities down to a single row.

The final three letters represent the seat columns, of which there are 8, ranging from 0 to 7, and following a pattern similar to that of the seat rows:

• Each letter can either be L for “left” and R for “right”.
• If the first letter is L, the seat is in the left half of the plane. If the first letter is R, the seat is in the right half of the plane.
• You’re probably seeing a pattern at this point.

It should become clear that you’re simply working with binary numbers in disguise. If the puzzle’s name, Binary Boarding, didn’t give it away, the use of only two letters to represent seat rows and columns, as well as their ranges, should have given it away.

Once I realized this, I wrote a couple of quick functions to convert the seat row and column designations into binary strings. They used the Python string class’ maketrans() method, which builds a character-for-character transliteration table, and the corresponding translate() method, which applies the translation table to a given string:

# Python

# Convert any "F" in a string to "0", and any "B" to "1".
def convert_FB_to_01(row):
    translation_table = row.maketrans("FB", "01")
    return row.translate(translation_table)

# Convert any "L" in a string to "0", and any "R" to "1".
def convert_LR_to_01(column):
    translation_table = column.maketrans("LR", "01")
    return column.translate(translation_table)

I used these functions to convert the row and seat designations from “FB” and “LR” strings into strings of binary numbers. From there, I used Python’s int() function to convert those binary strings into integers, taking advantage of its optional argument to specify the base of the number in string form:

# Python

# Convert the binary string “11010101” into a decimal integer
number = int(“11010101”, 2)

Have Fun!

The important thing to remember is to have fun. Advent of Code doesn’t offer any prizes, and its primary purpose is to help people become better programmers.

If you’re stuck on a problem, remember the power of taking a break and going for a walk. It’s an underrated yet effective approach to problem solving.

# Format error response and append status code

def get_token_auth_header():
    """Obtains the access token from the Authorization Header
    """
    auth = request.headers.get("Authorization", None)
    if not auth:
        raise AuthError({"code": "authorization_header_missing",
                        "description":
                            "Authorization header is expected"}, 401)

    parts = auth.split()

    if parts[0].lower() != "bearer":
        raise AuthError({"code": "invalid_header",
                        "description":
                            "Authorization header must start with"
                            " Bearer"}, 401)
    elif len(parts) == 1:
        raise AuthError({"code": "invalid_header",
                        "description": "Token not found"}, 401)
    elif len(parts) > 2:
        raise AuthError({"code": "invalid_header",
                        "description":
                            "Authorization header must be"
                            " Bearer token"}, 401)

    token = parts[1]
    return token

def requires_auth(f):
    """Determines if the access token is valid
    """
    @wraps(f)
    def decorated(*args, **kwargs):
        token = get_token_auth_header()
        jsonurl = urlopen("https://"+AUTH0_DOMAIN+"/.well-known/jwks.json")
        jwks = json.loads(jsonurl.read())
        unverified_header = jwt.get_unverified_header(token)
        rsa_key = {}
        for key in jwks["keys"]:
            if key["kid"] == unverified_header["kid"]:
                rsa_key = {
                    "kty": key["kty"],
                    "kid": key["kid"],
                    "use": key["use"],
                    "n": key["n"],
                    "e": key["e"]
                }
        if rsa_key:
            try:
                payload = jwt.decode(
                    token,
                    rsa_key,
                    algorithms=ALGORITHMS,
                    audience=API_AUDIENCE,
                    issuer="https://"+AUTH0_DOMAIN+"/"
                )
            except jwt.ExpiredSignatureError:
                raise AuthError({"code": "token_expired",
                                "description": "token is expired"}, 401)
            except jwt.JWTClaimsError:
                raise AuthError({"code": "invalid_claims",
                                "description":
                                    "incorrect claims,"
                                    "please check the audience and issuer"}, 401)
            except Exception:
                raise AuthError({"code": "invalid_header",
                                "description":
                                    "Unable to parse authentication"
                                    " token."}, 400)

            _app_ctx_stack.top.current_user = payload
            return f(*args, **kwargs)
        raise AuthError({"code": "invalid_header",
                        "description": "Unable to find appropriate key"}, 400)
    return decorated

# Controllers API

# This doesn't need authentication
@app.route("/ping")
@cross_origin(headers=['Content-Type', 'Authorization'])
def ping():
    return "All good. You don't need to be authenticated to call this"

# This does need authentication
@app.route("/secured/ping")
@cross_origin(headers=['Content-Type', 'Authorization'])
@requires_auth
def secured_ping():
    return "All good. You only get this message if you're authenticated"