Recognitions:
Homework Help

THAN programming - puzzle - learning aid

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.

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:

Code:
0 1 2 3 4 5 6 7 8 9 X X X X X X X X X X
T H A 0
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.

 PhysOrg.com science news on PhysOrg.com >> Heat-related deaths in Manhattan projected to rise>> Dire outlook despite global warming 'pause': study>> Sea level influenced tropical climate during the last ice age
 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.
 Recognitions: Homework Help 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.

THAN programming - puzzle - learning aid

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.

 Recognitions: Homework Help 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.
 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]
 Recognitions: Homework Help 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.
 Recognitions: Homework Help Science Advisor 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