The Four Cube Problem
A Case Study in BASIC, APL, and Functional Programming

E.E. McDonnell

Work in Progress

Several years ago Parker Brothers marketed a puzzle called Instant Insanity. The puzzle consisted of four cubes whose sides were colored in a certain arrangement of four different colors. The object of the puzzle was to stack the four cubes so that each side of the stack showed all four colors. This booklet gives two solutions to the problem of solving this puzzle with the aide of a computer, one written in BASIC, and the other in APL. Both are good of their kind (the BASIC program won a prize in a programming competition), but the APL solution is considerably shroter. This booklet tries to show the differences in the solutions resulting from the differences in the programming languages used.

As an additional experiment, the APL solution is further constrained to use two recently introduced ideas. The first of these is the direct definition form, developed by K.E. Iverson as a way of facilitating the definition of functions (and their use in exposition), and the second is the functional style of programming without variables, introduced by John Backus as a way of overcoming the disadvantages of current programming languages. It appears that what Backus advocates is already present to a large extent in Iverson’s direct definition form. Backus’s functional style of programming without variables can be obtained from APL, using the direct definition form, by avoiding the use of assignment and global variables.
 

0. Introduction

Those who are involved with teaching or selling APL are often asked why APL should be preferred to some other programming language, and the other language is frequently BASIC. The program I have seen used most often to demonstrate APL’s good qualities is the program for computing the average of a set of values. This program in APL is quite easy to write, and is very much shorter than the equivalent BASIC program. Everyone knows what an average is, and can appreciate the advantage of the APL version. The trouble is that it is almost too small an idea to make an effective point. Most people’s idea of a program is something that takes on the order of one or two hundred lines. To show them a comparison between a ten-line and a one-line program is liable to elicit the reaction, “Well, that’s fine, in a way, but my programming problems are a lot bigger than that, and you haven’t convinced me that APL’s advantages carry over to my size of problem.”

This booklet attempts to address the question whether the advantages of APL on very small problems carry over to larger problems. It gives a BASIC and an APL solution to the four cube puzzle. The problem is not an enormous one, but it is nonetheless far from being trivial. A fair amount of analysis is required, a careful choice of data representation must be made, and a programming strategy adopted.

It might be of some interest to you to know some of the background of the puzzle and the puzzle solvers. The puzzle was given in a contest sponsored by the Peninsula chapter of the ACM, located in San Francisco bay area of California. It was open to students in high schools of Santa Clara county, near San Francisco. The county is popularly known in the business press as Silicon Valley, since it is home to many of the high-technology electronics companies in the United States.

The BASIC program was written by Armand MacMurray, then a senior at Gunn High School in Palo Alto. The high schools in Palo Alto regularly run off with the lion’s share of National Merit Scholarships in the country, and Gunn High School, in particular, is well-known for its excellence in its mathematics and computer studies. Armand MacMurray was one of the leading mathematics and computer science students in his class. I didn’t find out that he had entered and won the ACM contest until after my APL program was written. Somewhat curiously, he had learned APL in his sophomore high school year when, as part of an exploratory experiences program, he spent several hours a week one semester in the Palo Alto I.P. Sharp office. He already knew BASIC at this point, having used it on the school district’s HP2000 time-sharing system. You can ask yourself, when you read his program, whether any of his APL knowledge filtered into his BASIC program. Armand was not aware of the puzzle until two weeks before the deadline for entries, so his effort represents at most two weeks’ work.

I wrote the APL solution. I became aware of the problem when one of my sons brought the announcement home from high school. I was interested in the problem because of its recreational aspects, and also because I had seen earlier APL versions of programs to solve the puzzle which had left me dissatified. My credentials include thirty years of computer programming experience, and twenty years of programming in APL. I have been Recreational APL editor of APL Quote-Quad since 1976.
 

1. The Problem

1.1 The Data

1.2 Output

1.3 The Language

1.4 The Documentation

1.5 Submitting Programs

1.6 Judging and Awards

1.7 Please Note

2. The BASIC Solution (by Armand MacMurray)

2.1 The BASIC Program Listing

2.2 Running the Program

3. The APL Algorithm

3.1 Representing the Cubes

3.2 The Algorithm

Adding a New Cube: We’re not quote ready yet to put a new cube on the stack.

Selecting the Successful Stacks: Out next problem is to decide which of these new stacks have no repeated colors on their sides, and to select these.

Solving the Problem: After we have selected the eligible stacks of height two, we can continue the process of adding a cube in all its distinct orientations to each stack, and selecting eligible stacks from the result, until we have added and selected using the top cube.

3.3 Solutions for Arbitrary Cubes

3.4 List of Functions

4. Comparsion

5. Conclusion

APL has an intrinsic advantage of about ten to one over BASIC in expressiveness. This advantage is enhanced by using the direct definition form for writing functions, thereby insuring that all programs give results, and further by using the “functional programming” strategy suggested by Backus, as a way of doing away with variables and obtaining a highly articulated programming structure.
 

References

Work in Progress

Originally appeared as a booklet published by APL Press, 1981.