Learning Competitive Programming on Retro Computers

delyan · January 19, 2024, 3:50pm

I have been researching whether retro computers are suitable for teaching (competitive) programming to elementary school children. I will go into the reasons why when I publish my research as an official blog post on delyan.org.

Here are the supported languages on CodeForces for example: Codeforces Command Lines (2023-10-06). Pascal may be the most “retro” language and it is not a bad choice. Definitely won’t go as esoteric as DJGPP.

What if we added Commodore64 BASIC to the supported languages on CodeForces? Ok! I know it sounds crazy - but it may be possible.

As part of my research I wanted to program something simple to understand how painful it would be to code in BASIC. What if we wanted to implement an algorithm to find all permutations of A, B, C, and D on a Commodore64 using BASIC? First - we are going to have to use nested loops - BASIC doesn’t have built-in functions for permutations. For a tiny number of N - something like this may be acceptable:

10 FOR A = 65 TO 68
20 FOR B = 65 TO 68
30 FOR C = 65 TO 68
40 FOR D = 65 TO 68
50 IF A <> B AND A <> C AND A <> D AND B <> C AND B <> D AND C <> D THEN
60 PRINT CHR$(A); CHR$(B); CHR$(C); CHR$(D)
70 END IF
80 NEXT D
90 NEXT C
100 NEXT B
110 NEXT A

This may be perfect and effective for teaching a 10 year old child about competitive programming:

We learn about FOR loops
We learn about ASCII values and how iterate over these
What uniqueness means and how to check for that
What are permutations vs combinations and the fact that permutations implies no repetitions
How to print/convert ASCII values to characters using CHR$

What if we try to write a recursion on a Commodore64?

Overall recursion should be possible in Commodore 64 BASIC. Maybe we can use GOSUB and RETURN statements. Hopefully we won’t hit the Commodore 64 BASIC limitations around the (hardware) stack size and memory management. These limitations make deep recursion inefficient and we may run into stack overflows.

But it is possible after all. Here is a simple recursion:

10 INPUT "Enter a number: ", N
20 GOSUB 100
30 END

100 REM Here is a recursive subroutine. It prints 100 through 1.
110 IF N = 0 THEN RETURN
120 PRINT N
130 N = N - 1
140 GOSUB 100
150 RETURN

Unfortunately there is no notion of stack with GOSUB and RETURN. (It turns out the MOS Technology 6510 CPU architecture of the Commodore64 does have a hardware stack. It is used by the assembly language operations and so it is only indirectly accessed when using BASIC.)