#import std
#import nat

(# The input file contains a list of words, with one word on each line.
The output is a maximal list of words in which each column is also a word.
For example

$ wordrect WORD.LST --s 2
eye
yen
end

#)

usage =

--<''> -[
wordrect - word rectangle detector
Copyright (C) 2008 Dennis Furey

Usage:
  wordrect WORD.LST [--exhaustive] [--sample n]

Options:
  --exhaustive  allow non-symmetric solutions (slow)
  --sample n    use only a randomly sampled n% of the word list]-

exhaustive =

%sLMk+ -&~&,leql$^&L&-+ -+
   ~&a^& ^rlfatPRPY/~& ~&ahhrPX; ~&ar^& ^T\~&falrtPXPR ~&alllPrXPllr2rhPHX; ~&rr&& %bNfOXsLXssLXXMk; -+
      ~&rr->rl %sLsLLsbNfOXXLLXXMk+ ^/~&l -+
         ~&r?\~&lrlrtPX ^(
            %sLLMk+ (%bNMk; ~&alPfalPRaqr)?r/~&lrl ~&lrrhlSK7x3lC,
            ^rrgFPlT/~&lrrt *lrrh2lD ~&prllPClrPXS; %sbNfOXXLMk; ~&a^& ^rrrPlfatPRPBC/~& ~&ahlrrPlhPHX),
         ^/~& %bNMk+ ~&alrEPalPalParPfabbIPWlrYiBPNQNQq:-0+ ~&rrhrlPS+-,
      ^lNrXX/~&lr ~&rgF+ (*D ^/~&r ^|H\~& =>/~&rrrPlHB)^*D/~&ll ~&rlrDrlNCCK7S+-,
   %bNfOXfOXsLXLMk+ ^px\~&hS * ^(
      ~&L; %bNfOXMk+ ~&lrPrX+ ^|(~&,-:0!+ ~&llPlrPrXXS)*^+ %cbNTMk+ ^arPardl2lrdr2HXPfalrvPDPMVNq(
         leql$^; ~&NiC; iol; ~&alParPfabbIPWalPQarPq:-0++ *+ -$+ ~&iK22X,
         %cnSXTMk+ -+
            *^ ^V\~&v ^|llPlrPrTsPX/~& successor*drPSL,
            ~&/`/; ~&ar^& ^V/~&alrigPZX ^M/~&f -<&l+ ~&ariFhK2hhPtSXS+-),
      ^/~&+ +^/(\/~&H+ ~&h) (*~+ -&&-+ (+)*lNrCXK9+ *-~&h)++ *+ -:0!!+ ^|(~&,\/-=)*lK2hlPrSAS+ ~&LhthPXSs),
   %sLLLMk+ leql-<hFiiDlStK9&h+ eql|=+ ~&itBF+-

symmetric =

%sLMk+ ~&ihB+ -+
   ~&a^& ^rlfatPRPY/~& ~&ahlrhK2hhPiXSNK26PPXrX; ~&ar^& ^rlfalrtPXPRPY/~& ~&alllPrXPllr2rhPHlrPHX; ~&rr&& -+
      ~&rrlZB->rl %fOsLLsfOXLLXXMk; ^/~&l ^/(eql?rrhhlPiX/~&rrhlSK7x3lC ~&rl) ^rrgFPlT/~&rrt -+
         *prllPClrPXSPS %sfOXLMk+ ~&a^& ^rrrPlfatPRPBC/~& ~&ahlrlhPHX,
         ^D/~&rrh ~&rrh2lX; %sfOXLfOXCk leql+~&lhl2ltPX&& -+
            ^|H\~& *~+ -&&-+ (==^)^*p\!* ~&NiCK9tNiXS+ &h!*NiC,
            ~&ltPrlhPHX+ ~&NlhlNS3XlHthlx4rX+-+-,
      ^lNrXX/~&lr ~&rgF+ (*D ^/~&r ^|H\~& =>/~&rrlHB)^*D/~&ll ~&rlrDrlNCCK7S+-,
   %fOWsLXLMk+ ^px\~& * ^(
      ~&r+ ^|(~&,-:0!)*^+ ~&/`/; ~&ar^& ^V/~&al ^M/~&f ~&ariFhK2hhPtSXS,
      +^(//~&+ ~&l,+^/~&r \/~&H+ ~&lth)++ ^/~&+ -+
         //+ *~+ -&&-+ ~&t+ (+)*lNrCXK9+ *-~&h,
         *+ -:0!!+ %cfALMk+ ^|(~&,\/-=)*lK2hlPrSAS+ ~&hthPXSs+-),
   %sLLMk+ leql-<&h+ eql|=+ ~&itBF+-

#comment usage
#executable <'par',''>
#optimize+

wordrect =

<.file$[contents: --<''>]>+ ||usage! ~command; -&
   ~files.&ihBtZB&& ~options; all -!
      ~keyword[='exhaustive'&& ~parameters.&Z,
      ~keyword[='sample'&& ~parameters.&itZBhB; -&~&,leql\'99',subset\digits&-!-,
   ||<'wordrect: no solutions found'>! ~&l?(exhaustive+ ~&r,symmetric+ ~&r)+ ^(
      ~options; any ~keyword[='exhaustive',
      ^H\~files.&h.contents ~&?(*~+ %~,~&!)+ %np+ ~parameters*=+ ~keyword[='sample'*~+ ~options)&-