Acrostic Generator: Part one

It’s been a while since my last blog post, which was about my Google Summer of Code project. Even though it has been months since I completed GSoC, I have continued working on the project, increasing acrostic support in Crosswords.

We’ve added support for loading Acrostic Puzzles in Crosswords, but now it’s time to create some acrostics.

Now that Crosswords has acrostic support, I can use screenshots to help explain what an acrostic is and how the puzzle works.

Let’s load an Acrostic in Crosswords first.

Acrostic Puzzle loaded in Crosswords

The main grid here represents the QUOTE: “CARNEGIE VISITED PRINCETON…” and if we read out the first letter of each clue answer (displayed on the right) it forms the SOURCE. For example, in the image above, name of the author is “DAVID ….”.
Now, the interesting part is answers for the clues fit it in the SOURCE.

Let’s consider another small example:
QUOTE: “To be yourself in a world that is constantly trying to make you something else is the greatest accomplishment.”
AUTHOR: “Ralph Waldo Emerson”

If you see correctly, letters of SOURCE here are part of the QUOTE. One set of answers to clues could be:

Solutions generated using AcrosticGenerator. Read the first letter of each Answer from top to bottom. It forms ‘Ralph Waldo Emerson’.

Coding the Acrostic Generator

As seen above, to create an acrostic, we need two things: the QUOTE and the SOURCE string. These will be our inputs from the user.

Additionally, we need to set some constraints on the generated word size. By default, we have set MIN_WORD_SIZE to 3 and MAX_WORD_SIZE to 20.. The user is allowed to change it. However, users are allowed to change these settings.

Step 1: Check if we can create an acrostic from given input

You must have already guessed it. We check if the characters in the SOURCE are available in the QUOTE string. To do this, we utilize IPuzCharset data structure.
Without going in much detail, it simply stores characters and their frequencies.
For example, for the string “MAX MIN”, it’s charset looks like [{‘M’: 2}, {‘A’: 1}, {‘X’:1}, {‘I’: 1}, {’N’: 1}].

First, We build a charset of the source string and then iterate through it. For the source string to be valid, the count of every character in the source charset should be less than or equal to the count of that character in the quote charset.

for (iter = ipuz_charset_iter_first (source_charset);
       iter;
       iter = ipuz_charset_iter_next (iter))
    {
      IPuzCharsetIterValue value;
      value = ipuz_charset_iter_get_value (iter);

      if (value.count > ipuz_charset_get_char_count (quote_charset, value.c))
        {
          // Source characters are missing in the provided quote
          return FALSE;
        }
    }

return TRUE;

Since, now we have a word size constraint, we need to add one more check.
Let’s understand through this an example.

QUOTE: LIFE IS TOO SHORT
SOURCE: TOLSTOI
MIN_WORD_SIZE: 3
MAX_WORD_SIZE: 20

Since, MIN_WORD_SIZE is set to 3, the generated answers should have a minimum of three letters in them.

Possible solutions considering every solution
has a length equal to the minimum word size:
  T _ _
  O _ _
  L _ _
  S _ _
  T _ _
  O _ _
  O _ _

If we take the sum of the number of letters in the above solutions, It’s 21. That is greater than number of letters in the QUOTE string (14). So, we can’t create an acrostic from the above input.

if  ((n_source_characters * min_word_size) > n_quote_characters)
  {
    //Quote text is too short to accomodate the specificed minimum word size for each clue
    return FALSE;
  }

While writing this blog post, I found out we called this error “SOURCE_TOO_SHORT”. It should be “QUOTE_TOO_SHORT” / “SOURCE_TOO_LARGE”.

Stay tuned for further implementation in the next post!