[FIXED] Given a number, find the sequence to reach it

Issue

I am working on this challenge:

A bot can do either of the 2 instructions:

• [F]orward: move ahead by +1 and double its speed
• [B]ack: Stop, change direction and reset its speed.

The initial speed is 1.

Given a distance, return a sequence that will satisfy it. The sequence can only have a maximum of 3 'B's. If a solution is not possible with 3 'B's then return empty string.

For example,

findSeq(2) -> FFBF (1+2-1)
findSeq(3) -> FF (1+2)
findSeq(4) -> FFFBFF (1+2+4 - (1+2))

Here is what I have so far:

def findSeq(dist):
    curr = 0
    seq = ""
    speed = 1
    mul = 1
    
    while (curr != dist):
        seq += 'F'
        curr += (speed*mul)
        speed *= 2
        
        if curr > dist and mul != -1:
            seq += 'B'
            mul = -1
            speed = 1

        elif curr < dist:
            mul = 1
        
        if curr == dist:
            return seq

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

This works for findSeq(2), findSeq(3) and findSeq(4). However, it starts breaking for findSeq(5) -> (it gives FFFBFFFBFF)

I'm not sure what I'm missing.

Solution

A couple of observations: A sequence of n F commands, moves the train 2^n - 1 in the current direction. Without loss of generality, all solutions are of the form F^k1 B F^k2 B F^k3 B F^k4, with k1, k2, k3, k4 >= 0 because if we don't to move the train, we can simply set some of the k's to 0.

This gives a restatement of the problem: given n, find non-negative k1, k2, k3, k4 such that (2^k1 - 1) - (2^k2 - 1) + (2^k3 - 1) - (2^k4 - 1) = n.

The 1's cancel in the sum, so you need to find 2^k1 + 2^k3 - 2^k2 - 2^k4 = n.

If n has N bits, then without loss of generality, each of the four numbers can be at most N+1.

I'm sure there's a cleverer approach, but just doing a search of the (N+2)^4 possibilities yields a O((log n)^4) solution.

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 suggests an O((logn)^2) improvement: enumerating all numbers of the form q = 2^k1 + 2^k3, and then seeing if q-n is of the same form.

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 ''

Answered By - Paul Hankin