list2-mb.py

#!/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.

#numbers = [1,2,2,3]

def remove_adjacent(numbers):
    noadjacents = []
    for number in numbers:
        if len(noadjacents) == 0:
            noadjacents.append(number)    # add first list element to new list
        elif number == noadjacents[-1]:
            pass                          # skip next element if new list ends with same number
        else:
            noadjacents.append(number)    # if not, add next element
    return noadjacents


# 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.
    

## not linear, but my preference due to simplicity
# import numpy as np
#def linear_merge(list1, list2):
#    merged_list = sorted(np.append(list1,list2))
#    return merged_list

list1 = [3,5,1,3,6]
list2 = [4,7,9,1,6]

def linear_merge(list1,list2):
    merged_list = []
    if len(list1) > 0 and len(list2) > 0:
        if list1[0] < list2[0]:
            merged_list.append(list1.pop(0))
        else:
            merged_list.append(list2.pop(0))
    elif len(list1) == 0:
        merged_list.append(sorted(list2))
    elif len(list2) == 0:
        merged_list.append(sorted(list1))
    else:
        pass
    return merged_list

#def linear_merge(list1, list2):
#  merged_list = []
#  while len(list1) and len(list2):
#    if list1[0] < list2[0]:
#      merged_list.append(list1.pop(0))
#    else:
#      merged_list.append(list2.pop(0))


# Note: the solution above is kind of cute, but unforunately 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.


# 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'])


if __name__ == '__main__':
  main()