PCjs Machines
Home of the original IBM PC emulator for browsers.
PCjs Blog
Puzzled Programmers
A book I used to have a copy of (and perhaps still do, in the bowels of my storage unit) was “Puzzled Programmers” by Michael Wiesenberg. It was published by Microsoft Press in 1987, and I recently rediscovered an online copy in the Internet Archive’s Open Library:
Someone else was currently “borrowing” it, so I added myself to the wait-list, and a few days ago, the Internet Archive notified me that it was available for reading. I started skimming it, and noticed that for each of the puzzles, it included complete solutions in all the aforementioned languages: BASIC, Pascal, and C. I also noticed this portion of the Introduction:
Timing the Programs on Your Computer
Run times are specified for each puzzle, but you should look at these times only as guidelines or, in the vernacular, as ballpark figures. The figures given are for a Hewlett-Packard Vectra (IBM PC AT compatible) running at a clock speed of 8 MHz. Obviously, the times will differ with other interpreters and on other computers. The following table gives you some idea of how long a program ought to take on your particular system. This table shows timings on various systems of the programs presented in the solution to Puzzle 5.
Computer BASIC Turbo Pascal Microsoft C
-------------------------------------------------------------------------------
Tandy 1000 (4.77 MHz) 2 minutes 11 seconds 1.3 seconds 2.4 seconds
IBM PC XT clone (4.77 MHz) 1 minute 58.5 seconds 1.3 seconds 2.3 seconds
IBM PC A T (6 MHz) 50 seconds 0.5 seconds 0.9 seconds
HP Vectra (8 MHz) 35 seconds 0.5 seconds 0.4 seconds
Macintosh Plus 8 seconds < 1 second < 1 second
Apple II C 2 minutes 20 seconds 23.6 seconds* n/a
-------------------------------------------------------------------------------
*Apple Pascal
This almost seemed like an invitation to try my hand at Puzzle #5 and see how a PCjs “machine” compared.
A Pleasant Fourthsum
I skipped ahead to page 27, “Puzzle 5: A Pleasant Fourthsum”, and started reading. I have to admit that the story completely failed to interest me. There were lots of irrelevant details about a delicious breakfast that this imaginary bunch of successful twenty-somethings was enjoying, when suddenly one of them says:
"Before we get into the future of languages at I-Q, I've got a great computer puzzle for everyone."
which he then states in one sentence:
"Find a four-digit number that is the sum of the fourth powers of its digits."
and then the conversation returns to other random topics, like whether anyone should be worried that FORTRAN might become a weapons guidance language, and whether they need to make lunch reservations – when they’ve barely finished breakfast!
Skipping ahead to the “Solutions” section, it turned out that the challenge was to actually find all four-digit numbers, not just a number. Also, only numbers 1000 through 9999 are considered (no numbers with leading zeros).
Just for fun, I created my own solution in JavaScript first:
let p = new Array(10);
/**
* test(n)
*
* Returns true IFF the number matches the criteria.
*
* @param {number} n
* @returns {boolean}
*/
function test(n) {
let total = 0;
let value = n;
while (n) {
total += p[n % 10];
n = (n / 10)|0;
}
return total == value;
}
function run() {
let n = 1000;
for (let d = 0; d < 10; d++) {
p[d] = Math.pow(d, 4);
}
while (true) {
if (test(n)) console.log(n);
if (++n > 9999) break;
}
}
run();
then I looked at the solutions in “Puzzled Programmers”. Here’s the BASIC solution:
5 REM BASIC Solution to Puzzle #5 in "Puzzled Programmers" (c) 1987
10 DIM PWR(9)
20 FOR I = 0 TO 9
30 PWR(I) = I^4
40 NEXT I
50 H000 = 1000
60 FOR H = 1 TO 9
70 I00 = 0
80 FOR I = 0 TO 9
90 J0 = 0
100 FOR J = 0 TO 9
110 PARTSUM = H000 + I00 + J0
120 PART4THS = PWR(H) + PWR(I) + PWR(J)
130 FOR K = 0 TO 9
140 SUM = PARTSUM + K
150 IF PART4THS + PWR(K) <> SUM THEN 190
160 PRINT SUM; "= ";
170 PRINT USING "#^4 + "; H, I, J;
180 PRINT USING "#^4"; K
190 NEXT K
200 J0 = J0 + 10
210 NEXT J
220 I00 = I00 + 100
230 NEXT I
240 H000 = H000 + 1000
250 NEXT H
and the C solution (which I modified to loop 100 times, to make timing with a stopwatch easier):
/* C solution to puzzle #5 in "Puzzled Programmers" (c) 1987 */
main()
{
int pwr[10], /* the fourth power of each digit */
h, /* the digit in the thousands position */
h000, /* h * 1000, that is, the value of the number
in the thousands position */
i, /* the digit in the hundreds position */
i00, /* i * 100, that is, the value of the number
in the hundreds position */
j, /* the digit in the tens position */
j0, /* i * 10, that is, the value of the number
in the tens position */
part4ths, /* h^4 + i^4 + j^4 */
partsum, /* h000 + i00 + j0 */
k, /* the digit in the ones position */
sum, l;
for (i = 0; i < 10; i++) pwr[i] = i * i * i * i;
for (l = 100; l-- > 0;) {
for (h000 = 1000, h = 1; h <= 9; h++, h000 += 1000) {
/* thousands digit */
for (i00 = i = 0; i <= 9; i++, i00 += 100) {
/* hundreds digit */
for ( j0 = j = 0; j <= 9; j++, j0 += 10) {
/* tens digit */
partsum = h000 + i00 + j0;
part4ths = pwr[h] + pwr[i] + pwr[j];
for ( k = 0; k <= 9; k++) { /* ones digit */
sum = partsum + k; /* this produces the four-digit number */
if (part4ths + pwr[k] == sum) {
if (!l) printf("%d = %d^4 + %d^4 + %d^4 + %d^4\n",
sum, h, i, j, k);
}
}
}
}
}
}
}
Here’s my own C solution, which is slightly smaller and faster than the book’s solution:
/* @jeffpar's optimized C solution to puzzle #5 */
main()
{
int p[10];
int d, l, n, s;
for (d = 0; d < 10; d++) p[d] = d * d * d * d;
for (l = 100; l-- > 0;) { /* loop 100 times for timing purposes */
for (n = 100; n < 1000; n++) {
/* I originally used a "do...while (t /= 10)" loop here
to create the power summation (where t was a copy of n),
but since we know n is a 3-digit number, we can inline
all three power references and minimize the number of
divisions; we also bias the sum by -(n*10) so that we
don't have to add (n*10) to d for the final comparison. */
s = p[n/100] + p[(n/10)%10] + p[n%10] - (n*10);
for (d = 0; d < 10; d++) {
if (s + p[d] == d) {
if (!l) printf("%d = %d^4 + %d^4 + %d^4 + %d^4\n",
n * 10 + d, n/100, (n/10)%10, n%10, d);
}
}
}
}
}
And finally, here’s the book’s Pascal solution:
program sum4ths(input, output);
var
pwr: { the fourth power of each number, 0 to 9 }
array[0..9] of integer;
h, { the digit in the thousands position }
h000, { h * 1000, that is, the value of the number
in the thousands position }
i, { the digit in the hundreds position }
i00, { i * 100, that is, the value of the number in
the hundreds position }
j, { the digits in the tens position }
j0, { j * 10, that is, the value of the number in
the tens position }
part4ths, { h^4 + i^4 + j^4 }
partsum, { h000 + i00 + j0 }
k, { the digit in the ones position }
sum: integer;
begin
for i := 0 to 9 do pwr[i] := i * i * i * i;
h000 := 1000;
for h := 1 to 9 do begin { thousands digit }
i00 := 0;
for i := 0 to 9 do begin { hundreds digit }
j0 := 0;
for j := 0 to 9 do begin { tens digits }
partsum := h000 + i00 + j0;
part4ths := pwr[h] + pwr[i] + pwr[j];
for k := 0 to 9 do begin { ones digit }
sum := partsum + k; { this produces the four-digit number }
if part4ths + pwr[k] = sum then
writeln(sum, ' = ', h, '^4 + ', i, '^4 + ', j, '^4 + ', k, '^4')
end;
j0 := j0 + 10;
end;
i00 := i00 + 100;
end;
h000 := h000 + 1000;
end
end.
You can play with all these solutions in the 4.77Mhz IBM PC XT machine below. Use CD \PUZZLED\PUZZLE5 to switch
to the directory for Puzzle #5.
To run the BASIC version, use GWBASIC, since the machine boots MS-DOS 3.20:
C:\PUZZLED\PUZZLE5>GWBASIC PUZZLE5.BAS
To compile and run the C version, you can use the pre-installed copy of Microsoft C 4.00:
C:\PUZZLED\PUZZLE5>cl puzzle5.c
Microsoft (R) C Compiler Version 4.00
Copyright (C) Microsoft Corp 1984, 1985, 1986. All rights reserved.
puzzle5.c
Microsoft (R) Overlay Linker Version 3.51
Copyright (C) Microsoft Corp 1983, 1984, 1985, 1986. All rights reserved.
Object Modules [.OBJ]: PUZZLE5.OBJ
Run File [PUZZLE5.EXE]: PUZZLE5.EXE/NOI
List File [NUL.MAP]: NUL
Libraries [.LIB]: ;
C:\PUZZLED\PUZZLE5>puzzle5
1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4
To compile and run the Pascal version, load diskette “IBM Pascal 1.00 (Combined)” in drive A, and then type the commands shown below:
C:\PUZZLED\PUZZLE5>a:pas1
IBM Personal Computer Pascal Compiler
Version 1.00 (C)Copyright IBM Corp 1981
Source filename [.PAS]: puzzle5p
Object filename [PUZZLE5P.OBJ]:
Source listing [NUL.LST]:
Object listing [NUL.COD]: puzzle5p
Pass One No Errors Detected.
C:\PUZZLED\PUZZLE5>a:pas2
Code Area Size = #0296 (662)
Cons Area Size = #004C (76)
Data Area Size = #002A (42)
Pass Two No Errors Detected.
C:\PUZZLED\PUZZLE5>a:link
IBM Personal Computer Linker
Version 1.00 (C) Copyright IBM Corp 1981
Object Modules: puzzle5p
Run File: puzzle5p
List File [PUZZLE5P.MAP] :
Libraries [ ] :
Publics [No]:
Line Numbers [No]:
Stack size [Object file stack]:
Load Low [Yes]:
DSAllocation [No]:
C:\PUZZLED\PUZZLE5>puzzle5p
1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4
It appears that PCjs is somewhat faster than a real machine. For example, the author’s BASIC solution ran for almost two minutes on a PC XT clone, but it finishes in about one and a half minutes on the 4.77Mhz PC XT configuration below.
Clearly, I still have some work to do if I want PCjs to faithfully simulate how slow these systems used to be.
[PCjs Machine "ibm5160-msdos320"]
Waiting for machine "ibm5160-msdos320" to load....
Jeff Parsons
Sep 21, 2017