Unit 10 — What Does This Program Do? (Arrays)

Slide 1 of 72

The problem: Who ends up in locker 2?

Six lockers stand in a row, numbered 1 to 6, and each one holds a numbered token. At the end of the day the caretaker runs this ACSL program. It swaps the tokens around, and then it adds up a score from the lockers with odd numbers:

A(1) = 4, A(2) = 9, A(3) = 2, A(4) = 7, A(5) = 5, A(6) = 1
FOR k = 1 TO 3
   t = A(k)
   A(k) = A(7 - k)
   A(7 - k) = t
NEXT k
s = 0
FOR k = 1 TO 6 STEP 2
   s = s + k * A(k)
NEXT k
OUTPUT A(2), s

What is output?

This is the Junior What Does This Program Do? question for Contest 3: a short program that works on an array, a numbered row of boxes, traced by hand with no computer. The loops are the ones you already know from Unit 6. What is new is that one line can change one box of the row, and the box it changes is worked out from a counter, as in A(7 - k). Lose track of a single box and every line after it goes wrong.
This unit teaches it in three steps: how ACSL writes arrays and how to turn them into Python lists (Lesson 1), how programs change an array in place: swapping, reversing, shifting and running totals (Lesson 2), and how to trace a grid of rows and columns, including its diagonals (Lesson 3). Write down your first guess now. You will check it in Lesson 1 and trace it by hand in Lesson 2.
- Read ACSL arrays A(i) and grids A(r, c), and check where the positions start before you trace.
- Translate an array that starts at 1 into Python, with an unused box at position 0.
- Trace in-place changes box by box: swaps, reversals, shifts, rotations and running totals.
- Trace grids by rows and by columns, along diagonals and triangles, and across neighbours.
Lesson 1 — Arrays in ACSL and in Python

Division: Junior and above.

An array is a row of boxes that share one name. ACSL writes one box with round brackets: A(3) is the box at position 3 of the array A. The number in the brackets is the position (also called the index); what is stored in the box is its value.

A line such as
```
A(1) = 4, A(2) = 9, A(3) = 2
```
fills three boxes at once, from left to right. Everything else is the dialect you learned in Units 3 and 6: FOR includes its end value, % is the remainder, and int(x) rounds down.
Where do the positions start?

A program says where its positions start. Most ACSL programs use A(1) as the first box; some start at A(0). Read the program and use the positions it uses: never shift them yourself.

A Python list always starts at position 0. When an ACSL array starts at 1, put an unused 0 in front, so that ACSL's A(1) is Python's A[1].
```
A = [0, 4, 9, 2, 7, 5, 1]
print(A[1], A[2], A[6])
print(len(A))
```
Scroll the code for more ↓
Output
```
4 9 1
7
```
A[2] is 9, the token in locker 2, exactly as in the ACSL program. len(A) is 7, not 6, because it counts the unused box at position 0 too. When an ACSL array starts at 0, no extra box is needed: ACSL's A(0) is Python's A[0].
Filling an array with a formula

Many programs fill the boxes with a loop instead of listing the values.
```
FOR i = 1 TO 6
   A(i) = i * i - 4 * i
NEXT i
```
On paper, draw a row of six boxes, write the positions above them, and fill them in one pass at a time. In Python, start from the unused box and append one value per pass.
```
A = [0]
for i in range(1, 7):
    A.append(i * i - 4 * i)
print(A)
print(A[3], A[6])
```
Scroll the code for more ↓
Output
```
[0, -3, -4, -3, 0, 5, 12]
-3 12
```
Because the list already holds position 0, the first append lands at position 1, the next at position 2, and so on: each value goes into the box its i names. The row is -3, -4, -3, 0, 5, 12, so A(3) is -3 and A(6) is 12.
Positions worked out from a counter

The position in the brackets can be any expression. A(i + 1) is the box after box i, and A(i - 1) is the box before it. In an array of n boxes, A(n + 1 - i) is box i counted from the other end: its mirror.

For n = 6:

i 1 2 3 4 5 6

n + 1 - i 6 5 4 3 2 1

Work out the position first, then look in that box.

`i`	1	2	3	4	5	6
`n + 1 - i`	6	5	4	3	2	1

A = [0, 4, 9, 2, 7, 5, 1]
n = 6
for i in range(1, n + 1):
    print(i, n + 1 - i, A[i] - A[n + 1 - i])

Output

The differences are 3, 4, -5, 5, -4, -3. The second half is the first half with the signs turned round, because each pair of boxes meets twice: once from each end. In a trace, write the computed position in its own column, next to the value found there.
Reading an array from the input

A programming problem gives the numbers in the input. ACSL writes a read into each box as
```
INPUT n
FOR i = 1 TO n
   INPUT A(i)
NEXT i
```
In Python, read the whole line of numbers, split it, and append each one after the unused box. Here the line is typed in, since nobody is here to type it.

parts = "3 8 1 6".split()
A = [0]
for piece in parts:
    A.append(int(piece))
n = len(A) - 1
print(n, A[1], A[n])

Output

4 3 6

n is len(A) - 1, one less than the length, because of the unused box. A[n] is the last box, 6.

A value used as a position

A value from one array can be the position in another. Here C(v) counts how many times the value v appears in A: a tally.
```
FOR v = 0 TO 5
   C(v) = 0
NEXT v
FOR i = 1 TO 8
   C(A(i)) = C(A(i)) + 1
NEXT i
```
Work out the inner brackets first: C(A(3)) means "look up A(3), then use that value as the position in C".

A = [0, 2, 5, 2, 0, 3, 2, 5, 1]
C = []
for v in range(6):
    C.append(0)
for i in range(1, 9):
    C[A[i]] = C[A[i]] + 1
print(C)

Output

[1, 1, 3, 1, 0, 2]

C starts at position 0 because 0 is one of the values. The tally is 1, 1, 3, 1, 0, 2: the value 2 appears three times and 4 never does. C needs a box for every value that can turn up; a value of 6 here would be a position past the end of C.
Checking the opening problem

Here is the locker program, translated line by line. Lesson 2 shows how to get the same answer by hand.

A = [0, 4, 9, 2, 7, 5, 1]
for k in range(1, 4):
    t = A[k]
    A[k] = A[7 - k]
    A[7 - k] = t
s = 0
for k in range(1, 7, 2):
    s = s + k * A[k]
print(A[2], s)

Output

5 67

FOR k = 1 TO 6 STEP 2 became range(1, 7, 2), so k takes 1, 3, 5. Did it match your guess? Running a translation is how you check an answer while you practise; in the contest you trace it by hand.

Put it together: this program reads n numbers and pairs each box with its mirror: A(1) with A(n), A(2) with A(n - 1), and so on. It prints the largest pair sum and the first i that gives it. When n is odd, the middle box has no partner and is left out.

INPUT n
FOR i = 1 TO n
   INPUT A(i)
NEXT i
best = A(1) + A(n)
at = 1
FOR i = 2 TO int(n / 2)
   IF A(i) + A(n + 1 - i) > best THEN
      best = A(i) + A(n + 1 - i)
      at = i
   END IF
NEXT i
OUTPUT best, at

The first input line holds n (at least 2), and the second line holds the n numbers. It is saved as assets/l1.py.

Try it

n = int(input())
parts = input().split()
A = [0]
for piece in parts:
    A.append(int(piece))
best = A[1] + A[n]
at = 1
for i in range(2, n // 2 + 1):
    if A[i] + A[n + 1 - i] > best:
        best = A[i] + A[n + 1 - i]
        at = i
print(best, at)

Run it from this unit's folder, feeding it an input file:
```
python assets/l1.py < assets/l1/1.in
```
best starts from the real first pair, never from a made-up 0, so an array of negative numbers (assets/l1/4.in) still works. With n = 2 (assets/l1/2.in) the loop is FOR i = 2 TO 1, which runs zero times, and the first pair is the answer.
Lesson 2 — Changing an array in place

Division: Junior and above.

To trace an array program, draw the row of boxes with the positions above them. When a line changes a box, cross out the old value and write the new one. Every later line must use the new value: that is where most mistakes happen.

Sum, count and the largest value

The loops from Unit 6 work on arrays too: the counter runs over the positions.

A(1) = 6, A(2) = -2, A(3) = 9, A(4) = 4, A(5) = 9, A(6) = -5
big = A(1)
at = 1
neg = 0
FOR i = 1 TO 6
   IF A(i) > big THEN
      big = A(i)
      at = i
   END IF
   IF A(i) < 0 THEN
      neg = neg + 1
   END IF
NEXT i
OUTPUT big, at, neg

A = [0, 6, -2, 9, 4, 9, -5]
big = A[1]
at = 1
neg = 0
for i in range(1, 7):
    if A[i] > big:
        big = A[i]
        at = i
    if A[i] < 0:
        neg = neg + 1
print(big, at, neg)

Output

9 3 2

9 is in box 3 and again in box 5. With >, the tie does not replace the best, so at stays 3; with >=, it would move on to 5. big starts at A(1), a real value, so the program works even if every value is negative.
Swapping two boxes

To swap two boxes you need a third place to hold one value for a moment.
```
t = A(i)
A(i) = A(j)
A(j) = t
```
Without t, the first line would wipe out the old A(i) before it could be copied.
```
A = [0, 4, 9, 2]
A[1] = A[3]
A[3] = A[1]
print(A)
B = [0, 4, 9, 2]
t = B[1]
B[1] = B[3]
B[3] = t
print(B)
```
Scroll the code for more ↓
Output
```
[0, 2, 9, 2]
[0, 2, 9, 4]
```
The first try gives 2, 9, 2: the 4 is lost, and both boxes end up holding 2. With t, the 4 and the 2 really change places. When a question swaps without a spare variable, that is usually the trap.
Reversing: swap to the middle and stop

To reverse an array of n boxes, swap each box with its mirror, A(n + 1 - i). The loop must stop at the middle, int(n / 2). If it ran all the way to n, every pair would be swapped twice, and the array would end where it started.

A = [0, 3, 8, 1, 6, 4]
n = 5
for i in range(1, n // 2 + 1):
    t = A[i]
    A[i] = A[n + 1 - i]
    A[n + 1 - i] = t
print(A)
B = [0, 3, 8, 1, 6, 4]
for i in range(1, n + 1):
    t = B[i]
    B[i] = B[n + 1 - i]
    B[n + 1 - i] = t
print(B)

Output

[0, 4, 6, 1, 8, 3]
[0, 3, 8, 1, 6, 4]

With n = 5, int(5 / 2) is 2: box 1 swaps with box 5, box 2 with box 4, and the middle box 3 stays put. The second loop reverses the array and then reverses it back, so B is unchanged.
Tracing the opening problem

In the locker program, k runs 1, 2, 3, which is int(6 / 2): exactly to the middle.

k 7 - k swap boxes 1 to 6 after the pass

start 4 9 2 7 5 1

1 6 4 and 1 1 9 2 7 5 4

2 5 9 and 5 1 5 2 7 9 4

3 4 2 and 7 1 5 7 2 9 4

So A(2) is 5. The second loop takes k = 1, 3, 5: 1 * 1 + 3 * 7 + 5 * 9 is 1 + 21 + 45, which is 67. The output is 5 67.
Shifting: the direction of the loop matters

To shift every value one box to the left, copy each box from its right-hand neighbour: A(i) = A(i + 1). Going left to right works, because each box is read before it is overwritten.

To shift to the right, A(i) = A(i - 1), the loop must go from right to left, FOR i = n TO 2 STEP -1. Going left to right copies the first value into every box.

`k`	`7 - k`	swap	boxes 1 to 6 after the pass
start			`4 9 2 7 5 1`
1	6	`4` and `1`	`1 9 2 7 5 4`
2	5	`9` and `5`	`1 5 2 7 9 4`
3	4	`2` and `7`	`1 5 7 2 9 4`

A = [0, 4, 1, 6, 3, 8]
for i in range(5, 1, -1):
    A[i] = A[i - 1]
print(A)
B = [0, 4, 1, 6, 3, 8]
for i in range(2, 6):
    B[i] = B[i - 1]
print(B)

Output

[0, 4, 4, 1, 6, 3]
[0, 4, 4, 4, 4, 4]

Going right to left gives 4, 4, 1, 6, 3: every value moved one box right, and box 1 still holds its old value. Going left to right, box 2 gets 4, then box 3 copies the new box 2, and so on, so B is all 4s.
Rotating: nothing falls off

A rotation is a shift where the value that falls off one end comes back in at the other. Save it in t before the shift, then put it in the empty box.
```
t = A(1)
FOR i = 1 TO n - 1
   A(i) = A(i + 1)
NEXT i
A(n) = t
```

A = [0, 4, 1, 6, 3, 8]
n = 5
for k in range(2):
    t = A[1]
    for i in range(1, n):
        A[i] = A[i + 1]
    A[n] = t
print(A)

Output

[0, 6, 3, 8, 4, 1]

Two rotations to the left give 6, 3, 8, 4, 1. A rotation of n boxes, done n times, brings every value back home.

A pass that uses its own changes

A(i) = A(i) + A(i - 1) looks at the box before, which the same loop has just changed. So each box becomes the total of everything up to it: a running total, or prefix sum.
```
A = [0, 2, 5, 1, 4, 3]
for i in range(2, 6):
    A[i] = A[i] + A[i - 1]
print(A)
```
Scroll the code for more ↓
Output
```
[0, 2, 7, 8, 12, 15]
```
The boxes become 2, 7, 8, 12, 15. Box 3 adds the new box 2 (7), not the old one (5). In a trace, always read from the row as it is now, with the crossings-out.

Put it together: this program reads n numbers and a count k, rotates the array k places to the right, and prints the whole array on one line.

INPUT n, k
FOR i = 1 TO n
   INPUT A(i)
NEXT i
FOR j = 1 TO k
   t = A(n)
   FOR i = n TO 2 STEP -1
      A(i) = A(i - 1)
   NEXT i
   A(1) = t
NEXT j

The first input line holds n and k; the second holds the n numbers. To print the values on one line, the Python program builds the line as a string, adding a space and the next value each time. It is saved as assets/l2.py.

Try it

first = input().split()
n = int(first[0])
k = int(first[1])
parts = input().split()
A = [0]
for piece in parts:
    A.append(int(piece))
for j in range(k):
    t = A[n]
    for i in range(n, 1, -1):
        A[i] = A[i - 1]
    A[1] = t
line = str(A[1])
for i in range(2, n + 1):
    line = line + " " + str(A[i])
print(line)

Trace it by hand on each input before you run it from this unit's folder:
```
python assets/l2.py < assets/l2/1.in
```
Rotating n boxes n times changes nothing (assets/l2/3.in), so rotating 7 times is the same as rotating 2 times when n is 5 (assets/l2/4.in). With k = 0 (assets/l2/2.in) the outer loop runs zero times.
Lesson 3 — Grids: arrays with rows and columns

Division: Junior and above.

A 2D array is a grid, like a spreadsheet. ACSL writes one box as A(r, c): row r, then column c, always in that order. As in Unit 3, a Python grid is a list of rows, and A(r, c) becomes A[r][c]. When the rows and columns start at 1, give the grid an unused row 0 and an unused column 0.
Filling a grid with a formula
```
FOR r = 1 TO 3
   FOR c = 1 TO 4
      A(r, c) = r + 2 * c
   NEXT c
NEXT r
```
On paper, draw the grid with the row numbers down the side and the column numbers across the top. In Python, build each row with append, then append the row to the grid.

A = []
for r in range(4):
    row = []
    for c in range(5):
        row.append(r + 2 * c)
    A.append(row)
for r in range(1, 4):
    print(A[r][1], A[r][2], A[r][3], A[r][4])

Output

3 5 7 9
4 6 8 10
5 7 9 11

The loops start at 0, so the unused row 0 and column 0 exist, and after that A[r][c] is exactly ACSL's A(r, c). Row 1 is 3 5 7 9: along a row, c goes up by 1 and the value by 2. Down a column, r goes up by 1 and the value by 1.
Rows or columns: which loop is outside?

To add up one row, keep r fixed and let c run. To add up one column, keep c fixed and let r run. So for row totals the r loop is outside; for column totals the c loop is outside.

A = [[0, 0, 0, 0],
     [0, 5, 1, 7],
     [0, 2, 8, 3],
     [0, 6, 4, 9]]
for r in range(1, 4):
    total = 0
    for c in range(1, 4):
        total = total + A[r][c]
    print("row", r, total)
for c in range(1, 4):
    total = 0
    for r in range(1, 4):
        total = total + A[r][c]
    print("column", c, total)

Output

row 1 13
row 2 13
row 3 19
column 1 13
column 2 13
column 3 19

total = 0 sits inside the outer loop, so each row or column starts a fresh total. Watch for programs that write A(c, r) where you expect A(r, c): the loops are the same, but the program walks down columns instead of along rows.
Diagonals

In a square grid of size n, the main diagonal runs from top left to bottom right: the boxes A(i, i). The other diagonal runs from top right to bottom left: the boxes A(i, n + 1 - i). Each needs only one loop, because the row and the column are both worked out from i.

A = [[0, 0, 0, 0],
     [0, 5, 1, 7],
     [0, 2, 8, 3],
     [0, 6, 4, 9]]
n = 3
d1 = 0
d2 = 0
for i in range(1, n + 1):
    d1 = d1 + A[i][i]
    d2 = d2 + A[i][n + 1 - i]
print(d1, d2)

Output

22 21

The main diagonal is 5, 8, 9, and the other is 7, 8, 6. When n is odd, the centre box (8 here) is on both diagonals and is counted in both sums.

Triangles of the grid

The boxes with c < r are below the main diagonal, and the boxes with c > r are above it. A program visits a triangle by letting the inner loop's start or end use the outer counter, as in Unit 6: FOR c = 1 TO r visits the diagonal and everything below it.

A = [[0, 0, 0, 0],
     [0, 5, 1, 7],
     [0, 2, 8, 3],
     [0, 6, 4, 9]]
low = 0
for r in range(1, 4):
    for c in range(1, r + 1):
        low = low + A[r][c]
print(low)

Output

Row 1 gives 5, row 2 gives 2 + 8, and row 3 gives 6 + 4 + 9, which makes 34. Write the inner end at the start of each row of your trace, as in Unit 6.

Swapping across the diagonal

Swapping A(r, c) with A(c, r) mirrors the grid across its main diagonal, so rows become columns. As with reversing, each pair must be swapped once: the inner loop starts just past the diagonal, FOR c = r + 1 TO n.

A = [[0, 0, 0, 0],
     [0, 5, 1, 7],
     [0, 2, 8, 3],
     [0, 6, 4, 9]]
n = 3
for r in range(1, n + 1):
    for c in range(r + 1, n + 1):
        t = A[r][c]
        A[r][c] = A[c][r]
        A[c][r] = t
for r in range(1, n + 1):
    print(A[r][1], A[r][2], A[r][3])

Output

5 2 6
1 8 4
7 3 9

The first row is now 5 2 6, the old first column. Had the inner loop run over every column, each pair would be swapped twice and the grid would come back unchanged.
Neighbours

A(r, c + 1) is the box to the right of A(r, c), and A(r + 1, c) is the box below it. A loop that compares each box with its right-hand neighbour must stop one column early, at n - 1, or it reads past the edge.

A = [[0, 0, 0, 0],
     [0, 5, 1, 7],
     [0, 2, 8, 3],
     [0, 6, 4, 9]]
up = 0
for r in range(1, 4):
    for c in range(1, 3):
        if A[r][c + 1] > A[r][c]:
            up = up + 1
print(up)

Output

The pairs are 5 1, 1 7, 2 8, 8 3, 6 4 and 4 9, and three of them go up. Each row of 3 boxes has only 2 neighbour pairs.

Put it together: this program reads a square grid of size n and prints the sum of the main diagonal, the sum of the other diagonal, and how many rows add up to the same total as the main diagonal.

INPUT n
FOR r = 1 TO n
   FOR c = 1 TO n
      INPUT A(r, c)
   NEXT c
NEXT r
d1 = 0
d2 = 0
FOR i = 1 TO n
   d1 = d1 + A(i, i)
   d2 = d2 + A(i, n + 1 - i)
NEXT i
same = 0
FOR r = 1 TO n
   s = 0
   FOR c = 1 TO n
      s = s + A(r, c)
   NEXT c
   IF s == d1 THEN
      same = same + 1
   END IF
NEXT r
OUTPUT d1, d2, same

The first input line holds n; each of the next n lines is one row. It is saved as assets/l3.py.

Try it

n = int(input())
A = []
row = []
for c in range(n + 1):
    row.append(0)
A.append(row)
for r in range(n):
    row = [0]
    for piece in input().split():
        row.append(int(piece))
    A.append(row)
d1 = 0
d2 = 0
for i in range(1, n + 1):
    d1 = d1 + A[i][i]
    d2 = d2 + A[i][n + 1 - i]
same = 0
for r in range(1, n + 1):
    s = 0
    for c in range(1, n + 1):
        s = s + A[r][c]
    if s == d1:
        same = same + 1
print(d1, d2, same)

Run it from this unit's folder:
```
python assets/l3.py < assets/l3/1.in
```
Each input row gets an unused 0 in front, and the grid gets an unused row 0, so A[r][c] matches ACSL's A(r, c). assets/l3/1.in is a magic square: every row and both diagonals add up to the same total. With n = 1 (assets/l3/2.in) the single box is on both diagonals.
- Check where the positions start (1 or 0) before you trace anything.
- To reverse, swap each box with its mirror and stop at the middle, or every pair is swapped back.
- To shift right, loop from right to left; the other way copies the first value into every box.
- The main diagonal is A(i, i), and the other diagonal is A(i, n + 1 - i).
- Change the boxes one at a time, exactly as the program does. The locker program prints 5 67.
You can now trace an ACSL program that uses arrays or grids and write its exact output.

Unit 10 — What Does This Program Do? (Arrays)

The problem: Who ends up in locker 2?

Lesson 1 — Arrays in ACSL and in Python

Where do the positions start?

Filling an array with a formula

Positions worked out from a counter

Reading an array from the input

A value used as a position

Checking the opening problem

Lesson 2 — Changing an array in place

Sum, count and the largest value

Swapping two boxes

Reversing: swap to the middle and stop

Tracing the opening problem

Shifting: the direction of the loop matters

Rotating: nothing falls off

A pass that uses its own changes

Lesson 3 — Grids: arrays with rows and columns

Filling a grid with a formula

Rows or columns: which loop is outside?

Diagonals

Triangles of the grid

Swapping across the diagonal

Neighbours