Simple programming training puzzle

[rcgldr]

This is a repost of an old thread, maybe some new members can give it a shot. This puzzle was included at the start of a casual IBM Fortran programming class for high school students back in 1969. (Yes, I'm that old). I don't know the origin of this puzzle.

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 punch an asterisk for every asterisk read. It's a broken copy program that you'll fix with program assignment 1.

 

[uart]

Ok Jeff I'll kick it off with the first one.



0 1 2 3 4 5 6 7 8 9 X X X X X X X X X X

Spoiler

T 4 A 0 H 0

 

[CRGreathouse]

The first two are easy enough:

Spoiler

0123456789----------
T4A0H0

0123456789----------
7T5A1H1T7T7T71

But I can't get the third one to work; the lack of addressable locations makes it difficult.

 

[rcgldr]

But I can't get the third one to work; the lack of addressable locations makes it difficult.

With only 4 basic instructions, there's always trial and error. Try doing the 2nd problem a bit differently.

 

[CRGreathouse]

So there are 4^20 basic types of programs (about a trillion), and 13^20 total programs.

 

[rcgldr]

So there are 4^20 basic types of programs (about a trillion), and 13^20 total programs.

True, but take a look at the very first instruction, it can't be an H or an A, so that only leaves two possibilities, a branch or a T. The next instruction after any T will normally be a branch. The 2nd instruction after a T will be an A or a branch. The next instruction after an A or an H will be either a branch or a T. Taking this into account and the number of possibilities is greatly reduced.

 

[Bill_B]

Neat puzzle, thanks for posting it. Here's my attempt.

1.

Spoiler

0123456789xxxxxxxxxx
T4A0H0

2.

Spoiler

0123456789xxxxxxxxxx
7T5A1H1T7T7T71

3.

Spoiler

0123456789xxxxxxxxxx
T0T0T08HT7AT7AT7A

 

[rcgldr]

Neat puzzle, thanks for posting it. Here's my attempt.

Almost, in the case of problem 3, running past the end of the last instruction isn't allowed. You need to figure out another way to stop all I/O. You're close though. Note that problem 2 could be implemented similar to problem 3 (same starting sequence).

Note that this was an exercise for students just learning how to program, yet it's challenging even for experienced programmers, being that it's more puzzle oriented. Then again, one issue that seems to be forgotten is that there are only 4 instructions, so if you get stuck, there aren't a lot of reasonable variations to try.

 

[Bill_B]

OK, I assumed (incorrectly) that reaching the end of the instructions would terminate the program.

Since there doesn't appear to be a way to actually terminate execution while the input tape still has data, this solution at least terminates the I/O (though it makes me cringe a little ) -


3.

Spoiler

0123456789xxxxxxxxxx
T0T0T097HT8AT8AT8A7

 

[rcgldr]

Since there doesn't appear to be a way to actually terminate execution while the input tape still has data, this solution at least terminates the I/O (though it makes me cringe a little)

The problem didn't state anything about terminating execution, just I/O, so you've solved the puzzle. By the way, what is your computer doing while you read this post?

 

[Bill_B]

Well, the CPU isn't pegged, so it's not stuck in an infinite loop but I get what you mean - it's not shut down, and is just sitting there idling.

I understand why that aspect of the solution has to be the way it is, but I'll just continue to pretend that there's an undocumented idle delay implemented somewhere