Forth for Enlightenment, part eight of ten, Backwords 4

In part six, a full runnable program was presented. But the startup time, generating the random puzzle, takes forever. How to speed it up? One thing to try is to abandon strings, which aren't randomly writable, and use arrays, which are. Characters aren't allowed as a data type in arrays. Only numbers are allowed. All we need are 9 different numbers. But some numbers are easier to convert to characters than others. In particular, the ASCII values of characters can be directly converted. The code for lower case "a" is 97, with the alphabet following sequentially. An array is created with the highly imaginitive name "a". Here's the code:

« 97 105 FOR x x NEXT { 9 } →ARRY 'a' STO » 'MKARRR' STO

The 97 105 FOR x starts a loop from ASCII values 'a' through 'i'. The next x pushes that value onto the stack. NEXT ends the loop. At the end of the loop, 9 values are on the stack. The list { 9 } is pushed, which is used by →ARRY to create an array on the stack of length 9, using the numeric values just pushed. This array is stored in the variable a. The whole function is called MKARRR.

Given the array, we need a function to shuffle it. But such a function will probably need a helper function that swaps values at two positions. It's a bit more complex. Two positions from 1 to 9 are placed on the stack before called.

«
  DUP2 'a' SWAP 1 →LIST GET
  SWAP 'a' SWAP 1 →LIST GET
  ROT 1 →LIST 'a' SWAP ROT PUT
  'a' SWAP ROT 1 →LIST SWAP PUT
» 'SWAPA' STO

You can see that each line ends with GET or PUT. These are the functions that get or put values into an array. Both GET and PUT require a list for the array index. that's because arrays can be two dimensional, and making the coordinates a single list allows the same number of arguments for any array dimensions. A stack track should help see what's going on. The function is passed two array indexes to swap, which are called x and y below.

start	x	y
DUP2	x	y	x	y
'a'	x	y	x	y	'a'
SWAP	x	y	x	'a'	y
1	x	y	x	'a'	y	1
→LIST	x	y	x	'a'	{ y }
GET	x	y	x	yval
SWAP	x	y	yval	x
'a'	x	y	yval	x	'a'
SWAP	x	y	yval	'a'	x
1	x	y	yval	'a'	x	1
→LIST	x	y	yval	'a'	{ x }
GET	x	y	yval	xval
ROT	x	yval	xval	y
1	x	yval	xval	y	1
→LIST	x	yval	xval	{ y }
'a'	x	yval	xval	{ y }	'a'
SWAP	x	yval	xval	'a'	{ y }
ROT	x	yval	'a'	{ y }	xval
PUT	x	yval
'a'	x	yval	'a'
SWAP	x	'a'	yval
ROT	'a'	yval	x
1	'a'	yval	x	1
→LIST	'a'	yval	{ x }
SWAP	'a'	{ x }	yval
PUT

The stack is used for temporaries. It starts with DUP2, because both GET and PUT will consume an index for both coordinates. From there on out, it's all about goofing around with the stack until the arguments are in the right places. One can test this function by running MKARRR, entering two indexes on the stack, calling SWAPA, and looking at the a array for the results.

We need a new shuffle that uses this routine to create a puzzle.

«
  1 9 FOR x
    x x RAND * FLOOR 1 + SWAPA
  NEXT
» 'SHFLA' STO

Clearly, 1 9 FOR x starts a loop that runs 9 times.
Two x's are put on the stack. RAND returns a random number between zero and 1. It's multiplied by the current x, the integer part is extracted with FLOOR. Then one is added with 1 +. This produces a number from 1 to x. Finally, that first x on the stack and the computed random number between 1 and x are swapped with SWAPA. So each value can get swapped to any other position. This whole function takes about 6 seconds to run on the HP-28C. While there probably are ways to make this faster still, six seconds is fast enough.

We still need a function which turns the array into a puzzle string. It's quite simple. The CHR function turns an ASCII number into a single character string. The '+' operator concatenates strings.

«
  a ARRY→ DROP ""
  1 9 START
    SWAP CHR +
  NEXT
» 'A2S' STO

The entire a array is put on the stack as a single object. ARRY→ converts that into the individual values with the list { 9 } at the top of the stack, which is then DROPped. A zero length string is pushed onto the stack so that it can be appended to. The second line starts the loop. An ASCII value is SWAPped to the top of the stack, converted to a one character string, and appended to the running string answer. And that's all there is too it.

Finally, a modification of 'BACK' is needed that uses the new shuffle.

« CLLCD MKARRR SHFLA A2S
  1 'BMV' STO
  WHILE DUP "abcdefghi" ≠ REPEAT
    BMV 1 DISP 'BMV' 1 STO+ DUP 2 DISP
    DO UNTIL KEY END STR→ REV
  END
  2 DISP
  "You win" 3 DISP
  'BMV' PURGE
  'a' PURGE
» 'ABACK' STO

And that's it. This version is quite a bit larger, but also quite a bit faster. Usually, in space vs. time trade offs, the code size is ignored. In this case, the code size is nearly everything. Have a bit of fun with it.