## Wednesday, February 7, 2018

### Buzzword poem generator algorithm

Conditions of the problem
Given: a list of buzzwords.
Problem: generate poem from these buzzwords.

We also need to know:

1) Result poem lines number.
2) Rhyme scheme.
3) Syllables in each line.

4) Minimum number of words in each line.
also:
5) Somehow know the number of syllables in each buzzword.
6) Somehow get the list of rhyming buzzwords.

Algorithm
1) Knowing the total number of syllables in each line  generate all combinations of sums (compositions) from all available number of syllables.
E.g. we have buzzwords with the number of syllables 1, 2 and 3, and the total number of syllables in line (i.e. sum of syllables) equal 3. Compositions of 3 are:
+ 1 + 1
+ 2
+ 1
3
If we assume that we don't have buzzwords with number of syllables 2 then only two possible combinations can be: 1 + 1 + 1 and 3.
NB: Each positive integer n has 2 ** (n - 1) distinct compositions.

2) Knowing the number of syllables in each line, generate the base (I call it so) for future poem. The base is generated from random compositions for each number of syllables.
E.g. for two line poem with 3 and 4 syllables, the possible base can be the next:
[2, 1]
[1, 2, 1]
or
[2, 1]
[2, 2]
The poem base can be also limited to the minimum number of words per line.
For the example above with the minimum number of words equal 3, possible base can be the next:
[1, 1, 1]
[1, 1, 2]
or (notice that the first line has only one possible option):
[1, 1, 1]
[1, 1, 1, 1]

3) Knowing the rhyme scheme it is possible to get the last number of syllables for each line from poem base and group these numbers by rhyme scheme letters, thereby simplify the search of rhyme buzzwords.
The last number of syllables for each line are taken because only the last words form a rhyme.
For example the rhyme scheme is ABA, and the poem base is:
[1, 2, 1]
[1, 1, 2]
[3, 2]
Last numbers of syllables for each line are 1, 2 and 2.

1 A
2 B
2 A
Group them by rhyme scheme letters:
A: [1, 2], B: [2]

It is required to find all buzzwords that are rhyme, and have 1 and 2 syllables, then randomly select one
from the list of found variants for A letter.
And find only one random buzzword with 2 syllables for B letter.
It is important that after using a buzzword, it must be removed from the list of buzzwords to avoid duplication.
If the rhymes was not found it is required to indicate that, for example by returning empty result.

4) To this step we already have poem base, and rhyme scheme letters mapped to the found buzzwords. In case of empty mapping of rhyme scheme letters to buzzwords — go to step 2 and try again.
If the mapping of rhyme scheme letters to buzzwords isn't empty, start filling the poem base with buzzwords according to the number of syllables. The filling of each poem base line must be performed until the penultimate number of syllables, because the last ones were already found in previous step and saved in the mapping of rhyme scheme letters to buzzwords.
As in the previous step, it is important that after using a buzzword, it must be removed from the list of buzzwords to avoid duplication.
If the filling of the poem was not succeed — go to step 2 and try again.
If the number of attempts is too big, stop trying and display the error message.

Enhancements

Support the poem metrical feet, to generate more smooth poems.

This algorithm was used in my project: https://github.com/delimitry/buzzword_poem_generator