Remove triplets of adjacent numbers from the list

user_11688611 0
Viewed 388

Here is the problem. The input is a list of integers. If three adjacent numbers appear next to each other they should be dropped and the operation goes again. Iphone app with the balls of the same colors. The output should be the count of the balls that will be destroyed.

Example:

input = [3,3,4,4,4,3,4]

1st iteration

output: [3,3,3,4]

Final output:

6

4,4,4 on the first iteration, so three balls. and 3,3,3 on the second. Overall six.

My code is below. It will remove the 4,4,4 but will fail after, because list index will quickly go out of range.

    def balls(a):
    
        curr_index = 0
        removed_count = 0
        while len(a) > 2:

            if (a[curr_index] == a[curr_index+1]) and (a[curr_index] == a[curr_index+2]):

                a.remove(a[curr_index])
                a.remove(a[curr_index+1])
                a.remove(a[curr_index+2])

            curr_index += 1
            removed_count += 3

        return removed_count

a = [3, 3, 4, 4, 4, 3, 4]
    
print(balls(a)) # should print 6

Any ideas?

python
7 Answers

Here is one way to do it:

your_list=[3, 3, 4, 4, 4, 3, 4]

def remove_one(l):
    if len(l)>2:
        for i in range(len(l)-2):
            if l[i]==l[i+1]==l[i+2]:
                res.extend(l[i:i+3])
                l=l[:i]+l[i+3:]
                return l
    return []

res=[]
while len(your_list)>2:
    your_list=remove_one(your_list)

print(len(res))

Output:

6
user_82285580 
input_values = [3,3,4,4,4,3,4]


values = input_values
while len(values) >= 3:
    for x in range(0,len(values)-2):    
        
        # if we find 3 values in ar row
        if values[x] == values[x+1] and values[x] == values[x+2]:
            
            # update values by cutting out the series
            values = values[:x] + values[x+3:]
            
            # break this for loop
            break
    else:
        # for loops can have an else statement
        # this means that we came at the end of the for loop
        # this if we didn't break the loop (and didn't found a valid triple)
        # then we brea
        break
   
#result  - amount of removed balls     
values, len(input_values) - len(values)
user_12750870

A more generic approach where you can define N

(it will find exact N values)


input_values = [3,3,4,4,4,4,3,3,4]

# amount of neighbours
N = 4

values = input_values

# keep looping as long as we've N values
while len(values) >= N:
    
    # we need this if we break the inner loop
    stop = False
    
    # loop over values from left to right
    # 3 -> 3 -> 4 -> 4 -> ... until  -N + 1
    # because that is the last spot that we've N values left 
    for x in range(0, len(values) - N + 1):    
        
      
        # scout for the next numbers (x+1 x+2 x+3 ....)
        # this goes from, x+1 until the end of the serie
        # also start counting from 2 - because
        # if we've a single match, 2 numbers are equal
        for e, y in enumerate(range(x+1, len(values)), start=2):
            
            # if x and y are different, the stop this scouting
            # remember y = x+1   x+2  x+3 ....
            if values[x] != values[y]:
                break
  
            # if we reached this stage, we know that 
            # x and x+1     x+2   ... are equal
            # but also check if we've enough matches
            if e == N:
                # update values by cutting out the series
                values = values[:x] + values[y+1:]
                stop = True
                break
        
        if stop:
            break
 
      
    else:
        # for loops can have an else statement
        # this means that we came at the end of the for loop
        # this if we didn't break the loop (and didn't found a valid triple)
        # then we brea
        break
        
values, len(input_values) - len(values)
user_12750870

An approach with a minimal threshold

input_values = [3,3,4,4,4,4,4,3,3,4]

# threshold
N = 3

values = input_values
while len(values) >= N:
    
    # we need this if we break the inner loop
    stop = False
    
    # loop over values
    for x in range(0, len(values) - N + 1):    
        
        # scout for the next numbers (x+1 x+2 x+3 ....)
        for e, y in enumerate(range(x+1, len(values)), start=2):

            # check if the values of x and  x+1   (x+2  x+3 ...) are different
            if values[x] != values[y]:
                
                # if so, check if we've reached our threshold of N
                if e >= N:
                
                    # if this is the case update values by cutting out the series
                    values = values[:x] + values[y:]
                    stop = True
                    break
                    
                # if x+n  != x then we break this scouting loop
                break

        # stop is True, this means, that we found N neibouring numbers
        # thus we can break this loop, and start over with a new* value
        if stop:
            break
 
      
    else:
        # for loops can have an else statement
        # this means that we came at the end of the for loop
        # thus if we didn't break the loop (and didn't found a valid triple)
        # then we break
        break
        
values, len(input_values) - len(values)
user_12750870

There are a couple of issues with your code.

The first is you're trying to iterate over the list a single time, but that won't work for your example.

The second is you're assuming the list will always reduce to less than 3, which won't be the case if you have more numbers.

There are also some places you can simplify the syntax, for example:

if (a[curr_index] == a[curr_index+1]) and (a[curr_index] == a[curr_index+2]):

is equivalent to:

if a[curr_index] == a[curr_index + 1] == a[curr_index + 2]:

And

a.remove(a[curr_index])
a.remove(a[curr_index+1])
a.remove(a[curr_index+2])

is equivalent to:

del a[curr_index: curr_index + 3]

So here is one way to accomplish this, thought there are more efficient ways.

def balls(a):

    removed = 0
    complete = False

    # Run until complete is set or the list is too short for a match
    while not complete and len(a) >= 3:

        for idx, val in enumerate(a):
            if val == a[idx + 1] == a[idx + 2]:
                del a[idx: idx + 3]
                removed += 3
                break  # Restart every time we find a match

            # If it's the last possible match, set complete
            if idx == len(a) - 3:
                complete = True
                break

    return removed
user_49511870

I'm little bit late, but my idea is to do the processing in one pass. The idea is that when you drop a tripple, go back two positions to re-check if a new tripple has been created by that change.

Example:

3 3 4 4 4 3
    ^--- tripple found here, remove it
3 3 3
^--- move the cursor 2 positions left and continue checking

The code:

def drop3(lst):
    # drop3 destroys the lst, make a copy if you want to keep it
    dropped = 0 
    cursor = 0 
    limit = len(lst) - 2 
    while cursor < limit:
        if lst[cursor] == lst[cursor+1] == lst[cursor+2]:
            del lst[cursor:cursor+3]
            cursor = max(0, cursor-2)
            limit -= 3
            dropped += 3
        else:
            cursor += 1
    return dropped
user_53788160

A linear-tme solution:

def balls(a):
    b = []
    for x in a:
        b.append(x)
        if b[-3:] == [x] * 3:
            del b[-3:]
    return len(a) - len(b)
user_130084390
Related