Register to reply

THAN programming - puzzle - learning aid

by rcgldr
Tags: learning, programming, puzzle
Share this thread:
rcgldr
#1
Jun2-07, 03:07 AM
HW Helper
P: 7,033
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:

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.
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
Moo Of Doom
#2
Jun2-07, 04:01 AM
P: 367
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
#3
Jun2-07, 11:34 PM
HW Helper
P: 7,033
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
#4
Jun3-07, 02:53 AM
P: 367
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.
rcgldr
#5
Jun3-07, 03:21 PM
HW Helper
P: 7,033
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
#6
Jun3-07, 04:31 PM
P: 367
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
#7
Jun4-07, 12:34 AM
HW Helper
P: 7,033
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
#8
Jun4-07, 11:17 AM
Sci Advisor
HW Helper
P: 2,538
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


Register to reply

Related Discussions
Learning c#, .NET programming Programming & Computer Science 5
Help with puzzle from smc General Math 4
The 15 puzzle Set Theory, Logic, Probability, Statistics 0
Programming-based learning General Math 2
Discovering new species of dinosaurs Biology 5