Slimps, Slumps, and Slurpies

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

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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

  • Terminal symbols (sometimes displayed in bold faced type or enclosed in double quotes).  These are the "atoms" of the language.  

  • Non-terminal symbols, frequently enclosed in angled brackets (< >)  which are formed from  concatenations terminal symbols and other non-terminal symbols 

  • Rules which define the non-terminal symbols.  All of the non-terminal symbols are defined by occurring on left side of a rule and are usually considered the name of the rule.

  • Meta-symbols  used in the rules defining the non-terminal symbols.   The meta prefix  means "about"  so meta-symbols are those used in talking about the language but are not part of the language.   The common meta-symbols in EBNF are:   

    • < >  (brackets surrounding a non-terminal name).

    • ::=   (is equivalent to, "means").

    • |       (definition alternatives, "or").

    • [ ]     (0 or 1 occurrences of enclosed symbols).

    • { }     (0 or more occurrences of enclosed symbols).  The definition of curly brackets varies according to the implementer.   Some references define curly brackets to mean one or more occurrences.  The ISO standard says that one or more occurrences should be represented as { }-, a minus sign after the brackets.    

    • . ;    (rule terminators - some way to indicate the end of a rule, commonly dot or semicolon. I have also seen  <EOL> used).

    • "    (double quotes, sometimes used around single character terminal symbols which might be confused with meta-symbols).

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

Compiler development is an interesting area of study.  Compilers read source code and  generate output programs that run independently of the compiler.  Interpreters perform the same function except they execute the resulting code immediately.   Maybe it would be interesting to develop a mini-language and implement a Delphi interpreter.   
 http://compilers.iecc.com/ is the home page of an active compilers newsgroup.   Lots of good browsing here including this link to an online book entitled  "Let's Build a Compiler" by Dr. Jack Crenshaw.
Wonder if there exists a Delphi YACC?  We could start with a Slurp compiler that would read the rules and identify arbitrary strings. 

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.