# More examples of arrays, strings, loops and functions.

#Here is a function that tests if an array is sorted (in increasing order):

def sorted(A): # True iff A is sorted
    answer = True  # forall type of problem: the empty list is sorted
    i = 0
    while answer and i<len(A)-1: # we need to stop one position sooner
        if A[i]>A[i+1]: answer = False
        i += 1
    #while
    return answer
#sorted.

# Given an array such as A = [2,4,6,8], the built-in operation A.insert(2,9)
# will insert 9 into position 2 in A, shifting other values downwards.  A
# becomes [2,4,9,6,8].  This operation is destructive like append.

# the following function inserts a number into a sorted array and keeps it
# sorted:

def sortedinsert(x,A): # destructive insert x into sorted array A
    i = 0 # index A
    inserted = False  # will stop array
    while not(inserted) and i<len(A):
        if x<A[i]:
            A.insert(i,x)
            inserted = True
        else: i+= 1
    #while
    if not(inserted): A.append(x)  # add to end if not inserted before
#sortedinsert

# Note that the above function does not need to return a value because
# insert and append are destructive (and A is a "pointer").

A = [1,3,6,9,12]
sortedinsert(4,A)
print A, sorted(A)


# The following function reverses a string:

def reverse(s): #returns s reversed
    rs = ""  # start with empty string, this is the reverse string to be built
    i = 0
    while i<len(s):
        rs = s[i] + rs  # s[i] added to FRONT of rs, thus reversing order
        i += 1
    # while
    return rs
# reverse

print reverse("abcd")

# The following function checks if a string is a "palindrome," that is, if
# it reads the same forwards and backwards.  For example, "bob" and "noon"
# are palindromes.  This is a boolean function.  It is also a forall-type
# function because we need to confirm that the characters at ALL positions
# satisfy some property.

def palindrome(s):
    answer = True  # because it's a forall-type calculation
    i = 0 # indexes s
    ls = len(s)  # length of s will be referred to repeatedly
    while answer==True and i < ls/2:
        if s[i] != s[ls-1-i]: answer = False
        i += 1
    # while
    return answer
#palindrome

print palindrome("abcdcba")


# another way to write the function is to see if it's the same as the reverse:
# return s == reverse(s).  However, that's not as efficient as above.

# The following function converts a day-of-the week string such as
# "Monday" or "Thursday" into a number: 0 for Sunday and 6 for Saturday.
# If the input string is not one of the seven days, we will return -1
# to indicate invalid input.

# For this, we can use a bunch of if-else statements which is not a good
# idea.  Instead, we will put all the day strings into the following array:

DofW = ["Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"]

# now I just need to search the array and return the INDEX at which the string
# was found, and -1 if not found:

def indexof(x,A): # return index of first x in A, or -1 if not found
    i = 0
    answer = -1
    while answer== -1 and i<len(A):
        if A[i]==x: answer = i
        i += 1
    # while
    return answer
# indexof

def daytonum(d):
    return indexof(d,DofW)
#daytonum

print daytonum("Tuesday") # should print 2

### How would you define the inverse?  Given 2, we want to return "Tuesday":

def numtoday(n):
    if (n<0 or n>6): return "invalid"
    else: return DofW[n]
#numtoday

print numtoday(3)  # should print "Wednesday"


## Another example on strings: the following function loops through a
# string and retuns a list/array of vowels.

Vowels = ["a","e","i","o","u","A","E","I","O","U"]

def findvowels(s):  # return list of vowels in string s
    V = []  # array to be built (of unknown size)
    i = 0 # indexes s
    while i<len(s):
        if s[i] in Vowels: V.append(s[i])
        i += 1
    #while
    return V
#findvowels.

print findvowels("hello world")

# How would you change the function so that the V list does not contain
# duplicates? (only one 'o')?


# ANSWER: change the boolean expression of the if statement to
#     s[i] in Vowels and not(s[i] in V):
    

# The following function converts the upper-case letters of a string into
# lower case.  Hint: the ascii values of the lower case alphabetical letters
# are always 32 more than their upper case versions.  For example, ord('B') is
# 66 and ord('b') is 98.  The ascii range of upper case letters are from
# ord('A') to ord('Z'), which is 65 to 90, inclusive.

def lower_case(s): # returns s with all letters in lower case
    ax = ""  # string to be reconstructed, letter by letter
    i = 0 # indexes s
    while i<len(s):
        asci = ord(s[i])  # ascii value of ith char
        if asci>=ord('A') and asci <= ord('Z'):  # is upper case letter
            asci = asci + 32  # convert to ascii value of lower case letter
        # asci stays unchanged if not upper case letter
        ax = ax + chr(asci)   # add char to string being built
        i += 1
    #while
    return ax
#lower_case

# The following function tests if two strings are equal regardless of case:

def nceq(s,t): # returns True iff strings s and t are equal regardless of case
    return lower_case(s) == lower_case(t)
#nceq

# The above function is slightly inefficient because it needs to traverse
# the strings three times: one on s, one on t and one when testing for ==.
# It also uses more memory because it builds two new strings, although the
# memory will be reclaimed when the function call ends.  The following
# is slightly more efficient, but more difficult to write.  To make things
# simpler first I will define a function to check if two individual characters
# are equal regardless of case:

def eqchar(a,b): # True iff a an b are equal regardless of case
    ac,bc = ord(a),ord(b)  # get ascii values
    if (ac>=65 and ac<=90): ac += 32  # convert value to lower case
    if (bc>=65 and bc<=90): bc += 32  # convert value to lower case
    return ac == bc
# eqchar

def nceq2(s,t):
    if len(s)!=len(t): return False
    answer = True   # this is a FORALL type of function
    i = 0 # indexes s and t
    while answer and i<len(s):
        if not(eqchar(s[i],t[i])): answer = False
        i += 1
    #while
    return answer
# nceq2

print nceq2("hello","Hello")

# Nested loops next ...

        
##########################################################################
######################### more practice problems #########################
##########################################################################

#1. Write a function to convert the name of a Month into a number.
#This time however, calling monthnum("January") should return 1, not 0.
#Calling monthnum("December") should return 12.  Return -1 if the input
#parameter is not valid.


#1b. The following array contains the number of days in each month, starting
#with Januray.  We'll assume that it's not a leap year so Feburary has
#28 days:

#DM = [31,28,31,30,31,30,31,31,30,31,30,31]

#Write a function "daysin" that takes a STRING representing the Month
#and returns the number of days in the month.  So daysin("Feburary") should
#return 28, daysin("December") should return 31.  Return 0 if the argument
#is an invalid string.

#Do not do this from scratch: write this function by calling the other
#function(s).

#2. Use the sortedinsert function to invent a "sorting algorithm," which
#should take an unsorted array and return a sorted version.  For example

#sort([4,1,5,8,2]) should return [1,2,4,5,8].

#Hint: do not try to change the original array destructively.  Instead,
#build the sorted array string with the empty [], and keep inserting
#values into it in sorted order.


#3. Write a NESTED loop that prints the following:

#1
#1 2
#1 2 3
#1 2 3 4
#1 2 3 4 5 
#...

#Your print statements may print AT MOST ONE number at a time.
#Encapsulate your loop into a function that can print an arbitrary
#number of lines of this pattern.

#3b.  Now do this one:

#5
#5 4
#5 4 3
#5 4 3 2 
#5 4 3 2 1


#3c. And this one (challenge)

#        1
#      2 1
#    3 2 1
#  4 3 2 1
#5 4 3 2 1

#You must use nested loops and your solution must be generalizable.