Unit 3 — What Does This Program Do? (Branching)

Lesson 1 — Reading ACSL pseudocode

Division: Junior and above.

An ACSL program is a list of statements, one per line. The ones you meet most:

• INPUT a, b reads values. In a short-answer question the values are given to you, for example "the input is a = 26 and b = 9".

• x = expression stores a value, exactly as in Python.

• OUTPUT x prints. OUTPUT x, y prints both values on one line; in this book, as in Python's print(x, y), they are separated by one space.

• IF … THEN … ELSE IF … THEN … ELSE … END IF makes decisions. END IF marks where the IF stops, the job indentation does in Python.

• WHILE … END WHILE and FOR … NEXT repeat. They are in Lesson 3.

The dialect table

Python and ACSL pseudocode agree on most things. This table lists the ones you must translate, and the traps.

One more pair: ACSL's || is Python's or, which is true when at least one side is true.

ACSL works out an expression in this order: ! first, then ^, then *, / and %, then + and -, then the comparisons, then &&, and || last. Python's order is the same, except that not comes after the comparisons. When you translate, add brackets to make the order you mean certain.

Real division and the remainder

Python has three division tools. ACSL pseudocode has only / and %; a whole-number quotient is written int(a / b). Predict each line, then check it against the output.

Powers

ACSL writes a power with ^; Python writes it with **. A power is worked out before *, /, + and -.

ACSL int is a floor

ACSL's int(x) gives the greatest integer that is less than or equal to x. For 3.7 that is 3, and for -3.7 it is -4, because -4 is below -3.7 on the number line and -3 is above it.

Python's int(x) does something else: it chops off the decimal part, which moves a negative number up toward zero. To get ACSL's int, use floor from Python's math module. You met import with the random module; import math loads the math tools the same way.

Absolute value and square roots

abs(x) works the same in both languages. ACSL's sqrt(x) is math.sqrt(x) in Python, and it always gives a float.

Not, and, or

ACSL's !, && and || are Python's not, and and or. Put brackets after not, so it applies to the whole comparison.

Translating the opening problem

Here is the problem from the top of the unit, translated line by line. Here the input values are written into the program, as a = 26 and b = 9, in place of reading them with input().

The full program, reading a and b from one input line, 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

The files assets/l1/2.in to assets/l1/4.in send the program down each of the other branches. Trace each one by hand first, then check with the program.

Lesson 2 — Tracing branches

Division: Junior and above.

To trace a program is to run it by hand, the way the computer would. Keep a small table with one column per variable. Go line by line; whenever a variable changes, write its new value in its column. At an IF, work out the condition, write down true or false, and follow only the branch that runs.

Tracing the opening problem

Input: a = 26, b = 9.

The first condition is true, so the ELSE IF and ELSE branches are skipped entirely. The answer is 15. Check it against assets/l1/1.out.

Only the first true branch runs

In an IF … ELSE IF … ELSE chain the conditions are tested from the top. The first true one runs its branch, and the rest are never looked at, even if they are true too. Predict the output, then check it.

Separate IFs all get tested

Three separate IF statements are not a chain. Each one is tested in turn, and each test sees the values left by the ones before it.

Nested conditions

An IF can sit inside a branch of another IF. The inner test only happens if the program reaches it. In ACSL pseudocode, each IF has its own END IF, which tells you where it stops.

IF x > y THEN
   IF x % 2 == 0 THEN
      z = x - y
   ELSE
      z = x + y
   END IF
ELSE
   z = y * 2
END IF

And before or

In both languages, && (and) is worked out before || (or), just as * comes before +.

Whole-number arithmetic

Many branching questions pull digits apart with % and whole-number division. In ACSL that division is int(n / 10); in Python, n // 10 gives the same whole number.

Put it together: this program reads three whole numbers, the side lengths of a triangle, and prints what kind of triangle they make. It uses a chain, a nested IF, and and/or together. 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 — Loops, arrays, grids and strings

Division: Intermediate and above.

Junior students meet loops, arrays and strings in later contests. Intermediate and Senior students are tested on all of them in Contest 1, so this lesson covers each one in ACSL pseudocode and in Python. Tracing works the same way: a table of variables, one line at a time.

FOR loops include the end

FOR k = 1 TO 9 STEP 2
   OUTPUT k
NEXT k

This outputs 1, 3, 5, 7, 9: ACSL's FOR includes the end value 9. Python's range stops before its end, so the translation is range(1, 10, 2): one more than the end. Without STEP, the step is 1.

A negative STEP counts down. FOR k = 20 TO 2 STEP -6 visits 20, 14, 8, 2. Counting down, Python's range needs an end one less than ACSL's, so the translation is range(20, 1, -6).

WHILE loops

WHILE condition … END WHILE is Python's while. The test comes before each pass, so the body can run zero times.

Arrays

An ACSL array is written with round brackets: A(3) is the item at position 3. A program says where its positions start. Most past ACSL problems start at A(1); some start at A(0).

Python lists always start at position 0. When an ACSL array starts at 1, the easy translation is to put an unused 0 at position 0, so that A(1) is A[1].

A(1) = 6, A(2) = 3, A(3) = 8, A(4) = 5
FOR j = 1 TO 3
   IF A(j) > A(j + 1) THEN
      A(j + 1) = A(j + 1) + A(j)
   END IF
NEXT j
OUTPUT A(4)

2D arrays: grids

A 2D array is a grid of rows and columns, like a spreadsheet or a game board. ACSL writes one box as A(r, c): row r, column c, always in that order.

In Python a grid is a list of lists: a list of rows, each row a list. grid[r] is a whole row, and grid[r][c] is one box in it.

To visit every box, use nested loops: rows on the outside, columns on the inside. This order, left to right along row 0, then row 1, and so on, is how you read a page.

A program often builds a grid from a rule. Build each row with append, then append the row to the grid. Here each box holds r * c, and, as in most ACSL problems, rows and columns start at 1: row 0 and column 0 are unused zeros.

FOR r = 1 TO 3
   FOR c = 1 TO 4
      A(r, c) = r * c
   NEXT c
NEXT r

Some programs walk the grid a different way: down each column. Swap the loops: columns outside, rows inside. This adds up column 1 of the grid above: 1 + 2 + 3.

Strings

In ACSL, as in Python, a string's positions start at 0, len(S) is its length, S[j] is one character, and + joins strings. Substrings are where the two differ. ACSL's rules, for S = "ACSL WDTPD":

A Python slice S[a:b] stops before position b, and S[a:] starts at position a. So only the first form is written the same way. When a Python program is shown, use Python's rules; when ACSL pseudocode is shown, use ACSL's.

Real division inside a loop

A real division can change a whole number into a decimal, and ACSL's int then rounds down, even below zero.

Put it together: this program reads a grid of whole numbers and prints the column, counted from 1, with the largest total, and that total. The first input line holds the numbers of rows and columns; each following line is one row. If two columns tie, the one further left wins. It is saved as assets/l3.py.

Run it from this unit's folder:

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