#!/usr/bin/env python
# coding: utf-8

# # 8 Lists
# <a href="https://colab.research.google.com/github/rambasnet/FDSPython-Notebooks/blob/master/Ch08-1-Lists.ipynb" target="_parent"><img src="https://colab.research.google.com/assets/colab-badge.svg" alt="Open In Colab"/></a>
# 
# - http://openbookproject.net/thinkcs/python/english3e/lists.html
# 
# ## Topics
# - list data structure
# - syntax to create lists
# - methods or operations provided to list objects
# - list operators
# - list traversal
# - list applications and problems
# 
# ## 8.1 Lists
# - a type of sequence or container
# - ordered collection of values called elements or items
# - lists are similar to strings (ordered collections of characters) except that elements of a list can be of any type

# ## 8.2 Creating lists
# - several ways; the simplest is to enclose the elements in square brackets [ ]

# In[15]:


alist = [] # an empty list


# In[16]:


blist = list() # an empty list


# In[17]:


type(alist)


# In[18]:


# creating lists with some elements of same type
list1 = [10, 20, 30, 40]
list2 = ['spam', 'bungee', 'swallow']


# In[6]:


# lists with elements of different types
list3 = ["hello", 2.0, 10, [10, ('hi', 'world'), 3.5], (1, 'uno')]


# In[20]:


# print list
print(list3)


# In[21]:


# quickly create a list of range of numbers between 1 and 19
list4 = list(range(1, 20, 1))


# In[22]:


print(list4)


# In[23]:


# print multiple lists
print(alist, list1, list2, list3)


# In[11]:


# Exercise: create a list of even numbers between 1 and 20 inclusive


# In[12]:


# Exercise: create a list of odd numbers between 1 and 20 inclusive


# In[13]:


# Exercise: create a list of numbers from 20 to 1 inclusive


# ## 8.3 Accessing elements
# - same syntax for accessing characters of a string, the index operator: ['index']

# In[14]:


# let's see what elements are in list1
list1


# In[15]:


# access an element, which one?
list1[0]


# In[16]:


list3


# In[17]:


list3[2-2]


# In[18]:


# list index can be variable as well
index = 0
print(list3[index])


# In[19]:


# can you use float value as an index?
list3[1.0]


# In[20]:


# how many elements are there in list3?
len(list3)


# In[21]:


# what happens if you access an index equal to the size of the list
list3[5]


# In[3]:


list3


# In[24]:


# Exercise: access and print the last element of list3


# In[4]:


# Can we use negative index?
# Can you guess the output of the following code?
print(list3[-1])


# In[32]:


# Exercise - access and print 'world' in list3


# ## 8.4 Membership
# - checking if some data/object is a member/element in the given list
# - **in** and **not in** boolean operators let's you check for membership

# In[1]:


horsemen = ["war", "famine", "pestilence", ["death"]]
'death' in horsemen


# In[2]:


'War' not in horsemen


# In[3]:


["death"] in horsemen


# ## 8.5 Traversing lists
# - for or while loop can be used to traverse through each element of a list

# In[29]:


list3


# In[5]:


# common technique; use for loop
for item in list3:
    print(item)


# In[6]:


for item in list3:
    if isinstance(item, list) or isinstance(item, tuple):
        for l in item:
            print(l)
    else:
        print(item)


# In[8]:


horsemen = ["war", "famine", "pestilence", "death"]
for i in [0, 1, 2, 3]:
    print(horsemen[i])
# better way to do the same thing?


# In[10]:


print("traversing using indices")
for i in range(len(horsemen)):
    print(horsemen[i])


# In[11]:


print('traversing each element')
for ele in horsemen:
    print(ele)


# ## 8.6 list operators
# - \+ operator concatenates two lists and gives a bigger list
# - \* operator repeats a list elements a given number of times

# In[24]:


list2


# In[26]:


list3


# In[27]:


list4 = list2 + list3


# In[28]:


list4


# In[29]:


[0]*10


# In[30]:


a = [1, 2, 3]*4


# In[31]:


a


# In[32]:


b = [a]*3


# In[33]:


b


# In[42]:


# 2-D list or matrix
matrix = [[1, 2], [3, 4], [5, 6]]


# In[43]:


print(matrix)


# In[44]:


matrix


# In[45]:


# How do you replace 5 with 50 in matrix?
matrix[2][0] = 50


# In[46]:


matrix


# ## 8.7 Slicing lists
# - all the slice operations that work with strings also work with lists
# - syntax: [startIndex : endIndex : step]
# - startIndex is inclusive; endIndex is exclusive; step is optional by default 1

# In[36]:


# create a list of lower-case alphabets
alphas = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] # add the rest...


# In[37]:


alphas


# In[38]:


# there's better way to create lists of all lowercase ascii
import string
alphas = list(string.ascii_lowercase)


# In[39]:


print(alphas[:])


# In[40]:


print(alphas[::3])


# In[41]:


print(alphas[1:3])


# In[42]:


print(alphas[::-1])


# ## 8.8 Lists and strings
# - match made in heaven - work together really well :)

# In[44]:


# convert string to list of characters
alphaList = list(string.ascii_lowercase)


# In[45]:


alphaList


# In[46]:


# convert list to string by joining pairs of chars with a delimiter
alphaStr = '|'.join(alphaList)


# In[47]:


alphaStr


# ## 8.9 lists are mutable
# - we can change/replace/update list elements in place

# In[48]:


names = ["john", "David", "Alice"]
names[0] = "jake"


# In[49]:


names


# In[50]:


# How to correct spelling of jake?
names[0][0]


# In[51]:


names[0][0] = 'J'


# In[52]:


names[0] = 'Jake'


# In[53]:


names


# In[54]:


alphas


# In[55]:


alphas[:4] = ['A', 'B', 'C', 'D']


# In[56]:


alphas


# In[57]:


alphas[:4] = []


# In[58]:


alphas


# ## 8.10 Deleting list elements
# - del statement removes an element from a list given its index

# In[59]:


alphas


# In[60]:


del alphas[0]


# In[61]:


alphas


# In[62]:


del alphas[26]


# In[63]:


alphas.index('z')


# In[64]:


alphas.index(alphas[-1])


# In[65]:


del alphas[1:3]


# In[66]:


alphas


# In[67]:


indexOfZ = alphas.index('z')
del alphas[indexOfZ]


# In[68]:


print(alphas)


# ## 8.11 Objects and references
# - **is** operator can be used to test if two objects are referencing the same memory location
#     - meaning they're essentially the same object with the same values

# In[78]:


# even though a and b are two separate objects is still evaluates to True
a = 'apple'
b = 'apple'
a is b


# In[69]:


# even though c and d are two separate objects is still evaluates to True
c = 10
d = 10
c is d


# In[73]:


# what abut tuple?
e = (1, 2)
f = (1, 2)
print(e == f)
print(e is f)


# In[79]:


# What about lists?
l1 = [1, 2, 3]
l2 = [1, 2, 3]
print(l1 == l2)
print(l1 is l2)


# ## 8.12 Copying lists (Shallow copy vs Deep copy)
# - see [PythonTutor.com to visualize aliasing](http://pythontutor.com/visualize.html#code=import%20copy%0A%0Aa%20%3D%20%5B1,%20%5B2,%203%5D%5D%0Ab%20%3D%20a%0Ac%20%3D%20a.copy%28%29%0Ad%20%3D%20a%5B%3A%5D%0Af%20%3D%20copy.deepcopy%28a%29&cumulative=false&curInstr=0&heapPrimitives=false&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false)
# - assignment *=* operator does shallow copy

# In[80]:


a = [1, 2, 3]
b = a
print(a is b)
print(a == b)


# In[81]:


b[0] = 10
print(a)
print(b)


# In[82]:


# How do you actually clone lists - do a deep copy?
c = a[:] # easy way shallow copy
d = a.copy() # shallow copy
import copy
e = copy.deepcopy(b)


# In[83]:


c is a


# In[84]:


d is a


# In[85]:


b is e


# ## 8.13 List methods
# - list objects have a bunch methods that can be invoked to work with list
# - run help(list)

# In[86]:


help(list)


# In[87]:


a = []
a.append(1)
a.append(2)
a.append([2, 3])


# In[88]:


a


# In[89]:


a.extend([3, 4])


# In[90]:


a


# In[91]:


a.append([5, 6])


# In[92]:


a


# In[93]:


a.insert(0, 'hi')


# In[94]:


a


# In[95]:


a.reverse()


# In[96]:


a[0].reverse()


# In[97]:


a


# In[98]:


a.sort()


# In[99]:


blist = list(range(10, 0, -1))


# In[100]:


blist


# In[101]:


blist.sort()


# In[102]:


print(blist)


# In[103]:


blist.sort(reverse=True)


# In[104]:


blist


# In[105]:


m = max(blist)
mI = blist.index(m)


# In[106]:


print(mI)


# In[107]:


min(blist)


# In[108]:


print(blist.count(100))


# ## 8.14 List applications
# 
# ### convert a string to list of integers

# In[4]:


nums = input('Enter 5 numbers separated by space: ')


# In[5]:


nums


# In[76]:


nums = nums.split(' ')


# In[77]:


nums


# In[78]:


intNums = []
for n in nums:
    intN = int(n)
    intNums.append(intN)


# In[79]:


intNums


# In[80]:


intNums.sort()


# In[81]:


intNums


# ### convert list of integers to string

# In[94]:


' '.join(intNums)


# In[99]:


strNum = []
for n in intNums:
    strNum.append(str(n))


# In[100]:


strNum


# In[101]:


strNum = ' '.join(strNum)


# In[102]:


strNum


# ## 8.15 Passing list to function - pass-by-reference
# - mutable types such as list are passed-by-reference 
# - an alias or reference is passed instead of a copy of the data

# In[84]:


def getData(someList):# someList is formal parameter
    for i in range(5):
        a = int(input('enter a number: '))
        someList.append(a)


# In[85]:


alist = []
getData(alist) # alist is actual argument


# In[86]:


# when formal parameter is updated, actual parameter is also updated
alist


# ### [visualize - pass-by-reference with pythontutor.com](http://pythontutor.com/visualize.html#code=def%20getData%28someList%29%3A%23%20someList%20is%20formal%20parameter%0A%20%20%20%20for%20i%20in%20range%285%29%3A%0A%20%20%20%20%20%20%20%20a%20%3D%20int%28input%28'enter%20a%20number%3A%20'%29%29%0A%20%20%20%20%20%20%20%20someList.append%28a%29%0A%0Aalist%20%3D%20%5B%5D%0AgetData%28alist%29%20%23%20alist%20is%20actual%20argument&cumulative=false&curInstr=0&heapPrimitives=false&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false)

# ## 8.16 return list from functions
# - lists can be returned from functions

# In[121]:


def getMaxMin(alist):
    m = max(alist)
    minVal = min(alist)
    return [m, minVal]
    


# In[122]:


alist = list(range(-1000, 2000000))
print(getMaxMin(alist))


# In[123]:


assert getMaxMin(alist) == [1999999, -1000]


# ## 8.17 Casting list into tuple and back
# - since tuples are immutable it may be benefitial to cast them into lists and update
# - can convert list back to tuple again

# In[88]:


atuple = (1, 2, 3)
alist = list(atuple)
print(alist)


# In[89]:


btuple = tuple(alist)


# In[90]:


print(btuple)


# In[91]:


atuple == btuple


# In[93]:


# eventhough the elements are equal; the types of two objects are not
print(atuple, alist)
print(atuple == alist)


# ## 8.18 Exercises
# 1. Practice with the rest of the methods of list

# 2. Draw memory state snapshot for a and b after the following Python code is executed:
# 
# ```python
# a = [1, 2, 3]
# b = a[:]
# b[0] = 5
# ```

# 3. Lists can be used to represent mathematical vectors. Write a function `add_vectors(u, v)` that takes two lists of numbers of the same length, and returns a new list containing the sums of the corresponding elements of each. The following test cases must pass once the add_vectors is complete.

# In[124]:


def add_vectors(a, b):
    pass


# In[125]:


# test cases
assert add_vectors([1, 1], [1, 1]) == [2, 2], 'vectors not added correctly'
assert add_vectors([1, 2], [1, 4]) == [2, 6], 'vectors not added correctly'
assert add_vectors([1, 2, 1], [1, 4, 3]) == [2, 6, 4], 'vectors not added correctly'


# ## Kattis problems
# - the following Kattis problems can be solved using list
# 
# 
# 1. Dice Game - https://open.kattis.com/problems/dicegame
# - Height Ordering - https://open.kattis.com/problems/height
# - What does the fox say? - https://open.kattis.com/problems/whatdoesthefoxsay
# - Army Strength (Easy) - https://open.kattis.com/problems/armystrengtheasy
# - Army Strength (Hard) - https://open.kattis.com/problems/armystrengthhard
# - Black Friday - https://open.kattis.com/problems/blackfriday
# 
# ### List sorting with two keys
# 1. Roll Call - https://open.kattis.com/problems/rollcall
# - Cooking Water - https://open.kattis.com/problems/cookingwater
# 

# In[ ]: