Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple programming training puzzle

  1. Sep 24, 2008 #1

    rcgldr

    User Avatar
    Homework Helper

    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:

    Code (Text):

    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.
     
  2. jcsd
  3. Sep 24, 2008 #2

    uart

    User Avatar
    Science Advisor

    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
    T 4 A 0 H 0
     
  4. Sep 24, 2008 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The first two are easy enough:
    0123456789----------
    T4A0H0

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

    But I can't get the third one to work; the lack of addressable locations makes it difficult.
     
  5. Sep 24, 2008 #4

    rcgldr

    User Avatar
    Homework Helper

    With only 4 basic instructions, there's always trial and error. Try doing the 2nd problem a bit differently.
     
    Last edited: Sep 24, 2008
  6. Sep 25, 2008 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    So there are 4^20 basic types of programs (about a trillion), and 13^20 total programs.
     
  7. Sep 25, 2008 #6

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  8. Sep 25, 2008 #7

    Bill_B

    User Avatar
    Gold Member

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

    1.
    0123456789xxxxxxxxxx
    T4A0H0

    2.
    0123456789xxxxxxxxxx
    7T5A1H1T7T7T71

    3.
    0123456789xxxxxxxxxx
    T0T0T08HT7AT7AT7A
     
  9. Sep 26, 2008 #8

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  10. Sep 26, 2008 #9

    Bill_B

    User Avatar
    Gold Member

    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 :smile: ) -


    3.
    0123456789xxxxxxxxxx
    T0T0T097HT8AT8AT8A7
     
  11. Sep 27, 2008 #10

    rcgldr

    User Avatar
    Homework Helper

    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?
     
  12. Sep 27, 2008 #11

    Bill_B

    User Avatar
    Gold Member

    Well, the CPU isn't pegged, so it's not stuck in an infinite loop :smile: 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 :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Simple programming training puzzle
  1. An simple program (Replies: 3)

Loading...