# Tutorial 3 - Problem 4

# Which searching algorithm does find() implement?
# Answer: Linear search

# Why is find() seen as the inverse of the indexing [ ] operator?
# Answer: Because, given a character, find returns the index (of first occurrence of
#         the character in the word, whereas, given en index, the indexing [] operator
#         returns the character in word at that index.

# Let’s rewrite the above function such that it uses the more appropriate for loop.
# Why is the for loop more appropriate than the while loop in the above algorithm?
# Answer: Because we know how many iterations the loop must do -> length of word

##def find(word, letter):
##  index = 0
##  while index < len(word):
##    if word[index] == letter:
##      return index
##    index = index + 1
##  return -1

# Return first occurrence of letter in word
def find1(word, letter):
  for index in range(len(word)):
    if word[index] == letter:
      return index
  return -1


# Return last occurrence of letter in word
def find2(word, letter):
  position = -1
  for index in range(len(word)):
    if word[index] == letter:
      position = index
  return position

# Let’s modify the original find( ) above (the one with the while loop)
# such that it has only one return statement (the one at the end of the function body)
# and has a third parameter, namely the index in word where it should start searching.
# Let’s make sure we use a descriptive name when we name this 3rd parameter.

def findStartingAt1(word, letter, startingHere):
  index = startingHere
  position = -1
  while index < len(word):
    if word[index] == letter:
      position = index
      index = len(word)
    else:
      index = index + 1
  return position

def findStartingAt2(word, letter, startingHere):
  position = -1
  for index in range(startingHere, len(word), 1):
    if word[index] == letter:
      position = index
  return position


# Main part of program

print('find1("banana", "a")): ', find1("banana", "a"))
print('find1("banana", "t")): ', find1("banana", "t"))
print('find2("banana", "a")): ', find2("banana", "a"))
print('find2("banana", "t")): ', find2("banana", "t"))
print('findStartingAt1("Greetings everyone!", "a", 0)): ', findStartingAt1("Greetings everyone!", "a", 0))
print('findStartingAt1("Greetings everyone!", "r", 5)): ', findStartingAt1("Greetings everyone!", "r", 5))
print('findStartingAt2("Greetings everyone!", "a", 0)): ', findStartingAt2("Greetings everyone!", "a", 0))
print('findStartingAt2("Greetings everyone!", "r", 5)): ', findStartingAt2("Greetings everyone!", "r", 5))

# Actual results of our test cases:
##find1("banana", "a")):  1
##find1("banana", "t")):  -1
##find2("banana", "a")):  5
##find2("banana", "t")):  -1
##findStartingAt1("Greetings everyone!", "a", 0)):  -1
##findStartingAt1("Greetings everyone!", "r", 5)):  13
##findStartingAt2("Greetings everyone!", "a", 0)):  -1
##findStartingAt2("Greetings everyone!", "r", 5)):  13