[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

Recognizing strings based on a set of restrictions is a common computational problem.  A Slurpy is a string of characters that has certain properties. Your program will read in strings of characters and output whether or not they are Slurpies. 

A Slump is a character string that has the following properties:

1. Its first character is either a 'D' or an 'E'.

2. The first character is followed by a string of one or more 'F's.

3. The string of one or more 'F's is followed by either a Slump or a 'G'. The Slump or 'G' that follows the F's ends the Slump. For example DFFEFFFG is a Slump since it has a 'D' for its first character, followed by a string of two F's, and ended by the Slump 'EFFFG'.

4. Nothing else is a Slump.

A Slimp is a character string that has the following properties:

1.  Its first character is an 'A'.

2. If it is a two character Slimp then its second and last character is an 'H'. If it is not a two character Slimp then it is in one of these two forms:

   1.  'A' followed by 'B' followed by a Slimp followed by a 'C'.

   2.  'A' followed by a Slump (see above) followed by a 'C'.

3. Nothing else is a Slimp.

A Slurpy is a character string that consists of a Slimp followed by a Slump.

Background & Techniques

This problem is from the 1996 Mid-Atlantic Regional ACM Programming Contest.   56 college teams tried it and 35 solved is successfully.    Are you ready to join a team?

My first thought in selecting this problem was that it would make a good filler program while I worked on something more challenging.     And it is a pretty good example of a recursive definition, Slumps are defined in terms of  letters and Slumps.   Slimps are made from letters, Slimps and Slumps.

Then, while thinking about a more concise way to define the problem, I spent a pleasant afternoon rediscovering Extended Backus-Naur Form (EBNF) method of specifying  the syntax (the elements and rules of a language).    Delphi, Pascal, any other programming language as well as the "Slurp" language of our current problem can be defined using EBNF.     It's pretty darn simple to be so powerful.  Any  EBNF language definition consists of

Because of the variations,  every document using EBNF to define a language will usually define the conventions it is using.  Mine will be standard except that  I'll put the terminal symbols in bold type to distinguish them from  non-terminal and meta-symbols.  So our problem can be defined with these three rules: 

1. <Slump> ::= DF{F}G | EF{F}G | DF{F}<Slump> | EF{F}<Slump>;

2. <Slimp> ::= AH | AB<Slimp>C | A<Slump>C;

3. <Slurpy> ::= <Slimp><Slump>;

In case you're interested, here's a link to the final draft of the ISO EBNF Standards document.  I know little about the International Standard Organization, except that they don't make their standards freely available via the Web and they must use very expensive paper since they want 62 Swiss Francs ($40!) for the 12 page EBNF Standards document!   Sounds like a rip-off to me -- maybe it's not surprising that the standard is usually ignored.   

Rant aside, EBNF is useful for compiler writers since they provide straightforward language definitions - in fact there are "compiler compilers"  that can read any EBNF description set and produce a compiler program based the the rules.  YACC (Yet Another Compiler Compiler) is the prototype for this and is widely distributed in the Unix/Linux world.   (Windows versions exist). 

 Running/Exploring the Program 

Suggestions for Further Explorations

Modified:  May 15, 2018

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.