# The Golfer Riddle

The famous golfer riddle - first published (as far as I know) by rule-celebrity Dr. Ernest Friedmann-Hill (creator of the JESS rule engine) in this online-article.

Here's the riddle:

You look at the blackboard. It’s one of those word puzzles, the logic kind. Mrs. Krabapple is waiting for you to solve it. You quickly scan what she's scrawled on the board with her crone’s hand:

• A foursome of golfers is standing at a tee, in a line from left to right.
• Each golfer wears different colored pants; one is wearing red pants.
• The golfer to Fred’s immediate right is wearing blue pants.
• Joe is second in line.
• Bob is wearing plaid pants.
• Tom isn’t in position one or four, and he isn’t wearing the hideous orange pants.

In what order will the four golfers play, and what color are each golfer’s pants?

You get the gist of it right away, but how on earth are you supposed to figure it out? There’s no formula to use, no analytic procedure for deriving a solution. Algebra was one thing, but this? Why weren’t you paying attention in class?

Rules to the rescue! A rule–based program can satisfy Mrs. Krabapple by efficiently finding the one combination of names, positions, and colors that fits all the constraints.

## The Solution

Credits for this solution to JBoss-Rules - most of this example is contained in their distribution.

Short note: I implemented a solution to the golfer-riddle in Prolog using backward chaining... They look quite similar but the Prolog-version is a few lines shorter...

### Basic Idea

We have two classes, `Golfer` and `GolfingExample`, the latter responsible for initializing the rule engine, reading the rules from a file, asserting the facts (here: `Golfer`-objects) to the working memory and invoking the engine.

1. Create Golfer-objects for every possible combination of name, color and position.
2. Let the rule engine select those which satisfy the riddle's conditions.

## The Java Classes

### `Golfer.java`

```    public  class Golfer {
private String name;
private String color;
private int position;

public Golfer() {}

public Golfer(String name,   String color, int position) {
super();
this.name = name;
this.color = color;
this.position = position;
}

public String getColor() {
return this.color; }

public String getName() {
return this.name;  }

public int getPosition() {
return this.position;  }

} // Golfer
```

Ok, that one is very straightforward, nothing special here, just a simple JavaBean.

### `GolfingExample.java`

Now for our infrastructure-code, which has to control creation of `Golfer`-objects and invoke the rule engine.

``````public class GolfingExample {

public static void main(final String[] args) throws Exception {

// read the rules from file "golf.drl"
final PackageBuilder builder = new PackageBuilder();
GolfingExample.class.getResourceAsStream( "golf.drl" ) ) );

// create ruleBase and working memory
final RuleBase ruleBase = RuleBaseFactory.newRuleBase();

final StatefulSession session = ruleBase.newStatefulSession();

// create all possible Golfer objects
String[] names = new String[] { "Fred", "Joe", "Bob", "Tom" };
String[] colors = new String[] { "red", "blue", "plaid", "orange" };
int[] positions = new int[] { 1, 2, 3, 4 };

for ( int n = 0; n < names.length; n++ ) {
for ( int c = 0; c < colors.length; c++ ) {
for ( int p = 0; p < positions.length; p++ ) {
session.assertObject(
new Golfer( names[n], colors[c], positions[p]) );
}
}
}

// invoke the rule engine
session.fireAllRules();
session.dispose();

} // main
} // GolfingExample
```
```

Now we have our Java-infrastructure in place and can start coding the rule file.

### Developing the Golf Rules

#### Version Zero: Find Fred

Lets start with a very simple version of a rule file, just to find Fred:

File `golf.drl`(version 0):

``````rule "very simple golfer"
when // there is a golfer named Fred
g: Golfer( name == "Fred )
then
System.out.println(  g.getName() + "   " +
g.getPosition() + "   " +
g.getColor() );
end // very simple golfer
```
```

This rule makes our rule engine look for every Golfer object whose name-attribute == "Fred". Not suprisingly, given the large number of Golfer-objects we asserted in our `GolfingExample`, it finds the following:

```Fred  orange   4
Fred  orange   3
Fred  orange   2
Fred  orange   1
Fred  plaid   4
Fred  plaid   3
Fred  plaid   2
Fred  plaid   1
Fred  blue   4
Fred  blue   3
Fred  blue   2
Fred  blue   1
Fred  red   4
Fred  red   3
Fred  red   2
Fred  red   1
```

These are all objects with name==Fred.

#### Version One: Find Fred and his Right Neighbour

Not let's add a second condition: The golfer to Fred's right is wearing blue. We do not know his name yet... For our convenience, we add a function named `printTwoGolfers` to our rule file, making it easier to print out our results!

Our rule now looks for pairs of golfers: Fred and the golfer to his right side (for whom the condition `position==fredsPosition+1` holds).

File `golf.drl`(version 1)

``````package org.drools.examples;

import org.drools.examples.Golfer;

rule "golfer riddle version 1"
when
// a golfer named fred
fred: Golfer( name == "Fred",
\$fredsPosition : position, \$fredsColor : color  )

// the golfer behind fred wears blue
second: Golfer( name != "Fred",
position == ( \$fredsPosition + 1 ),
color == "blue", color != \$fredsColor )
then
printTwoGolfers( fred, second );
end // rule version 1

function void printTwoGolfers( Golfer first, Golfer g2 ) {
System.out.println(
first.getName() + "-" + first.getPosition() + "-" + first.getColor() + ">>>" +
g2.getName() + "-" + g2.getPosition() + "-" + g2.getColor() );
}
```
```

This version finds pairs of golfers where Fred is positioned before the second one.:

``````Fred-3-orange>>>Tom-4-blue
Fred-3-plaid>>>Tom-4-blue
Fred-3-red>>>Tom-4-blue
Fred-2-orange>>>Tom-3-blue
Fred-2-plaid>>>Tom-3-blue
Fred-2-red>>>Tom-3-blue
...
(many lines deleted)
...
Fred-1-orange>>>Tom-2-blue
Fred-1-plaid>>>Tom-2-blue
Fred-1-orange>>>Joe-2-blue
Fred-1-plaid>>>Joe-2-blue
Fred-1-red>>>Joe-2-blue
```
```

#### Version Two: Add Joe to the Pair...

Another information we get from our riddle is that Joe is second in line. Lets add this condition to our rule, making the rule engine search for triplets of golfers:

File `golf.drl`(version 2)

``````package org.drools.examples;
import org.drools.examples.Golfer;

rule "Joe, Fred and his Neighbour"
when
// a golfer named fred
fred: Golfer( name == "Fred",
\$fredsPosition : position, \$fredsColor : color  )

// Golfer behind Fred wears blue
second: Golfer( \$unknownsName : name != "Fred",
\$unknownsPosition :  position == ( \$fredsPosition + 1 ),
\$unknownsColor : color == "blue", color != \$fredsColor )

// Joe is second
joe: Golfer( name == "Joe", \$joesPosition : position == 2,
position != \$fredsPosition,
\$joesColor : color != \$fredsColor )

then
printGolfer( fred ); System.out.print(">>");
printGolfer( second );System.out.print(">>");
printGolfer( joe );
System.out.println();
end // rule version 2

function void printGolfer( Golfer g ) {
System.out.print(
g.getName() + "-" + g.getPosition() + "-" + g.getColor());
}
```
```

The result, nobody wonders any longer, finds triples:

``````Fred-3-plaid>>Tom-4-blue>>Joe-2-orange
Fred-3-orange>>Tom-4-blue>>Joe-2-plaid
Fred-3-orange>>Tom-4-blue>>Joe-2-blue
Fred-3-red>>Tom-4-blue>>Joe-2-orange
Fred-3-orange>>Tom-4-blue>>Joe-2-red
Fred-3-plaid>>Tom-4-blue>>Joe-2-blue
Fred-3-red>>Tom-4-blue>>Joe-2-plaid
...
(many lines deleted)
...
Fred-1-plaid>>Joe-2-blue>>Joe-2-blue
Fred-1-plaid>>Joe-2-blue>>Joe-2-red
Fred-1-red>>Joe-2-blue>>Joe-2-blue
```
```

Hey - that's not what we wanted: Joe occurs twice within triples! Every golfer should occur only once...

The reason for this seemingly inconsistent behavior lies in our rule: both the variables `joe`and `second`can independently be instantiated to a golfer named `joe`. We could avoid this by adding a second rule - but our task was solving the riddle, not perfection :-)

#### The final version of `golf.drl`

```rule "Golfer Riddle"
when
// A golfer named Fred,
Golfer( name == "Fred",
\$fredsPosition : position, \$fredsColor : color  )

// Der Golfer hinter Fred trägt blau
Golfer( \$unknownsName : name != "Fred",
\$unknownsPosition :  position == ( \$fredsPosition + 1 ),
\$unknownsColor : color == "blue", color != \$fredsColor )

// Joe steht an zweiter Stelle
Golfer( name == "Joe", \$joesPosition : position == 2,
position != \$fredsPosition,
\$joesColor : color != \$fredsColor )

// Bob traegt Karo
Golfer( name == "Bob",
name != \$unknownsName,
\$bobsPosition : position != \$fredsPosition,
position != \$unknownsPosition, position != \$joesPosition,
\$bobsColor : color == "plaid",
color != \$fredsColor, color != \$joesColor,
color != \$unknownsColor )

// Tom ist nicht 1. oder 4., traegt kein Orange
Golfer( \$tomsName : name == "Tom",
\$tomsPosition : position != 1, position != 4,
position != \$fredsPosition, position != \$joesPosition,
position != \$bobsPosition,
\$tomsColor : color != "orange", color != "blue",
color != \$fredsColor, color != \$joesColor,
color != \$bobsColor )

then
System.out.println( "Fred " + \$fredsPosition + " " + \$fredsColor );
System.out.println( "Joe " + \$joesPosition + " " + \$joesColor );
System.out.println( "Bob " + \$bobsPosition + " " + \$bobsColor );
System.out.println( "Tom " + \$tomsPosition + " " + \$tomsColor );
end
```

This rule solves the riddle, but finds two (equal!) solutions - which I leave open for you to solve :-)

``````Fred 1 orange
Joe 2 blue
Bob 4 plaid
Tom 3 red
Fred 1 orange
Joe 2 blue
Bob 4 plaid
Tom 3 red
```
```