Quick news

A Gray code generator in PHP

Submitted by fgm on Sun, 2009-02-22 19:09

For a recent case, I had to define the behaviour of a system with a lot of independent conditions to check, which could trigger any number of a set of messages and actions on data, and all of this based on a plain english (i.e. non algorithmic) description of the data, which only covered the most commons scenarios for these conditions, leaving lots of undefined combinations of inputs. What's one to do in such cases ?

During CS101, you probably learnt to build a Karnaugh map and reduce it in order to obtain reliable code in such cases. But for reduction to be actually doable by hand, you need to generate the Gray code by which to index it, and most online tools stop at 3x3, which wasn't sufficient. So here is the tiny contribution of the day: a Gray code generator in PHP. Nothing remarkable, just the kind of tool which takes 10 minutes to write, and you sometimes need to have at hand.

<?php
// $Id$
/**
* Generate a $size-sized Gray code sequence on stdout
*
* Probably not performance-efficient, though, but sufficient for usual needs:
* 7 sec on a small server for a 20-bit code.
*
* (c) 2009 OSInet
*
* Licensed under the General Public License version 3.
*/

$size = 10;     // Number of bits of the code
$print = FALSE; // Set to TRUE to generate code on stdout.
$current = array_fill(0, $size, 0);

function rightMostOne($arValue)
  {
  $pos = 0;
  while ($pos < count($arValue))
    {
    if ($arValue[$pos] == 1)
      return $pos;
    $pos++;
    }
  if ($pos == count($value))
    return -1;
  }

function numberOfOnes($arValue)
  {
  $ret = 0;
  foreach ($arValue as $bit)
    {
    if ($bit)
      $ret++;
    }
  return $ret;
  }

// ---- main -------------------------------------
$max = 1 << $size;
for ($i = 0; $i < $max ; $i++)
  {
  if ($print)
    {
    $s = '';
    foreach ($current as $bit)
      {
      $s = $bit . $s;
      }
    printf("%s\n", $s);
    }

  if (numberOfOnes($current) % 2)
    {
    $pos = (1 + rightMostOne($current)) % $size;
    // echo "pos = $pos\n";
    $current[$pos] = 1 - $current[$pos];
    }
  else
    {
    $current[0] = 1 - $current[0];
    }
  }
?>