A Tractable Artificial Intelligence Problem

This essay is about a suggested student project in Java programming. This essay gives a rough overview of how it might work. It does not describe an actual complete program. I have no source, object, specifications, file layouts or anything else useful to implementing this project. Everything I have to say to help you with this project is written below. I am not prepared to help you implement it; I have too many other projects of my own.

I do contract work for a living, which could include writing a program such as this. However, I don’t do people’s homework for them. That just robs them of an education.

You have my full permission to implement this project any way you please.

This is a fairly simple artificial intelligence problem that mimicks, in miniature, the problem computer programmers have extracting specifications from users and turning those specifications into code.

Have a look at The Learn To Count Applet, particularly the source code. It contains code to count out in words in various languages.

I wrote the class for each language by getting a set of example numbers and words from a native speaker or a phrasebook or by sampling Internet posts, e.g. 21 == "vingt et un" in French, and deducing the rules for converting numbers to words and writing the code. I would then print out a set of sample numbers using the rules (selecting the samples to ensure I cover all the rule variants), and check them with a native speaker. He would then give me some more examples to explain the exceptions to the rules he had forgotten about previously. I would then convert those exceptions into rules, code them, and go round again until the native speaker was happy. Sometimes the native speaker would tell me the rules directly. Usually, these were less useful and less ambiguous than two or three examples.

I discovered there were various patterns in the rules. Different languages had various combinations of the standard patterns.

The process was fairly easy, quite mechanical, and allowed for a fair bit of trial and error rather than demanding brute reasoning.

Could you automate the task of writing code for additional languages?

Could you write a program that, just shown some counting examples from a foreign language, could compose a program to generate all the longs out in words? The answer is yes, you could write such a program, no problem, though it would be "cheating ". It would just require a bit of patience to manually write the code for each human written language, then recognize it, and cough up the previously optimised code when handed a set of examples in that language.

What we want is something a little cleverer, that could work on a language it had never seen before, but that was a human language. Again you could cheat, in a lesser way this time, my simply cataloging all features of counting in all written human languages, writing custom code to recognize each feature, and cranking out code by turning on or off pieces of preformed boilerplate.

One way to attack the problem is to ask yourself, "How could I rapidly generate, generalise and optimise the cheating solution?" Another is, how could I solve the simpler problem of just handling the 20 or so languages the Learn To Count Applet already knows, or some subset of them.

So think of it as a contest. You will be handed a Java class, that will accept a long positive or negative and will return you a String for the corresponding number in words in the target language. Your program will then, by probing the class for examples, and making inferences, construct a program that reproduces the one inside the black box to convert numbers to words for the unknown language inside the class.

You get points for:

Elegance (mathematically simple and ingenious)
Generality (ability to handle various curves thrown at it.)
Compactness, speed and beauty of both the code itself and the code generated.
How accurate generated code is.
How few calls to the black box class to generate examples you required. Only unique samplings count. There is no penalty for asking for the same number more than once.
If you want a slightly simpler problem, for fewer points, assume you are given a bit map of interesting examples to start, that cover at least one example of each of the quirks of the language. You may still need to probe other numbers to test your assumptions about the patterns behind those examples.
You get bonus points if you can also generate code to go the other way, take a word accurately spelled out in numbers in the foreign language and convert it to a long.
You also get bonus points for being the first to submit a long->words class with Java source for any actual human language to the Learn To Count class library. There is no point in great duplication of effort there.

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.18]	The information on this page is for non-military use only.
	You are visitor number 6,596.	Military use includes use by defence contractors.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/Mindprod website mirror)
	http://mindprod.com/project/ai.html	J:\mindprod\project\ai.html