The Lilliputian Procgen Challenge

There was a discussion on euphoria recently about procedurally generated text vs random text, where it was decided that procedurally generated text involved more than just randomness, it involved rules on how to put text together. I know that’s vague, but there’s not a clear boundary here.

So I’d like to start a challenge: create the smallest program you can that produces procedurally generated text. The goals are twofold: first, make your program using the smallest number of lines of code possible, and second: make it as clear as possible why this should be considered procgen and not just random text.

This isn’t a competition, I’m just really interested in seeing what people consider procgen and if it can be done without a huge corpus.

Languages could include Inform, C++, etc. Programs can be pasted into this thread.

/* The variables adjs, verbs, and nouns contain arrays of common English adjectives, verbs, and nouns. */
/* I'm also not including an implementation of select(), a function that chooses an item from an array at random. */

var LETTERS = "abcdefghijklmnopqrstuvwxyz".split('');

function createRegistry () {
  var used = {};
  LETTERS.forEach(letter => {used[letter] = false;});
  return used;
}

function useLetters (word, used) {
  word.split('').forEach(letter => {
    used[letter] = true;
  });
}

function countUnusedLetters (word, used) {
  var letters = _.uniq(word.split(''));
  var n = 0;
  letters.forEach(letter => {
    if (used[letter] === false) n++;
  })
  return n;
}

function findNextWord (words, used) {
  return words.sort((a, b) => {
    var aS = countUnusedLetters(a, used);
    var bS = countUnusedLetters(b, used);
    if (aS > bS) return -1;
    if (aS < bS) return 1;
    return 0;
  })[0];
}

function isPangram (used) {
  return LETTERS.every(letter => used[letter]);
}

function createPangram (used) {
  var chosenWord;
  words = ['the'];
  useLetters('the', used);
  chosenWord = select(adjs);
  words.push(chosenWord);
  useLetters(chosenWord, used);

  [adjs, nouns, verbs, adjs, adjs, nouns].forEach(corpus => {
    chosenWord = findNextWord(corpus, used);
    words.push(chosenWord);
    useLetters(chosenWord, used);
  });
  return {
    success: isPangram(used),
    phrase: words.slice(0, 5).concat(['the']).concat(words.slice(5))
  }
}

var failsafe = 0;
var succeeded = false;
var generated;

while (failsafe < 1000 && !succeeded) {
  generated = createPangram(createRegistry());
  if (generated.success) {
    console.log("Success after " + (failsafe + 1) + " tries.");
    succeeded = true;
  }
  failsafe++;
}

console.log(generated.phrase.join(' '));

Since I was pushing for the definition of procedural generation as distinct from just using randomness to produce content, I felt like I should come here and exemplify.

This program (run on Node.js) generates a random pangram using corpora of common English words and the familiar “the quick brown fox jumps over the lazy dog” format. It produces output like:

the sufficient contemporary knowledge believes the equal complex jazz
the powerful administrative background enjoys the excellent quick jazz
the physical wonderful objective marks the unique maximum organization
the significant powerful everybody makes the equal maximum jazz
the large communist everybody experiences the wonderful quick jazz
the religious contemporary everybody follows the quick maximum jazz

It does this by choosing the first adjective at random and then selecting whichever word has the most unused letters next; so this algorithm is actually deterministic save for the choice of initial word - “sufficient” as the first adjective will always give “the sufficient contemporary knowledge believes the equal complex jazz”, and some initial adjectives will never produce a pangram through this algorithm; this is why the program uses a multiple-tries approach to search for working pangrams.

(In actuality, the corpora I’m using can only generate 41 pangrams through this algorithm, so this is definitely a toy example)

This is exactly the kind of content I’m looking for. Nice work!

Very nice, Bruno!

This isn’t quite Lilliputian, but here’s the source for Garbage Collection in case anyone’s interested:

Source Code
"Garbage Collection" by expl0rerfr34k (retrieved to this world by Matt Weiner)

When play begins: say "[italic type]Some of our more goal-oriented friends have complained that explorers are too aimless--they don't know what to do with something that just gives you a bunch of stuff to take apart. So I decided to give them a nice linear directed version of the Garbage Explorer experience. Happy garbage-picking!--expl0rerfr34k[roman type][paragraph break]".

When play begins:
	choose row with a final response rule of immediately undo rule in the Table of Final Question Options;
	blank out the final question wording entry;
	choose row with a final response rule of immediately restore saved game rule in the Table of Final Question Options;
	blank out the final question wording entry.
	
Use American dialect and the serial comma.

Garbage Dump is a room.

Material is a kind of value. The materials are defined by the Table of Material Composition.

Permeability is a kind of value. The permeabilities are waterproof, porous, and holey.

Hardness is a kind of value. The hardnesses are brittle, flexible, chunky, crumbly, and soft.

Color is a kind of value. The colors are black, gray, green, red, brown, fuchsia, chartreuse, pink, maroon, yellow, blue, purple, and white.

Table of Material Composition
material	absorption	breakability 	adjectival form
wood	porous	brittle	"wooden"
metal	waterproof	brittle	"metal"
rubber	waterproof	flexible	"rubber"
rope	porous	flexible	"rope"
earth	porous	crumbly	"dirt"
rock	holey	chunky	"stone"
plastic	waterproof	brittle	"plastic"
meat	porous	soft	"fleshy"
glass	waterproof	brittle	"glass"

Connection is a kind of value. The connections are defined by the Table of Material Connection.

Table of Material Connection
connection	preposition	primary material list	secondary material list
lodged	" in"	{wood, metal, rubber, rope, rock, plastic, glass}	{earth, meat}
screwed	" to"	{rubber, wood, metal, plastic, glass}	{wood, metal, plastic}
attached	" to"	{rubber, wood, metal, plastic, glass}	{wood, metal, plastic, glass}
set	" in"	{glass, plastic, metal}	{wood, metal, plastic, rock}
tied	" to"	{rope, rubber}	{wood, metal, plastic, glass, rubber, rope, rock}
stuck	" to"	{wood, metal, rubber, rope, earth, rock, plastic, meat, glass}	{wood, metal, rubber, rope, earth, rock, plastic, meat, glass}
smeared	" on"	{earth, meat}	{wood, metal, rubber, rope, rock, plastic, glass}


A piece of garbage is in the Garbage Dump.
The piece of garbage has a material called the primary material. The piece of garbage has a material called the secondary material. The piece of garbage can be simple or composite. [If it's composite it has two materials. If not, ignore the secondary one.] The piece of garbage has a connection called the attachment.

Table of Fragment Texts
breakability	fragment adjective list	fragment noun list
brittle	{"jagged", "sharp", "smashed", "cracked", "smooth"}	{"shard", "piece", "fragment", "panel"}
flexible	{"ripped", "frayed", "bent", "tangled", "knotted"}	{"length", "piece", "fragment", "strand", "string"}
crumbly	{"crumbling", "wet", "thick", "dusty"}	{"clod", "hunk", "chunk", "piece", "mass", "lump"}
chunky	{"crumbling", "rough", "smooth", "bumpy", "jagged", "cracked", "smashed", "chipped"}	{"hunk", "chunk", "piece", "block"}
soft	{"greasy", "rotting", "soft", "squishy", "wet", "decomposing", "desiccated"}	{"hunk", "chunk", "mass", "piece", "blob"}

To say fragment description of (matter - a material):
	let shattering be the breakability of matter;
	choose a row with breakability of shattering in the Table of Fragment Texts;
	let adjective-word be a random member of the fragment adjective list entry;
	let noun-word be a random member of the fragment noun list entry;
	if noun-word is not "piece" and noun-word is not "length" and a random chance of 2 in 5 succeeds:
		if a random chance of 2 in 3 succeeds:
			say "[adjective-word] ";
		say "[adjectival form of matter] [noun-word]";
	otherwise:
		if a random chance of 2 in 3 succeeds:
			say "[adjective-word] ";
		say "[noun-word] of [matter]".
		
To shine is a verb. To bead up is a verb. To drip is a verb. To shimmer is a verb. To pool is a verb. To well is a verb. To spread is a verb. To sink is a verb. To stain is a verb. To wet is a verb. To bubble is a verb. To gather is a verb.

Table of Liquid Descriptions
absorption	liquid verb text	liquid preposition text	can be presubstantive
waterproof	"[shine]" 	" on"	true
waterproof	"[bead up]"	" on"	false
waterproof	"[drip]"	" down"	true
waterproof	"[shimmer]"	" on"	true
waterproof	"[pool]"	" on"	true
waterproof	"[well]"	" in the hollows of"	true
waterproof	"[spread]"	" across"	true
porous	"[well]"	" out of"	true
porous	"[sink]"	" into"	true
porous	"[stain]"	""	true
porous	"[wet]"	""	true
holey	"[gather]"	" in the pits of"	true
holey	"[bubble]"	" out of"	true
holey	"[sink]"	" into"	true
holey	"[drip]"	" from"	true

To decide what text is a random member of (L - list of texts):
	let N be the number of entries in L;
	let X be a random number between 1 and N;
	decide on entry X of L.

The ooze is a thing.

To say ooze text of (glop - the ooze) on (item - the piece of garbage):
	if the item is simple:
		let matter be the primary material of the item;
		let liquid penetrability be the absorption of matter;
		sort the Table of Liquid Descriptions in random order;
		choose a row with absorption of liquid penetrability in the Table of Liquid Descriptions;
		if a random chance of 1 in 2 succeeds:
			say "A [random color] [ooze synonym] [regarding the glop][liquid verb text entry][liquid preposition text entry] a [if a random chance of 1 in 2 succeeds][fragment description of matter][otherwise][surface of matter][end if].";
		otherwise:
			if the liquid preposition text entry is "": [passive voice necessary]
				now the story tense is past tense;
				say	"A [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] is [liquid verb text entry] by a [random color] [ooze synonym].";
				now the story tense is present tense;
			otherwise:
				say "[Liquid preposition text entry in truncated upper case] a [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] [if the can be presubstantive entry is true and a random chance of 7 in 9 succeeds][liquid verb text entry] a [random color] [ooze synonym][otherwise]a [random color] [ooze synonym] [liquid verb text entry][end if].";
	otherwise: [if the item is composite]
		let matter be the primary material of the item;
		let first liquid penetrability be the absorption of matter;
		let second matter be the secondary material of the item;
		let second liquid penetrability be the absorption of second matter;
		sort the Table of Liquid Descriptions in random order;
		choose a row with absorption of first liquid penetrability in the Table of Liquid Descriptions;
		let first liquid verb be the liquid verb text entry;
		let first liquid preposition be the liquid preposition text entry;
		let first presubstantive be the can be presubstantive entry;
		choose a row with absorption of the second liquid penetrability in the Table of Liquid Descriptions;
		let second liquid verb be the liquid verb text entry;
		let second liquid preposition be the liquid preposition text entry;
		let second presubstantive be the can be presubstantive entry;
		if the substituted form of "[first liquid verb]" exactly matches the text "[second liquid verb]":
			if a random chance of 1 in 2 succeeds:
				say  "A [random color] [ooze synonym] [regarding the glop][first liquid verb][first liquid preposition] a [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] and a [if a random chance of 1 in 3 succeeds][fragment description of second matter][otherwise][surface of second matter][end if] [maybe that]it is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage].";
			otherwise:
				say "A [random color] [ooze synonym] [regarding the glop][first liquid verb][first liquid preposition] a [if a random chance of 1 in 3 succeeds][fragment description of second matter][otherwise][surface of second matter][end if] and a [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] that is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage] it.";
		otherwise:
			if a random chance of 1 in 4 succeeds and first presubstantive is true: [From the first matter flops a glop, which drop on the second matter--glop must be last here, so we check for presubstantive at the beginning]
				if the first liquid preposition is "": [passive voice necessary]
					now the story tense is past tense;
					say	"A [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] is [first liquid verb] by a [random color] [ooze synonym],[run paragraph on]";
					now the story tense is present tense;
					say " which [second liquid verb][second liquid preposition] the [if a random chance of 1 in 3 succeeds][fragment description of second matter][otherwise][surface of second matter][end if] that it is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage].";
				otherwise: [not passive voice]
					say "[first liquid preposition in truncated upper case] a [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] [first liquid verb] a [random color] [ooze synonym], which [second liquid verb][second liquid preposition] the [if a random chance of 1 in 3 succeeds][fragment description of second matter][otherwise][surface of second matter][end if] that it is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage].";
			otherwise if a random chance of 1 in 3 succeeds and second presubstantive is true: [second material first]
				if the second liquid preposition is "": [passive voice necessary]
					now the story tense is past tense;
					say	"A [if a random chance of 1 in 3 succeeds][fragment description of second matter][otherwise][surface of second matter][end if] is [second liquid verb] by a [random color] [ooze synonym],[run paragraph on]";
					now the story tense is present tense;
					say " which [first liquid verb][first liquid preposition] the [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] that is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage] it.";
					now the story tense is present tense;
				otherwise: [not passive voice]
					say "[second liquid preposition in truncated upper case] a [if a random chance of 1 in 3 succeeds][fragment description of second matter][otherwise][surface of second matter][end if] [second liquid verb] a [random color] [ooze synonym], which [first liquid verb][first liquid preposition] the [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] that is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage] it.";
			otherwise:
				say "A [random color] [ooze synonym] [regarding the glop][first liquid verb][first liquid preposition] a [if a random chance of 1 in 3 succeeds][fragment description of matter][otherwise][surface of matter][end if] and [regarding the glop][second liquid verb][second liquid preposition] a [if a random chance of 1 in 3 succeeds][fragment description of second matter][otherwise][surface of second matter][end if][if a random chance of 2 in 3 succeeds] that it is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage][end if].";

To say maybe that:
	if a random chance of 2 in 3 succeeds, say "that ".
	
To say maybe that is:
	if a random chance of 2 in 3 succeeds, say "that is ".
			
To say ooze synonym:
	say "[one of]ooze[or]slick[or]liquid[or]secretion[or]film[at random]".
	
To say surface of (matter - a material):
	if a random chance of 1 in 4 succeeds:
		say "[adjectival form of matter] surface";
	otherwise:
		choose a row with breakability of the breakability of matter in the Table of Fragment Texts;
		let noun-text be a random member of the fragment noun list entry;
		say "[noun-text] of [matter]".
		
To draw from the garbage heap:
	now the primary material of the piece of garbage is a random material;
	if a random chance of 1 in 4 succeeds:
		say "A [fragment description of the primary material of the piece of garbage].";
	otherwise:
		if a random chance of 1 in 2 succeeds:
			now the piece of garbage is composite;
			now the attachment of the piece of garbage is a random connection;
			now the primary material of the piece of garbage is a random entry in the primary material list of the attachment of the piece of garbage; 
			now the secondary material of the piece of garbage is a random entry in the secondary material list of the attachment of the piece of garbage; 			
			while the secondary material of the piece of garbage is the primary material of the piece of garbage:
				now the secondary material of the piece of garbage is a random entry in the secondary material list of the attachment of the piece of garbage;
			if a random chance of 1 in 2 succeeds:
				say "A [fragment description of the primary material of the piece of garbage] is [attachment of the piece of garbage][preposition of the attachment of the piece of garbage] a [fragment description of the secondary material of the piece of garbage].";
			otherwise:
				say ooze text of the ooze on the piece of garbage;
		otherwise:
			now the piece of garbage is simple;
			say ooze text of the ooze on the piece of garbage.
		
To decide which material is a random entry in (LM - list of materials):
	let N be the number of entries in LM;
	let X be a random number between 1 and N;
	decide on entry X of LM.

To say (T - a text) in truncated upper case:
	let X be T;
	if character number 1 in X is " ":
		replace character number 1 in X with "";
	replace character number 1 in X with character number 1 in X in upper case;
	say X.
	
Instead of looking for the first time:
	say "You pick up some garbage from the dump: [run paragraph on]";
	draw from the garbage heap;
	say "[line break]Examine another piece of garbage? (y/n)  ";
	while the player consents:
		say line break;
		draw from the garbage heap;
		say "[line break]Examine another piece of garbage? (y/n)  ";
	say "You leave the dump.";
	end the story finally.

The thing that makes it procedural rather than random is that there’s a bit of an underlying model–the material of a piece of garbage affects the main noun (you can have a “length” of rubber or rope but not of metal), the main adjective (only rubber or rope can be “frayed”), and the verb that describes how the ooze sits on it (ooze can “bead up” only on certain materials). And there’s a check to see if the same verb would be used twice in a sentence, which compresses them into one verb with a compound direct object.

There are also a few different sentence structures–if this were part of a larger game I’d try to have something that keeps track of where the focus is, so the game could pick a sentence structure that places emphasis on the focus. So if you type “x ooze” you get “A red ooze beads up on a panel of glass,” if you type “x glass” you get “On a panel of glass a red ooze beads up.”

The corpus isn’t very big but there is a reasonable variety of sentences you can get.

I hadn’t seen any Inform examples before, thanks!

The programming language FurryScript is designed to make a random procedural text. But what exactly is “procgen and not just random text” anyways (it does have rules how to put the text together (many different kind of rules are possible to implement with this), but it is unclear what exactly is wanted)