Programming 1

Week 13: Exercises

1. Reversing a List

You are given a class LinkedList with a single attribute head that points to the head of a linked list:

class Node:
  def __init__(self, val, next):
    self.val = val
    self.next = next
    
class LinkedList:
  def __init__(self, head):
    self.head = head

Write a method reverse() that will reverse a LinkedList.

2. Word Iterator

For this exercise, a word is any sequence of characters for which .isalpha() returns True.

Write a function words() that takes a file object (such as sys.stdin) and returns a sequence of strings representing all words in the file. The caller should be able to iterate over the strings using for, e.g.

for s in words(sys.stdin):
  print(s)

Do not return a list of all the strings; instead, generate the strings as they are needed.

3. Most Common Words

Write a program that reads text from standard input until the end of input, and reports

• the average length of each word

• the most frequent word of each length

Use the words() function from the previous exercise. Ignore case: "Potato" and "potato" should be considered as the same word. For example, with the input

a green tree and a blue sky and a brown tree     
and a blue lake and some green grass and a red flower

the program should print

average length: 3.30
length 1: a (5 occurrences)
length 3: and (5 occurrences)
length 4: tree (2 occurrences)
length 5: green (2 occurrences)
length 6: flower (1 occurrences)

4. Largest Product in a Grid

Solve Project Euler's problem 11.

5. Number Spiral Diagonals

Solve Project Euler's problem 28.