Home > Software engineering >  Incremental duplicates
Incremental duplicates

Time:12-14

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] 
  • Related