Module assignment: Python text analysis toolkit

Why this assignment

You have learned the tools of this module one at a time: immutable strings, lists of pieces with join, two pointers, letter counts, dict keys, run-length compression and the sliding window. A real program uses several of them at once, and the skill that matters most is choosing the right one for each part of the job. This assignment asks you to build a small text analysis tool that reads a line of text and a word, then prints six facts about them. Each fact uses one of the patterns from the module, so the program is a single place to practise all of them.

Work through it in order. The spec below is exact, because the output is checked character by character. A missing space or a wrong capital letter counts as a wrong answer, so read the output format carefully before you start.

The specification

Your program reads two lines from standard input.

• Line 1 is the text. It may be empty. It may contain spaces, punctuation and capital letters. Assume only ASCII characters, so every character has a code from 0 to 127.
• Line 2 is the word to compare with. It may be empty. It contains no spaces.

The program prints exactly six lines, in this order, with the labels spelled as shown and one space after each colon:

words: <number>
vowels: <number>
palindrome: <YES or NO>
compressed: <encoding>
longest unique run: <number>
anagrams: <number>

Each line is defined as follows.

1. words is the number of words in line 1. A word is a piece of text between spaces. Several spaces in a row count as one separator, and empty pieces do not count as words. An empty line 1 has 0 words.
2. vowels is the number of the letters a, e, i, o and u in line 1, in either upper or lower case. Every other character is ignored.
3. palindrome is YES if line 1 reads the same forwards and backwards after you ignore case and every character that is not a letter or a digit. An empty line 1 is a palindrome, so it prints YES. Otherwise print NO.
4. compressed is the run-length encoding of line 1, written as the compression lesson's method writes it, but with one change: always print the encoding, even when it is longer than the input. Characters are compared exactly, so A and a are different, and spaces count as characters. An empty line 1 gives an empty encoding, so the line is compressed: with a trailing space.
5. longest unique run is the length of the longest substring of line 1 that contains no repeated character. Spaces count as characters, and characters are compared exactly. An empty line 1 gives 0.
6. anagrams is the number of words from line 1 that are anagrams of line 2. Two strings are anagrams when they have the same length and the same count of every character. Compare exactly, so case matters, and an empty line 2 matches nothing.

Print each number as a plain integer, with no commas and no extra spaces.

Worked examples

The first example uses a short phrase and a repeated word. Check each line against the definitions above before you read the answer.

Input:

Level up at noon
noon

Output:

words: 4
vowels: 6
palindrome: NO
compressed: L1e1v1e1l1 1u1p1 1a1t1 1n1o2n1
longest unique run: 6
anagrams: 1

Walk through three of the lines. The four words are Level, up, at and noon, so the count is 4. The vowels are e and e in Level (2), u in up (1), a in at (1), and o and o in noon (2), which totals 6. The text without spaces and case is levelupatnoon, which is not a palindrome, so the answer is NO. The compressed line lists every run, including the single spaces: a run of one space is written as 1, so you see a space character followed by the digit 1. The longest unique run is six characters long, for example vel up, which has no repeats. The only anagram of noon among the words is noon itself, so the answer is 1.

The second example has three anagrams and a longer unique run.

Input:

listen silent enlist cat
tinsel

Output:

words: 4
vowels: 7
palindrome: NO
compressed: l1i1s1t1e1n1 1s1i1l1e1n1t1 1e1n1l1i1s1t1 1c1a1t1
longest unique run: 9
anagrams: 3

The three words listen, silent and enlist are anagrams of tinsel, so the answer is 3. The word cat is not.

The third example is the edge case. Test it with a blank first line.

Input:

(an empty line)
a

Output, where the compressed line ends with a space:

words: 0
vowels: 0
palindrome: YES
compressed: 
longest unique run: 0
anagrams: 0

Every count is zero, the empty text is a palindrome, and the encoding is empty. Many submissions fail this case, often with a words count of 1 or with an IndexError from text[0], so test it before you submit.

Requirements checklist

Copy this list into your notes and tick each item when you have tested it.

• The program reads line 1 and line 2 with sys.stdin.readline() or input(), so spaces inside the text survive.
• The first worked example prints exactly the six lines shown, including the spaces in compressed.
• The second worked example prints exactly the six lines shown.
• An empty line 1 prints the empty-input output, with no exception.
• An empty line 2 prints anagrams: 0, with no exception.
• Several spaces in a row do not add extra words.
• The palindrome check ignores case, spaces and punctuation, and it does not build a cleaned copy of the text.
• The compression uses a list of pieces with "".join, not +=, and always prints the encoding.
• The longest unique run uses a sliding window and a table of last positions, with no nested loop over all substrings.
• The anagram check counts characters. It does not sort, and it does not compare the words with == after sorting.
• The code has one function per fact, each with a clear name, and main only reads input and prints output.
• You have written down the time and extra space of each function in a comment.

Grading rubric

Your grade depends on how much of the output is correct on hidden inputs, which include the empty cases, repeated spaces and long lines of text. The levels below describe what each score looks like in practice.

60 percent: the program runs and gets the simple cases right. It prints six lines for the first worked example, with the correct labels in the correct order. It may fail when line 1 is empty or when line 2 is empty, and it may give a wrong answer for the palindrome or the longest unique run on unusual inputs. The code may be one long block at the top level with little structure.

80 percent: all worked examples and most edge cases are correct. It passes both worked examples exactly, including the trailing space rules. It handles repeated spaces in the word count. It does not crash on empty input. The compression uses a list and join, and the anagram check counts characters. The code has separate functions, although some may be long or unclear. It may still be slow on a line of 100,000 characters, for example because the longest unique run uses a nested loop.

100 percent: every line is correct on every input, the code is clear and the complexity is right. It passes the worked examples and all the hidden cases, including empty lines, very long lines, mixed case and punctuation. Each function is short and has one job. The palindrome check uses two pointers without a copy, the longest unique run uses a sliding window in O(n) time, and the anagram check uses a count table in O(n) time. Each function has a comment stating its time and extra space. The code has no unused variables and no repeated work inside loops.

Step-by-step plan

Build the program in stages. Test each stage on the worked examples before you move on. This order makes it easy to find where a mistake started.

1. Reading the input. Write a main that reads line 1 and line 2 and prints both with labels. Confirm that a line with spaces comes through whole. Confirm that an empty line 1 does not crash your reader. The method rstrip("\n") removes only the line break, so the spaces stay.
2. The word count. Write split_words. Split line 1 on spaces with split(" "), and keep only the pieces that are not empty. Test it on "Level up at noon" (4), on a line with three spaces between words, and on the empty line (0). Note that split() with no argument also splits on tabs, which the spec does not mention, so use split(" ").
3. The vowel count. Write count_vowels, which loops over the characters and checks each one against "aeiou" after lower(). Test it on "AEIOUaeiou" (10).
4. The palindrome check. Write is_palindrome with two pointers. Skip characters that are not letters or digits with isalnum(), and compare the rest after lower(). Test it on "A man, a plan, a canal: Panama" (YES), on "Level up at noon" (NO) and on the empty line (YES).
5. The compression. Write compress with a list of pieces and the run loop from the lesson. Make it always return the encoding, not the original. Test it on "aabbbc", which should give a2b3c1, and on the empty line, which should give an empty string.
6. The longest unique run. Write longest_unique with the window and a list of 128 last positions indexed by ord(c). Test it on "abcabcbb" (3) and on "Level up at noon" (6).
7. The anagram count. Write is_anagram with a list of 128 counts, not 26, because the text is not limited to lowercase letters. Then write the loop over the words of line 1 that counts each anagram of line 2. Test it on "listen" and "silent" (True), and on an empty line 2 (no matches).
8. Put it together. Print the six lines in the order given. Compare your output with the worked examples character by character, including the trailing space on the empty compressed line.

Hints

Try the plan first. Open a hint only when you are stuck for more than about fifteen minutes, and close it once it has helped.

Reference solution

Try the whole assignment before you open this. The reference below is one correct solution. It is written for clarity, and it follows the complexity stated in each comment. Your code may be shorter or organised differently, and it still counts as correct if it prints the same output.

import sys
 
 
def count_vowels(s):
    # O(n) time, O(1) extra space: count a, e, i, o, u in either case.
    count = 0
    for ch in s:
        if ch.lower() in "aeiou":
            count += 1
    return count
 
 
def split_words(s):
    # O(n) time, O(n) extra space: pieces between spaces, empty pieces dropped.
    return [piece for piece in s.split(" ") if piece != ""]
 
 
def is_palindrome(s):
    # O(n) time, O(1) extra space: two pointers, skipping non-alphanumerics.
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
 
def compress(s):
    # O(n) time, O(n) extra space: run-length encoding, always returned.
    parts = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        parts.append(str(j - i))
        i = j
    return "".join(parts)
 
 
def longest_unique(s):
    # O(n) time, O(1) extra space: sliding window over 128 ASCII characters.
    last = [-1] * 128
    start = 0
    best = 0
    for i, c in enumerate(s):
        code = ord(c)
        if last[code] >= start:
            start = last[code] + 1
        last[code] = i
        best = max(best, i - start + 1)
    return best
 
 
def is_anagram(a, b):
    # O(n) time, O(1) extra space: count characters, cancel out, check zeros.
    if len(a) != len(b):
        return False
    count = [0] * 128
    for x, y in zip(a, b):
        count[ord(x)] += 1
        count[ord(y)] -= 1
    return all(c == 0 for c in count)
 
 
def main():
    text = sys.stdin.readline().rstrip("\n")
    word = sys.stdin.readline().rstrip("\n")
 
    words = split_words(text)
    anagrams = sum(1 for w in words if is_anagram(w, word))
 
    print("words: " + str(len(words)))
    print("vowels: " + str(count_vowels(text)))
    print("palindrome: " + ("YES" if is_palindrome(text) else "NO"))
    print("compressed: " + compress(text))
    print("longest unique run: " + str(longest_unique(text)))
    print("anagrams: " + str(anagrams))
 
 
if __name__ == "__main__":
    main()

Stretch extension

If you finish early, extend the program so it reads many test cases. The first line holds a number t, and each following pair of lines is one case, with the same six lines of output for each. Check that your reader does not lose its place when a line is empty. Then measure the time on one line of 100,000 characters, using time.perf_counter() as you learned in the second lesson. Write one sentence on whether the time grows as you expect.

What to submit

Submit your main.py and the output of your program on the three worked examples. Compare the output with the expected text exactly. Pay attention to the trailing space in the empty case. If your output differs in any character, the difference is the first thing to fix, before you add any new feature.

What this assignment checks

• You can read input that may contain spaces and empty lines.
• You can choose between a palindrome check with two pointers, a count of characters for anagrams, a run-length encoder with a list and a sliding window for the longest unique run.
• You can keep each function small, name it for what it computes and state its time and extra space.
• You can test edge cases before you rely on a result, and you can read a mismatch against the spec to find the bug.

The reference solution is only one way to do it. A correct program that is clear, handles the edge cases and states its complexity can earn the same grade.