I suggest an algorithm that derives the solution directly from the given number, without a search.
Observations
As others have also noted this comes down to finding terms of the form (2a - 1) - (2b - 1) + (2c - 1) - (2d - 1).
Also, observe that when you have a solution, you can always append some "B" at the end, which do not change the represented distance. So we can say that exactly 3 "B" letters are needed, and all four terms (given above) are needed. This also means we can eliminate the -1 in each term, as they cancel each other.
When we look at the binary representation of those terms, we should have something like this:
0b1000000 - 0b100 + 0b10000 - 0b10
...where the number of trailing zeroes in those numbers is variable.
When playing with those terms it becomes clear that it is not possible to generate a value that -- in its binary representation -- has 4 groups of adjacent 1-digits (or more). For example: 0b1010101 cannot be encoded with "F" and three "B" instructions.
Case 1: the binary representation has one group of 1-bits
When there is only one adjacent group of 1-digits, it is easy.
For instance 0b11100 can be produced with FFFFFBFF. The first group of "F" is as long as there are digits, and the second group of "F" is as long as there are trailing zeroes.
Case 2: the binary representation has two groups of 1-bits
When there are two groups of 1-digits, it is also quite easy:
For instance 0b11001110 can be produced with FFFFFFFFBFFFFFFBFFFFBF. Note how each group of "F" is shorter than the previous one, and represents the number of binary digits that remain when a group of same-digits is removed from the left side. So:
- 11001110 translates to 8xF,
- 001110 to 6xF,
- 1110 to 4xF and
- 0 to 1xF.
Case 3: the binary representation has three groups of 1-bits
The case where there are three groups of 1-digits, is the most complex one. By analysing this in more depth it turns out that at least one separating group of 0 (that splits two groups of 1s) must have a length of 1 (i.e. just one separating zero). So for instance, there is no solution for 0b1001001, because both groups of 0s have size 2. Secondly, the remaining group of 1-digits that is not adjacent to this single 0, must also be single.
So: 0b1010011 has no solution either, because the right-side group (which is not adjacent to the single enclosed 0) has two 1s. But 0b11011001 has a solution, because there is an isolated 0 (between 1s) and the other remaining group of 1s is single too (at the right side).
Implementation
With these rules, it is possible to have a fast algorithm, as it does not really search for a solution, but derives it from the given number's binary representation:
import re
def encode(position):
binary = bin(position)[2:]
# Split in sizes of same digits. First group will consist of 1s
sizes = list(map(len, re.findall(r"1+|0+", binary)))
if len(sizes) > 6:
return "" # Not possible
# Create sequences of F, corresponding
# to the number of binary digits that follow
digits = ["F" * sizes[-1]]
for size in reversed(sizes[:-1]):
digits.append(digits[-1] + "F" * size)
digits.reverse()
# Simple cases:
if len(sizes) <= 4:
return "B".join(digits)
# The case where there are 3 groups of 1s in the binary representation:
digits.append("") # Make sure that digits[5] is defined
if sizes[0] == 1 and sizes[3] == 1: # The isolated single zero is at group 3
return "B".join((digits[1], digits[4], digits[2], digits[5]))
if sizes[4] == 1 and sizes[1] == 1: # The isolated single zero is at group 1
return "B".join((digits[0], digits[2], digits[5], digits[3]))
return "" # Not possible.
Some driver code:
# Helper function to verify a solution
def decode(code):
# Naive implementation according to rules
position = 0
direction = 1
speed = 1
for ch in code:
if ch == "B":
direction = -direction
speed = 1
else:
position += speed * direction
speed *= 2
return position
for i in range(1, 73):
code = encode(i)
decoded = decode(code)
print(i, code, decoded)
The first natural number for which there is no solution, is 73, which has binary representation 0b1001001.
