CS101 »

Unit 2.5: Problem Solving Strategies

Table of Contents

Contents

Introduction

Solving problems is one of the most important skills for a programmer. Solving problems is a lifelong challenge. In this lesson we're going to look at some aspects of how to approach complicated problems. We will look at a specific problem, not just to solve it, but also to draw general lessons about how we can get better at problem solving.

The problem that we will use was suggested by one of our students, Mattias Wecksten: Given your birthday and the current date, calculate your age in days. Compensate for leap days. Assume that the birthday and current date are correct dates (and no time travel). Simply put, if you were born on 1 Jan 2012 and today's date is 2 Jan 2012, you are 1 day old.

Quiz 1

What is the first thing we should do to solve a problem like this one?

  1. Start writing code
  2. Make sure we understand the problem
  3. Search Google for the answer
  4. Write an algorithm that solves it

Answer

Understanding the Problem

Our problem is, "Given your birthday and the current date, calculate your age in days". So what does it mean to understand a problem?

What all computational problems have in common is that they have a set of inputs and a set of desired outputs. A problem is therefore defined by a set of possible inputs (usually an infinite set) and the relationship between those inputs and the desired outputs. The solution to the problem is a procedure that can take any input from the set and produce an output that satisfies the relationship we want.

The first rule in the Pythonista's Guide to solving All Problems in the Known Computational Galaxy is to always ask, "What are the inputs?" Now there is one rule before that, the zeroeth rule, which is "Don't Panic". If you panic, you are never going to be able to solve the problem. But the first substantial rule is to figure out what the inputs are.

What are the Inputs?

For our example problem, the inputs are fairly clearly stated: your birthday and the current date. But we want this to work for any birthday and any given current date—otherwise, we could just solve the problem once without the need to write a procedure. The set of valid inputs are therefore really any two dates where the second date is after the first date, with no time travel. We will check this in our code. We will also require the dates are valid in the Gregorian calendar (which began 15 Oct 1582).

For most real-world problems, it's up to you to figure out how to encode the inputs, and this is one of the most important decisions you can make in solving a problem. In this case, the template for the problem indicates how the inputs are to be represented: there are six parameters to the daysBetweenDates() procedure, namely year1, month1, day1, year2, month2, day2. Our solution needs the inputs represented in this way.

What are the Outputs?

The next thing we need to understand about the problem is, "What are the outputs?" The statement of the question, "Given your birthday and the current date, calculate your age in days", gives some idea of what the output should be: your age in days. But it doesn't specify exactly what the output should be.

Quiz 2

How should we specify the output?

  1. Print a number giving the number of days between the first date and the second date
  2. Return a number giving the number of days between the first date and the second date
  3. Output three values giving the number of years, months, and days between the two input dates

Answer

So now we have the second step in our Universal Guide to Solving All Problems, which is: understanding what the outputs are. All we have left to do is the third step, which is the hard one: to actually solve the problem. But if you don't do the first parts, you are going to have a very hard time solving the problem. You always want to start out by thinking about the inputs and outputs before going on to the difficult part of mapping the inputs to the outputs.

prob_solve_steps.png

Understanding the Relationship between Inputs and Outputs

So now we understand our problem; we know what the inputs are and what the outputs are. We now need to make sure we understand the relationship between the two.

Quiz 3

What should we do next?

  1. Start coding!
  2. Panic
  3. Work out examples

Answer

Quiz 4

For each of these examples, give the expected output or write "Undefined" if there is no defined output, meaning that the inputs given were not valid.

  1. daysBetweenDates(2012, 12, 7, 2012, 12, 7)
  2. daysBetweenDates(2012, 12, 7, 2012, 12, 8)
  3. daysBetweenDates(2012, 12, 8, 2012, 12, 7)
  4. daysBetweenDates(2012, 6, 29, 2013, 6, 29)
  5. daysBetweenDates(2012, 6, 29, 2013, 6, 31)

Answer

Working through Examples

Having understood the inputs, the outputs, and the relationship between the two, you might be ready to start coding. But if the problem is a challenging one, it would be better to first consider systematically how to solve the problem as a human. If you don't yourself understand in a systematic way how to solve the problem, you're probably not ready to start writing code. Let's think carefully and systematically about how we would actually go about solving some cases.

Suppose we wanted to find daysBetweenDates(2013, 1, 24, 2013, 6, 29). As a human we might look at a calendar and count the days.

  • Jan 24–Jan 31: 7 days
  • All of Feb: 28 days
  • All of Mar: 31 days
  • All of April: 30 days
  • All of May: 31 days
  • June 1–June 29: 29 days

The sum is 156.

Now if we make the problem harder by asking daysBetweenDates(2013, 1, 24, 2024, 6, 29), we would need to add the days in the years between 2013 and 2024. Some years would have 365 days and others would be leap years. So this is a fairly complicated problem.

Let's try to write an algorithm that systematizes how we solve this problem as a human. We will begin in pseudocode.

days = number of days in month1 - day1
month1 += 1
while month1 < month2:
    days += number of days in month 1
days += day2
while year1 < year2:
    days += days in year1

Quiz 5

Should we implement this algorithm?

  1. Yes, this is correct
  2. Yes, this doesn't address all cases, but is a good start
  3. No, we should figure out how to address all cases first
  4. No, we should try to find a simpler way

Answer

A Different Approach

Let's think of a simple way we might solve this problem. We start on the first day and simply keep counting off each day until we get to the next day. Here is the algorithm:

days = 0
while date1 is before date2:
    date1 = day after next day
    days += 1

Is this actually practical? For a human it would not be practical to count off days if the dates are really far apart. But what about for a computer? Here's a quiz that requires a bit of guesswork.

Quiz 6

Roughly how long will it take a Python program using this approach to count the number of days between 12 Dec 1912 and 12 Dec 2012?

  1. A few nanoseconds
  2. A few milliseconds
  3. A few seconds
  4. A few minutes
  5. A few hours
  6. Way too long!

Answer

Premature Optimization

If we're using this program for humans to calculate how many days old they are in an interactive way, then the fact that we have to wait three-hundredths of a second for the answer doesn't matter; getting that down to a hundredth of a second isn't worth the extra effort. However, if we are using this in a service that's doing this computation lots and lots of times for lots and lots of different dates, then maybe it isn't fast enough, and it's worth putting the extra time and effort into doing something better. We shouldn't put that time and effort in until we know we need it to be faster. 

This point is important enough to put into our guide to solving all problems.

steps.png

So we have our first steps:

  1. Don't panic
  2. Make sure we understand the inputs and the outputs
  3. Work through some examples by hand to think about how we would solve the problem systematically
  4. Then try to work out a simple mechanical solution.

The key here is simplicity; the simpler it is, the more likely we are going to be able to program it correctly. Eventually we might have to worry about making it faster, but let's not worry about that until we have to.

Now we have a simple mechanical solution, and we've written that out as pseudocode. We are ready to start coding, but we should think carefully about how to do that. The question is, what should we write first?

Quiz 7

Given this algorithm:

days = 0
while date1 is before date2:
    date1 = day after next day
    days += 1

What should we code first?

  1. the daysBetweenDates() procedure to solve the whole problem
  2. a nextDay(year, month, day) procedure which takes the current date given as a year, month, and a day and returns the next day, but which only works for simple cases (and assumes all months have the same number of days)
  3. an isLeapYear(year) procedure which takes a year and returns True or False based on whether that year is a leap year
  4. a daysInMonth(month) procedure that takes a month and returns the number of days in that given month

This is quite a subjective question; you could certainly make an argument for at least two of these answers. Try to figure out which is the best answer. 

Answer

Quiz 8

Let's start with writing the nextDay() procedure, and to keep things simple, we'll assume all months have thirty days. Define a procedure nextDay(year, month, day) that takes as input a valid date in the Gregorian calendar. The date is encoded as numbers for the year, month, and day. The procedure returns the next day as a three-number tuple year, month, day. Assume all months have 30 days. 

Answer

Making Progress is Good!

We haven't solved a problem, but we are making progress, and making progress is really good! This is a key point, and we should have a smiley face:

progress.png

We should be happy we are making progress. The way to make progress isn't to write lots of code, but to write small bits of code to test them and know what they do. We haven't solved the problem yet (we have lots of simplifications), and we've only solved one part of it, but because of our solution, once we implement nextDay() correctly, we're a good part of the way there.

Quiz 9

What should we do next?

  1. Refine nextDay() to work correctly for real months.
  2. Define daysBetweenDates() to give approximate answers using our current nextDay() procedure.
  3. Go to the beach and celebrate, since our answer is good enough. We're happy with our answer.

Answer

Quiz 10

Define a daysBetweenDates() procedure that would produce the approximately correct results given the current nextDay() procedure, and that would produce exactly correct results given a correct nextDay() procedure. 

Hint: Doing daysBetweenDates() by itself will still be more complicated than we want one procedure to be. Start by defining a helper procedure. You should test the helper procedure independently before you try to build the complete daysBetweenDates() procedure. What would be a useful helper procedure?

Answer

Testing Our Solution

Let's try a sample call to the function we wrote in Quiz 10 to see how well our solution works:

  • daysBetweenDates(2013, 1, 24, 2013, 6, 29)

This was the first example we did by hand. We get 155, which is not exactly correct but is close. We got 156 by hand. Since our nextDay() assumes all months have 30 days, it's not surprising we don't get exactly the right answer here.

Let's try another example. This will be a good sanity check to see if our solution is fast enough:

  • daysBetweenDates(1912, 12, 12, 2012, 12, 12)

We've got 100 years here and our solution returns 36000. Seems correct, with our 12 months of 30 days, our year is 360 days long instead of 365.

Let's try one more example. Try to guess what will happen here before you run it.

  • daysBetweenDates(2013, 1, 1, 2012, 12, 20)

The answer is 0, which is not really correct. Can you see why the code returns zero? It's a valid answer given our assumptions, but it's not a satisfactory answer. We could change the specification to say that if the first date is after the second date then the answer is 0. It would make more sense to get a negative result, but this would make our code more complicated.

It would be better instead to program defensively. If the assumptions the function depends on are not satisfied by the inputs, it's a lot more helpful to raise an assertion to give a failure, rather than to continue and give a mysterious result. So let's do that in a quiz.

Quiz 11

Add an assertion to daysBetweenDates() to give an assertion failure when the inputs are invalid.

The syntax for an assertion is assert <Expression>. If the value of the expression is False, the assertion fails, and execution will stop with an exception.

Answer

Testing for Valid Inputs

When we run this revised code with invalid inputs, instead of getting the value 0, we get an AssertionError:

assertion.png

This is not a really friendly error message for a regular user, but for a programmer it is helpful, as it points to the exact line in the code where the assertion failed.

Real World Problem

We've got the guts of our program working, we've tested it, and we've got some confidence it's going to work correctly. We have a problem, though. We're not getting the correct answer. That is because not all months have 30 days. We've tried to put this off but we now have to deal with the complexity of how many days there actually are in a month. That's our last thing to deal with. What should we do to finish this problem?

Quiz 12

We have a lot of things we could do next:

  • A. write isLeapYear(year)
  • B. write stub daysInMonth(year, month) that always returns 30
  • C. modify daysInMonth(year, month) to be correct except for leap years
  • D. modify daysInMonth(year, month) to account for leap years
  • E. modify nextDay(year, month, day) to use daysInMonth(year, month)
  • F. test isLeapYear(year)
  • G. test daysInMonth(year, month) except for leap years
  • H. test daysInMonth(year, month) including leap years
  • I. test nextDay(year, month, day) using stub daysInMonth(year, month)
  • J. test daysBetweenDates() for simple cases
  • K. test daysBetweenDates() for all test cases

We don't necessarily need to do all of these, and the order we do these makes a big difference in how efficiently and correctly we solve the problem. List the steps you will do in order, e.g., ABACAB. This is not the correct answer, but you can include the steps more than once and you don't have to use all of the steps. Several different ways to answer this question are accepted as correct.

In order to answer this question, you should think about the dependencies between the various steps, but also about what order of implementing and testing them will be most likely to efficiently lead to a correct solution.

Answer

Quiz 13

The final quiz for this lesson is to finish daysBetweenDates() on your own. Use the suggestions above to develop and test your code. If you get stuck, read part of the answer, but then go back to solving it yourself after seeing the solution for the first part.

Answer

Conclusion

There are lots and lots of ways to solve this problem. If we wanted it to be faster, there are ways to do it better than this naïve approach of going day-by-day. But as far as getting correct code, the simple approach has lots of advantages. If you want to extend this as another programming exercise, you could try to make it faster. Also, if this were not a programming exercise, Python has built-in types for managing dates. Using those would make your life a lot easier. If you have an interesting way of solving it, post that for discussion on the class forum.

That concludes this lesson on problem solving.  Developing better problem solving skills is really a lifetime of effort. The guidelines given here will be useful in solving problems you face in the future.  Our first step is always to not panic.  Then we think about the inputs and the outputs and making sure we understand the problem by working through some problems by hand.  We then think of a simple mechanical solution that we will be able to turn into code.  Then the final step, which is what we've been doing in the last quiz, is to develop our solution incrementally in small steps that we can test as we go.

Last_steps.png

Thanks for sticking to the lesson, and we hope you'll solve lots of hard problems in the future!

Answer Key

Quiz 1: Answer

  • Make sure we understand the problem

The best answer is the second choice: make sure we understand the problem. Let's examine the other answers to see why. It's often tempting to start writing code right away, because that's what we do as programmers. But there are dangers in beginning to write code straightaway, without making sure to understand the problem first. We might get stuck and get frustrated, or we might write a lot of code that doesn't really solve the problem we wanted to solve.

Searching Google is a fine answer if this weren't a practice problem. But since it is a practice problem, you'll learn a lot more if you try to solve it on your own first before searching for the answer.

Writing an algorithm that solves the problem also depends on understanding the problem: until we understand the problem, we won't know how to design an algorithm to solve it.

Quiz 2: Answer

  • Return a number giving the number of days between the first date and the second date

Returning a number is much more useful than printing the number. If we return the number, we can do further computations with it. If we print it out, it gets printed out and then it's hard to use for anything else. And the third choice, outputting three values, doesn't really match what was stated.

Note that we haven't really stated what the output should be if the second date is before the first date. That's because we are assuming that this will never happen.

Quiz 3: Answer

  • Work out some examples

You could start coding if you are really confident, but the best way to understand the relationship between the inputs and the outputs is to work out some examples. That will also give us some test cases to make sure our code really works.

Quiz 4: Answer

  1. 0
  2. 1
  3. undefined
  4. 365
  5. undefined

Quiz 5: Answer

  • No, we should try to find a simpler way

This code is already fairly complex. It has two loops and lots of statements, and it doesn't handle many cases. It doesn't handle the case where the input dates are in the same month, or where month2 < month1, year2 > year1. It also doesn't handle counting days in leap years well. We could fix the code to handle these things; if you chose the second answer, I would encourage you to try it. Our goal as programmers is to try to find a simpler method, because it is very hard to get all of these things correct, and you end up with very complicated code.

Often the way humans solve things is not the simplest. We are lazy. Computers are not. Doing things in a simple, mechanical way will more likely lead to a correct solution.

Quiz 6: Answer

  • A few milliseconds

We have 100 years. A year is roughly 365 days. We have ~36,500 days. A modern processor can do about 1 billion instructions per second (1 nanosecond/instruction). An instruction is not the same as a single Python statement; each Python statement gets translated into several instructions that the computer executes. We can roughly estimate that for each time through this loop, we need about 1000 instructions. We therefore need 36.5M instructions total (1000 * 36,500). That will be about 36.5M nanoseconds, which is 36.5 milliseconds.

Quiz 7: Answer

  • nextDay(year, month, day)

The one that I think is best is the nextDay() procedure; this is sort of the most important thing to make this solution work.  If we can't do this, then we would have to think of a different approach.  The reason I think this is best is because we can solve this in a simple way for a simple case, which is what we'll do next, not worrying about the complexity of how many days are in different months, and get a good feeling that we're able to get close to the right answer in other cases.  The other answer that I think would be okay is isLeapYear(). This is something that we know we're going to need at some point, as we will need to determine whether years are leap years to know how many days there are in February. But it is kind of a grungy, painful thing to write.  It's something we know we will be able to do, and it's not something too interesting, so we are going to leave it until later.  You can certainly make a case for doing that first. 

The other two are really not good answers.  Trying to do the whole problem at this point is a little early; we still want to break it down into simpler parts and make progress and know we are making progress.  daysInMonth() is closer to something reasonable, but the problem is that until we write these other procedures, we might not know enough to implement this correctly.  The reason I'm going to suggest that this is not what we want is that the number of days in a month actually depends on the year if the month is February. 

Quiz 8: Answer

def nextDay(year, month, day):
    '''Warning: this version incorrectly assumes 
       all months have 30 days!'''
    if day < 30:
        return year, month, day + 1
    else:
        if month < 12:
            return year, month + 1, 1
        else:
            return year + 1, 1, 1

Note that I start with a docstring.  This is treated as a special comment by most Python systems, and I put in this warning so people realize this implementation is not actually correct, so it shouldn't be used to schedule, say, the apocalypse, but it's good for our testing for now. 

The logic is quite simple.  If the day is less than 30 (since we are assuming all months have 30 days), we increase the day by one, and I return a three-number tuple of the year, the month and the day.  Otherwise we need to increase the month, so we are going to advance to the next month (and reset the day to one).  If we are in December, then we need to increase the year by one and reset the date to January 1st. 

As with the larger problem, you should start this by thinking about some test cases, and see that those behave as expected. I should note that for some cases, say January 30th, the day following January 30th should be January 31st, but I will get February 1st because of our assumption that all months have 30 days.  We should also try a more difficult case, such as the end of the year.  We could use December 31st or December 30th (because of the assumption, and either way we get January 1st of the next year.

Quiz 9: Answer

  • define daysBetweenDates() to give approximate answers using our current nextDay() procedure.

Any of these could be correct, especially depending on how close you live to a beach and how nice the weather is today, but I will suggest we write daysBetweenDates() rather than refine nextDay(). The advantage of doing number 2 first is we will have a lot of confidence that we are on the right track if this works.  We will be very close and getting approximate answers, showing we are on the right track.  We can then figure out the details of nextDay(), but we won't have to change the code of daysBetweenDates() later. 

Quiz 10: Answer

The solution to this problem is broken down into three parts:

  • Step One: Pseudocode

  • Step Two: Helper Function

  • Step Three: daysBetweenDates()

Let's think about the pseudocode we had before:

days = 0
while date1 is before date2:
    date1 = day after next day
    days += 1

We have this while loop, where we need to know as the stopping condition if date1 is before date2. We then have the body that keeps incrementing the date. If we are going to make a helper procedure, we should write something that makes it easier to make the date comparison.  That will be a lot better to do as a helper procedure than to do it inside of the daysBetweenDates() code.  Knowing whether one date is before another date is something that is possibly useful in other contexts; we will actually see another use for it in writing this.  The other advantage of writing this as a separate helper procedure is that we can test that separately.

We'll write a procedure dateIsBefore(year1, month1, day1, year2, month2, day2) that takes as input two dates, which will still be encoded as three values.  It will return True or False telling us if year1, month1, day1 is before year2, month2, day2.

def dateIsBefore (year1, month1, day1, year2, month2, day2):
    '''Returns True if year1-month1-day1 is before year2-month2-day2.
       Otherwise, returns False.'''
    if year1 < year2:
        return True
    if year1 == year2:
        if month1 < month2:
            return True
        if month1 == month2:
            return day1 < day2
    return False

If year1 is before year2, we can return True right away. If the years are equal, we need to look at the months. If month1 is before month2 we return True. If the months are also the same then we look at the days. Note that we don't have elses here, but if we don't hit the returns we will fall through to the last statement here, which is return False.

Now that we have the helper procedure, defining days between dates is pretty simple.

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    '''Returns the number of days between year1-month1-day1 and
       year2-month2-day2. Assumes inputs are valid dates in Gregorian calendar, 
       and the first date is not after the second.'''
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay (year1, month1, day1)
        days += 1
    return days

We have our while loop condition checking if date1 is before date2, and then we update the year1, month1, and day1 values with the next day. We then add one to the number of days.

Quiz 11: Answer

This question is a little trickier than it seems. If the two dates are the same, we need to get the answer 0 rather than an exception. The solution is to use a not, and switch the order of the dates.

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    '''Returns the number of days between year1/month1/day1
       and year2/month2/day2. Assumes inputs are valid dates
       in Gregorian calendar.'''
    # program defensively! Add an assertion if the input is not valid!
    assert not dateIsBefore(year2, month2, day2, year1, month1, day1)
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days += 1
    return days

Quiz 12: Answer

  • BEICIAFK

Here's what I'll suggest. I'm going to first write stub daysInMonth() that will take a year and a month and always return 30, which is not always correct (B). Then we'll modify our nextDay() routine to use that stub (E) and right away we'll test it (I). At this point we won't have done anything that will change the outputs from what we were getting before, but we've restructured the code in a way that all we have to do is improve daysInMonth() and we will have the right answer. We have modified daysInMonth() to be correct except for leap years. I'm putting off leap years as long as I can because they're annoying. They only come up occasionally. So I'll modify daysInMonth() to be correct except for leap years (C). Then it's a good idea to test again (I). It would have been okay to do the testing in daysInMonth() (G) but it might be easier to run the same test again and again (I). I'll do the leap years next. I'll write a helper procedure as step six (A) and then test it again. It makes more sense to test this separately (F). After I've done that I should have a fully correct solution. I could test it separately so I'll just right ahead to run all the test cases (K).

One thing that would certainly make sense is to move the leap year stuff to the beginning. The property all the correct answers should have is that you're writing small bits of code that you can test independently as you go. One of the most important things as a developer is to think of ways to structure code: to organize the way you build code so you can test meaningfully as you go. As you get more confident as a programmer you might skip some of these steps.

Part of my motivation in asking this question is that when I wrote the code myself is I had a bug in my solution because I didn't do the steps carefully enough. All the test cases failed. Debugging took a lot longer than if I followed this pattern. What I encourage you to do as you program is to write code to run all these tests as part of your solution. Then, when you finally get to step K it will magically all work the first time!

Quiz 13: Answer

Let's start with the code we had before that works correctly except for the assumption that all months have 30 days:

def dateIsBefore (year1, month1, day1, year2, month2, day2):
    '''Returns True if year1-month1-day1 is before year2-month2-day2.
       Otherwise, returns False.'''
    if year1 < year2:
        return True
    if year1 == year2:
        if month1 < month2:
            return True
        if month1 == month2:
            return day1 < day2
    return False

def nextDay(year, month, day):
    '''Warning: this version incorrectly assumes 
       all months have 30 days!'''
    if day < 30:
        return year, month, day + 1
    else:
        if month < 12:
            return year, month + 1, 1
        else:
            return year + 1, 1, 1

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    '''Returns the number of days between year1/month1/day1
       and year2/month2/day2. Assumes inputs are valid dates
       in Gregorian calendar.'''
    # program defensively! Add an assertion if the input is not valid!
    assert not dateIsBefore(year2, month2, day2, year1, month1, day1)
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days += 1
    return days

The first step will be to define a stub procedure daysInMonth() that gives the number of days in a month. But for our stub procedure we're going to always return 30 and we're going to modify nextDay() to call daysInMonth():

def dateIsBefore (year1, month1, day1, year2, month2, day2):
    '''Returns True if year1-month1-day1 is before year2-month2-day2.
       Otherwise, returns False.'''
    if year1 < year2:
        return True
    if year1 == year2:
        if month1 < month2:
            return True
        if month1 == month2:
            return day1 < day2
    return False

# stub procedure that always returns 30
def daysInMonth(year, month):
    '''Warning:  this version incorrectly assumes 
       all months have 30 days!'''
    return 30

def nextDay(year, month, day):
    # call daysInMonth()
    if day < daysInMonth(year, month):
        return year, month, day + 1
    else:
        if month < 12:
            return year, month + 1, 1
        else:
            return year + 1, 1, 1

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    '''Returns the number of days between year1/month1/day1
       and year2/month2/day2. Assumes inputs are valid dates
       in Gregorian calendar.'''
    # program defensively! Add an assertion if the input is not valid!
    assert not dateIsBefore(year2, month2, day2, year1, month1, day1)
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days += 1
    return days

We need to write some test cases as well. Add this test procedure to the bottom of the code and then call it:

def test():
    # tests within 30-day months
    assert daysBetweenDates(2013, 1, 1, 2013, 1, 1) == 0
    assert daysBetweenDates(2013, 1, 1, 2013, 1, 2) == 1
    assert nextDay(2013, 1, 1) == (2013, 1, 2)
    assert nextDay(2013, 4, 30) == (2013, 5, 1)
    assert nextDay(2012, 12, 31) == (2013, 1, 1)
    print 'Tests Completed'

test()

Next, we should modify daysInMonth() to be correct for all months except February in leap years, and add some more test cases:

def dateIsBefore (year1, month1, day1, year2, month2, day2):
    '''Returns True if year1-month1-day1 is before year2-month2-day2.
       Otherwise, returns False.'''
    if year1 < year2:
        return True
    if year1 == year2:
        if month1 < month2:
            return True
        if month1 == month2:
            return day1 < day2
    return False

# modified daysInMonth
def daysInMonth(year, month):
    '''Warning:  this version does not account for leap years!'''
    if month == 2:
        return 28
    elif month == 4 or month == 6 or month == 9 or month == 11:
        return 30
    else:
        return 31 

def nextDay(year, month, day):
    if day < daysInMonth(year, month):
        return year, month, day + 1
    else:
        if month < 12:
            return year, month + 1, 1
        else:
            return year + 1, 1, 1

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    '''Returns the number of days between year1/month1/day1
       and year2/month2/day2. Assumes inputs are valid dates
       in Gregorian calendar.'''
    assert not dateIsBefore(year2, month2, day2, year1, month1, day1)
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days += 1
    return days

def test():
    assert daysBetweenDates(2013, 1, 1, 2013, 1, 1) == 0
    assert daysBetweenDates(2013, 1, 1, 2013, 1, 2) == 1
    assert nextDay(2013, 1, 1) == (2013, 1, 2)
    assert nextDay(2013, 4, 30) == (2013, 5, 1)
    assert nextDay(2012, 12, 31) == (2013, 1, 1)

    # added test cases
    assert nextDay(2013, 2, 28) == (2013, 3, 1)
    assert daysBetweenDates(2013, 1, 1, 2014, 1, 1) == 365        
    print 'Tests Completed'

test()

Finally, we have to account for leap years. The rules for leap years are pretty complicated. If the year is divisible by 400, then it is a leap year. If it is divisible by 100, but not 400, then it is not a leap year. If it is not covered by the previous two examples but is divisible by 4,then it is a leap year. Otherwise it is not a leap year. Let's turn that into code. Let's also run some test cases to ensure that we get correct results:

def isLeapYear(year):
    if year % 400 == 0:
        return True
    if year % 100 == 0:
        return False
    if year % 4 == 0:
        return True
    return False
assert isLeapYear(2000) == True
assert isLeapYear(2100) == False
assert isLeapYear(2012) == True
assert isLeapYear(2013) == False

Now that we're confident we have this right, we can change the case for February in daysInMonth(). If it is a leap year, we return 29, otherwise we return 28. Let's also add a couple of tests that depend on leap years:

def dateIsBefore (year1, month1, day1, year2, month2, day2):
    '''Returns True if year1-month1-day1 is before year2-month2-day2.
       Otherwise, returns False.'''
    if year1 < year2:
        return True
    if year1 == year2:
        if month1 < month2:
            return True
        if month1 == month2:
            return day1 < day2
    return False

# modified daysInMonth
def daysInMonth(year, month):
    if month == 2:
        if isLeapYear(year):
            return 29
        return 28
    elif month == 4 or month == 6 or month == 9 or month == 11:
        return 30
    else:
        return 31 

def nextDay(year, month, day):
    if day < daysInMonth(year, month):
        return year, month, day + 1
    else:
        if month < 12:
            return year, month + 1, 1
        else:
            return year + 1, 1, 1

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    '''Returns the number of days between year1/month1/day1
       and year2/month2/day2. Assumes inputs are valid dates
       in Gregorian calendar.'''
    assert not dateIsBefore(year2, month2, day2, year1, month1, day1)
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days += 1
    return days

def test():
    assert daysBetweenDates(2013, 1, 1, 2013, 1, 1) == 0
    assert daysBetweenDates(2013, 1, 1, 2013, 1, 2) == 1
    assert nextDay(2013, 1, 1) == (2013, 1, 2)
    assert nextDay(2013, 4, 30) == (2013, 5, 1)
    assert nextDay(2012, 12, 31) == (2013, 1, 1)
    assert nextDay(2013, 2, 28) == (2013, 3, 1)
    assert daysBetweenDates(2013, 1, 1, 2014, 1, 1) == 365  

    # added tests for leap years
    assert nextDay (2012, 2, 28) == (2012, 2, 29)
    assert daysBetweenDates(2012, 1, 1, 2013, 1, 1) == 366      
    print 'Tests Completed'

test()