Unit 14 — What Does This Program Do? (Strings)

Lesson 1 — Strings and pieces in ACSL and in Python

Division: Junior and above.

A string is a row of characters: letters, digits, spaces and signs. Each character has a position, and in ACSL, as in Python, the first position is 0. len(S) is the number of characters, and S[j] is the character at position j.

For S = "ELEPHANT":

On paper, write the positions above the letters like this before you trace anything.

Three ways to cut a piece

A piece of a string (a substring) is written with a colon inside the square brackets. ACSL has exactly three forms, and only the first one means the same as in Python.

Here is the table as Python.

The trap: reading ACSL with Python's eyes

You already know Python's slices, and that is exactly the danger. Python's S[3:] starts at position 3 and runs to the end. Python's S[1:3] starts at position 1 and stops before position 3.

How long is each piece?

Counting the characters of a piece is a quick check on your work.

So S[j:j] is one character, the same as S[j], and S[j:j + 1] is two characters. Two pieces come up again and again:

• S[:len(S) - 1] is every character except the last one.
• S[len(S) - 1:] is the last len(S) - 1 characters: every character except the first one.

Joining and comparing

+ joins two strings end to end. It adds no space: "ANT" + "EATER" is "ANTEATER". == is true only when two strings are exactly the same: the same length, and the same character at every position. A space counts as a character, and so does its absence.

Checking the opening problem

Here is the password machine, translated line by line. S[3:] becomes S[len(S) - 3:] and S[1:3] becomes S[1:4].

Put it together: this program reads a word S and a number n, and makes a badge: the first n letters joined to the last n letters. It also outputs the middle: the letters left over between them, positions n through len(S) - 1 - n.

INPUT S
INPUT n
badge = S[:n] + S[n:]
middle = S[n:len(S) - 1 - n]
OUTPUT badge, middle

The first input line holds the word, in capital letters, and the second line holds n. The word has at least 2 * n + 1 letters, so the middle is never empty. It is saved as assets/l1.py.

Run it from this unit's folder, feeding it an input file:

python assets/l1.py < assets/l1/1.in

Lesson 2 — Walking along a string

Division: Junior and above.

Many programs look at a string one character at a time. The positions run from 0 to len(S) - 1, so the loop is

FOR j = 0 TO len(S) - 1
   ...S[j]...
NEXT j

The - 1 matters: ACSL's FOR includes its end value, and position len(S) does not exist. In Python it becomes for j in range(len(S)):, because range stops before its end.

Counting one character

To count how often one character appears, compare each S[j] with it and add 1 when they match.

S = "EXCELLENCE"
c = 0
FOR j = 0 TO len(S) - 1
   IF S[j] == "E" THEN
      c = c + 1
   END IF
NEXT j
OUTPUT c

Python can also walk along a string without positions, with for ch in S:. Both loops are shown here.

Counting a group of characters: vowels

To count several different characters, join the tests with || (Python's or).

IF S[j] == "A" || S[j] == "E" || S[j] == "I" || S[j] == "O" || S[j] == "U" THEN

Building a new string

A program can build a new string, starting from the empty string "" and joining one character on each pass.

S = "BASKETBALL"
T = ""
FOR j = 0 TO len(S) - 1
   IF j % 2 == 0 THEN
      T = T + S[j]
   END IF
NEXT j
OUTPUT T

Reversing: which side do you join on?

T = T + S[j] joins each character on the end, so it copies the string in order. R = S[j] + R joins each character on the front, so the first character ends up last: the string comes out reversed.

A loop that runs backwards and joins on the end reverses too:

FOR j = len(S) - 1 TO 0 STEP -1
   R = R + S[j]
NEXT j

Palindromes

A palindrome reads the same forwards and backwards, like RADAR or NOON. A program can test it in two ways:

• build the reverse and compare it with ==;
• compare each character with its mirror, S[j] with S[len(S) - 1 - j], from the outside in.

For the mirror test, the loop only needs to reach the middle: FOR j = 0 TO int(len(S) / 2) - 1.

Put it together: this program reads a word, reverses it, and says whether it is a palindrome.

INPUT S
R = ""
FOR j = 0 TO len(S) - 1
   R = S[j] + R
NEXT j
IF R == S THEN
   OUTPUT R, "YES"
ELSE
   OUTPUT R, "NO"
END IF

The input is one word in capital letters. It is saved as assets/l2.py.

Trace it by hand on each input before you run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

Lesson 3 — Moving pieces, comparing letters, shrinking strings

Division: Junior and above.

The hardest string questions put a piece inside a loop, compare letters, or chop a string shorter on every pass. Each one is traced the same way: work out the piece first, write it down, and only then compare or join it.

A piece that moves along the string

S[j:j + 1] is positions j through j + 1: a piece of two characters that moves along as j grows. The loop must stop at len(S) - 2, so that j + 1 is still inside the string.

S = "ASSESSMENT"
c = 0
FOR j = 0 TO len(S) - 2
   IF S[j:j + 1] == "SS" THEN
      c = c + 1
   END IF
NEXT j
OUTPUT c

In Python the same piece is S[j:j + 2].

Endings: the last k letters

S[k:] is the last k characters, so a loop over k looks at longer and longer endings of the word.

FOR k = 1 TO len(S)
   ...S[k:]...
NEXT k

In Python the ending is S[len(S) - k:].

Comparing letters

< and > compare two capital letters by their order in the alphabet: "A" < "B" is true, and "M" > "Z" is false. Every string in this unit that is compared this way uses capital letters only. (In Python every capital letter comes before every small letter, so "Z" < "a" is true: never mix the two when you compare.)

Comparing letters lets a program find the letter latest in the alphabet, just as it finds the largest number.

Putting two letters in order

Compare two letters and join them smaller first:

a = S[j]
b = S[j + 1]
IF a > b THEN
   T = T + b + a
ELSE
   T = T + a + b
END IF

Shrinking a string with WHILE

A WHILE loop can chop a string shorter on every pass until it is used up.

• S = S[len(S) - 1:] keeps the last len(S) - 1 characters: it drops the first character.
• S = S[:len(S) - 1] keeps the first len(S) - 1 characters: it drops the last character.

Remember to compute len(S) for the string as it is now, since it shrinks on every pass.

Put it together: this program reads a word S and a shorter pattern P. It counts how many times P appears in S, overlaps included, and outputs the count and the first position where P starts (or -1 if it never does).

INPUT S
INPUT P
m = len(P)
c = 0
first = -1
FOR j = 0 TO len(S) - m
   IF S[j:j + m - 1] == P THEN
      c = c + 1
      IF first == -1 THEN
         first = j
      END IF
   END IF
NEXT j
OUTPUT c, first

The first input line holds the word and the second holds the pattern, both in capital letters. It is saved as assets/l3.py.

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in