Problem solving in programming

Problem solving in programming

There's no "right" way to go about problem solving in any discipline. But there are quite a few ways to make your life easier when trying to come up with solutions. Here are some suggested strategies, roughly in the order one would make use of them.

Develop a growth mindset

First things first, we want to make sure we're in a good frame of mind for working on a challenge. There's been a large number of studies (e.g., Aronson et al. 2002, Dweck 2006, Blackwell et al. 2007) on the effect of mindset on academic performance and resilience. As a rough summary, we can think of two kinds of mindsets with respect to one's response to challenging situations. A growth mindset views challenges as opportunities to grow one's understanding and skills, while a fixed mindset view challenges as indications of one's innate abilities.

In this class, we will be faced with numerous challenges. It is important to remind ourselves that failure is not an indication that we aren't up to the task at hand. Rather failure is feedback that can help us learn.

One small-scale example of applying growth mindset would be how we respond to an error raised by some python code we've written. On face, the large amount of text in the error is intimidating and indicates that we have made some mistake. But if we view the error as a tool for determining what went wrong, we're much more likely to succeed in achieving our goal.

Define the problem

Clearly and as precisely as possible state the challenge at hand. Specify what, if any, input you expect to have. What is the output you are expected to provide?

Define tests of correctness

Think of what a successful solution looks like. If your solution takes the form of a function, can you write tests for that functions correctness before even beginning? Just because a program has run without errors doesn't mean that it is doing what you wanted. Think carefully about what sort of edge cases you might run into, and write your tests accordingly.

Propose possible solutions

You don't have to have thought this all the way through before starting! The goal is to get some ideas about what tasks are involved in getting to your desired output. Which leads us to...

Break the challenge down into smaller chunks

It's generally an impossible task to hold the entire challenge in your head. If there are parts of the challenge that can be accomplished independently, note this and work on it when you see fit. You can follow the same general problem solving strategies for sub-tasks as you do for the overall challenge.

Write your solution as pseudocode

After proposing a possible solution, it's often helpful to have an intermediate representation between the solution as described verbally and the code you end up writing. This helps keep you on track for following the logic of what you want to do when you run into the inevitable syntax difficulties while writing the actual code.

Write some code!

Thinking though things is important, but at some point we just have to try it out. It's helpful to view problem solving as an iterative process. For example, you may have thought you had defined the challenge in its entirety, but actually writing your implementation of the solution may have convinced you that you are missing some crucial input and have to return to defining the problem.

On the small scale, when you're getting started with writing code (or even just writing pseudocode), think of the variables you'll need and the roles they play in your solution. "Role" in this sense doesn't refer to any particular data type or syntax. Rather "role" refers to the higher level concept of the purpose that the variable has in the context of the challenge at hand. Jorma Sajaniemi has a helpful classification of common variable roles for reference.

Example problem: sorting a list

Let's try an example of sorting a list. Note that this functionality is already built into python lists and numpy arrays. But it's a good exercise to try this ourselves!

Problem statement

Given a list of numbers, output a new list which contains all of the elements of the original list but sorted in ascending order.

Test cases

What sort (no pun intended) of tests could we do to convince ourselves we have a correct solution?

>>> a = [5, 4, 2, 2, 9]
>>> b = sort(a)
>>> print(b)
[2, 2, 4, 5, 9]
>>> a = [1, 65, 2, 5.0, -2.3]
>>> b = sort(a)
>>> print(b)
[-2.3, 1, 2, 5.0, 65]

Proposed solution

  1. Find the smallest element of the original list
  2. Remove the smallest list and insert it into the sorted list
  3. Repeat 1-2 until we have gone through all of the original list

Sub-tasks

We need to be able to find the index of the smallest element of a list.

One way of doing this might be:

  1. Set a variable to be some very large number.
  2. For each element in the list, if that element is smaller than the previous smallest, forget about the previous one and remember the new smallest element.

Pseudocode

input: list

sorted list <- empty list
while list is not empty
    find minimum element of list
    remove minimum element from list
    insert minimum element into sorted list

output: sorted list

Solution as code

In [1]:
def index_of_min(sequence):
    """Find the index of the smallest element of the list.
    
    Parameters
    ----------
    sequence : list
        elements should all be numbers
    
    Returns
    -------
    min_index : int
        index of the minimum element of the list
    """
    # left as an in-class exercise
    pass
        
    
def sort(sequence):
    """Sort a sequence of numbers in ascending order.
    
    Parameters
    ----------
    sequence : list
        elements should all be numbers
    
    Returns
    -------
    sorted_sequence : list
    """
    # create an empty list to hold the sorted elements
    sorted_sequence = []
    while len(sequence) > 0:
        # get minimum element of the list
        min_index = index_of_min(sequence)
        min_element = sequence.pop(min_index)
        sorted_sequence.append(min_element)
    return sorted_sequence

Trying out our test cases

In [2]:
a = [5, 4, 2, 2, 9]
sorted_a = [2, 2, 4, 5, 9]
b = sort(a)
print("correct solution: {}".format(sorted_a))
print("our solution:     {}".format(b))

a = [1, 65, 2, 5.0, -2.3]
sorted_a = [-2.3, 1, 2, 5.0, 65]
b = sort(a)
print("correct solution: {}".format(sorted_a))
print("our solution:     {}".format(b))
correct solution: [2, 2, 4, 5, 9]
our solution:     [2, 2, 4, 5, 9]
correct solution: [-2.3, 1, 2, 5.0, 65]
our solution:     [-2.3, 1, 2, 5.0, 65]

Notes on this particular problem

As the benchmarking below indicates, this isn't a particularly efficient way to sort a list. But a slowly running program that gets the correct answer is almost always better than a quick running program that gets the incorrect answer. Stated more dramatically, premature optimization is the root of all evil.

If you've been playing around with the sorting function defined above, you may have noticed that it has the nasty habit of emptying out the inputted list. We could get around this by copying the inputted list and working on the copied list, e.g.,

def sort(sequence):
    # this only overwrites the symbol, "sequence", not the list in memory
    sequence = sequence.copy()
    ...
In [3]:
import numpy as np

def test_mysort():
    a = list(np.random.choice(1000, size=100))
    b = sort(a)
    
def test_pysort():
    a = list(np.random.choice(1000, size=100))
    a.sort()

def test_npsort():
    a = np.random.choice(1000, size=100)
    a.sort()
In [4]:
%timeit test_mysort()
572 µs ± 21 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [5]:
%timeit test_pysort()
33.7 µs ± 305 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [6]:
%timeit test_npsort()
14.9 µs ± 553 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

social