Week 8

String indexing and loop design

Not covered yet

• Week 4 notes have been corrected: do not include for loops
• multi-variable assignment not covered in this course

Syntax trees

• The course random tree tool allows you to randomly generate expressions according to a subset of the Python expression syntax (and a tiny subset of English)
• The course parse tree tool allows you to enter a program in this syntax and view its automatically-generated syntax tree
  • the chained-logical-operator bug revealed in the last class has been fixed
  • a list of the syntactic alternatives for statement, expression, and literal forms has been added
  • you will be asked on one or more tests to fill in the names of syntactic forms at appropriate positions in a parse tree
    • you will be given the names of the forms as on this web page

Demo: string indexing, slicing, and inclusion

>>> s = 'abcd'
>>> s[1]
'b'
>>> s[1.0]
Traceback (most recent call last):
  File "", line 1, in ?
TypeError: string indices must be integers
>>> s[1:3]
'bc'
>>> len(s)
4
>>> s[1:len(s)]
'bcd'
>>> s[1:]
'bcd'
>>> s[:3]
'abc'
>>> s[:]
'abcd'
>>> 'c' in 'ab' + 'cd'
True
>>> 'ham' in 'they served ham and eggs'
True
>>> 'ham' in 'they served spam and eggs'
False
>>> 'ham' not in 'they served spam and eggs'
True

Indexing

• Expression syntax:

  string_expression [ index_expression ]

• Semantics: evaluate the expressions and return a string containing the single character whose position is indicated by the index value

  • index values must always be integers

• Positive index values: the corresponding string characters increase from left to right, running from 0 to the string length minus one

  • such indexing beginning with 0 is said to be zero-based

• FYI: Negative index values: are equivalent to the positive index value obtained by adding the negative value to the length of the string

  • they decrease from right to left, starting with -1 for the last element and progressing to minus the length of s for the first element
  • this is introduced in chapter 8 of your text
  • you may use negative index values in this course if you like, but you never have to

Indexing diagram

Slicing

• Expression syntax:

  string_expression [ [start_expression] : [end_expression] ]

• Semantics: evaluate the expressions and return a string containing the characters in the sequence of positions beginning with that indicated by the start expression index and ending with one minus the end expression index

  • index values have the same meaning as in indexing expressions

  • start_expression defaults to 0 (the slice starts at the beginning)

  • end_expression defaults to the length of the string (the slice ends

    at the end)

The in and not in operators

• When both its arguments are strings, the binary in operator returns a boolean value indicating if the first operator is a substring of the second.
• not in is the opposite of in
• The operator precedence of these operators is the same as the relational operators

Indexed loops

• Indexed loops, counted loops in which the count is also used as a string index,

  are very common

• Example:

  def chars_in_string(s1, s2):
      """
      Return a boolean value indicating if every character in s1 is in s2.
  
      >>> chars_in_string('ni', 'win')
      True
      >>> chars_in_string('Ni', 'win')
      False
      >>>
      """
      index = 0
      while index < len(s1):
          if s1[index] not in s2:
              return False
          index = index + 1
      return True

Exercise: remove_char

def remove_char(s, c):
    """
    Return string s with all instances of character c removed.

    >>> remove_char('eggs', 'g')
    'es'
    >>>
    """
    # Hint: use an accumulating indexed loop
    #.
    #.
    #.
    #.
    #.
    #.
    #.

Solution: remove_char

def remove_char(s, c):
    """
    Return string s with all instances of character c removed.

    >>> remove_char('eggs', 'g')
    'es'
    >>>
    """
    # Hint: use an accumulating indexed loop
    index = 0
    result = ''
    while index < len(s):
        if s[index] != c:
            result = result + s[index]
        index = index + 1
    return result

Demo: order of strings

>>> 'a' < 'b'
True
>>> 'A' < 'a'
True
>>> 'a' < 'B'
False
>>> 'egg' < 'eggs'
True
>>> '0' < '1'
True
>>> '9' < '10'
False
>>> 'ab' < 'ac'
True
>>>

Rules for ordering of string

• The relational operators may all be used to compare strings
• Characters in the ASCII character set are ordered by corresponding numeric values
  • the usual alphabetical ordering between characters of the same case
  • all upper-case letters are before all lower-case letters
  • digits are in usual numeric order, before all letters
• Strings containing multiple characters are ordered lexicographically
  • in two strings the first pair of character in corresponding positions that are different determine the ordering of the strings
  • if one string is a prefix of the other, it is the lesser of the two

If the value of s is the string 'Wowzer!', what is s[7] ?

1. '!'
2. 'r'
3. none of the above, but no error
4. syntax error
5. runtime error

Answer: E

If the value of s is the string 'Wowzer!', what is s[1:3] + s[6] ?

1. 'Wow!'
2. 'ow!'
3. 'Wow'
4. none of the above, but no error
5. syntax error
6. runtime error

Answer: B

The type of an index must be

1. int
2. float
3. string
4. A or B
5. any of the above

Answer: A

What's it print?

s = 'Monty'
s[0] = 'm'
print s

1. monty
2. Monty
3. m
4. none of the above, there is an error

Answer: D

Demo: characters as numbers

>>> ord('a')
97
>>> chr(97)
'a'
>>> ord('A')
65
>>> ord('A') < ord('a')
True
>>> ord('.')
46
>>> chr(0)
'\x00'
>>> chr(255)
'\xff'
>>> chr(256)
Traceback (most recent call last):
  File "", line 1, in ?
ValueError: chr() arg not in range(256)
>>> ord('8') - ord('5')
3

Midterm grades and drop deadline

• The roster with all grades, including a mid-term estimate, will be in the Oncourse Post'em tool by next Monday
• You will receive email via Oncourse as soon as they are posted
• Wednesday next week is the withdrawal deadline
  • please see me if you have questions about staying in the course

The ord and chr functions

• All data in computers is represented as numbers
• The built-in function ord (an abbreviation for "ordinal") takes a character and returns its associated number
• The built-in function chr (an abbreviation for "character") takes an integer between 0 and 255 (inclusive) and returns its associated character
• The ordering of characters is based on their numeric ordering, that is, ord(c1) < ord(c2) if and only if c1 < c2

Exercise: char_table

def char_table():
    """
    Print a table with the numbers 0 through 255 in the first column and
    the corresponding character in the second column. (Separate the columns with
    a space.)
    """
    # FYI: All printing keyboard characters and more appear in the list.
    # Non-printing characters are automatically represented by escape sequences
    # of the form `\xHH`, where `HH` is two "hexadecimal" (base 16) digits

    # Hint: use ord in a counted loop
    #.
    #.
    #.
    #.

Solution: char_table

def char_table():
    """
    Print a table with the numbers 0 through 255 in the first column and
    the corresponding character in the second column. (Separate the columns with
    a space.)
    """
    # FYI: All printing keyboard characters and more appear in the list.
    # Non-printing characters are automatically represented by escape sequences
    # of the form `\xHH`, where `HH` is two "hexadecimal" (base 16) digits

    # Hint: use ord in a counted loop
    i = 0
    while i < 256:
        print i, chr(i)
        i = i + 1

Exercise: leap_year

def leap_year(year):
    """
    Return a boolean indicating if int year is a leap year.  A year is a
    leap year if it is evenly divisible by 4 (that is, there is no
    remainder when divided by 4), and it is not evenly divisible by 100, with
    the exception that years evenly evenly divisible by 400 are leap years.
    >>> leap_year(2006)
    False
    >>> leap_year(2004)
    True
    >>> leap_year(1900)
    False
    >>> leap_year(2000)
    True
    >>>
    """
    #...

Solution: leap_year

def leap_year(year):
    """
    Return a boolean indicating if int year is a leap year.  A year is a
    leap year if it is evenly divisible by 4 (that is, there is no
    remainder when divided by 4), and it is not evenly divisible by 100, with
    the exception that years evenly evenly divisible by 400 are leap years.
    >>> leap_year(2006)
    False
    >>> leap_year(2004)
    True
    >>> leap_year(1900)
    False
    >>> leap_year(2000)
    True
    >>>
    """
    return year % 4 == 0 and not (year % 100 == 0) or year % 400 == 0

Practice and review problems

• Solutions in the Oncourse resources
• Uncover a bit of a solution as a hint and then try to figure out the rest
• Test solutions also in Oncourse resources

Rotation ciphers

• A very old form of encryption is the rotation cipher, which replaces each letter with the result of moving it "ahead* by some fixed number of positions in the alphabet, wrapping around to 'a' after 'z'.
• A rot-n cipher replaces each character with one n positions ahead
  • for example in a rot-2 cipher, 'a' becomes 'c' and 'y' becomes 'a'
  • the rot-13 cipher is the most common, since applying it a second time returns the original text (since there are 26 = 13 * 2 letters in our alphabet)
• Any encryption that systematically substitutes one character for another, such as a rotation cipher, is very easy to defeat

Example: lower_rot13

def lower_rot13(s):
    """
    Return the result of encoding the string s by applying the 'rot-13'
    cipher to the lowercase characters in s and leaving the the others
    unchanged.

    >>> lower_rot13('abc')
    'nop'
    >>> lower_rot13('nop')
    'abc'
    >>> lower_rot13('This is an encoded message.')
    'Tuvf vf na rapbqrq zrffntr.'
    >>>
    """
    index = 0
    answer = ''
    while index < len(s):
        char = s[index]
        if 'a' <= char and char <= 'z':
            # position of s[index] in alphabet (0-based)
            n = ord(char) - ord('a')
            n = (n + 13) % 26 # rotate 13 positions
            answer = answer + chr(n + ord('a'))
        else: # don't change the character unless it is lowercase
            answer = answer + s[index]
        index = index + 1
    return answer