title: Wrongly asked or am I stupid?
body: <p>There's a blog post comment on <a href="http://www.codinghorror.com/blog/2010/02/the-nonprogramming-programmer.html#comments" rel="nofollow noreferrer">codinghorror.com</a> by Paul Jungwirth which includes a little programming task:</p>
  
  <blockquote>
    <p>You have the numbers 123456789, in that order. Between each number, you must insert either nothing, a plus sign, or a multiplication sign, so that the resulting expression equals 2001. Write a program that prints all solutions. (There are two.)</p>
  </blockquote>
  
  <p>Bored, I thought, I'd have a go, but I'll be damned if I can get a result for 2001.  I think the code below is sound and I reckon that there are zero solutions that result in 2001.  According to my code, there are two solutions for 2002.  Am I right or am I wrong?</p>
  
  <pre><code>/**
   * Take the numbers 123456789 and form expressions by inserting one of ''
   * (empty string), '+' or '*' between each number.
   * Find (2) solutions such that the expression evaluates to the number 2001
   */
  
  $input = array(1,2,3,4,5,6,7,8,9);
  
  // an array of strings representing 8 digit, base 3 numbers
  $ops = array();
  $numOps = sizeof($input)-1; // always 8
  $mask = str_repeat('0', $numOps); // mask of 8 zeros for padding
  
  // generate the ops array
  $limit = pow(3, $numOps) -1;
  for ($i = 0; $i &lt;= $limit; $i++) {
      $s = (string) $i;
      $s = base_convert($s, 10, 3);
      $ops[] = substr($mask, 0, $numOps - strlen($s)) . $s;
  }
  
  // for each element in the ops array, generate an expression by inserting
  // '', '*' or '+' between the numbers in $input.  e.g. element 11111111 will
  // result in 1+2+3+4+5+6+7+8+9
  $limit = sizeof($ops);
  $stringResult = null;
  $numericResult = null;
  for ($i = 0; $i &lt; $limit; $i++) {
      $l = $numOps;
      $stringResult = '';
      $numericResult = 0;
      for ($j = 0; $j &lt;= $l; $j++) {
          $stringResult .= (string) $input[$j];
          switch (substr($ops[$i], $j, 1)) {
              case '0':
                  break;
              case '1':
                  $stringResult .= '+';
                  break;
              case '2':
                  $stringResult .= '*';
                  break;
              default :
          }
      }
  
      // evaluate the expression
  
      // split the expression into smaller ones to be added together
      $temp = explode('+', $stringResult);
      $additionElems = array();
      foreach ($temp as $subExpressions)
      {
          // split each of those into ones to be multiplied together
          $multplicationElems = explode('*', $subExpressions);
          $working = 1;
          foreach ($multplicationElems as $operand) {
              $working *= $operand;
          }
          $additionElems[] = $working;
      }
      $numericResult = 0;
      foreach($additionElems as $operand)
      {
          $numericResult += $operand;
      }
  
      if ($numericResult == 2001) {
          echo "{$stringResult}\n";
      }
  }
  </code></pre>