Flipping pairs in compressed list in Python

Question

I'm new to Python and I've been banging my head around a problem for a few days now. I have been considering leaving it blank and waiting from the prof's answers but we still haven't received the answers from the previous assignment (3 months ago) and I really want to progress.

THE SETUP:

I made the following function than can compress lists according to repetitions:

def compress(list: List[T]) -> List[Tuple[T, int]] :
    """Returns the compressed list"""
    if len(list) == 1 :
        return [(list[0], 1)]
    result: List[Tuple[T, int]] = []
    count: int = 1
    i: int
    for i in range(1, len(list)) :
        if list[i] != list[i-1] :
            result.append((list[i-1], count))
            count = 1
        else :
            count = count + 1
            if i == len(list)-1 :
                result.append((list[i], count))
    return result

assert compress([3, 3, 3, 3, 1, 1, 2, 3, 3]) == [(3, 4), (1, 2), (2, 1), (3, 2)]
assert compress(['a','a','c','c','c','d','c','c','c','c']) == [('a', 2), ('c', 3), ('d', 1), ('c', 4)]

I also made the following decompressing function:

def decompress(code: List[Tuple[T, int]]) -> List[T] :
    """Returns the decompressed list"""
    return [value for (value, nb) in code for i in range(nb)]

assert decompress([(3, 4), (1, 2), (2, 1), (3, 2)]) == [3, 3, 3, 3, 1, 1, 2, 3, 3]
assert decompress([('a', 2), ('c', 3), ('d', 1), ('c', 4)]) == ['a', 'a', 'c', 'c', 'c', 'd', 'c', 'c', 'c', 'c']

I then made a "flipping" function that flips every other item in a list (I know it's useless but hey, the exercice said I had to so...):

def flipping(liste:List[T]) -> List[T] :
    """Returns the list after flipping every other item"""
    length:int = len(liste)
    quotient: int = length // 2
    i:int
    result: List[T] = []
    for i in range(quotient) :
        resultat = result + [liste[2*i+1], liste[2*i]]
    if length % 2 == 1 :
        result = result + [liste[-1]]
    return result

assert flipping([1, 2, 3]) == [2, 1, 3]
assert flipping([1, 2, 3, 4]) == [2, 1, 4, 3]
assert flipping(['a', 'a', 'a', 'a', 'c', 'c', 'd', 'c', 'c']) == ['a', 'a', 'a', 'a', 'c', 'c', 'c', 'd', 'c']

THE PROBLEM:

I am now asked to make a function that can flip items the same way, but from a compressed list and WITHOUT decompressing it (yeah I know, no fun).

The only thing I know for sure is it should look like this:

def flipping_compressed(code:List[Tuple[T, int]]) -> List[Tuple[T, int]] :
    #does magic
    return result

assert flipping_compressed([('a', 1), ('c', 1), ('d', 1)]) == [('c', 1), ('a', 1), ('d', 1)]
assert flipping_compressed([('a', 1), ('c', 1), ('d', 1), ('a', 1)]) == [('c', 1), ('a', 2), ('d', 1)]
assert flipping_compressed([(3, 4), (1, 2), (2, 1), (3, 2)]) == [(3, 4), (1, 2), (3, 1), (2, 1), (3, 1)]

I've been trying for days and ended up every time with a huge function full of nested ifs that don't work anyway. The whole assignment is supposed to be done in under two hours so I have obviously been missing something here.

I'd appreciate any help from more experienced comrads that enjoy a good problem :)

Cheers!

Answer 1

This is called "run length encoding"; search the topic for resources.

This operates on simply partitioned pairs in the original list: positions 0 & 1, 2 & 3, 4 & 5, ... To do the swapping without decompressing the list, you need to partition your list at all swap points. For instance, given your compressed list

[(3, 4), (1, 2), (2, 1), (3, 2)]

You need to break a single element anywhere it needs to be swapped with the adjacent element. In this example,

(3, 4)   pos 0-3, no need to break
(1, 2)   pos 4-5, no need to break
(2, 1)   pos 6 .. needs a partner
(3, 2)   pos 7-8, needs the first element separated.

The one needed break gives you

[(3, 4), (1, 2), (2, 1), (3, 1), (3, 1)]

Swapping within a group does nothing; the only operations needed are where the pair elements are of different values. That's (2, 1), (3, 1) here.

[(3, 4), (1, 2), (3, 1), (2, 1), (3, 1)]

As it happens, this is your final result.

Let's look at another case you gave:

[('a', 2), ('c', 3), ('d', 1), ('c', 4)]

With required parity breaks, this becomes

[('a', 2), ('c', 2), ('c', 1), ('d', 1), ('c', 4)]

Now, swap the adjacent pairs of even-odd index:

[('a', 2), ('c', 2), ('d', 1), ('c', 1), ('c', 4)]

To get the final result, you now need to make a pass over the list, checking the items you swapped for "bonding" with the adjacent elements. In this example, the only joining is the solo c, giving you

[('a', 2), ('c', 2), ('d', 1), ('c', 5)]

This is the desired result.

I trust that you can work up some code from this algorithm outline.