#!/usr/bin/python -tt
# Copyright 2010 Google Inc.
# Licensed under the Apache License, Version 2.0
# http://www.apache.org/licenses/LICENSE-2.0

# Google's Python Class
# http://code.google.com/edu/languages/google-python-class/

# Additional basic list exercises


# D. Given a list of numbers, return a list where
# all adjacent == elements have been reduced to a single element,
# so [1, 2, 2, 3] returns [1, 2, 3]. You may create a new list or
# modify the passed in list.
def remove_adjacent(nums):
    # +++your code here+++
    lista = []
    for n in nums:
        if len(lista) == 0 or n != lista[-1]:
            lista.append(n)
    return lista


# E. Given two lists sorted in increasing order, create and return a merged
# list of all the elements in sorted order. You may modify the passed in lists.
# Ideally, the solution should work in "linear" time, making a single
# pass of both lists.
def linear_merge(list1, list2):
    # +++your code here+++
    result = []
    # Look at the two lists so long as both are non-empty.
    # Take whichever first element is smaller.
    while len(list1) and len(list2):
        if list1[0] < list2[0]:
            result.append(list1.pop(0))
        else:
            result.append(list2.pop(0))

    # Now tack on what's left
    result.extend(list1)
    result.extend(list2)
    return result


# Note: the solution above is kind of cute, but unfortunately list.pop(0)
# is not constant time with the standard python list implementation, so
# the above is not strictly linear time.
# An alternate approach uses pop(-1) to remove the endmost elements
# from each list, building a solution list which is backwards.
# Then use reversed() to put the result back in the correct order. That
# solution works in linear time, but is more ugly.


def reversed_linear_merge(list1, list2):
    # +++your code here+++
    result = []
    # Look at the two lists so long as both are non-empty.
    # Take whichever last element is bigger.
    while len(list1) and len(list2):
        if list1[-1] > list2[-1]:
            result.append(list1.pop(-1))
        else:
            result.append(list2.pop(-1))

    # Now tack on what's on the left
    result.extend(reversed(list1))
    result.extend(reversed(list2))
    return list(reversed(result))


# Simple provided test() function used in main() to print
# what each function returns vs. what it's supposed to return.
def test(got, expected):
    if got == expected:
        prefix = ' OK '
    else:
        prefix = '  X '
    print('%s got: %s expected: %s' % (prefix, repr(got), repr(expected)))


# Calls the above functions with interesting inputs.
def main():
    print('remove_adjacent')
    test(remove_adjacent([1, 2, 2, 3]), [1, 2, 3])
    test(remove_adjacent([2, 2, 3, 3, 3]), [2, 3])
    test(remove_adjacent([]), [])

    print()
    print('linear_merge')
    test(linear_merge(['aa', 'xx', 'zz'], ['bb', 'cc']),
         ['aa', 'bb', 'cc', 'xx', 'zz'])
    test(linear_merge(['aa', 'xx'], ['bb', 'cc', 'zz']),
         ['aa', 'bb', 'cc', 'xx', 'zz'])
    test(linear_merge(['aa', 'aa'], ['aa', 'bb', 'bb']),
         ['aa', 'aa', 'aa', 'bb', 'bb'])

    print()
    print('reversed_linear_merge')
    test(reversed_linear_merge(['aa', 'xx', 'zz'], ['bb', 'cc']),
         ['aa', 'bb', 'cc', 'xx', 'zz'])
    test(reversed_linear_merge(['aa', 'xx'], ['bb', 'cc', 'zz']),
         ['aa', 'bb', 'cc', 'xx', 'zz'])
    test(reversed_linear_merge(['aa', 'aa'], ['aa', 'bb', 'bb']),
         ['aa', 'aa', 'aa', 'bb', 'bb'])


if __name__ == '__main__':
    main()

@@ -904,23 +904,16 @@
 ts.%0Adef 
-linear_
 merge(li
@@ -1785,25 +1785,16 @@
 .%0A%0A%0Adef 
-reversed_
 linear_m
@@ -2830,23 +2830,16 @@
  print('
-linear_
 merge')%0A
@@ -2839,39 +2839,32 @@
 erge')%0A    test(
-linear_
 merge(%5B'aa', 'xx
@@ -2930,39 +2930,32 @@
 'zz'%5D)%0A    test(
-linear_
 merge(%5B'aa', 'xx
@@ -3029,23 +3029,16 @@
    test(
-linear_
 merge(%5B'
@@ -3164,33 +3164,24 @@
 ')%0A    test(
-reversed_
 linear_merge
@@ -3262,33 +3262,24 @@
 %5D)%0A    test(
-reversed_
 linear_merge
@@ -3364,25 +3364,16 @@
    test(
-reversed_
 linear_m

improved answer for list2