I've list of integers, which the list is circular. I want to find consecutive duplicates, instead of them place duplicate number 1 to the start position. Also need to do this until there are no consecutive duplicates in the list or list is empty. I tried while loops with different forms but couldn't reach my goal. Tried cycling with itertools.cycle
, cause -1 and 0 are also consecutive, but couldn't remove or insert. Also finding out when to stop is problem, tried int_list == list(set(int_list))
but there might some non-consecutive duplicates, so that create a infinite loop. Here is an example:
int_list = [1,1,1,2,3,4,5,6,7,7,8,8,9,10,8,11,4,12,15,13,14,14,15,16,1]
processed_list = [11,8,11,4,12,15,13,17]
Edit:
The original problems is in this Codewars kata.
CodePudding user response:
The deque
is close to a circular list, because it allows to rotate the list. I took advantage of that in the code below.
The algorithm compares the item[0]
with the next item item[1]
and also the previous item (in circular sense) item[-1]
discarding all dups and incrementing the original item[0]
if any dups were found.
If there was no duplicate found, the list is rotated and the process is repeated with the new item[0]
.
The process stops if there was a full length list rotation without finding a dup.
# Version 2
from collections import deque
def process(inp):
circ = deque(inp)
rcnt = 0 # rotations without finding a dup
while rcnt < len(circ):
try:
n = circ[0]
isdup = False
while circ and circ[1] == n:
isdup = True
circ.popleft()
while circ and circ[-1] == n:
isdup = True
circ.pop()
except IndexError:
break
finally:
if isdup:
circ[0] = n 1
rcnt = 0
else:
circ.rotate( 1)
rcnt = 1
print(list(circ)) # uncomment to watch the progress
return list(circ)
test = [1,1,1,2,3,4,5,6,7,7,8,8,9,10,8,11,4,12,15,13,14,14,15,16,1]
print(process(test))
With uncommented debug print
:
[2, 2, 3, 4, 5, 6, 7, 7, 8, 8, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[3, 3, 4, 5, 6, 7, 7, 8, 8, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[4, 4, 5, 6, 7, 7, 8, 8, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[5, 5, 6, 7, 7, 8, 8, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[6, 6, 7, 7, 8, 8, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[7, 7, 7, 8, 8, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[8, 8, 8, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[9, 9, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[10, 10, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[11, 8, 11, 4, 12, 15, 13, 14, 14, 15, 16]
[16, 11, 8, 11, 4, 12, 15, 13, 14, 14, 15]
[15, 16, 11, 8, 11, 4, 12, 15, 13, 14, 14]
[14, 15, 16, 11, 8, 11, 4, 12, 15, 13, 14]
[15, 15, 16, 11, 8, 11, 4, 12, 15, 13]
[16, 16, 11, 8, 11, 4, 12, 15, 13]
[17, 11, 8, 11, 4, 12, 15, 13]
[13, 17, 11, 8, 11, 4, 12, 15]
[15, 13, 17, 11, 8, 11, 4, 12]
[12, 15, 13, 17, 11, 8, 11, 4]
[4, 12, 15, 13, 17, 11, 8, 11]
[11, 4, 12, 15, 13, 17, 11, 8]
[8, 11, 4, 12, 15, 13, 17, 11]
[11, 8, 11, 4, 12, 15, 13, 17]
[17, 11, 8, 11, 4, 12, 15, 13]
[13, 17, 11, 8, 11, 4, 12, 15]
the last line is the result:
[13, 17, 11, 8, 11, 4, 12, 15]