It looks like Fido may have some furry four-footed company. I hope they get along.Paeryn wrote: ↑Wed Jul 24, 2019 8:19 pmKira the Koding Kitty (as he insists he be called) says he's only including words containing the 26 English lower-case letters, though he can be purr-suaded to allow hyphens which will be ignored and possibly upper-case which will be treated as lower-case, but only if I give him some turkey. And it will have to wait until he's been fishing!

I've added a heap data structure to the insane line-numbered Basic anagram program. The revised program reads as follows:

Code: Select all

```
1000 REM hanagram.bas -- Find anagrams
1010 REM Written July 24, 2019 by Eric Olson
1020 REM
1030 REM This program demonstrates using letter counts and a heap to
1040 REM find anagrams in the insane British dictionary.
1050 REM
2000 F$="/usr/share/dict/british-english-insane"
2001 REM 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),H(M0),V0(26)
2040 CLOSE #1:OPEN F$ FOR INPUT AS #1
2050 A1=ASC("a")-1:A2=ASC("0"):N0=0:H0=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
2120 N0=N0+1:L$(N0)=A$:K$(N0)=V$:GOSUB 4000
2130 NEXT I:CLOSE #1
2140 IF H0=0 THEN 9000
2150 GOSUB 4500
2160 J0=J:L$(J0)=L$(J0)+":"
2170 IF H0=0 THEN 2400
2180 GOSUB 4500
2190 IF K$(J)<>K$(J0) THEN 2160
2200 L$(J0)=L$(J0)+" "+L$(J)+",":GOTO 2170
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
2900 GOTO 9000
4000 REM Insert a key into the heap
4010 REM inputs: N0 the key to insert
4020 H0=H0+1:R=H0:H(R)=N0
4030 S=INT(R/2):IF S=0 THEN RETURN
4035 B0$=K$(H(R))+L$(H(R))
4036 B1$=K$(H(S))+L$(H(S))
4040 IF B0$>=B1$ THEN RETURN
4060 T=H(S):H(S)=H(R):H(R)=T:R=S:GOTO 4030
4500 REM Remove a key from the heap
4510 REM output: J the key removed
4520 J=H(1):H(1)=H(H0):H0=H0-1:S=1
4530 R0=2*S:R1=R0+1:IF R0>H0 THEN RETURN
4535 B0$=K$(H(R0))+L$(H(R0)):IF R1>H0 THEN 4550
4536 B1$=K$(H(R1))+L$(H(R1))
4540 IF B0$>=B1$ THEN 4600
4550 IF B0$>=K$(H(S))+L$(H(S)) THEN RETURN
4560 T=H(R0):H(R0)=H(S):H(S)=T:S=R0:GOTO 4530
4600 IF B1$>=K$(H(S))+L$(H(S)) THEN RETURN
4660 T=H(R1):H(R1)=H(S):H(S)=T:S=R1:GOTO 4530
9000 END
```

Code: Select all

```
$ time ./gplbasic hanagram.bas >hanagram-gpl.insane
real 14m1.851s
user 14m0.341s
sys 0m0.131s
$ fbc -lang qb hanagram.bas
$ time ./hanagram >hanagram-fbc.insane
real 0m46.614s
user 0m45.546s
sys 0m1.000s
$ time ./anagram.perl >perl.insane
real 0m13.547s
user 0m13.349s
sys 0m0.182s
$ md5sum *.insane
bec74aa3b31577edbb291aeb7269a4d5 hanagram-fbc.insane
bec74aa3b31577edbb291aeb7269a4d5 hanagram-gpl.insane
bec74aa3b31577edbb291aeb7269a4d5 perl.insane
```