home *** CD-ROM | disk | FTP | other *** search
/ Boldly Go Collection / version40.iso / TS / 17A / ANGRY.ZIP / ANGRY.DOC < prev    next >
Text File  |  1992-07-30  |  5KB  |  129 lines
  1. Article 337 of rec.puzzles.crosswords:
  2. Path: wet!netcomsv!apple!agate!ames!olivea!uunet!munnari.oz.au!manuel!nimbus!tridge
  3. From: tridge@nimbus.anu.edu.au (Andrew Tridgell)
  4. Newsgroups: rec.puzzles.crosswords
  5. Subject: angry: a cross word builder (version 1.0)
  6. Message-ID: <1992Jul28.002644.11322@newshost.anu.edu.au>
  7. Date: 28 Jul 92 00:26:44 GMT
  8. Sender: news@newshost.anu.edu.au
  9. Organization: Australian National University, Canberra
  10. Lines: 908
  11. Originator: tridge@nimbus
  12.  
  13. I got quite a few replies from people who said that they would like a
  14. copy of my crossword builder, so I'm now posting version 1.0. At this
  15. stage I'm just posting source code. The main reason for this is that
  16. the replies I got raised several queries that showed my ignorance of
  17. crossword building. Once these are resolved (if ever) then I'll have
  18. to organise a post of an IBM PC binary.
  19.  
  20. Before I go on I should explain that the code was produced as part of
  21. a race. My wife tried to produce the crossword by hand (with the help
  22. of a windows based crossword program) and I tried to write code to do
  23. it automatically. I won, which shows the code was not designed to be
  24. "model programming". It helped that my wife is hopeless with
  25. crosswords.
  26.  
  27. Here are some of the questions that were raised along with some other
  28. limitations of the code:
  29.  
  30. Q) Does it produce rotationally symmetric crosswords?
  31.  
  32. A) No. I didn't even know crosswords were supposed to be rotationally
  33. symmetric. Why are they? I looked a few up in the paper and found that
  34. were indeed symmetric, which I had never noticed before.
  35.  
  36.  
  37. Q) Can you input your own grid?
  38.  
  39. A) No. It probably wouldn't be all that hard to re-code it to do this
  40. but I suspect that with a short list of words you wouldn't get a high
  41. success rate. If you fed it the whole dictionary then there wouldn't
  42. be a problem (I think).
  43.  
  44.  
  45. Q) Can it produce crosswords with no black squares? (such as 6x6 problem)
  46.  
  47. A) No. It can ONLY produce crosswords where you can place the words
  48. one at a time so that after each word the crossword is "legal". This
  49. precludes a whole host of possible crosswords.
  50.  
  51.  
  52. Q) What is the .pzl format?
  53.  
  54. A) It's the format used by the Microsoft windows shareware program
  55. "xword" - available from a friendly ftp site near you. Angry also
  56. saves the puzzles in plain text, with spaces for black squares. I put
  57. in the .pzl format so you could get pretty printouts.
  58.  
  59.  
  60. Q) How does it work?
  61.  
  62. A) Brute force, with a bit of smarts built in. In concept it tries all
  63. words in all positions then picks the word with the highest "score",
  64. places that word then tries again. Doing this with a dictionary would
  65. take years of course, so I then define a "depth" so the user can
  66. compromise between speed and better crosswords. If
  67. depth==number_of_words then it is brute force. If depth is N then do this
  68.  
  69.     1. pick N words at random
  70.     2. find the best position for each word (highest score - see below)
  71.     3. choose randomly from among highest scoring words
  72.     4. place word
  73.     5. if any words left go to 1.
  74.     6. remove any words not connected to other words
  75.     7. goto 1
  76.     FINAL. If depth > 10 then do a brute force final effort.
  77.  
  78.     SCORE: 
  79.        +35 for connection not at the end of a word
  80.        +30 for connection at end of a word
  81.        +9 for not lying along an edge
  82.        +1 for being oriented differently to the last word
  83.     (these are VERY ad hoc)
  84.  
  85. Angry gives up when it can't place any more words. It then tries to
  86. produce another, and prints it if it is better then the first. These
  87. keeps going till you stop the program. (press ^C under unix - press
  88. and key under DOS)
  89.  
  90. Whenever a better xword is found it is written both to best.doc and
  91. best.pzl.
  92.  
  93.  
  94. Usage: angry Xsize Ysize WordList [depth]
  95.  
  96. Xsize: number of squares across 
  97.  
  98. Ysize: number of squares down
  99.  
  100. WordList: file containing a column of words 
  101.  
  102. depth: depth of search.  This defaults to 1 (fastest). I recommend
  103. about 5 for normal use. If you put in 11 or high then you will
  104. activate a brute force search at the end of the build (slow).
  105.  
  106.  
  107. Q) How fast is it?
  108.  
  109. A) That depends on the depth. With a depth of 1 it produces crosswords
  110. every few seconds on a Sun4. On a PC it may take 30 seconds to get a
  111. crossword. The time will increase as Xsize*Ysize. It will not increase
  112. with an increase in wordlist length (not by much anyway) unless
  113. depth>10 in which case the final stage goes linearly with the number
  114. of words.
  115.  
  116.  
  117. Q) How big can it get?
  118.  
  119. A) The only limitation is the machines memory. Also the words can't
  120. be longer than 1000 letters - which I don't think will be a problem
  121. (at least in English!)
  122.  
  123.  
  124.  
  125. OK enought drivel for now - here is the source. Remember - it cost
  126. nothing.
  127.  
  128.  
  129.