Chp 5 Functions

Instructions

Write each of the functions below. Use the function names specified.

As always, the unit test will crash if not all functions are defined.

The unit test is found here. Past it below your code; when run, it will generate a by-now familiar report.

Let me give you a piece of advice. Many of the functions below are easier to write if you first write yourself a helper function (or functions). Those helper functions are not required, since they will not be unit tested. Indeed whether you write any, and if you do what they are and how they're named, is up to you. But any time you realize a unit-tested function has become long and complex, you should probably split it up into multiple functions. Those smaller functions are easier to get right, and each can be individually tested in the console. Remember: write functions, make them short and single-task, and test them extensively.

Character Count

Write a function that returns the number of occurrences of a given character in a given string.

• Function name: char_count

• Parameters(s): a string and a character

• Return value(s): the number of occurrences of the character in the string

Don't use any built-in string functions.

Test Cases:

>>> char_count('spam and eggs', 'g')

2

>>> char_count('spam and eggs', 'z')

0

>>> char_count('spam and eggs', '')

0

>>> char_count('', '')

0

Reverse

Write a function named reverse that takes a string and returns that string reversed.

If you Google, you'll likely encounter [::-1]. Don't use that. Instead iterate through the argument string and build the reversed string as you go.

Test Cases:

>>> reverse('')

''

>>> reverse('abc')

'cba'

>>> reverse('   ')

'   '

Index First, Index Last

Write two functions, one named index_first and the second index_last; index_first should return the positive index of the first occurrence of a character in a string, index_last should return the positive index of the last. Each thus has two parameters. The first is a string, the second a character.

Return -1 if that character is not in the string.

Don't use any built-in string function.

Challenge: once you're written index_first and reverse, index_last can have a body one line long.

Test Cases:

>>> index_first('spam and eggs', 'g')

10

>>> index_last('spam and eggs', 'g')

11

>>> index_first('spam and eggs', 'z')

-1

>>> index_first('spam and eggs', '')

-1

>>> index_first('', 'z')

-1

>>> index_first('', '')

-1

Character Strip

Write a function named strip_char that takes a string and  a character and returns the  string with all instances of the character stripped out. Leave the string otherwise unchanged.

Don't use any built-in string functions.

Test Cases:

>>> strip_char('spam and eggs', 'g')

'spam and es'

>>> strip_char('spam and eggs', 'z')

'spam and eggs'

>>> strip_char('spam and eggs', '')

'spam and eggs'

>>> strip_char('', '')

''

Strip Non-Alpha

Write a function named to_alphanum that takes a string and and returns it stripped of all non-alphanumeric characters. The alphanumeric characters are the letters a - z, A - Z and the digits 0 - 9.

Test Cases:

>>> to_alphanum('Hello, World!')

'HelloWorld'

>>> to_alphanum('')

''

Pangrams

A sentence is a pangram if it contains every character of the alphabet at least once. The most famous English pangram is "The quick brown fox jumps over the lazy dog." Note that case does matter.

Write a function named is_pangram that takes a sentence and returns True if it's a pangram and False if it's not.

Test Cases:

>>> is_pangram('Pack my box with five dozen liquor jugs.')

True

>>> is_pangram('Pack my box with five dozen liquor pugs.')

False

Palindromes

Below is Wikipedia's definition of "palindrome", modified just a bit:

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. Famous examples include "A man, a plan, a canal, Panama!", "Amor, Roma", "race car", "stack cats", "step on no pets", "taco cat", "put it up", "Was it a car or a cat I saw?" and "No 'x' in Nixon". Notice that differences in non-alphanumeric characters or a difference in capitalization in the forward and backwards versions don't matter.

Write a Boolean-valued function named is_palindrome  that takes a string as an argument, returns True if it is a palindrome and False if it is not. 

Suggestion: before you determine whether the input string is a palindrome, strip it of all non-alphanumeric characters and then convert it to all lower-case or all upper-case.

Challenge: by the use of functions defined above, you can make the body of palindrome a one-liner.

Test Cases:

>>> is_palindrome('taco cat')

True

>>> is_palindrome('Taco, cat!')

True

>>> is_palindrome('taco dog')

False

>>> is_palindrome('')

True

>>> is_palindrome('t')

True

Anagrams

Two words are anagrams if they contain the same letters but not necessarily in the same order. (Assume that a word consists of lower-case letters of the alphabet.) For instance, "python" and "typhon" are anagrams, but "python" and "ypthan" are not. Write a Boolean-valued function named is_anagram that takes a pairs of strings and returns True if they are anagrams and False if they are not.

If  you do a Google search, you might be told to use Python's sort function. Don't do that. Yes, it works, but you'll have learned nothing if you do. I want you to struggle a little with this one. Don't accept someone else's solution.

I think this is the first of the functions that's a little tricky. There are lots of ways that it can go wrong; that's why I have so many test cases.

Test Cases:

>>> is_anagram('dog', 'god')

True

>>> is_anagram('dog', 'dogg')

False

>>> is_anagram('ddog', 'dogg')

False

>>> is_anagram('ddogg', 'ddoggz')

False

>>> is_anagram('dog', '')

False

>>> is_anagram('', '')

True

Is Int? (Extra Credit)

Write a function named is_int that takes a string and returns True when when that string can be interpreted as an int and False when it cannot.

The rules on what strings can be interpreted as an int:

1. The only characters that can occur in the string are the digits '0123456789', spaces and pluses and minuses; and the string must contain at least one digit.

2. The string can begin with or end with any number of spaces.

3. After a possible initial sequence of spaces, the string can have a sequence of pluses and minuses (with no space in between them). So '+-+12' is perfectly acceptable, though '+ -+12' is not (there's a space between the first '+' and the '-' that follows.

4. The string can have a space or spaces between the initial substring of plusses and minuses (if there is such an initial substring) and the sequence of digits that follows. But once the digits begin, there can be no spaces until after the last digit has appeared.

Test Cases:

>>>  is_int('123')

True

>>> is_int('  123')

True

>>> is_int('123   ')

True

is_int('  123   ')

True

>>> is_int('1 23')

False

>>> is_int('-123')

True

>>> is_int('--123')

True

>>> is_int('+123')

True

>>> is_int('+-+123')

True

>> is_int('+-+  123')

True

>>> is_int('  +-+  123  ')

True

>>> is_int('+ -+123')

False

>>> is_int('+-+12 3')

False

>>> is_int('-')

False

>>> is_int('')

False

Caesar Cipher

In a Caesar Cipher, each letter is shifted either forwards or backwards in the alphabet a certain, constant number of positions. If for instance we run the Caesar cipher with a shift of 3, "a" becomes "d", "b" becomes "e", "c" becomes "f", etc. Notice that if we reach the end of the alphabet, we wrap around to the start. Thus if the shift is 3, "x" becomes "a", "y" becomes "b" and "z" becomes "c".

Write a function named caesar_cipher that implements a Caesar cipher. It should take a string and a number of positions (an int) to shift; and it should return a string.

Allow for the possibility of both negative and positive (and 0) shifts. Place no restriction of the size of the shift. 26 is acceptable (but a bore). So is 8916100448256. And -3451745901230.

Assume that I'll use only lower case letters.

Test Cases:

>>> caesar_cipher('spam', 36)

'czkw'

>>> caesar_cipher('eggs', -12)

'suug'

>>> caesar_cipher(caesar_cipher('spam', 12), -12)

'spam'

>>> caesar_cipher('', 0)

''

Word List

Write a function named word_list that returns a list of the words in a strings. Words are separated by spaces. 

Recall that if we wish to add an object named obj to the a list named lst, we do this: lst.append(obj). Don't use any built-in list function (like split).

Note that your function should be abe to handle words separated by multiple spaces.

Test Cases:

>>> word_list('spam and eggs')

['spam', 'and', 'eggs']

>>> word_list('spam  and   eggs') # multiple spaces between words

['spam', 'and', 'eggs']

>>> word_list('   ')

[]

>>> word_list('')

[]

Space Cull

Write a function named space_cull that strips all extraneous spaces from a string. What are those?

• All spaces at the start or the end of the string are extraneous.

• Any more than one space between words is extraneous.

Here's  a suggestion: run your input through word_list and then work with the output of that. This makes for an elegant solution. Please don't make use of any built-in Python function that removes spaces.

Test Cases:

>>> space_cull('  spam and eggs') # extra spaces at start

'spam and eggs'

>>> space_cull('spam and eggs  ') # extra spaces at end

'spam and eggs'

>>> space_cull('  spam and eggs  ') # extra spaces at both start and end

'spam and eggs'

>>> space_cull('spam  and   eggs') # extra interior spaces

'spam and eggs'

>>> space_cull('  ') # everything is an extra space!

''

>>> space_cull('')

''

Pyg Latin

Write a function named pyg_latin that takes a string and returns its Pyg-Latin translation.

The rules:

• 1. If a word begins with a vowel, add "-way" to the end. Example: "ant" becomes "ant-way".

  2. If a word begins with a consonant cluster, move that cluster to the end and add "ay" to it. Examples: "pant" becomes "ant-pay" and "plant" becomes "ant-play".

It's obvious, right, that you should first run the input string through word_list?

Test Cases:

>>> pyg_latin('spam and eggs')

'am-spay and-way eggs-way'

Balanced Parentheses

Write a Boolean-valued function named is_balanced that takes a string and returns True if the parentheses within in are balanced and False if they are not. 

What does it mean to say that parentheses are balanced? It means that open and close parentheses can be paired up in such a way that each open parenthesis is paired with a close parenthesis that comes after.

Do note that the input string will likely contain more than just parentheses.

Test Cases:

>>> is_balanced('')

True

>>> is_balanced(')')

False

>>> is_balanced('()')

True

>>> is_balanced(')(')

False

>>> is_balanced('((2 - 3) + 4) * 3 * (4 + 5)')

True

Here's a cryptic hint:

(()) → 0, 1, 2, 1, 0   Good!

(())) → 0, 1, 2, 1   Bad!

))(( → 0, -1   Bad!

(()()))( → 0, 1, 2, 1, 2, 1, 0, -1   Bad!

Binary to Decimal

Write a function that converts from binary to decimal. 

• Function name: bi_to_dec

• Parameter(s): a string of 0's and 1's

• Return value(s): the decimal conversion of the argument string (which should be of type int)

We'll discuss binary in class, but the Wikipedia article is an excellent resource. The section titled "Binary counting" has what you need.

Test Cases:

>>> bi_to_dec('0')

0

>>> bi_to_dec('1')

1

>>> bi_to_dec('10')

2

>>> bi_to_dec('1011001')

89

Palindromic Sequence

The palindromic sequence begins:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, ...

Each number is palindromic; that is, each is the same read forward and back. Moreover, the sequence contains all palindromic numbers, and it contains them in order.

Write a function named pal_seq that takes the integer n and returns the nth palindromic number. We'll assume that the index of the first element of the sequence is 1.

Now, this can be done in various ways. Here's an ugly, brute-force algorithm: simply count from 0 and as you do determine which are palindromes. I challenge you to do better.

Test Cases:

>>> pal_seq(1)  

1

>>> pal_seq(100) 

919

>>> pal_seq(500) 

40104

The Self-Descriptive Sequence

The first member of  our sequence is '0'. (Note that it's a string.)

The second member is '10' (again a string), which tells us that the previous member had 1 of the digit 0.

The third member is '1110', which reads "the previous member had 1 of the digit 1 followed by 1 of the digit 0".

The fourth, fifth and sixth members of the sequence are '3110' (the previous  member had 3 of the digit 1 followed by 1 of the digit 0), '132110' (the previous member had 1 of the digit 3 followed by 2 of  the digit 1 followed by 1 of the digit 0) and '1113122110'  (the previous member had 1 of the digit 1 followed by 1 of the digit 3 followed by 1 of the digit 2 followed by 2 of the digit 1 followed by 1 of the digit 0).

Notice how we break each member up into same-digit chunks to find the next member. So we'd chunk the sixth member as 111-3-1-22-11-0, which would give us '311311222110' for the seventh.

Write a function named des_seq that takes some positive integer n and returns the nth member of the sequence above. (We'll count like mathematicians. The initial member of the sequence is member number 1.)

A word of advice: write your a helper function that takes a string and turns it into a list of chunks of that list that consist of a single character repeated. For instance, it would take '112223' and return ['11', '222', '3'].

Test Cases:

>>> des_seq(1)

'0'

>>> des_seq(2) 

'10'

>>> des_seq(6) 

'1113122110'

>>> des_seq(12) 

'11131221131211132221232112111312111213322110'

Pangram Count

Create a file named 'pgram_file.txt'. Follow this link. Place the contents of the file you find there in pgram_file.txt.

Now write a function named pangram_count that examines the contents of pgram_file.txt and returns the number of sentences in it that are pangrams. Assume that sentences are separated by periods.

Note that a sentence may span several lines of the text file.

Your function should begin:

def pangram_count(file_name):

    pfile = open(file_name, 'r')

You'll call the function like this:

>>> pangram_count('pgram_file.txt')

I won't provide test cases here. You can easily make your own.

On the day  you turn in the functions, I'll ask that you change the contents of pgram_file.txt.

A final word: in my function, I read the entire contents of the file in at once with pfile.read(). That returns the whole of the  file as a single string.

L-Systems

(What follows is a rework of the chapter on L-Systems in How to Think Like a Computer Scientist: Interactive Edition. Thank you to the authors.)

Here's an apparently pointless little exercise. Start with a string. Traverse it, and every time you find a certain character, replace it with a certain sequence of characters. Repeat. For instance, let's say we start with "F" and replace any "F" we find with "F-F++F-F". (Why that? Don't worry about that yet. All will become clear.) Here's what we get if we traverse twice.

1.  "F"

2. "F-F++F-F"

3. "F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F"

We were given the initial "F". Wh then stepped through it and replaced each "F" with "F-F++F-F".  The result was "F-F++F-F". We then stepped through that result -  "F-F++F-F" -  and as before replaced each "F" with "F-F++F-F". (Everything that wasn't an "F" was left as is.) The new result was "F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F". This could of course be carried on as long as we like.

A system like the one described - one where we're given a start string and a replacement rule we iteratively apply, first to the start string and then to the previous output of the rule - is called a L-System. Google that.

(What's been done here is characteristic of what mathematicians  call "iteration". When mathematicians use that word, they mean a process wherein the output of any one stage becomes the input of the next stage.  Newton's Method (a function from the Selection chapter) is a great example; at each stage, the previous approximation is used in the computation of the new, better approximation.) 

I want you to write a series of functions, one for each L-System described below.  Each of your functions will have a single parameter - the number of iterations the L-System should produce. Each should return the result of final iteration. For instance, if we name the function that produces the L-System described above snowflake, then:

>>> snowflake(1)

'F'

>>> snowflake(2)

'F-F++F-F'

>>> snowflake(3)

'F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F'

Koch Snowflake

Function Name: snowflake

Initial Value: "F"

Replacement Rule: "F" becomes "F-F++F-F"

Hilbert Curve

Function Name: hilbert

Initial Value: "L"

Replacement Rule: "L" becomes "+RF-LFL-FR+", "R" becomes "-LF+RFR+FL-"

Dragon Curve

Function Name: dragon

Initial Value: "FX"

Replacement Rule: "X" becomes "X+YF+", "Y" becomes "-FX-Y"

Arrowhead Curve

Function Name: arrowhead

Initial Value: "YF"

Replacement Rule: "X" becomes "YF+XF+Y",  "Y" becomes "XF-YF-X"

Peano-Gosper Curve

Function Name: peano_gosper

Initial Value: "FX"

Replacement Rule: "X" becomes "X+YF++YF-FX--FXFX-YF+",  "Y" becomes "-FX+YFYF++YF+FX--FX-Y"

Sierpinski Triangle

Function Name: sierpinski_tri

Initial Value: "FXF--FF--FF"

Replacement Rule: "F " becomes "FF", "X" becomes "--FXF++FXF++FXF--"

Test Cases:

>>> hilbert(3)

'+-LF+RFR+FL-F-+RF-LFL-FR+F+RF-LFL-FR+-F-LF+RFR+FL-+'

>>> dragon(5)

'FX+YF++-FX-YF++-FX+YF+--FX-YF++-FX+YF++-FX-YF+--FX+YF+--FX-YF+'

>>> arrowhead(4)

'XF-YF-XF+YF+XF+YF+XF-YF-XF-YF+XF+YF-XF-YF-XF-YF+XF+YF-XF-YF-XF+YF+XF+YF+XF-YF-XF'

>>> peano_gosper(2)

'FX+YF++YF-FX--FXFX-YF+'

>>> sierpinski_tri(3)

'FFFF--FF--FXF++FXF++FXF--FF++FF--FXF++FXF++FXF--FF++FF--FXF++FXF++FXF--FF--FFFF--FFFFFFFF--FFFFFFFF'