Weekly Programming Challenge #2

Generate Random Names from a Grammar

The role-playing geek in me has always been fascinated by ways to randomly generate content for fantasy games. Fifteen years ago I wrote several programs to randomly generate treasures, dungeons, characters, and even entire towns, and I don’t think I ever got tired of seeing the endless variety of things that those programs produced.

Best of all, those programs sat at the intersection of fiction and another of my favorite things: grammars.

Grammars

A grammar is just a formal set of rules that describe all possible elements of a set. For example, if we have a set of strings that look like ‘a’, ‘b’, ‘ab’, ‘aab’, ‘aabb’, ‘aaab’, ‘abbb’, and so forth, one grammar that describes those strings might be this:

S := A B
A := ‘’ | ‘a’ A
B := ‘’ | ‘b’ B

Each of those lines is called a production rule. The first symbol on the first line is (by convention) the start symbol, and represents where the grammar starts. Here, that’s an S. The grammar tells us that S may be substituted with an A followed by a B.

So, expanding S, we now have A B, and we can set about expanding those symbols in turn. We start with A, which (according to the rule) may be substituted with either an empty string, or a ‘a’ followed by another A. B expands similarly. (Those quoted strings are called terminals, because they cannot be substituted by anything else.) We repeat this process until the result is entirely composed of terminal symbols.

Generating Content from a Grammar

Here’s the fun part! We can generate content from a grammar by recursion. If we define a function for each non-terminal symbol (S, A, and B, in the grammar above), we can compose those functions in such a way that calling S will return a random string, like in the Ruby implementation below:

def S
  A + B
end
def A
  if rand(10) < 5
    ""
  else
    "a" + A
  end
end
def B
  if rand(10) < 5
    ""
  else
    "b" + B
  end
end

Isn’t that cool? Have I mentioned that I love playing with grammars?

Weekly Programming Challenge #2

So, this all brings us to our weekly challenge. We’re going to write a program that randomly generates Sindarin-esque names from a simple grammar. I won’t give you the grammar, though. Oh, no. That’s part of the fun. :) Instead, you’ll need to come up with the grammar by analyzing yourself some Tolkien. (I recommend this list of compound Sindarin names, but use whatever source you prefer.)

I’ll give you a hint, though — don’t try to define the grammar on a character-by-character basis. Instead, identify syllables, and build the grammar around those.

So, the challenge:

Normal mode: implement a name generator. Your solution should:

1. Display a list of ten randomly generated Sindarin-esque names.
2. Generate names of at least two syllables, and no more than five.
3. Be grammar-based, as described above. The grammar does NOT need to be able to generate every possible Sindarin name — just enough to be convincing.
4. Include the grammar used— even if just as a comment in the code.

Feel free to use whatever source you prefer while researching Sindarin names, but you might be hard pressed to find a more exhaustive list than this one.

Hard mode: your program must accept, as an argument, a file containing a grammar definition, and randomly generate ten strings from that grammar. The grammar may be in whatever format is easiest for you to parse (but you get serious bonus points for being able to read Extended Backus-Naur Form (EBNF)). Your submission should include a file with a grammar for Sindarin names, as well as at least one other grammar of your choice.

Surprise me! For this level, be creative! The sky is the limit. Whatever you come up with should be at least as difficult as hard mode, but it doesn’t need to be viciously difficult. Creativity is the key!

Go! The deadline for submissions is 12:00pm MDT (18:00 UTC) on Saturday, August 13.

This challenge is now ended, but please feel free to post your solutions anyway! I always love to see how people approach problems like this.