Write A Function Lines(a) That Determines How Many Balls Will Be Destroyed
Solution 1:
This is an iterative solution using a lo and hi pointer traversing the input.
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.
The code
in_outs = [([2,2,1,1,1,2,1], 6),
([0, 0, 0, 0, 0], 5),
([2, 3, 1, 4], 0),
]
deftest(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, Paddy3118deflines(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 positionswhile 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)
Output
START Testing answer From Paddy3118
lines([2, 2, 1, 1, 1, 2, 1]) == 6lines([0, 0, 0, 0, 0]) == 5lines([2, 3, 1, 4]) == 0
STOP Testing answer From Paddy3118
Checking other examples
Extend the above with the following harnesses to aid testing
#%% IA from Ignacio Alorreimport itertools
defgrouping_balls(balls):
return ["".join(g) for k, g in itertools.groupby(balls)]
defdestroy_balls(list_balls, destroyed):
iflen(list_balls) < 1:
return destroyed
balls_grp = grouping_balls(list_balls)
# No more balls to destroyifmax(map(len,balls_grp)) < 3:
return destroyed
# Destroying and merging ballselse:
non_dest_balls = ""for l in balls_grp:
iflen(l) < 3:
non_dest_balls += l
else:
destroyed += len(l)
return destroy_balls(non_dest_balls, destroyed)
deflines_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 = -1def_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 inenumerate(a):
if element == previous:
counter += 1else:
counter = 1
previous = element
previous_index = i
if counter >= 3:
for _ inrange(previous_index, i+1):
a.pop(previous_index)
total_destroyed += 1
_lines_ahx(a)
return total_destroyed
deflines_AHX(a):
"From Ahx"global total_destroyed
global counter
global previous
global previous_index
total_destroyed = 0
counter = 0
previous = -1
previous_index = -1return _lines_ahx(a)
test(lines_AHX)
Full Output
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
Solution 2:
You can use a stack for this (simple list implementation). Check if the last 3 balls are of the same kind. If they are, then keep popping all balls of the same kind. Else, add the ball to the stack and continue. Each ball can be added once and removed once to the list, so the complexity should be O(N) as well. At the end, number of balls destroyed = count of original balls - length of stack.
Solution 3:
We need to count the number of occurrences in the input list.
If the current ball color (element) is equals to the previous ball color (previous), then increase the counter by one.
for i, element inenumerate(a):
if element == previous:
counter += 1If they are not equal, then there will be a possibility the next color may repeat more than three. Therefore store the current colors' index
for i, element inenumerate(a):
if element == previous:
counter += 1else:
counter = 1
previous = element
previous_index = i
Now check if the color is repeated more than three times.
If it does we need to remove the balls from the list.
While removing we also need to count the number of destroyed balls.
if counter >= 3:
for _ inrange(previous_index, i+1):
a.pop(previous_index)
total_destroyed += 1There might be a confusion, why I did a.pop(previous_index)?
If you debug this part of code on an example. For instance: [2, 2, 1, 1, 1, 2, 1]
When i== 4, the current list is [2, 2, 1, 1, 1] which satisfies the count >= 3
- Iteration = 1, the list will become
[2, 2, 1, 1]
If you say remove the next element, which will pop the final element
- Iteration = 2, the list will become
[2, 2, 1]
Now, on Iteration 3, which element will be pop? index-out-of-bound.
- Iteration = 3, the list won't change
[2, 2, 1]
Therefore, during the iteration always pop the current element. Since the next element will be the current one.
Now we need to call the method again, to see if there is any balls left
if counter >= 3:
for _ inrange(previous_index, i+1):
a.pop(previous_index)
total_destroyed += 1
lines(a)
But, we have to be careful since we have declared previous, previous_index, counter and totally_destroyed as a local variable.
If we keep them as a local attributes, all variables will be re-iniitalized so the alogrithm result won't be true.
Therefore we have to initialize them as a global variable and return the total number of destroyed balls.
Code:
total_destroyed = 0
counter = 0
previous = -1
previous_index = -1deflines(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 inenumerate(a):
if element == previous:
counter += 1else:
counter = 1
previous = element
previous_index = i
if counter >= 3:
for _ inrange(previous_index, i+1):
a.pop(previous_index)
total_destroyed += 1
lines(a)
return total_destroyed
test_a = [2, 2, 1, 1, 1, 2, 1]
test_b = [0, 0, 0, 0, 0]
test_c = [2, 3, 1, 4]
print(lines(test_a))
total_destroyed = 0
counter = 0
previous = -1
previous_index = -1print(lines(test_b))
total_destroyed = 0
counter = 0
previous = -1
previous_index = -1print(lines(test_c))
Results:
6
5
0
Solution 4:
My solution has two parts. One method to group by balls by their number grouping_balls. Then a recursive method first check there are still groups bigger than 3, if so destroy them and merge the rest for the next iteration destroy_balls.
import itertools
# Split balls by type# For 2211121 you would get: ["22", "111", "2", "1"]defgrouping_balls(balls):
return ["".join(g) for k, g in itertools.groupby(balls)]
# Keeps destroying balls as long as there are groups of 3 or moredefdestroy_balls(list_balls, destroyed):
iflen(list_balls) < 1:
return destroyed
balls_grp = grouping_balls(list_balls)
# No more balls to destroyifmax(map(len,balls_grp)) < 3:
return destroyed
# Destroying and merging ballselse:
non_dest_balls = ""for l in balls_grp:
iflen(l) < 3:
non_dest_balls += l
else:
destroyed += len(l)
return destroy_balls(non_dest_balls, destroyed)
Input = [0,0,0,0,0]
destroy_balls(''.join(map(str,Input)), 0)
Solution 5:
I thought of another algorithm that first does a run-length encoding of the whole input before using a single pointer traversing the list and deleting stuff. It works a lot better on larger input.
To test it I wrote a routine downto_zero that generates sequences of ones and zeroes which are all deleted, eventually.
I follow up by doing a timed run of all the examples.
Note: run in Ipython shell of Spyder IDE for timings.
Note: the example for Ahx makes great use of recursion and fails with an input of length 12, let alone 7500.
RLE code and Test Generator
#%% Test Generator for long tests
in_outs = [([2,2,1,1,1,2,1], 6),
([0, 0, 0, 0, 0], 5),
([2, 3, 1, 4], 0),
]
import sys
deftest(f, in_outs=in_outs):
print(f"\nSTART Testing answer {f.__doc__}")
for arg, ans in in_outs:
arg_txt = arg iflen(arg) <= 8elsef"[<{len(arg)} terms>]"try:
out = f(arg.copy())
except:
out = f'<Exception thrown! {sys.exc_info()[0]}>'if out != ans:
print(f" {f.__name__}({arg_txt}) != {ans} # instead gives: {out}")
else:
print(f" {f.__name__}({arg_txt}) == {out}")
print(f"STOP Testing answer {f.__doc__}\n")
defdownto_zero(n=3):
"Test generator that reduces all input"if n == 0:
return []
x = ([0, 1] * ((n+1)//2))[:n] # 0,1 ... of length n
e = x[-1] # end item
ne = 0if e == 1else1# not end item
r = ([e, e, ne, ne] * n)[:2*n]
return x + r
#%% RLE Runlengh encoded from me, Paddyfrom itertools import groupby
deflines_RLE(a):
"From Paddy3118 using run-length encoding"
a = a.copy() + [-1] # Add terminator
a = [[key, len(list(group))] for key, group in groupby(a)] # RLE
d = pt = 0# delete count, pointerwhile pt +1 < len(a):
i0, n0 = a[pt] # item, count at ptif n0 > 2:
d += n0
del a[pt]
if pt > 0:
if a[pt - 1][0] == a[pt][0]: # consolidate
a[pt - 1][1] += a[pt][1]
del a[pt]
pt -= 1continueelse:
pt += 1return d
test(lines_RLE, in_outs)
#%% Timed testingprint("TIMED TESTING\n=============")
n = 2_500for f in (lines, lines_RLE, lines_IA, lines_AHX):
dn = downto_zero(n)
%time test(f, [(dn, len(dn))])
Output with timings
START Testing answer From Paddy3118 using run-length encoding
lines_RLE([2, 2, 1, 1, 1, 2, 1]) ==6
lines_RLE([0, 0, 0, 0, 0]) ==5
lines_RLE([2, 3, 1, 4]) ==0
STOP Testing answer From Paddy3118 using run-length encoding
TIMED TESTING
=============START Testing answer From Paddy3118
lines([<7500 terms>]) ==7500
STOP Testing answer From Paddy3118
Wall time: 2.44 s
START Testing answer From Paddy3118 using run-length encoding
lines_RLE([<7500 terms>]) ==7500
STOP Testing answer From Paddy3118 using run-length encoding
Wall time: 19 ms
START Testing answer From Ignacio Alorre
lines_IA([<7500 terms>]) ==7500
STOP Testing answer From Ignacio Alorre
Wall time: 10.9 s
START Testing answer From Ahx
lines_AHX([<7500 terms>]) !=7500 # instead gives: <Exception thrown!<class 'RecursionError'>>
STOP Testing answer From Ahx
Wall time: 16 ms
Post a Comment for "Write A Function Lines(a) That Determines How Many Balls Will Be Destroyed"