History

1998-1999 PVM distributed version

The original idea for the rose hit me between 1998-1999(it's in some journal entries from that time, but I don't remember exact dates). Soon after my cousin and I decided to use it, or more specifically the need for efficient grid organization, in project for parallel computing at University.

That project was finished using the PVM distributed platform, using a heuristic like the following:

  1. Distribute the program and the text file/2-letter,3-letter combo information to various nodes.
  2. At each node randomly fill a grid.
  3. After the grid was finished, search the grid for 2-letter swaps the produce 'better'(*) grids, and do so until no swap produces a better grid.
  4. Return the grid to the main node, here pick the best grid.
  5. Repeat as necessary.

(*) - A value of the grid was an evaluation based on how popular 2 and 3 letter combinations could be written.

Conclusion: a good algorithm, given sufficient time would provide fairly efficient grids.

2003 random selection version

This one was completely braindead and thus didn't suffer from the "would settle for suboptimal" flaw of the previous algorithm. But it was also slow and unpredictable.

Conclusion: slow and unpredictable, but some 'fair' quality grids were produced.

Current Algorithm

2003 weighted (re)organization heuristic

One of the first major improvements of the new algorithm is that the letters are laid out on the grid and the program assigns a distance between every point. This distance is used to augment scores and provide a means of qualitatively measuring efficiency. While at the moment it seems like a fairly obvious measurement, it was lacking in previous versions (which used a rigid node connection-type of layout).

Here are the current heuristic's steps:

  1. Load the text file(preferably something large with lots of common words so that good we can work with good averages) and count 2-letter combinations.
  2. Place the best character at the best location.
    1. Select an unplaced character.
    2. Location and Adjacency Score: Sum for each letter on grid ([occurance of 2-letter combination]+[occurance of 2-letter combination reversed] / [distance to letter])
    3. Character and Node Score: Sum for all letters ([occurance of 2-letter combination]+[occurance of 2-letter combination reversed] / [the node's distance to all other nodes]{this augments the characters score by the node's distance to all other nodes to give preferential treatment to well-placed nodes})
    4. Add B and C together for the character/location total value.
    5. Do this for all unplaced letters in all unfilled node locations. The best character/location is chosen.
  3. Then, optimize, that is, try all two-letter swaps (starting at the highest valued letters first) to see if the sum value of all nodes increases. If so, swap, if not, continue. Optimizing this way (with the highest valued letters first) allows 'grouping', if you will, where minor letters follow more major ones. This allows the grid to adjust over time as new letters are added.
  4. Repeat steps 2 and 3 until the grid is filled.

Conclusion: This algorithm consistantly produces good quality grids in less than ten seconds.