#            CSC 15 Basic Practice Problems

# Test your solutions in Python (make sure you can call the functions too).


#0a Write code to construct a list containing all the numbers that are
#   evenly divisible by 8 from 0 to 10000, i.e., the list
#   [0,8,16,24,32,40,48,56,64, ... 10000].  Hint: first line is
M = []
x = 0  # numbers to be added to list
while x<=10000:
    M.append(x)
    x = x+8
# end while

# another solution, this time the "iterator" i is incremented by one each time:

M=[]
i = 0
while i<=10000:
    if (i%8==0) M.append(i)
    i=i+1
#end while


#0b. Write a function 'product' that multiplies all numbers in an array.
#   For example, product([3,2,5]) should return 30.  Hint: the product
#   of the empty array is 1


def product(A):
    i = 0  # loop counter, indexes A
    prod = 1   # running product
    while i<len(A):
        prod = prod * A[i]
        i=i+1
    return prod


#1. Write a function 'doubles' that takes a list as parameter and constructs
#   a new list with two copies of each element of the parameter list.
#   For example, doubles([2,4,6,8]) should return [2,2,4,4,6,6,8,8].  Hint:
#   inside the loop, do two appends.

def doubles(A):
    i = 0  # indexes A
    B = []   # new array to be constructed
    while i<len(A):
        B.append(A[i])
        B.append(A[i])
        i = i+1
    return B



#2. Write a function to reverse a list (array).  That is, reverse([2,4,6,8])
#   should construct and return the list [8,6,4,2]


def reverselist(A):
    R = []   # reverse list to be constructed
    i = len(A)-1  # start index at end of list
    while i>=0
        R.append( A[i] )
        i =i-1
    return R



#3a. Write a function h that returns True iff there is a number greater than 100
#   in a list.  For example, h([4,6,1,109,3]) should return True.  It should
#   return False otherwise.

def h(A):
    answer = False   # default for "there exists" type of problems
    i = 0
    while i<len(A) and answer==False:
        if A[i]>100: answer = True
        i = i+1
    return answer



#3b Write a function h2 that returns True iff there is at least 2 numbers
#  in the given list that's greater than 100.  For example, h2([4,6,1,109,3])
#  should return False, and h2([45,180,21,346,12]) should return True

def h2(A):
    count = 0   # counts numbers seen that are > 100:
    i = 0
    while i<len(A) and count<2:
        if A[i]>100: count = count+1
        i = i+1
    if count>=2: return True
    else: return False
    # can also just say   return (count>=2);



#4 Write a nested loop that prints
#
# X X X X X
# X X X X
# X X X
# X X
# X
#
# The outer loop should run 5 times.  The inner loop prints each line.

i = 5  # outer loop counter
while i>=1:
    j = 0  # inner loop counter
    while j<i:
        print "X",   # , at end ensures printing on same line
        j = j+1
    # inner loop
    print ""    # prints new line
    i = i-1
# outer loop


#5. Write a function 'odds' that takes an array as an argument and returns
#   and array containing all the odd numbers of the given array.  For
#   example, odds([4,3,6,8,1,9]) should return [3,1,9], which are all the
#   odd numbers of the given (parameter) list.

def odds(A):
    B = []  # array to be constructed
    i = 0
    while i<len(A):
        if (A[i]%2 == 1):
            B.append(A[i])
        i = i+1
    return B


#6 write a function sublist(A,B) that returns True iff every element of
#  A also appears in B.  For example, sublist([2,4,6], [1,2,3,4,5,6,7])
#  should return True. (implicitly returns False if A is not a sublist of B)
#  hint: the expression (x in B) is True iff x occurs in array B

def sublist(A,B):
    i = 0  # indexes A
    answer = True   # This is a "for all" type of problem
    while i<len(A) and answer==True:
        if (not (A[i] in B)):   # can also say if (A[i] in B)==False: 
            answer = False
        i = i+1
    return answer



#7 (similar) write a function intersection(A,B) that returns the
#  intersection of the lists A, B.  That is, it should return a list M
#  that contains all elements that are in both A and B. Duplicates are
#  fine.  For example, intersection([2,4,6,8], [1,2,3,4,5]) should
#  return [2,4], which is the intersection of the two lists.  Hint:
#  you don't need a nested loop.  All you have to do is to go through
#  the list A and look for the elements that are also in B.

def intersection(A,B):
    M = []   # intersection to be constructed
    i = 0    # indexes list A
    while i<len(A):
        if (A[i] in B): M.append(A[i])
        i =i+1
    return M
# note that the built-in predicate "in" allows us to write this function
# whithout a nested loop.


#8 write a function 'occurs(x,A)' that returns the first index in A where
#  x is found.  If x does not exist in A, then the function should return
#  -1

def occurs(x,A):
    i = 0
    answer = -1
    while i<len(A) and answer == -1
        if A[i]==x: answer = i
        i = i+1
    # while loop
    return answer
#occurs


# write a function count that returns the number of times x occurs in A.
# for example, count(3,[4,3,7,3,1]) should return 2
#
def count(x,A):
    cx = 0  # counter
    i = 0   # indexes A
    while i<len(A):
        if A[i]==x: cx += 1
        i += 1
    #
    return cx
#count

# (harder)  a permutation is a list of length n that contains the numbers
# 0 to n-1.  For example, [4,2,0,1,3] is a permutation of length 5.  It
# permutes the numbers 0 to 4.  That is, 4 becomes 0, 2 becomes 1, 0 becomes 2,
# etc.  Now we can use a permutation to permute or "scramble" a string of
# the same length, such as "hello" by applying the permutation to each
# character.  Applying the above permutation list to "hello" will result
# in "olhel":
#hello
#01234
#olhel

def permute(P,s): #permute string s by permutation array P
    t = "" # string to be constructed
    i = 0  # indexes P
    while i<len(P):
      j = P[i] # permute index i to index j
      t = t + s[j]  # add permuted character to string
      # or just t += s[P[i]]
      i += 1
    #while
    return t
#permute