编写函数行(a)，确定将销毁多少个球 [英] Write a function lines(a) that determines how many balls will be destroyed
问题描述
一些不同颜色的球成一条线.当形成连续的三个或更多相同颜色的球块时，将其从生产线上移除.在这种情况下，所有球都相互移动，并且这种情况可能会重复发生.
some balls of different colors in a line. When a continuous block of three or more balls of the same color is formed, it is removed from the line. In this case, all the balls are shifted to each other, and the situation may be repeated.
写一个函数行(a)，该函数行将确定要销毁多少个球.在初始时刻，最多可以有一个连续的块，由三个或更多个相同颜色的球组成.
Write a function lines(a) that determines how many balls will be destroyed. There can be at most one continuous block of three or more same-colored balls at the initial moment.
输入数据:
该函数采用初始球配置的列表a.球数小于或等于1000，球的颜色可以为0到9，每种颜色都有自己的整数.
The function takes a list a with initial balls disposition. Balls number is less or equals 1000, balls colors can be from 0 to 9, each color has its own integer.
输出数据:
该函数必须返回一个数字，即将要销毁的球的数量.
The function has to return one number, the number of the balls that will be destroyed.
Input:[2,2,1,1,1,2,1] Output:6
input : [0, 0, 0, 0, 0], output: 5
input:[2, 3, 1, 4], output: 0
我尝试使用两个指针的方法，但不确定如何执行.
I try to use the two pointer approach, but not sure how to do it.
def lines(a):
left = 0
right = len(a)-1
s=[]
while left < right :
if a[left] == a[left:right+1]:
s.extend(a[left: right+1])
del a[left: right+1]
else:
left += 1
right -= 1
return len(s)
test_a = [2, 2, 1, 1, 1, 2, 1]
print(lines(test_a))
我认为如果a [left] == a [left:right + 1]:不起作用，我尝试比较从左到右的元素与从右到左的元素相同.另外， del a [left:right + 1] 不起作用，我尝试删除那些已经扩展到新列表s的元素.
I think if a[left] == a[left:right+1]: did not work, i am try to compare elements from left to right is same as elements from right to left. Alsodel a[left: right+1] did not work, i try delete those elements which already extend to new list s.
感谢您的建议.
推荐答案
这是使用 lo 和 hi 指针遍历输入的迭代解决方案.
This is an iterative solution using a lo and hi pointer traversing the input.
请注意，通过附加一个结束标记来保证 not 作为输入颜色，这意味着逻辑检查颜色行程不需要在while循环外进行重复.
Note that by appending an end marker guaranteed not to be an input colour means that the logic checking for runs of colours does not need duplication outside the while loop.
代码
in_outs = [([2,2,1,1,1,2,1], 6),
([0, 0, 0, 0, 0], 5),
([2, 3, 1, 4], 0),
]
def test(f):
print(f"\nSTART Testing answer {f.__doc__}")
for arg, ans in in_outs:
try:
out = f(arg.copy())
except:
ans = '<Exception thrown!>'
if out != ans:
print(f" {f.__name__}({arg}) != {ans} # instead gives: {out}")
else:
print(f" {f.__name__}({arg}) == {out}")
print(f"STOP Testing answer {f.__doc__}\n")
#%% From me, Paddy3118
def lines(a):
"From Paddy3118"
a = a.copy() + [-1] # Add terminator
d = lo = hi = 0 # delete count, lo & hi pointers
lo_c = hi_c = a[0] # Colours at pointer positions
while hi +1 < len(a):
hi += 1; hi_c = a[hi]
if lo_c != hi_c:
if hi - lo > 2:
d += hi - lo
del a[lo: hi]
lo, hi, lo_c, hi_c = 0, 0, a[0], a[0]
else:
lo, lo_c = hi, hi_c
return d
test(lines)
输出
START Testing answer From Paddy3118
lines([2, 2, 1, 1, 1, 2, 1]) == 6
lines([0, 0, 0, 0, 0]) == 5
lines([2, 3, 1, 4]) == 0
STOP Testing answer From Paddy3118
检查其他示例
使用以下工具扩展上述内容以帮助测试
Extend the above with the following harnesses to aid testing
#%% IA from Ignacio Alorre
import itertools
def grouping_balls(balls):
return ["".join(g) for k, g in itertools.groupby(balls)]
def destroy_balls(list_balls, destroyed):
if len(list_balls) < 1:
return destroyed
balls_grp = grouping_balls(list_balls)
# No more balls to destroy
if max(map(len,balls_grp)) < 3:
return destroyed
# Destroying and merging balls
else:
non_dest_balls = ""
for l in balls_grp:
if len(l) < 3:
non_dest_balls += l
else:
destroyed += len(l)
return destroy_balls(non_dest_balls, destroyed)
def lines_IA(a):
"From Ignacio Alorre"
return destroy_balls(''.join(map(str, a)), 0)
test(lines_IA)
#%% AHX from Ahx
total_destroyed = 0
counter = 0
previous = -1
previous_index = -1
def _lines_ahx(a):
"""
Args:
a (list): input array
Returns:
(int): total number of destroyed balls.
"""
global total_destroyed
global counter
global previous
global previous_index
for i, element in enumerate(a):
if element == previous:
counter += 1
else:
counter = 1
previous = element
previous_index = i
if counter >= 3:
for _ in range(previous_index, i+1):
a.pop(previous_index)
total_destroyed += 1
_lines_ahx(a)
return total_destroyed
def lines_AHX(a):
"From Ahx"
global total_destroyed
global counter
global previous
global previous_index
total_destroyed = 0
counter = 0
previous = -1
previous_index = -1
return _lines_ahx(a)
test(lines_AHX)
完整输出
所有三个示例均在给定的testds上运行.由于测试非常小，因此没有给出时间.
All three examples work on the given testds. No timings are given as the tests are very small.
START Testing answer From Paddy3118
lines([2, 2, 1, 1, 1, 2, 1]) == 6
lines([0, 0, 0, 0, 0]) == 5
lines([2, 3, 1, 4]) == 0
STOP Testing answer From Paddy3118
START Testing answer From Ignacio Alorre
lines_IA([2, 2, 1, 1, 1, 2, 1]) == 6
lines_IA([0, 0, 0, 0, 0]) == 5
lines_IA([2, 3, 1, 4]) == 0
STOP Testing answer From Ignacio Alorre
START Testing answer From Ahx
lines_AHX([2, 2, 1, 1, 1, 2, 1]) == 6
lines_AHX([0, 0, 0, 0, 0]) == 5
lines_AHX([2, 3, 1, 4]) == 0
STOP Testing answer From Ahx
这篇关于编写函数行(a)，确定将销毁多少个球的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
