"""
Solution to the ADT puzzle from lecture; uses a stack.
This is fast!
"""

from typing import List
from adts import Stack

# Assumes that peek is not available


def puzzle2(lst: List[int]) -> List[int]:
    """Solve the puzzle."""
    s = Stack()

    for element in lst:
        s.push(element)
        match = True
        while match and not s.is_empty():
            right = s.pop()
            if s.is_empty():
                s.push(right)
                match = False
            else:
                left = s.pop()
                if left + 1 == right:
                    s.push(left * 2 + 1)
                else:
                    s.push(left)
                    s.push(right)
                    match = False

    lst = []
    while not s.is_empty():
        lst.append(s.pop())
    lst.reverse()

    return lst


if __name__ == '__main__':
    import time
    items = list(range(100000))

    # start the clock
    start = time.time()

    puzzle2(items)
        
    end = time.time()
    print(f"It took {end - start} seconds using the ADT-based algorithm")