Counting ways to divide a word into palindrome blocks

Question

I wrote this program as a solution to the 2015 British Informatics Olympiad question on "block" palindromes.

Brief overview of the task:

A palindrome is a word that shows the same sequence of letters when reversed.

If a word can have its letters grouped together in two or more blocks (each containing one or more adjacent letters) then it is a block palindrome if reversing the order of those blocks results in the same sequence of blocks.

For example, using brackets to indicate blocks, the following are block palindromes:

• BONBON can be grouped together as (BON)(BON);
• ONION can be grouped together as (ON)(I)(ON);
• BBACBB can be grouped together as (B)(BACB)(B) or (BB)(AC)(BB) or (B)(B)(AC)(B)(B)

Note that (BB)(AC)(B)(B) is not valid as the reverse (B)(B)(AC)(BB) shows the blocks in a different order.

TASK: Write a program which reads in a word of between 2 and 10 (inclusive) uppercase letters.

You should output a single number, the number of different ways the input can be grouped to show it is a block palindrome.

What tips do you have for improving my solution:

# theonlygusti's solution to Question 1(a)

word = input()

if not (2 <= len(word) <= 10):
    print("Your input must be between 10 and 2 characters, inclusive.")
    exit()

if not word.upper() == word:
    print("Your input must be all uppercase, e.g. BBACBB")
    exit()

if not word.isalpha():
    print("Your input must contain only letters, this means characters like numbers and spaces are not allowed.")
    exit()

def number_of_block_palindrome_groupings(string):
    total_groupings = 0
    for i in range(1, len(string)//2+1):
        if (string[:i] == string[-i:]):
            total_groupings += 1 + number_of_block_palindrome_groupings(string[i:-i])
    return total_groupings

print(number_of_block_palindrome_groupings(word))

Answer 1

Exit code

When exiting due to an error, it's good to use a non-zero exit code. Calling exit() without an explicit value will use the default 0, meaning success.

Naming

The name number_of_block_palindrome_groupings is a bit long an tedious. How about count_block_palindromes?

List comprehensions

Instead of accumulating a sum with a loop, you could use a list comprehension:

return sum([1 + count_block_palindromes(string[i:-i])
            for i in range(1, len(string) // 2 + 1)
            if string[:i] == string[-i:]])

Memoization

In case of long input with recursive patterns, the same substrings may be computed many times repeatedly. It could be a useful optimization to cache the results of computing each unique input. An easy way to implement that using functools.lru_cache.

import functools


@functools.lru_cache()
def count_block_palindromes(string):
    # ...

Doc tests

Doc tests are awesome. They are executable documentations serving as unit tests, for example:

def count_block_palindromes(string):
    """
    >>> count_block_palindromes("BONBON")
    1

    >>> count_block_palindromes("ONION")
    1

    >>> count_block_palindromes("BBACBB")
    3

    >>> count_block_palindromes("BABABABABABABABA")
    15

    >>> count_block_palindromes("BABABABABABABAB")
    33

    """
    # ... the code

This is runnable in Pycharm with Control Shift R, or in the shell with python -mdoctest yourscript.py.

Answer 2

Validation

Generally, when programming challenges tell you about the limitations on the input, that information is meant to help you decide on an implementation strategy. For example, knowing that the word is at most 10 characters means that you can safely use recursion without worrying about stack overflow. These are promises that you don't need to validate.

Nevertheless, if you do perform validation, then you should adhere to some conventions:

• Print error messages to sys.stderr, so as not to contaminate sys.stdout.
• Exit with a non-zero status code to indicate failure.

Implementation

Your number_of_block_palindrome_groupings function looks pretty good. I'd just say that you should avoid superfluous parentheses in if conditions.

You could write it more succinctly using sum(), but it's not necessarily better than what you wrote.

def number_of_block_palindrome_groupings(string):
    return sum(1 + number_of_block_palindrome_groupings(string[i:-1])
               for i in range(1, len(string) // 2 + 1)
               if string[:i] == string[-i:])