此代碼應該采用一串 r（紅色）、b（藍色）和 y（黃色）值并將它們成對組合以找到一種結果顏色。例如，'rybbry' -> 'brbyb' -> 'yyrr' -> 'ybr' -> 'ry' -> 'b'。它適用于小輸入，但永遠適用于大輸入。嵌套回圈太多？
def colour_trio(colours):
while len(colours) > 1:
new_colours = ''
for i in range(len(colours) - 1):
if colours[i:i 2] == 'rr' or colours[i:i 2] == 'by' or colours[i:i 2] == 'yb':
new_colours = new_colours 'r'
elif colours[i:i 2] == 'bb' or colours[i:i 2] == 'ry' or colours[i:i 2] == 'yr':
new_colours = new_colours 'b'
else:
new_colours = new_colours 'y'
colours = new_colours
if len(colours) == 1:
if colours[0] == 'b':
return 'b'
if colours[0] == 'y':
return 'y'
if colours[0] == 'r':
return 'r'
這個也試過了。仍然運行時間太長。
def colour_trio(colours):
colours = list(colours)
length = len(colours)
for i in range(length-1):
for k in range(length - 1 - i):
colours[k] = color_sum(colours[k:k 2])
return colours[0]
def color_sum(pair):
if pair[0] == pair[1]:
return pair[0]
if 'r' in pair:
if 'b' in pair:
return 'y'
return 'b'
return 'r'
下面是測驗器檔案的樣子：
def colour_trio_generator(seed):
rng = random.Random(seed)
items = ''
for n in islice(pyramid(3, 4, 1), 10000):
items = rng.choice('ryb')
yield items
if len(items) == n:
items = rng.choice('ryb')
uj5u.com熱心網友回復：
您的代碼使用重復的字串連接。字串上的每個加法操作都需要O(n)時間，因為字串是不可變的。此操作會發生O(n^2)多次，因此您的演算法的運行時間是O(n^3)，其中n是字串的長度。
一種優化是使用串列來存盤字母，然后呼叫' '.join()，將運行時從O(n^3)到O(n^2)：
def colour_trio(colours):
result = colours
while len(result) != 1:
letters = []
for fst, snd in zip(result, result[1:]):
if fst == snd:
letters.append(fst)
else:
[letter_to_add] = list(set('ryb') - set(fst) - set(snd))
letters.append(letter_to_add)
result = ''.join(letters)
return result
print(colour_trio("rybbry")) # Prints "b"
uj5u.com熱心網友回復：
我認為這比我發布的最后一個解決方案更快，也比其他解決方案更快，我認為類使一切看起來都井井有條，但是您可以將其重新加工成一個單一的功能。
PS。感謝您的反饋@KellyBundy！現在演算法是正確的，它需要更少的字符！
新解決方案
colors = ['r', 'b', 'y']
def split(x):
return [f'{Couple(i)}' for i in [f'{x[i]}{x[i 1]}' for i in range(len(x)-1)]]
class Couple:
def __init__(self, x) -> None:
self.a = x[0]
self.b = x[1]
def __repr__(self) -> str:
if self.a == self.b:
return self.a
return (set(colors).difference(set((self.a, self.b))).pop())
def ColoursTrio(x):
while len(x) > 1:
x = split(x)
return x[0]
print(ColoursTrio('bbr'))
甚至更短（更快）：
def ColoursTrio(x):
while len(x) > 1:
x = [f'''{i[0] if i[0] == i[1]
else set("rby").difference(set((i[0],
i[1]))).pop()}''' for i in [f'{x[i]}{x[i 1]}'
for i in range(len(x)-1)]]
return x[0]
print(ColoursTrio('bbr'))
舊解決方案
這幾乎有點令人費解，但我認為它更快，我也認為它與@BrokenBenchmark 發布的非常相似（我認為他的更好）所以我也會添加他的示例字串！
COLORS = ['r','b','y']
class ColorsCouple:
def __init__(self, x:str, y:str) -> None:
self.x = x
self.y = y
def mix(self):
if self.x == self.y:
return f'{self.x}'
if 'y' in (self.x, self.y):
return set(COLORS).difference((self.x, self.y)).pop()
return 'y'
class Colors:
def __init__(self, colors:str) -> None:
self.colors = self.get_couples([*colors])
def get_couples(self, element):
return [(element[i],element[i 1]) for i in range(len(element)-1)]
def get_color(self):
colors = [ColorsCouple(*couples).mix() if len(couples)==2 else couples[0] for couples in self.colors]
while len(colors)>1:
colors = self.get_couples(colors)
colors = [ColorsCouple(*couples).mix() if len(couples)==2 else couples[0] for couples in colors]
return colors[0]
def __repr__(self) -> str:
return f'{self.get_color()}'
print(Colors('bbr'))
print(Colors('rybbry'))
uj5u.com熱心網友回復：
另一種解決方案，首先是一些基準測驗結果，隨機字串為 70 到 560 個字母（我認為 140 是實際測驗中的最大值）：
n= 70 n=140 n=280 n=560
0.03 0.06 0.11 0.24 Kelly_linear (I might show this one later)
0.47 1.71 6.58 25.85 Kelly (this is the one I am already showing)
0.77 3.17 12.50 52.57 Jacopo_2
1.59 6.38 25.62 107.81 Jacopo_1
1.69 7.09 27.93 110.67 Fabio
1.82 7.69 30.17 120.77 BrokenBenchmark
我的解決方案是Kelly下面的功能。首先，我將每個字母加倍，然后修剪第一個和最后一個字母。就這樣rybbry變成了ryybbbbrry。從本質上講，這給了我所有的配對，如果您認為其中有空格，那么它將是ry yb bb br ry. 然后我用那對應該變成的字母替換成對的不同字母，但是是大寫的。所以我明白了BRbbYB。然后用該對將變為的替換相同BRBYB的字母對： 。然后回到小寫。重復直到完成。
完整的基準代碼（在線試用！）：
def Kelly(colours):
while len(colours) != 1:
colours = (colours
.replace('b', 'bb')
.replace('r', 'rr')
.replace('y', 'yy')
[1:-1]
.replace('br', 'Y').replace('rb', 'Y')
.replace('by', 'R').replace('yb', 'R')
.replace('ry', 'B').replace('yr', 'B')
.replace('bb', 'B')
.replace('rr', 'R')
.replace('yy', 'Y')
.lower())
return colours
def Jacopo_1(colours):
while len(colours) > 1:
new_colours = ''
for i in range(len(colours) - 1):
if colours[i:i 2] == 'rr' or colours[i:i 2] == 'by' or colours[i:i 2] == 'yb':
new_colours = new_colours 'r'
elif colours[i:i 2] == 'bb' or colours[i:i 2] == 'ry' or colours[i:i 2] == 'yr':
new_colours = new_colours 'b'
else:
new_colours = new_colours 'y'
colours = new_colours
if len(colours) == 1:
if colours[0] == 'b':
return 'b'
if colours[0] == 'y':
return 'y'
if colours[0] == 'r':
return 'r'
def Jacopo_2(colours):
colours = list(colours)
length = len(colours)
for i in range(length-1):
for k in range(length - 1 - i):
colours[k] = color_sum(colours[k:k 2])
return colours[0]
def color_sum(pair):
if pair[0] == pair[1]:
return pair[0]
if 'r' in pair:
if 'b' in pair:
return 'y'
return 'b'
return 'r'
def BrokenBenchmark(colours):
result = colours
while len(result) != 1:
letters = []
for fst, snd in zip(result, result[1:]):
if fst == snd:
letters.append(fst)
else:
[letter_to_add] = list(set('ryb') - set(fst) - set(snd))
letters.append(letter_to_add)
result = ''.join(letters)
return result
def Fabio(x):
while len(x) > 1:
x = [f'''{i[0] if i[0] == i[1]
else set("rby").difference(set((i[0],
i[1]))).pop()}''' for i in [f'{x[i]}{x[i 1]}'
for i in range(len(x)-1)]]
return x[0]
lengths = 70, 140, 280, 560
funcs = [
Kelly,
Jacopo_2,
Jacopo_1,
Fabio,
BrokenBenchmark,
]
from timeit import default_timer as timer, repeat
import random
Tss = [[] for _ in funcs]
for length in lengths:
tss = [[] for _ in funcs]
for _ in range(5):
colours = ''.join(random.choices('bry', k=length))
def run():
global result
result = func(colours)
expect = None
for func, ts in zip(funcs, tss):
t = min(repeat(run, number=1))
if expect is None:
expect = result
assert result == expect
ts.append(t)
# print(*('%7.3f ms ' % (t * 1e3) for t in sorted(ts)[:3]), func.__name__)
# print()
print(*(f' n={length:3} ' for length in lengths))
for func, Ts, ts in zip(funcs, Tss, tss):
Ts.append(min(ts))
print(*('%6.2f ' % (t * 1e3) for t in Ts), func.__name__)
print()
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/459275.html