Problem Solving

Programmers are paid to solve problems, and problems have patterns. Ava faces a few classics. Is this word a palindrome? How many times does each word appear? Do these two plant names use the same letters? Which numbers make a given total? A calm method works for all of them. Understand, plan, code, test, and improve.

• Classic puzzles have patterns
• A calm method for every problem
• Understand, plan, code, test, improve

A method for any problem

Follow five steps. First, understand the problem, and write down an example. Second, plan in plain words, before writing code. Third, solve a simpler version first. Fourth, code it, and test with small, and with tricky inputs. Fifth, improve, only when it already works. Skipping the plan is the most common beginner mistake.

Palindromes and anagrams

A palindrome reads the same forwards and backwards. Clean the text first, lower case and letters only, then compare it with its reverse. Two words are anagrams, if their sorted letters are equal. Both solutions are one line, once you know the tools. Test them with a few cases, including a tricky one.

def is_palindrome(s):
    s = "".join(c.lower() for c in s if c.isalnum())
    return s == s[::-1]

def anagrams(a, b):
    return sorted(a.lower()) == sorted(b.lower())

print(is_palindrome("A man, a plan, a canal: Panama"))
print(is_palindrome("fern"))
print(anagrams("Listen", "Silent"))

True
False
True

FizzBuzz and word counting

FizzBuzz is a famous test. For each number, print fizz for multiples of three, buzz for multiples of five, and fizzbuzz for both. The order of the checks matters. And word counting combines splitting, lowercasing, and a Counter, to find the most common words in a text.

from collections import Counter

for n in range(1, 16):
    if n % 15 == 0:
        print("FizzBuzz")
    elif n % 3 == 0:
        print("Fizz")
    elif n % 5 == 0:
        print("Buzz")
    else:
        print(n)

text = "the fern and the ivy and the rose"
print(Counter(text.split()).most_common(2))

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
[('the', 3), ('and', 2)]

Two sum: use a dictionary

Here is another classic. Given a list of numbers and a target, find two numbers that add to the target. The slow way tries every pair. The clever way remembers the numbers already seen in a dictionary, and for each new number, checks if its partner is already there. One pass, and constant time lookups.

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return seen[target - n], i
        seen[n] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([1, 2], 10))

(0, 1)
(1, 2)
None

Recursion: permutations of a word

Recursion solves problems by splitting them into smaller ones. To list the arrangements of a word, choose each letter as the first, and arrange the rest, recursively. The base case is a word of one letter. This pattern, called backtracking, solves puzzles from sudoku to route planning.

def arrangements(word):
    if len(word) <= 1:
        return [word]
    out = []
    for i, ch in enumerate(word):
        for rest in arrangements(word[:i] + word[i + 1:]):
            out.append(ch + rest)
    return out

print(arrangements("abc"))
print(len(arrangements("abcd")))

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
24

Find the duplicate

Your turn. Write a function that returns the first number that appears twice in a list, or None. Use a set, to remember what you have seen. Ready? Here is one solution. A set of seen numbers, and one pass through the list.

def first_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return n
        seen.add(n)
    return None

print(first_duplicate([3, 1, 4, 1, 5]))
print(first_duplicate([1, 2, 3]))

1
None

Summary