THAN programming - puzzle - learning aid

rcgldr

An extremely simple and old (1960's) programming language based on an imaginary machine. The machine has two peripherals, at paper tape reader, and a paper tape punch. The character set only includes two characters, Asterisk and Hypen. The CPU has 20 memory locations, which hold instructions, but only the first 10 locations, 0 through 9 are addressable via the branch instruction.

There are only 13 instructions, and 4 basic types of instruction:

T - Read a character from the tape reader. If the character read is a hyphen, execute next instruction. If the character read is an asterisk, skip the next instruction, and execute the instruction following the next instruction. If no character is read because the paper tape is past the end, then the machine will stop.

H - Punch a hypen, then execute next instruction.

A - Punch an asterisk, then execute next instruction.

0 - branch to location 0 and continue execution there.
1 - branch to location 1 and continue execution there.
2 - branch to location 2 and continue execution there.
...
9 - branch to location 9 and continue execution there.

Instruction execution can continue past memory location 9, but these memory locations can't be the target of a branch instruction.

Programming tasks:

1. Write a program to duplicate the paper tape in the reader using the paper tape punch.

2. Write a program to read the paper tape until 3 asterisks in a row are read, then start duplicating the paper tape as in program 1.

3. Write a program to read the paper tape until 3 asterisks in a row are read, then start duplicating the paper tape, but stop all I/O once 3 asterisks in a row are punched during the copy process.

Note that since there are only 13 instructions, trial and error will be good enough to write any of these programs.

To avoid spoilers, please white out your repsonse, or merely indicate that you've solved how to create programs 1, 2, and/or 3.

Sample program:

This program will punch a hyphen and asterisk for every hyphen read, and puch an asterisk for every asterisk read. It's a broken copy program that you'll fix with program assignment 1.

Moo Of Doom

I've done 1 and 2... working on 3.

[spoilers]
1.
0 1 2 3 4 5 6 7 8 9 X X X X X X X X X X
2 H T 1 A 2

2.
0 1 2 3 4 5 6 7 8 9 X X X X X X X X X X
6 H T 1 A 2 T 6 T 6 T 6 2
[/spoilers]

As practice for 3, I'm trying to find the algorithm whose highest referenced memory location is lowest among algorithms that achieve the same thing.

rcgldr

Only one here taking the challenge so far? Note that this was a programming "puzzle" given to high school students just learning how to program.

Moo Of Doom

Hah! Got 3 as well. That wasn't so hard after all.

[spoilers]
3.
0 1 2 3 4 5 6 7 8 9 X X X X X X X X X X
T 0 T 0 T 0 8 H T 7 A T 7 A T 7 A
[/spoilers]

That was a nice problem. I also wrote an interpreter for the language this morning, so I could fool around with it a bit. 'Twas fun.

rcgldr

Not quite, your program continues on after the last instruction, and there are only 4 types of instructions, so it will not stop all I/O. You're close though.

Moo Of Doom

How are you supposed to stop all I/O? If running out of commands on the command tape isn't enough, then the best I can do is have it end in an infinite loop. Seems like a poor solution, though.

[spoilers]
3.
0 1 2 3 4 5 6 7 8 9 X X X X X X X X X X
T 0 T 0 T 0 9 7 H T 8 A T 8 A T 8 A 7
[/spoilers]

rcgldr

It may seem poor to you, but it's the correct solution, and part of the exercise, to realize that there is only one instruction that doesn't involve I/O and to use it for that purpose. It's a reasonably clever solution, demonstrating inovation, especially since it's targeted at students learning programming for the first time, although some experienced programmers have had difficulty with this problem.

I'm 55 years old now, and I received this problem in high school, back in 1968. I don't know when this problem was first developed.

NateTG

This sort of problem is pretty clearly related to the notion of universal touring machines. I would expect that it developed in the 1940's.

http://en.wikipedia.org/wiki/Alan_Turing