Finding the number of "block chains" that are a certain length and begin with a certain string

Question

I'm currently practicing for the british informatics olympiad by doing past papers.

I was doing question 3 of the 2019 paper:

A set of children’s blocks, each illustrated with a single different letter, have been chained together in a line. They have been arranged so that it is not possible to find three (not necessarily adjacent) letters,from left to right, that are in alphabetical order.

Write a program that enumerates block-chains. Your program should input a single integer l (1 ≤ l ≤ 19) indicating that the blocks are illustrated with the first l letters of the alphabet, followed by a word p of between 1 and l uppercase letters indicating (in order) the leftmost letters of the block chain. p will only contain letters take from the first l letters of the alphabet and will not contain any duplicates. You should output a single integer giving the number of possible block-chains that begin with p.

I wrote this code for the question:

from itertools import permutations
from string import ascii_uppercase


def has_alphabetical_substring(s):
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if ascii_uppercase.index(s[i]) > ascii_uppercase.index(s[j]):
                continue

            for k in range(j + 1, len(s)):
                if ascii_uppercase.index(s[j]) <= ascii_uppercase.index(s[k]):
                    return True

    return False


def find_legal_block_chains(l, p):
    combinations = list(permutations(ascii_uppercase[:l], l))
    combinations = [combination for combination in combinations if all(combination[i] == p[i] for i in range(len(p)))]
    combinations = [combination for combination in combinations if not has_alphabetical_substring(combination)]

    return combinations


l, p = input().split()

print(len(find_legal_block_chains(int(l), p.upper())))

For example, if I input 4 CB, it prints 2. More tests which are required to pass can be found on the relevant marks page.

I have tested it against the test cases in the run scheme, and it works, but it's slow and inefficient.
I would be grateful to know any improvements that I could make to this program.

Answer 1

Some changes that make your approach a bit better:

1. You do not need the intermediate list of all possible combinations, you throw most of them away again anyway. You can use generator expressions instead, conserving huge amounts of memory:

def find_legal_block_chains(l, p):
    combinations = permutations(ascii_uppercase[:l], l)
    combinations = (
        combination
        for combination in combinations
        if all(combination[i] == p[i] for i in range(len(p)))
    )
    combinations = (
        combination
        for combination in combinations
        if not has_alphabetical_substring(combination)
    )

    return list(combinations)

2. The prefix is fixed. So there is no need to generate all length l possible block-chains only to throw away all of those which do not start with the prefix. Instead, add the prefix later. Also, you can special case len(p) == l:

def find_legal_block_chains(l, p):
    if len(p) == l:
        return [(p,)]
    combinations = permutations(set(ascii_uppercase[:l]) - set(p), l - len(p))
    combinations = (
        tuple(p) + combination
        for combination in combinations
        if not has_alphabetical_substring(tuple(p) + combination)
    )

    return list(combinations)

3. Avoid making repeated lookups in string.ascii_uppercase, instead pre-compute a lookup table. Also, iterate over the characters instead of always using indexing:

ASCII_TO_INDEX = {c: i for i, c in enumerate(ascii_uppercase)}

def has_alphabetical_substring(s):
    for i, c1 in enumerate(s):
        for j, c2 in enumerate(s[i + 1:], i + 1):
            if ASCII_TO_INDEX[c1] > ASCII_TO_INDEX[c2]:
                continue

            for c3 in s[j + 1:]:
                if ASCII_TO_INDEX[c2] <= ASCII_TO_INDEX[c3]:
                    return True

While this does speed up the runtime quite a bit, this is most notable if the prefix is longer.

Runtimes on my machine for the first ten testcases:

• OP: 107 ms ± 1.34 ms
• generators: 108 ms ± 508 µs
• prefix: 23.5 ms ± 170 µs
• lookup table: 8.57 ms ± 41.2 µs

And for the tenth test case ("12 LKJI", 1430):

• OP: OutOfMemoryError
• generator: > 1 min
• prefix: 448 ms ± 4.76 ms
• lookup table: 137 ms ± 1.08 ms

---

All test cases, for reference:

test = [
    ("1 A", 1),
    ("2 AB", 1),
    ("2 BA", 1),
    ("4 C", 5),
    ("4 AB", 0),
    ("6 FED", 5),
    ("8 HGFEDCBA", 1),
    ("8 H", 429),
    ("8 FED", 28),
    ("8 FEH", 42),
    ("12 LKJI", 1430),
    ("13 MH", 13260),
    ("14 N", 742900),
    ("16 KHF", 5508),
    ("16 FEDCBA", 1),
    ("18 FRN", 0),
    ("18 QPON", 2674440),
    ("18 R", 129644790)
]

---

The real solution to this problem is probably not found by optimizing this approach further, but by using combinatorics. E.g. there are \$l!\$ possible ways to arrange \$l\$ distinct letters, from which you then have to somehow subtract the illegal combinations.

A possible approach is to start asking yourself how many possibilities there are in the case where only one letter is not covered by the prefix and try to expand it from there.