Problem Solving Template (change the title)

To learn how to use this template, check out the course "Data Structures and Algorithms in Python".

This tutorial is an executable Jupyter notebook. Click the Open in Colab button at the top of this page to execute the code.

Jupyter Notebooks: This notebook is made of cells. Each cell can contain code written in Python or explanations in plain English. You can execute code cells and view the results instantly within the notebook. Jupyter is a powerful platform for experimentation and analysis. Don't be afraid to mess around with the code & break things - you'll learn a lot by encountering and fixing errors. You can use the "Kernel > Restart & Clear Output" menu option to clear all outputs and start again from the top.

Try executing the cells below:

Problem Statement

??? (past the problem statement here)

Source: ??? (link to the source)

The Method

Here's the systematic strategy we'll apply for solving problems:

State the problem clearly. Identify the input & output formats.
Come up with some example inputs & outputs. Try to cover all edge cases.
Come up with a correct solution for the problem. State it in plain English.
Implement the solution and test it using example inputs. Fix bugs, if any.
Analyze the algorithm's complexity and identify inefficiencies, if any.
Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

Solution

1. State the problem clearly. Identify the input & output formats.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

Problem

??? (express the problem clearly in our own words, and in absract terms

Input

???
???

(add more if required)

Output

???

(add more if required)

Based on the above, we can now create a signature of our function:

# Create a function signature here. The body of the function can contain a single statement: pass

2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

???
???
???
???
???

(add more if required)

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).

test = {
    'input': {
        ???
    },
    'output': ???
}

Let's create some helper functions for testing the edge cases.

from timeit import default_timer as timer
from textwrap import dedent
import math

def _str_trunc(data, size=100):
    data_str = str(data)
    if len(data_str) > size + 3:
        return data_str[:size] + '...'
    return data_str


def _show_test_case(test_case):
    inputs = test_case['input']

    if 'outputs' in test_case:
        expected_text = "Outputs"
        expected = test_case.get('outputs')
    else:
        expected_text = "Output"
        expected = test_case.get('output')

    print(dedent("""
    Input:
    {}

    Expected {}:
    {}
    """.format(_str_trunc(inputs), expected_text, _str_trunc(expected))))


def _show_result(result):
    actual_output, passed, runtime = result
    message = "\033[92mPASSED\033[0m" if passed else "\033[91mFAILED\033[0m"
    print(dedent("""
    Actual Output:
    {}

    Execution Time:
    {} ms

    Test Result:
    {}
    """.format(_str_trunc(actual_output), runtime, message)))


def evaluate_test_case(function, test_case, display=True):
    """Check if `function` works as expected for `test_case`"""
    inputs = test_case['input']

    if display:
        _show_test_case(test_case)

    start = timer()
    actual_output = function(**inputs)
    end = timer()

    runtime = math.ceil((end - start)*1e6)/1000
    if 'outputs' in test_case:
        passed = actual_output in test_case.get('outputs')
    else:
        passed = actual_output == test_case.get('output')

    result = actual_output, passed, runtime

    if display:
        _show_result(result)

    return result


def evaluate_test_cases(function, test_cases, error_only=False, summary_only=False):
    results = []
    for i, test_case in enumerate(test_cases):
        if not error_only:
            print("\n\033[1mTEST CASE #{}\033[0m".format(i))
        result = evaluate_test_case(function, test_case, display=False)
        results.append(result)
        if error_only and not result[1]:
            print("\n\033[1mTEST CASE #{}\033[0m".format(i))
        if not error_only or not result[1]:
            _show_test_case(test_case)
            _show_result(result)

    total = len(results)
    num_passed = sum([r[1] for r in results])
    print("\n\033[1mSUMMARY\033[0m")
    print("\nTOTAL: {}, \033[92mPASSED\033[0m: {}, \033[91mFAILED\033[0m: {}".format(
        total, num_passed, total - num_passed))
    return results

We can test the function by passing the input to it directly or by using the evaluate_test_case helper function defined above.

evaluate_test_case(???)

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

tests = []

tests.append(test)

tests.append({
    'input': {
        ???
    },
    'output': ???
})

# add more test cases

Evaluate your function against all the test cases together using the evaluate_test_cases (plural) function.

evaluate_test_cases(???)

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

3. Come up with a correct solution for the problem. State it in plain English.

Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution. Come with a correct solution and explain it in simple words below:

???
???
???
???
???

(add more steps if required)

4. Implement the solution and test it using example inputs. Fix bugs, if any.

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

7. Come up with a correct solution for the problem. State it in plain English.

Come with the optimized correct solution and explain it in simple words below:

???
???
???
???
???

(add more steps if required)

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

Submission

To save your work, select "File" > "Save a Copy in Drive" on Google Colab. Once the copy is created, click the "Share" button and select "Anyone with the link" under the "General Access" section to make this notebook publicly accessible.

Then, copy the notebook link and submit it on the assignment page.