ejolson wrote: ↑Sun Jul 21, 2019 7:33 pm

I'm presently working on a version in classic line-numbered Basic that organizes all the anagrams into a

heap data structure.

At FidoBasic headquarters I entered what looked like a lift. It turned out to be a time machine. Suddenly I was standing in the midst of the golden age of personal computing, still holding my Raspberry Pi. In true canine fashion Fido's head turned to one side as I explained the insane British anagram challenge to the wondering crowd of teenage student Basic programmers. By the time I was finished explaining how with a challenge anyone who writes a working program is a winner, one of the children motioned to me.

With the hunt-and-peck quickness of a ninja and stealth, a working program had already been written without my notice. On the screen of a nearby 8-bit microcomputer was the following:

Code: Select all

```
1000 REM banagram.bas -- Find anagrams
1010 REM Written July 16, 1978 by Eric Olson
1020 REM
1030 REM This program demonstrates using letter counts and linear
1040 REM lists to find anagrams in the insane British dictionary.
1050 REM
2000 REM F$="/usr/share/dict/british-english-insane"
2001 F$="tail.dat"
2010 M0=0:OPEN F$ FOR INPUT AS #1
2015 IF EOF(1)<>0 THEN 2030
2020 INPUT #1,A$:M0=M0+1:GOTO 2015
2030 DIM L$(M0),K$(M0),V0(26)
2040 CLOSE #1:OPEN F$ FOR INPUT AS #1
2050 A1=ASC("a")-1:A2=ASC("0"):N0=0
2060 FOR I=1 TO M0:INPUT #1,A$
2063 FOR J=1 TO 26:V0(J)=0:NEXT J:J=0
2065 IF J>=LEN(A$) THEN 2075
2068 J=J+1:C=ASC(MID$(A$,J,1))-A1
2070 IF (C<1) OR (C>26) THEN 2130
2071 V0(C)=V0(C)+1:GOTO 2065
2075 V$="":FOR J=1 TO 26
2080 V$=V$+CHR$(V0(J)+A2):NEXT J:J=0
2090 IF J>=N0 THEN 2120
2100 J=J+1:IF K$(J)<>V$ THEN 2090
2110 L$(J)=L$(J)+" "+A$+",":GOTO 2130
2120 N0=N0+1:L$(N0)=A$+":":K$(N0)=V$
2130 NEXT I:CLOSE #1
2400 FOR I=1 TO N0:A$=L$(I)
2410 IF RIGHT$(A$,1)=":" THEN 2430
2420 PRINT LEFT$(A$,LEN(A$)-1)
2430 NEXT I
9000 END
```

Two things caught my attention: The first was the fact that the comments listed me as the author; the second that the program would surely run with non-ninja turtle-like slowness because it used an O(n^2) algorithm based on linear lists to match and store the anagrams.

I turned to Fido and whispered under my breath, for a program written by someone who has not formally studied algorithms at the university this code shows remarkable skill and insight. The canine sneezed and and looked at me as if I had just congratulated myself. Then with a bark the dog developer announced, let's see if it really works.

Since the 4K memory of the PET 2001 was not sufficient to hold the insane British dictionary and the algorithm was too slow anyway, I connected the Pi 3B to a nearby television and typed

Code: Select all

```
$ tail -n 10000 /usr/share/dict/british-english-insane >tail.dat
$ wc tail.dat
10000 10000 93607 tail.dat
$ time ./bwbasic banagram.bas >banagram-bw.tail
real 18m30.145s
user 18m29.419s
sys 0m0.120s
$ time ./sbrandy banagram-mb.bas >banagram-mb.tail
real 0m23.888s
user 0m23.797s
sys 0m0.071s
$ time ./gplbasic banagram.bas >banagram-gpl.tail
real 0m9.476s
user 0m9.460s
sys 0m0.011s
$ fbc -lang qb banagram.bas
$ time ./banagram >banagram-fbc.tail
real 0m5.330s
user 0m5.313s
sys 0m0.011s
$ time ./anagram.perl >perl.tail
real 0m0.226s
user 0m0.205s
sys 0m0.021s
$ md5sum *.tail
2f0427e2de42059e20bb335e25c5c1ca banagram-bw.tail
2f0427e2de42059e20bb335e25c5c1ca banagram-fbc.tail
2f0427e2de42059e20bb335e25c5c1ca banagram-gpl.tail
2f0427e2de42059e20bb335e25c5c1ca banagram-mb.tail
2f0427e2de42059e20bb335e25c5c1ca perl.tail
```

The code for Matrix Brandy Basic was slightly different and read as

Code: Select all

```
1000 REM banagram-mb.bas -- Find anagrams
1010 REM Written July 17, 1978 by Eric Olson
1020 REM
1030 REM This program demonstrates using letter counts and linear
1040 REM lists to find anagrams in the insane British dictionary.
1050 REM
2000 REM F$="/usr/share/dict/british-english-insane"
2001 F$="tail.dat"
2010 M0=0:F1=OPENIN(F$)
2015 IF EOF#(F1)<>0 THEN 2030
2020 A$=GET$#(F1):M0=M0+1:GOTO 2015
2030 DIM L$(M0),K$(M0),V0(26)
2040 CLOSE# F1:F1=OPENIN(F$)
2050 A1=ASC("a")-1:A2=ASC("0"):N0=0
2060 FOR I=1 TO M0:A$=GET$#(F1)
2063 FOR J=1 TO 26:V0(J)=0:NEXT J:J=0
2065 IF J>=LEN(A$) THEN 2075
2068 J=J+1:C=ASC(MID$(A$,J,1))-A1
2070 IF (C<1) OR (C>26) THEN 2130
2071 V0(C)=V0(C)+1:GOTO 2065
2075 V$="":FOR J=1 TO 26
2080 V$=V$+CHR$(V0(J)+A2):NEXT J:J=0
2090 IF J>=N0 THEN 2120
2100 J=J+1:IF K$(J)<>V$ THEN 2090
2110 L$(J)=L$(J)+" "+A$+",":GOTO 2130
2120 N0=N0+1:L$(N0)=A$+":":K$(N0)=V$
2130 NEXT I:CLOSE# F1
2400 FOR I=1 TO N0:A$=L$(I)
2410 IF RIGHT$(A$,1)=":" THEN 2430
2420 PRINT LEFT$(A$,LEN(A$)-1);CHR$(10);
2430 NEXT I
9000 END
```

Fido's paw motioned that is was time to go, so we headed to the time machine. Once inside I suggested, let's go back to the future so I can get a Pi 4B. Fido became barking mad and growled, the 4B has already been released. I replied, but there won't be such a short supply in the future so shipping times will be quicker.

Instead we returned to the present and Fido created a bar chart depicting the performance of the different versions of Basic.

Fido's tail happily wagged back and forth while explaining, I've used dogarithmic coordinates because the timings involved so many different orders of magnitude. I think the canine coder meant logarithmic.