给定一个数字，找到到达它的序列
Given a number, find the sequence to reach it
我正在应对这个挑战：
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))
这是我目前的情况：
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
这适用于 findSeq(2)、findSeq(3) 和 findSeq(4)。但是，它开始中断 findSeq(5) -> (它给出 FFFBFFFBFF)
我不确定我错过了什么。
你的代码的问题是第二轮。请注意，当 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对于任何大于0的整数都可以写成2**n - 1时，这个函数会不经过任何转折就到达dist，路径就是'F' * n。这是因为 2**n - 1 的二进制表示是 n '1' 的序列。示例：
7 = 2**3-1 = 0b111 --> findSeq(0b111) = 'FFF'15 = 2**4-1 = 0b1111 --> findSeq(0b1111) = 'FFFF'31 = 2**5-1 = 0b11111 --> findSeq(0b11111) = 'FFFFF'
等等
要达到 5，它具有 0b101 的二进制表示，函数将执行以下操作：
- 达到 7
- 转过来，return到4（是2的幂，4=0b100）
- 转身，前进5
print(findSeq(5)) # 'FFFBFFBF'
这意味着您的算法的工作方式是从最高有效位 (MSB) 开始，即 leftmost-bit，对于从 1 到 0 的任何变化，您需要使用 1 圈，并且对于从 0 到 1 的另一个变化，您将需要使用另一个回合。发生这种情况是因为根据移动规则，二进制表示形式从 1 变为 0，函数重置为小于 dist 的最大数，并且具有 s 序列的二进制表示形式，其次是一系列零（例如 4 = 0b100 有 1 个“1”后跟 2 个“0”）。
这意味着使用您的算法您可以找到通往非常大的数字的路径，但对于一些可到达的小数字将找不到路径。以0b1101111111为代表的895这个非常大的数字。你可以看到从'1'到'0'只有一个变化（LSB在位置0时的位8和7），该函数将能够通过以下方式找到路径：
- 达到 1023 (
0b1111111111)
- return 到 768 (
0b1100000000)，有 2 个 '1' 后跟 8 个 '0'
- 前进到 895 (
0b1101111111)
print(findSeq(0b1101111111)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'
print(findSeq(895)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'
将 dist 更改为 892 将导致额外的回合：
- return 到 892 (
0b1101111100)
print(findSeq(0b1101111100)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'
print(findSeq(892)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'
但是对于相对较小的数字，例如由 0b10101 表示的 21，函数将找不到路径，尽管给出了有效路径 ('FFFFBFBFFF'):
- 前进 4 步到 15
- 转身，后退1步到14
- 再转个身，走3步14+7=21
解决建议
这是图搜索问题的一个很好的例子。在图形搜索问题中，您首先需要定义状态。这个问题中的状态是一个元组，其中每个元组由序列和当前位置组成，即 (seq, current_loc)。定义状态后，任何图形搜索算法都可以解决您的问题，其中两个最突出的解决方案是 BFS 和 DFS。因为我想用最短的步骤得到路径，所以我实现了 BFS。请查找更多信息 here。
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，找到 non-negative k1, k2, k3, k4 使得 (2^k1 - 1) - (2^k2 - 1) + (2^ k3 - 1) - (2^k4 - 1) = n.
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 的数字，然后查看 q-n 是否具有相同形式。
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 ''
我建议一种算法，该算法直接从给定的数字得出解决方案，无需搜索。
观察
正如其他人也指出的那样，这归结为查找形式为 (2a - 1) - (2b - 1) + (2c - 1) - (2d - 1).
此外，请注意，当您有解决方案时，您总是可以在末尾附加一些“B”，这不会改变表示的距离。所以我们可以说正好需要 3 个“B”字母，并且需要所有四个项（上面给出的）。这也意味着我们可以消除每一项中的 -1，因为它们相互抵消。
当我们查看这些项的二进制表示时，我们应该有这样的内容：
0b1000000 - 0b100 + 0b10000 - 0b10
...其中这些数字中尾随零的数量是可变的。
当使用这些术语时，很明显不可能生成一个值——在其二进制表示中——具有 4 组相邻的 1 位数字（或更多）。例如：0b1010101不能用“F”和三个“B”指令编码。
情况一：二进制表示有一组1位
当只有一组相邻的1位数字时，很容易。
例如0b11100可以用FFFFFBFF产生。第一组“F”只要有数字，第二组“F”只要有尾随零即可。
情况2：二进制表示有两组1位
当有两组1位时，也很容易：
例如0b11001110可以用FFFFFFFFBFFFFFFBFFFFBF产生。请注意每组“F”比前一组短，表示从左侧移除一组same-digits后剩余的二进制位数。所以：
- 11001110 转换为 8xF,
- 001110 到 6xF，
- 1110 至 4xF 和
- 0 到 1xF。
情况3：二进制表示有三组1位
有三组 1 位数字的情况是最复杂的一种情况。通过更深入地分析这一点，结果证明至少有一组 0（将两组 1 分开）的长度必须为 1（即只有一个分隔零）。因此，例如，0b1001001 没有解决方案，因为两组 0 的大小均为 2。其次，与此单个 0 不相邻 的剩余 1 位数字组也必须单身
所以：0b1010011也无解，因为right-side组（不与单个封闭的0相邻）有两个1。但是0b11011001有一个解决方案，因为有一个孤立的0（在1s之间），而剩下的另一组1s也是单个的（在右侧）。
实施
有了这些规则，就可以有一个快速的算法，因为它并不是真正地搜索解决方案，而是推导它来自给定数字的二进制表示：
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。
我正在应对这个挑战：
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))
这是我目前的情况：
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
这适用于 findSeq(2)、findSeq(3) 和 findSeq(4)。但是，它开始中断 findSeq(5) -> (它给出 FFFBFFFBFF)
我不确定我错过了什么。
你的代码的问题是第二轮。请注意，当 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对于任何大于0的整数都可以写成2**n - 1时，这个函数会不经过任何转折就到达dist，路径就是'F' * n。这是因为 2**n - 1 的二进制表示是 n '1' 的序列。示例：
7 = 2**3-1 = 0b111-->findSeq(0b111) = 'FFF'15 = 2**4-1 = 0b1111-->findSeq(0b1111) = 'FFFF'31 = 2**5-1 = 0b11111-->findSeq(0b11111) = 'FFFFF'
等等
要达到 5，它具有 0b101 的二进制表示，函数将执行以下操作：
- 达到 7
- 转过来，return到4（是2的幂，4=0b100）
- 转身，前进5
print(findSeq(5)) # 'FFFBFFBF'
这意味着您的算法的工作方式是从最高有效位 (MSB) 开始，即 leftmost-bit，对于从 1 到 0 的任何变化，您需要使用 1 圈，并且对于从 0 到 1 的另一个变化，您将需要使用另一个回合。发生这种情况是因为根据移动规则，二进制表示形式从 1 变为 0，函数重置为小于 dist 的最大数，并且具有 s 序列的二进制表示形式，其次是一系列零（例如 4 = 0b100 有 1 个“1”后跟 2 个“0”）。
这意味着使用您的算法您可以找到通往非常大的数字的路径，但对于一些可到达的小数字将找不到路径。以0b1101111111为代表的895这个非常大的数字。你可以看到从'1'到'0'只有一个变化（LSB在位置0时的位8和7），该函数将能够通过以下方式找到路径：
- 达到 1023 (
0b1111111111) - return 到 768 (
0b1100000000)，有 2 个 '1' 后跟 8 个 '0' - 前进到 895 (
0b1101111111)
print(findSeq(0b1101111111)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'
print(findSeq(895)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFF'
将 dist 更改为 892 将导致额外的回合：
- return 到 892 (
0b1101111100)
print(findSeq(0b1101111100)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'
print(findSeq(892)) # 'FFFFFFFFFFBFFFFFFFFBFFFFFFFBFF'
但是对于相对较小的数字，例如由 0b10101 表示的 21，函数将找不到路径，尽管给出了有效路径 ('FFFFBFBFFF'):
- 前进 4 步到 15
- 转身，后退1步到14
- 再转个身，走3步14+7=21
解决建议
这是图搜索问题的一个很好的例子。在图形搜索问题中，您首先需要定义状态。这个问题中的状态是一个元组，其中每个元组由序列和当前位置组成，即 (seq, current_loc)。定义状态后，任何图形搜索算法都可以解决您的问题，其中两个最突出的解决方案是 BFS 和 DFS。因为我想用最短的步骤得到路径，所以我实现了 BFS。请查找更多信息 here。
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，找到 non-negative k1, k2, k3, k4 使得 (2^k1 - 1) - (2^k2 - 1) + (2^ k3 - 1) - (2^k4 - 1) = n.
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 的数字，然后查看 q-n 是否具有相同形式。
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 ''
我建议一种算法，该算法直接从给定的数字得出解决方案，无需搜索。
观察
正如其他人也指出的那样，这归结为查找形式为 (2a - 1) - (2b - 1) + (2c - 1) - (2d - 1).
此外，请注意，当您有解决方案时，您总是可以在末尾附加一些“B”，这不会改变表示的距离。所以我们可以说正好需要 3 个“B”字母，并且需要所有四个项（上面给出的）。这也意味着我们可以消除每一项中的 -1，因为它们相互抵消。
当我们查看这些项的二进制表示时，我们应该有这样的内容：
0b1000000 - 0b100 + 0b10000 - 0b10
...其中这些数字中尾随零的数量是可变的。
当使用这些术语时，很明显不可能生成一个值——在其二进制表示中——具有 4 组相邻的 1 位数字（或更多）。例如：0b1010101不能用“F”和三个“B”指令编码。
情况一：二进制表示有一组1位
当只有一组相邻的1位数字时，很容易。
例如0b11100可以用FFFFFBFF产生。第一组“F”只要有数字，第二组“F”只要有尾随零即可。
情况2：二进制表示有两组1位
当有两组1位时，也很容易：
例如0b11001110可以用FFFFFFFFBFFFFFFBFFFFBF产生。请注意每组“F”比前一组短，表示从左侧移除一组same-digits后剩余的二进制位数。所以：
- 11001110 转换为 8xF,
- 001110 到 6xF，
- 1110 至 4xF 和
- 0 到 1xF。
情况3：二进制表示有三组1位
有三组 1 位数字的情况是最复杂的一种情况。通过更深入地分析这一点，结果证明至少有一组 0（将两组 1 分开）的长度必须为 1（即只有一个分隔零）。因此，例如，0b1001001 没有解决方案，因为两组 0 的大小均为 2。其次，与此单个 0 不相邻 的剩余 1 位数字组也必须单身
所以：0b1010011也无解，因为right-side组（不与单个封闭的0相邻）有两个1。但是0b11011001有一个解决方案，因为有一个孤立的0（在1s之间），而剩下的另一组1s也是单个的（在右侧）。
实施
有了这些规则，就可以有一个快速的算法，因为它并不是真正地搜索解决方案，而是推导它来自给定数字的二进制表示：
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。