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

Remember ACSL's substring rules: S[:n] is the first n characters, S[n:] is the last n characters, and S[a:b] is positions a through b, both included. Positions start at 0.

S = "MOUNTAINEER"
A = S[:4]
B = S[3:]
C = S[2:5]
OUTPUT A + B + C

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

This program is in Python, so Python's slicing rules apply.

S = "BLUEBERRIES"
a = S[:4]
b = S[4:]
c = S[2:5]
print(a, len(b), c)

Input. None: the program reads no input.

What exactly does the program print? Work it out by hand first; write the output exactly as it appears.

This is Exercise 2's program written in ACSL pseudocode, so ACSL's substring rules apply.

S = "BLUEBERRIES"
A = S[:4]
B = S[4:]
C = S[2:5]
OUTPUT A, len(B), C

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

INPUT S
n = len(S)
m = int(n / 2)
OUTPUT S[m], S[n - 1], S[m:n - 2]

Input. S = "PROGRAMMING"

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

S = "MISSISSIPPI RIVER"
count = 0
for ch in S:
    if ch == "S" or ch == "I":
        count = count + 1
print(count, len(S))

Input. None: the program reads no input.

What exactly does the program print? Work it out by hand first; write the output exactly as it appears.

S = "STRAWBERRY"
R = ""
FOR j = 0 TO len(S) - 1
   R = S[j] + R
NEXT j
OUTPUT R[:3] + R[3:]

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

S = "ABRACADABRA"
same = 0
diff = 0
FOR j = 0 TO int(len(S) / 2) - 1
   IF S[j] == S[len(S) - 1 - j] THEN
      same = same + 1
   ELSE
      diff = diff + 1
   END IF
NEXT j
OUTPUT same, diff

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

This ACSL program reads a word in capital letters. It builds a new word from the letters that are not vowels (A, E, I, O, U), in their order, and counts the vowels it leaves out.

INPUT S
T = ""
v = 0
FOR j = 0 TO len(S) - 1
   c = S[j]
   IF c == "A" || c == "E" || c == "I" || c == "O" || c == "U" THEN
      v = v + 1
   ELSE
      T = T + c
   END IF
NEXT j
OUTPUT T, v

1. Predict: trace the program by hand on the sample input and write down what it outputs, before you look at the sample output.
2. Verify: translate the program into Python and run it on the sample input.

The input is one line holding the word. Print the new word and the number of vowels, separated by one space.

Constraints

• the word has 1 to 50 characters, all capital letters A to Z
• at least one letter of the word is not a vowel, so the new word is never empty
• Y is not a vowel

Sample Input

PROGRAMMING

Sample Output

PRGRMMNG 3

Capital letters compare by their order in the alphabet.

S = "STRUCTURES"
big = S[0]
where = 0
late = 0
for j in range(len(S)):
    if S[j] > big:
        big = S[j]
        where = j
    if S[j] >= "N":
        late = late + 1
print(big, where, late)

Input. None: the program reads no input.

What exactly does the program print? Work it out by hand first; write the output exactly as it appears.

Remember ACSL's substring rules: S[:n] is the first n characters, S[n:] is the last n characters, and S[a:b] is positions a through b, both included. Positions start at 0.

S = "CHOCOLATE"
T = ""
WHILE len(S) > 1
   T = T + S[:1]
   S = S[len(S) - 2:]
END WHILE
OUTPUT T + S

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

S = "HANNAH AND ANNA"
c = 0
FOR j = 0 TO len(S) - 2
   IF S[j:j + 1] == "AN" THEN
      c = c + 1
   END IF
NEXT j
OUTPUT c

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

S = input()
out = ""
for j in range(len(S)):
    if j % 2 == 0:
        out = out + S[j]
    else:
        out = S[j] + out
print(out)

Input

PEPPERMINT

What exactly does the program print? Work it out by hand first; write the output exactly as it appears.

A run is a group of equal letters next to each other: BOOKKEEPER has the runs B, OO, KK, EE, P, E and R. This ACSL program reads a word and finds its longest run. When several runs are equally long, it keeps the first one.

INPUT S
best = 1
bestc = S[0]
run = 1
FOR j = 1 TO len(S) - 1
   IF S[j] == S[j - 1] THEN
      run = run + 1
   ELSE
      run = 1
   END IF
   IF run > best THEN
      best = run
      bestc = S[j]
   END IF
NEXT j
OUTPUT bestc, best

1. Predict: trace the program by hand on the sample input and write down what it outputs, before you look at the sample output.
2. Verify: translate the program into Python and run it on the sample input.

The input is one line holding the word. Print the letter of the longest run and its length, separated by one space.

Constraints

• the word has 1 to 50 characters, all capital letters A to Z

Sample Input

BOOKKEEPER

Sample Output

O 2

S = "ABCABCAB"
c = 0
b = 0
FOR k = 1 TO len(S) - 1
   IF S[:k] == S[k:] THEN
      c = c + 1
      b = k
   END IF
NEXT k
OUTPUT c, b

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

S = "STRESSEDDESERTS"
i = 0
j = len(S) - 1
steps = 0
while i < j and S[i] == S[j]:
    i = i + 1
    j = j - 1
    steps = steps + 1
print(steps, i, j)

Input. None: the program reads no input.

What exactly does the program print? Work it out by hand first; write the output exactly as it appears.

Capital letters compare by their order in the alphabet.

S = "WORDGAME"
T = ""
FOR j = 0 TO len(S) - 1 STEP 2
   P = S[j:j + 1]
   IF P[0] > P[1] THEN
      T = T + P[1] + P[0]
   ELSE
      T = T + P
   END IF
NEXT j
OUTPUT T

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

A sentence is a palindrome when its letters read the same forwards and backwards once the spaces are taken out: NEVER ODD OR EVEN is one. This ACSL program reads a line, keeps its letters, reverses them and compares.

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

1. Predict: trace the program by hand on the sample input and write down what it outputs, before you look at the sample output.
2. Verify: translate the program into Python and run it on the sample input.

The input is one line of capital letters and spaces. Print YES or NO and the number of letters, separated by one space.

Constraints

• the line has 1 to 80 characters: capital letters A to Z and spaces
• the line holds at least one letter
• spaces may appear anywhere, including at the start or the end of the line, and next to each other

Sample Input

NEVER ODD OR EVEN

Sample Output

YES 14

S = "LEVELED"
c = 0
FOR a = 0 TO len(S) - 2
   FOR b = a + 1 TO len(S) - 1
      T = S[a:b]
      R = ""
      FOR k = 0 TO len(T) - 1
         R = T[k] + R
      NEXT k
      IF T == R THEN
         c = c + 1
      END IF
   NEXT b
NEXT a
OUTPUT c

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.

The program cuts the word into two halves and deals them out like cards, one from each half in turn, until the word comes back to how it started.

O = "ABCDEFGHIJ"
S = O
k = 0
first = ""
done = 0
WHILE done == 0
   h = int(len(S) / 2)
   L = S[:h]
   R = S[h:]
   S = ""
   FOR j = 0 TO h - 1
      S = S + R[j] + L[j]
   NEXT j
   k = k + 1
   IF k == 1 THEN
      first = S
   END IF
   IF S == O THEN
      done = 1
   END IF
END WHILE
OUTPUT k, first

Input. None: the program reads no input.

What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.