Mathematical barbecue riddle

21 Nov 2016 - by 'Maurits van der Schee'

On the 19th of November, the Dutch Financial Times (Financieel Dagblad) has published a barbecue riddle on page 14. It is a combinatorial problem that certainly will have a nice theoretical solution, but that "we programmers" tend to solve in a few minutes using our favorite scripting language. The problem states (freely translated):

Problem

"Today is 'International Men's Day' and that's why we have a mathematical riddle about barbecuing. On our roof terrace there is a big barbecue with enough space for twenty pieces of meat next to each other. On this joyful day we have bought plenty of slices of bacon and hamburgers. Everybody knows you should never put two slices of bacon next to each other on the barbecue: the fat that drips from the bacon will make the coal catch fire. That's why next to a slice of bacon you should always put a hamburger, except for the position at the end of the BBQ, where there is no more room for meat.

In how many ways can we completely fill the barbecue, putting 20 pieces of meat next to each other?" (source)

Solution

I liked the puzzle as I could very well visualize it. And it took me no effort to write down the following algorithm:

<?php
$bbqs = [''];
for ($i=0;$i<20;$i++) {
  $new = [];
  foreach ($bbqs as $bbq) {
    array_push($new,$bbq.'h',$bbq.'s');
  }
  $bbqs = array_filter($new,function($v){ 
    return strpos($v,'ss')===false;
  });
}
var_dump(count($bbqs));

I'm pretty sure that this could be written more elegant, but this was what came to mind. The algorithm will start with 1 empty barbecue and will create a new set of barbecue configurations by adding a hamburger and a slice of bacon to each of them (doubling the amount of configurations). Next it will remove all barbecue configurations that violate the "no two slices of bacon in a row" rule.

In retrospect

Although the answer is correct (17711), this was not the way the problem was meant to be solved. That didn't matter to me as I still enjoyed the puzzle a lot. Thank you newspaper!

PS: Liked this article? Please share it on Facebook, Twitter or LinkedIn.

TQ
dev.com