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

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.

• Do you have a couple examples of Input you tested this on? Attempts such as 4 PORK and 8 DEADBEEF run without errors, but return 0 without printing. It does work for the sample run provided in the paper (4 CB returns 2), but a single test-case is quite limited for something like this. Writing a review would be easier with a bigger set of inputs to test on.
– Mast
Commented Dec 13, 2023 at 9:23
• @Mast there are a list of test-cases given in the mark scheme (here), if it helps. Commented Dec 13, 2023 at 15:28
• That does help, thank you. I'll add those to the question.
– Mast
Commented Dec 13, 2023 at 16:32
• @sbottingota This smells like a dynamic programming problem. Have you tried breaking it down into simpler cases and building a solution from there? Commented Dec 14, 2023 at 5:35

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)
1. 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)
1. 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.