Дано число, найдите последовательность, чтобы добраться до него

Проблема с вашим кодом была во втором повороте. Обратите внимание, что когда curr < dist вы меняете направление, но не сбрасываете скорость и не добавляете «B» к последовательности. Изменение

elif curr < dist:
    mul = 1

к

elif curr < dist and mul == -1:
    seq += 'B'
    mul = 1
    speed = 1

Должно решить вашу проблему. Кроме того, вы заявили, что путь может иметь не более 3 'B', поэтому вам нужно изменить

if seq.count('B') == 3 and curr != dist:
    return ''

к

if seq.count('B') == 4 and curr != dist:
    return ''

Алгоритм анализа

Небольшое представление о том, на какие расстояния может достигать эта функция (ограничено всего тремя поворотами). Когда dist можно записать как 2**n - 1 для любого целого числа больше 0, эта функция достигнет dist без каких-либо поворотов, и путь будет 'F' * n. Это потому, что двоичное представление 2**n - 1 представляет собой последовательность n '1'. Примеры:

1. 7 = 2**3-1 = 0b111 --> findSeq(0b111) = 'FFF'
2. 15 = 2**4-1 = 0b1111 --> findSeq(0b1111) = 'FFFF'
3. 31 = 2**5-1 = 0b11111 --> findSeq(0b11111) = 'FFFFF'

и т.д

Чтобы достичь числа 5, которое имеет двоичное представление 0b101, функция сделает следующее:

1. достичь 7
2. повернуться, вернуться к 4 (что является степенью 2, 4 = 0b100)
3. развернуться, перейти на 5

print(findSeq(5))  # 'FFFBFFBF'

Это означает, что ваш алгоритм работает следующим образом: начиная с самого старшего бита (MSB), который является самым левым битом, для любого изменения с 1 на 0 вам нужно будет использовать 1 ход, а для другого изменения с 0 на 1 вам нужно будет использовать еще один ход. Это происходит потому, что по правилам движения, изменения от 1 до 0 в двоичном представлении, функция сбрасывается до наибольшего числа, которое меньше dist и имеет двоичное представление из s последовательности единиц, за которыми следует последовательность нулей (например, 4 = 0b100 имеет 1 «1», за которым следует 2 «0»).

Это означает, что с помощью вашего алгоритма вы можете найти путь к очень большим числам, но для некоторых малых достижимых чисел путь не будет найден. Взяв очень большое число 895, представленное 0b1101111111. Вы можете видеть, что есть только одно изменение с «1» на «0» (биты 8 и 7, когда младший бит находится в ячейке 0), функция сможет найти путь:

1. достигнув 1023 (0b1111111111)
2. вернуться к 768 (0b1100000000), имеет 2 '1', за которыми следуют 8 '0'
3. перейти к 895 (0b1101111111)

print(findSeq(0b1101111111))  # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'
print(findSeq(895))  # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'

Изменение dist на 892 приведет к дополнительному ходу:

4. вернуться к 892 (0b1101111100)

print(findSeq(0b1101111100))  # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'
print(findSeq(892))  # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'

Но для относительно небольших чисел, таких как 21, которое представлено 0b10101, функция не найдет путь, хотя указан правильный путь («FFFFBFBFFF»):

1. Продвиньтесь на 4 шага до 15
2. Обернитесь, вернитесь на 1 шаг к 14
3. Снова повернитесь, сделайте 3 шага до 14 + 7 = 21.

Предложение решения

Это хороший пример задачи поиска по графу. В задаче поиска графа вам сначала нужно определить состояния. Состояния в этой задаче представляют собой кортежи, где каждый кортеж состоит из последовательности и текущего местоположения, то есть (seq, current_loc). После определения состояний любой алгоритм поиска по графу может решить вашу проблему, где двумя наиболее известными решениями будут BFS и DFS. Так как я хотел получить путь с кратчайшим количеством шагов, я реализовал BFS. Дополнительную информацию см. здесь.

Решение BFS выглядит следующим образом:

import math
import collections
def findSeq(dist):
    state_queue = collections.deque([])  # Pending states which have not been explored yet
    upper_lim   = 2**math.ceil(math.log2(dist))
    state = ['', 0]  # Starting state ; state is made out of the path at location [0], the 'B' count at location [1] and the distance at location [2]
    found = True
    while state[1] != dist:
        # adding states to the queue according to conditions:
        steps   = len(state[0].split('B')[-1])
        b_count = state[0].count('B')
        if 0 <= state[1] < upper_lim:  # advancing makes sense
            state_1 = [state[0] + 'F', state[1] + ((-1)**b_count) * 2**steps]
            state_queue.append(state_1)
        if b_count < 3 and state[1] >= 0:
            state_2 = [state[0] + 'B', state[1]]
            state_queue.append(state_2)
        try:
            state = state_queue.popleft()
        except IndexError:
            found = False
            break
    if found:
        return state[0]
    else:
        return ''

Обратите внимание, что это не оптимально, так как состояния в графе могут быть определены более эффективно, но это решение для всех случаев. Кроме того, граф можно представить в виде дерева, что означает, что вы не будете возвращаться к одному и тому же состоянию дважды (в текущем определении состояния), поэтому вам не нужно сохранять набор посещенных состояний.

Несколько замечаний: последовательность из n F команд перемещает поезд на 2 ^ n - 1 в текущем направлении. Без ограничения общности все решения имеют вид F^k1 B F^k2 B F^k3 B F^k4, где k1, k2, k3, k4 >= 0, потому что, если мы не будем двигать поезд, мы можем просто положить некоторые из k равны 0.

Это дает переформулировку задачи: для данного n найти неотрицательные k1, k2, k3, k4 такие, что (2^k1 - 1) - (2^k2 - 1) + (2^k3 - 1) - (2 ^к4 — 1) = п.

Единицы в сумме сокращаются, поэтому вам нужно найти 2 ^ k1 + 2 ^ k3 - 2 ^ k2 - 2 ^ k4 = n.

Если n имеет N битов, то без ограничения общности каждое из четырех чисел может быть не более чем N+1.

Я уверен, что есть более умный подход, но просто поиск (N + 2) ^ 4 возможностей дает решение O ((log n) ^ 4).

import itertools

def findSeq(n):
    N = max(1, n.bit_length())
    for k1, k2, k3, k4 in itertools.product(tuple(range(N+2)), repeat=4):
        if (1<<k1) - (1<<k2) + (1<<k3) - (1<<k4) == n:
            return 'B'.join('F' * x for x in (k1, k2, k3, k4))
    return ''

for i in range(100):
    print(i, findSeq(i))

@MattTimmermans предлагает улучшение O ((logn) ^ 2): перечисление всех чисел в форме q = 2 ^ k1 + 2 ^ k3, а затем проверка того, имеет ли qn ту же форму.

def findSeq2(n):
    N = max(1, n.bit_length())
    b2 = {(1<<k1)+(1<<k2): (k1, k2) for k1, k2 in itertools.product(tuple(range(N+2)), repeat=2)}
    for k1, k3 in b2.values():
        r = (1 << k1) + (1 << k3) - n
        if r in b2:
            k2, k4 = b2[r]
            return 'B'.join('F' * x for x in (k1, k2, k3, k4))      
    return ''

Я предлагаю алгоритм, который выводит решение прямо из заданного числа, без поиска.

Наблюдения

Как уже отмечали другие, это сводится к нахождению терминов в форме (2^a - 1) - (2^b - 1) + (2^c - 1) - (2^d - 1).

Кроме того, обратите внимание, что когда у вас есть решение, вы всегда можете добавить немного «B» в конце, что не изменит отображаемое расстояние. Таким образом, мы можем сказать, что нужны ровно 3 буквы «Б» и нужны все четыре термина (приведенные выше). Это также означает, что мы можем исключить -1 в каждом члене, так как они компенсируют друг друга.

Когда мы смотрим на двоичное представление этих терминов, у нас должно быть что-то вроде этого:

0b1000000 - 0b100 + 0b10000 - 0b10

... где количество конечных нулей в этих числах является переменным.

Играя с этими терминами, становится ясно, что невозможно сгенерировать значение, которое - в его двоичном представлении - имеет 4 группы смежных 1-цифр (или более). Например: 0b1010101 нельзя закодировать с помощью инструкций «F» и трех «B».

Случай 1: двоичное представление имеет одну группу 1-битов

Когда есть только одна соседняя группа 1-цифр, это легко.

Например, 0b11100 можно получить с помощью FFFFFBFF. Первая группа «F» — это до тех пор, пока есть цифры, а вторая группа «F» — до тех пор, пока есть конечные нули.

Случай 2: двоичное представление имеет две группы единичных битов.

Когда есть две группы 1-цифр, это тоже довольно просто:

Например, 0b11001110 можно получить с помощью FFFFFFFFBFFFFFFBFFFFBF. Обратите внимание, что каждая группа «F» короче предыдущей и представляет собой количество двоичных цифр, которые остаются, когда группа одинаковых цифр удаляется с левой стороны. Так:

• 11001110 переводится как 8xF,
• от 001110 до 6xF,
• 1110 до 4xF и
• от 0 до 1xF.

Случай 3: двоичное представление имеет три группы единичных битов.

Случай, когда есть три группы 1-цифр, является самым сложным. При более глубоком анализе оказывается, что по крайней мере одна разделяющая группа 0 (которая разделяет две группы единиц) должна иметь длину 1 (т. е. только один разделяющий ноль). Так, например, нет решения для 0b1001001, потому что обе группы нулей имеют размер 2. Во-вторых, оставшаяся группа цифр не смежный для этого единственного 0 также должна быть одинарной.

Итак: 0b1010011 тоже не имеет решения, потому что правая группа (которая не является смежной с одиночным заключенным 0) состоит из двух единиц. Но у 0b11011001 есть решение, потому что есть изолированный 0 (между единицами), а другая оставшаяся группа единиц тоже одна (справа).

Реализация

С этими правилами можно иметь быстрый алгоритм, поскольку он на самом деле не поиск для решения, а выводит из двоичного представления данного числа:

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.

Некоторый код драйвера:

# 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)

Первое натуральное число, для которого нет решения, — это 73, имеющее двоичное представление 0b1001001.