\ squabble.txt for windable  Leo Wong  27 April 2003 fyj + 
\ Find scrabble words for a combination of letters
\ After Bentley, Programming Pearls
\ Uses ospd.txt from: ftp://puzzlers.org/pub/wordlists/
\ ospd.txt lists 79,339 words
\ A larger list, enable1.txt, has 172,823 words
\ scrummage finds words of subsets of letters
\ See usage examples at the end of this file

include from.txt
from all2all.txt
from tools.txt
from string.txt
from files.txt
from qsort.txt
from bsearch.txt
from combperm.txt

S" ..\wordlists\ospd.txt" string datafile

256 array table
: tally-chars  ( ca u -- )
   0 table 256 CELLS ERASE  0 ?DO COUNT table ++ LOOP DROP ;
: make-sig  ( -- pad u )
   0 PAD C!
   0 table 256 0 DO DUP @ ?DUP IF
     I PAD COUNT + C! 1 PAD c+!
     DUP 1 > IF (.) PAD append ELSE DROP THEN THEN
   CELL+ LOOP  DROP
   PAD COUNT ;
: sig ( ca u -- pad u )  tally-chars make-sig ;

80000 CONSTANT maxwords \ 79,339 words in ospd.txt
0 VALUE nwords

TRUE ?ALLOCATE
maxwords DUP CELLS OVER 18 CHARS * + allocate-space temp CELLS ALLOT

: signatures
   datafile open-in
   BEGIN readl WHILE HERE nwords CELLS temp + !
   2DUP sig string, string, nwords 1+ TO nwords REPEAT 2DROP
   close-in ;

CR .( Loading words and their signatures ) CR
signatures

CR .( Sorting signatures ) CR
' sprecedes IS precedes  temp nwords quicksort

maxwords DUP CELLS OVER 20 CHARS * + allocate-space dictionary
CELLS ALLOT

0 VALUE nsigs
: squash  ( -- )
   0 PAD C! 0 TO nsigs 
   temp nwords 0 DO
     DUP @ COUNT 2DUP PAD COUNT COMPARE 
       IF 0 C, HERE nsigs CELLS dictionary + ! 2DUP string,
         2DUP PAD place nsigs 1+ TO nsigs THEN CHARS + COUNT string,
     CELL+
   LOOP DROP 0 C, ;

CR .( Squashing data )  CR
squash temp FREE THROW

: .words  ( i -- )
   CELLS dictionary + @ COUNT CHARS +
   BEGIN COUNT DUP WHILE 2DUP TYPE SPACE CHARS + REPEAT 2DROP ;

\ Compare signatures in binary search
:NONAME ( key dictionary i -- flag )  
  2>R COUNT 2R> CELLS + @ COUNT COMPARE ; IS bcomp

: (squabble)  ( ca u -- ) 
   2DUP slower sig PAD place
   PAD dictionary 0 nsigs 1- bsearch IF .words ELSE DROP THEN ;

: squabble  ( -- )  \ squabble <string>
   0 PARSE (squabble) ;

\ Scrummage: find all squabble subsets
\ Uses spad and cpad
CREATE spad 10 CHARS ALLOT
CREATE cpad 10 CHARS ALLOT

: (scrummage)  ( -- )
   0 cpad ! 0 vector subset
   0 ?DO DUP @ spad + C@ cpad cappend CELL+ LOOP DROP
   cpad COUNT (squabble) ;

: scrummage  \ scrummage <string>  ( some words may be repeated)  
  ['] (scrummage) is xCombo
  0 PARSE  >R spad R@ CMOVE R>
  DUP 1+ 2 ?DO DUP I combinations LOOP DROP ;

\ Usage examples:
squabble Forth
scrummage Forth