2
$\begingroup$

I want to create an algorithm to build a hex matrix with given: - max n rows - max m collumns - min t rown - min q collumns

containing the specific words from a list: "example", "test", "algorithm".

For example. To build a hex matrix with:

  - max n = 5 rows
  - max m = 6 collumns
  - min t = 5 rows
  - min t = 4 collumns
  - containg words: "orange", "test"

enter image description here

Can anyone point me in the right direction of how to build this type of algorithm? ( C++, C#, Swift, Objective-C)

$\endgroup$

2 Answers 2

0
$\begingroup$

Represent the Hex as Graph;

  • each node has additional property; has_letter; $T,F$
  • add the first randomly
    • choose starting point on the graph, probably randomly
    • place the letters by DFS or BFS,
    • add the letter into a list $l$.
  • adding another word with one connection, from start

    • from the list find the first letter of the new string that in the middle of another.
    • place the remaining words by DFS or BFS in nodes with $F$ flag.
  • adding another word with one connection, not necessary from the beginning.

    • from the list find the letters of the new string.
    • One part may be on the upper; as corner and almond. if the connection is $o$, alm on the upper,
    • One part may be on the lower, and nd from the previous example.
    • place the upper part with DFS or BFS in nodes with $F$ flag.
    • place the lower part with DFS or BFS in nodes with $F$ flag.

Hope this helps;

$\endgroup$
0
$\begingroup$

A hex graph can be represented as a 2D matrix where every other column is shifted vertically. It is no big deal to enumerate the six neighbors of a given cell.

This said, you can start from an empty grid and write the words, starting from a random cell and moving in random directions, as long as the next cell is empty or already contains the next letter.

As the last condition will rarely happen by accident, you may try to choose a letter in the word to be written and try to write that word both ways from a cell that already contains that letter.

Presumably you will want a compact matrix with many crossings, but I see no better way to try a large number of times until you find a satisfactory solution. (Well, optimization techniques such as simulated annealing could help, but I am not sure that such a sophistication is worth it.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.