OpenRules Solution for the Christmas Challenge

DMCommunity.org offered a new Dec-2017 Challenge called “Reindeer Ordering“. It has a nice Christmas formulation:
Santa always leaves plans for his elves to determine the order in which the reindeer will pull his sleigh. This year, for the European leg of his journey, his elves are working to the following schedule, which will form a single line of nine reindeer. Here are the rules:

  1. Comet behind Rudolph, Prancer and Cupid
  2. Blitzen behind Cupid
  3. Blitzen in front of Donder, Vixen and Dancer
  4. Cupid in front of Comet, Blitzen and Vixen
  5. Donder behind Vixen, Dasher and Prancer
  6. Rudolph behind Prancer
  7. Rudolph in front of Donder, Dancer and Dasher
  8. Vixen in front of Dancer and Comet
  9. Dancer behind Donder, Rudolph and Blitzen
  10. Prancer in front of Cupid, Donder and Blitzen
  11. Dasher behind Prancer
  12. Dasher in front of Vixen, Dancer and Blitzen
  13. Donder behind Comet and Cupid
  14. Cupid in front of Rudolph and Dancer
  15. Vixen behind Rudolph, Prancer and Dasher.

We need to create a decision model that determines the order of the reindeer.

Looks like a quite simple problem that can be solved by a 7-year-old kid by shuffling 9 cards with deer names. It may take a lot of tried-and-failed attempts but after a while the problem will be solved. Dr. Bob Moore submitted an interesting solution, for which he wrote a primitive constraint engine in Python. I like what Bob did, but I cannot agree with his suggestion that “most of the DMN tools are not appropriate” for this problem. The problem certainly can be formulated using traditional decision modeling constructs such as decision tables. Is every rule engine powerful enough to execute this decision model? Of course, the answer is “No”, but this is a good example of a problem domain where different decision modeling tools actually compete.

Back in 2011 I published a paper that proved that a business decision model is a special case of a constraint satisfaction problem, and thus can be solved by a rule engine implemented using any off-the-shelf constraint solver. Since then OpenRules provides its customers with a special rule engine called “Rule Solver” that is based on a JSR-331 compliant constraint solver. Let’s see how easily (and nicely) we may represent this problem in OpenRules using simple Excel tables.

This problem deals with 9 decision variables (one per deer) specified in this glossary:

Then we may express all deer ordering constraints using the following OpenRules decision table:

Hope this table is intuitive enough and doesn’t require any comments. Now we can run OpenRules rule engine using the execution mode “Solve”.  It will immediately produce the only solution:

     Prancer Cupid Rudolph Dasher Blitzen Vixen Comet Donder Dancer

It is interesting that after posting the above constraints we did not even need a search as all decision variables were already instantiated by constraint propagation. We will add the decision model “DecisionReindeer” to the standard OpenRules delivery.

Advertisements

One comment on “OpenRules Solution for the Christmas Challenge

  1. Jacob, your solution is an elegant demonstration of what you can do with OpenRules, but I think you misunderstood the comment “most of the DMN tools are not appropriate” you take from mine.

    It refers specifically to tackling the generalized problem which is what I wanted to do. Your solution (and Mike’s in Corticon) while perfectly correct, actually illustrate why I dismissed using tools which use a decision table approach when working on the challenge.

    If the objective is simply to solve to problem just as stated – what is the correct ordering for the nine named reindeer, given these fifteen particular ‘rules’ – I would trust most DMN/BRMS tools could cope easily. And both you and Mike certainly provide eloquent demonstrations of this. As I noted elsewhere my solution, with only nine reindeer, even brute force works perfectly well (as Damir’s SQL solution demonstrates).

    But this seems to work to the letter, not the spirit of the challenge. I wanted a solution which the elves would find useful from year to year as old reindeer retire, new ones join, and Santa comes up with a new set of ‘rules’ each year. Maybe Santa might even decide to upgrade his sleigh and have nineteen reindeer pulling it not nine (which would effectively kill brute force approaches).

    The immediate consequence of looking at the generalized problem is I could not explicitly use the name of any reindeer, nor any particular ordering rule anywhere in my solution, nor even assume how many reindeer I was working with. The reindeer names and the ordering ‘rules’ are simply input data (I only know them at run-time, not at modelling/build time). They cannot be part of the decision system itself.

    I may be being dim, but I can’t see how decision tables can help me here. When I start to build my solution, I seem to have no rows, and I don’t even know what columns I need. I’d be delighted if you could explain how I can use “traditional decision modelling constructs” because I’m stumped to see how they can help. I guess using Rete rules and patterns on the objects in working memory is probably viable, but in the context of this problem such an approach (at least to me) seems just a way of obfuscating list manipulation to make it look more clever than it really is.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.