[SOLVED] Programming Challenge #1 (Numbered in case there's more)

[roopurt18]

http://www.phpfreaks.com/forums/index.php/topic,177404.msg788966.html#msg788966

In the linked post, I stated that a good way to become a better programmer is to give yourself a challenging exercise.  I then offered to create a couple if anyone was interested, so here's the first.

 

Rewrite the following function so that it is easier to read and maintain, as well as optimizing where possible.  Imagine that this function exists in an application that you maintain and the logical tests are not so simple (i.e. pretend that $x >= $y is something more complex and harder to read).  Or imagine that this function was translated from one language to PHP verbatim and now it is your job to clean it up.

 

RESTRICTION: Not that you need to, but do not introduce any new functions into the code.  Your answer should include only the function doThis rewritten.

 

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){
  $result = 0;
  $value = very_expensive_operation($m, $n, $o);
  if(empty($m)){
    $result = 1;
    $result *= $bar;
  }else{
    if($n == 'one'){
      if($x < $y && $x > $z){
        $result = $y * $z + $x;
        $result *= $bar;
      }else{
        if($x >= $y || $x <= $z){
          $result = $y / $z - $x;
          $result *= $bar;
        }else{
          $result = $bar + $value;
          $result *= $foo;
        }
      }
    }else{
      if($o == 'two'){
        if($x < $y && $x < $z && ($y + $z <= 10)){
          $result = $y * $z + $x;
          $result *= $bar;
        }else{
          if(!($x >= $y || $x >= $z || ($y + $z <= 10))){
            $result = $y * $z + $x;
            $result *= $bar;
          }else{
            $result = $bar + $value;
            $result /= $foo;
          }
        }
      }else{
        $result = $foo;
        $result /= $bar;
      }
    }
  }
  return $result;
}
?>

 

Anyone who does this with brute force gets brownie points for perseverance.

[Daniel0]

Like this?

 

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o)
{
if(empty($m))
{
	return 1 / $bar;
}
else if($n == 'one')
{
	if($x < $y && $x > $z)
	{
		return ($y * $z + $x) * $bar;
	}
	else if($x >= $y || $x <= $z)
	{
		return ($y / $z - $x) * $bar;
	}
	else {
		return ($bar + very_expensive_operation($m, $n, $o)) * $foo;
	}
}
else if($o == 'two') {
	if($x < $y && $x < $z && ($y + $z <= 10) || !($x >= $y || $x >= $z || ($y + $z <= 10)))
	{
		return ($y * $z + $x) * $bar;
	}
	else {
		return ($bar + very_expensive_operation($m, $n, $o)) / $foo;
	}
}
else {
	return $foo / $bar;
}
}
?>

[roopurt18]

That's a start

[Daniel0]

:\

 

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o)
{
if(empty($m))
{
	return 1 / $bar;
}
else if(($n == 'one' && ($x < $y && $x > $z)) ||
        ($o == 'two' && (($x < $y && $x < $z && ($y + $z <= 10)) || !($x >= $y || $x >= $z || ($y + $z <= 10))))) // <-- wtf?
{
	return ($y * $z + $x) * $bar;
}
else if($n == 'one' || $o == 'two')
{
	return ($bar + very_expensive_operation($m, $n, $o)) / $foo;
}
else if($n == 'one' && ($x >= $y || $x <= $z))
{
	return ($y / $z - $x) * $bar;
}
else {
	return $foo / $bar;
}
}
?>

[roopurt18]

You're still missing a couple of items.  But let's assume it was spot on.

 

Can you prove that your rewrite is logically correct, i.e. that you didn't introduce any bugs?

[Daniel0]

No, I can't prove that I didn't make any bugs. I actually thought about that and it kind of bugs me that I couldn't. I suppose that is partially because I don't know what the function is indented to do and what it's intended output is and partially because very_expensive_function() is not defined in the above snippet.

 

Also, $asdf is not used so it's just redundant but I don't see any way of removing it from the argument list without breaking code that is dependent on the function.

[neylitalo]

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){

$result = 0;
$value = very_expensive_operation($m, $n, $o);

if(empty($m)){
	return $bar;
}

if($n == 'one'){
	if($x < $y && $x > $z){
		$result = ($y * $z + $x) * $bar;
	}else{
		$result = ($y / $z - $x) * $bar;
	}
	return $result;
}

if($o == 'two'){
	if($x < $y && $x < $z && ($y + $z <= 10)){
		$result = ($y * $z + $x) * $bar;
	}else{
		if($x < $y && $x < $z && ($y + $z > 10)){
			$result = ($y * $z + $x) * $bar;
		}else{
			$result = ($bar + $value) / $foo;
		}
	}
	return $result;
}

$result = $foo / $bar;

return $result;
}
?>

 

This is logically consistent with the original. I tried to do something with this, but couldn't find any way to clean up the conditions.

 

if($x < $y && $x < $z && ($y + $z <= 10)){
$result = ($y * $z + $x) * $bar;
}else{
if($x < $y && $x < $z && ($y + $z > 10)){

 

This is the logic for that section:

 

ONLY IF: Conditions a, b, and c are all true.

ONLY IF: Conditions a and b are true, and c is false

ANYTHING ELSE

 

The only place I was really able to clean anything up was in the if($n == 'one') area. If one of the first conditions is false, we know that its opposite counterpart is true - thereby making the else clause unnecessary. If the first conditions were not met, the second conditions were met by necessity.

[Daniel0]

I was thinking he wanted to move very_expensive_operation() somewhere so it would only be run if needed and not always. I figured that was why he named the function as he did.

[neylitalo]

Daniel0: In both of your posts, you have replaced:

 

<?php

if(empty($m)){
    $result = 1;
    $result *= $bar;
}

?>

 

with:

 

<?php

if(empty($m))
{
return 1 / $bar;
}

?>

 

$result *= $bar is equivalent to $result = $result * $bar, and since $result is 1, ($result * $bar) is equal to $bar.

 

And good catch with very_expensive_operation() - here's the updated code.

 

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){

$result = 0;

if(empty($m)){
	return $bar;
}

if($n == 'one'){
	if($x < $y && $x > $z){
		$result = ($y * $z + $x) * $bar;
	}else{
		$result = ($y / $z - $x) * $bar;
	}
	return $result;
}

if($o == 'two'){
	if($x < $y && $x < $z && ($y + $z <= 10)){
		$result = ($y * $z + $x) * $bar;
	}else{
		if($x < $y && $x < $z && ($y + $z > 10)){
			$result = ($y * $z + $x) * $bar;
		}else{
			$result = ($bar + very_expensive_operation($m, $n, $o)) / $foo;
		}
	}
	return $result;
}

$result = $foo / $bar;

return $result;
}
?>

[Daniel0]

Ah, used the wrong operator :-\ Second post was based on first so I didn't catch it there either.

 

So roopurt, yes, I did introduce a bug

[fert]

do we have to recode it in php?

[roopurt18]

Nope.

[roopurt18]

Scroll down for my solution.  By no means is this the only solution, nor do I even claim that it is correct.  What I'm most interested in is seeing if anyone else was familiar with this technique of refactoring code.  I doubt many of you are expecting what follows!  I'm leaving some white space before the solution, in case someone looks here by accident and still wants to try and solve it themselves.

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Solution:

 

List all variables used as l-values, i.e. they appear in code on the left side of assignment operations:

$result, $value

 

List all variables used as r-values, i.e. they appear in expressions or function calls:

$m, $n, $o, $x, $y, $z, $value

 

List all variables in neither list, these can be discarded as they are not used:

$asdf

 

Create a list of all logical tests, removing duplicates, and label them:

a : empty(m)

b : n == one

c : o == two

d : x < y

e : x >= y

f : x >= z

g : x > z

h : x <= z

i : x < z

j : y + z <= 10

 

Note that some of these are the logical NOT of others, i.e. d = !e.  Re-label the complements:

a  : empty(m)

b  : n == one

c  : o == two

d  : x < y

!d : x >= y

f  : x >= z

!f : x < z

g  : x > z

!g : x <= z

j  : y + z <= 10

 

Looking at this example, it is easy to see that depending on our logical tests, we are computing a result and saving it.  List all blocks of code that compute a result and label them, discarding duplicates:

#1 : $result = 1;

    $result *= $bar;

 

#2 : $result = $y * $z + $x;

    $result *= $bar;

 

#3 : $result = $y / $z - $x;

    $result *= $bar;

 

#4 : $result = $bar + $value;

    $result *= $foo;

 

#5 : $result = $foo;

    $result /= $bar;

 

#6 : $result = 0;

 

#7 : $value = very_expensive_operation($m, $n, $o);

 

#8 : $result = $bar + $value;

    $result /= $foo;

 

Convert our function to pseudocode.  First we replace all code blocks with their labels:

function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){
  #6
  #7
  if(empty($m)){
    #1
  }else{
    if($n == 'one'){
      if($x < $y && $x > $z){
        #2
      }else{
        if($x >= $y || $x <= $z){
          #3
        }else{
          #4
        }
      }
    }else{
      if($o == 'two'){
        if($x < $y && $x < $z && ($y + $z <= 10)){
          #2
        }else{
          if(!($x >= $y || $x >= $z || ($y + $z <= 10))){
            #2
          }else{
            #8
          }
        }
      }else{
        #5
      }
    }
  }
  return $result;
}

 

Next we replace our logic tests with their labels.

function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){
  #6
  #7
  if( a ){
    #1
  }else{
    if( b ){
      if( d && g ){
        #2
      }else{
        if( !d || !g ){
          #3
        }else{
          #4
        }
      }
    }else{
      if( c ){
        if( d && !f && j ){
          #2
        }else{
          if( !(!d || f || j) ){
            #2
          }else{
            #8
          }
        }
      }else{
        #5
      }
    }
  }
  return $result;
}

 

Add comments indicating the logic that lead there at each level of the code:

function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){
  #6
  #7
  if( a ){
    // a
    #1
  }else{
    // !a
    if( b ){
      // !a && b
      if( d && g ){
        // !a && b && (d && g)
        #2
      }else{
        // !a && b && !(d && g)
        if( !d || !g ){
          // !a && b && !(d && g) && (!d || !g)
          #3
        }else{
          // !a && b && !(d && g) && !(!d || !g)
          #4
        }
      }
    }else{
      // !a && !b
      if( c ){
        // !a && !b && c
        if( d && !f && j ){
          // !a && !b && c && (d && !f && j)
          #2
        }else{
          // !a && !b && c && !(d && !f && j)
          if( !(!d || f || j) ){
            // !a && !b && c && !(d && !f && j) && !(!d || f || j)
            #2
          }else{
            // !a && !b && c && !(d && !f && j) && !(!(!d || f || j))
            #8
          }
        }
      }else{
        // !a && !b && !c
        #5
      }
    }
  }
  return $result;
}

 

For each code block, write down the logic path that lead to it.  To simplify the syntax, replace && with . and || with + (. and + are boolean algebra operators):

#1 <- a

#2.a <- !a . b . (d . g)

#2.b <- !a . !b . c . (d . !f . j)

#2.c <- !a . !b . c . !(d . !f . j) . !(!d + f + j)

#3 <- !a . b . !(d . g) . (!d + !g)

#4 <- !a . b . !(d . g) . !(!d + !g)

#5 <- !a . !b . !c

#6 <- always

#7 <- always

#8 <- !a . !b . c . !(d . !f . j) . !(!(!d + f + j))

 

#1, #5, #6, and #7 can not be simplified, we leave them as they are.  We simplify the others.  Here is a link to some stuff on boolean algebra:

http://www.ee.surrey.ac.uk/Projects/Labview/boolalgebra/index.html

 

#3

#3 <- !a . b . !(d . g) . (!d + !g)
      !a . b . !(d . g) . !(d . g) (De Morgan's)
      !a . b . !(d . g) (Identity)
      !ab!(dg)

 

#8

#8 <- !a . !b . c . !(d . !f . j) . !(!(!d + f + j))
      !a . !b . c . !(d . !f . j) . !!(!d + f + j)
      !a . !b . c . !(d . !f . j) . (!d + f + j)
      (!a . !b . c) . (!d + f + !j) . (!d + f + j)
      (!a . !b . c) . (!d + !df + !dj + f + fj + !d!j + f!j)
      (!a!bc) . (!d + !df + !dj + !d!j + f + fj + f!j)
      (!a!bc) . (!d(1 + f + j + !j) + f(1 + j + !j))
      (!a!bc) . (!d + f)
      !a!bc!(d!f)

 

#4

Note that the expression evaluates to zero, which means code block #4 is never executed.  We can therefore drop code block #4 entirely.

#4 <- !a . b . !(d . g) . !(!d + !g)
      !a . b . !(d . g) . (dg) (De Morgan's)
      !a . b . (!(d . g) . (dg))
      !a . b . (0)
      0

 

#2.c

#2.c <- !a . !b . c . !(d . !f . j) . !(!d + f + j)
        !a . !b . c . (!d + f + !j) . (d . !f . !j)
        !a . !b . c . (d!d!f!j + df!f!j + d!f!j)
        !a . !b . c . (0 + 0 + d!f!j)
        !a!bcd!f!j

 

#2

Note we take #2.a + #2.b + #2.c and solve

#2 <- !abdg + !a!bcd!fj + !a!bcd!f!j
      !a(bdg + !bcd!f(j + !j))
      !a(bdg + !bcd!f(1))
      !a(bdg + !bcd!f)
      !ad(bg + !bc!f)

 

Rewriting our simplified rules:

#1 <- a

#2 <- !ad(bg + !bc!f)

#3 <- !ab!(dg)

#4 <- DROPPED - NEVER EXECUTED

#5 <- !a!b!c

#6 <- always

#7 <- always

#8 <- !a!bc!(d!f)

 

Take note that we had this list of boolean expressions:

a  : empty(m)

b  : n == one

c  : o == two

d  : x < y

!d : x >= y

f  : x >= z

!f : x < z

g  : x > z

!g : x <= z

j  : y + z <= 10

From that list, j does not make an appearance in our simplified rules, so we can drop that as well.  Thus $y + $z <= 10 will not be making an appearance in the final code.

 

I can now create a shell of our function:

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){
  // First we shall set up our boolean variables
  $a = empty($m);
  $b = $n == 'one';
  $c = $o == 'two';
  $d = $x < $y;
  $f = $x >= $z;
  $g = $x > $z;

  // #6
  // #7
  if($a){
    // #1 <- a
  }else{
    // !a
    if($d && ($b && $g || !$b && $c && !$f)){
      // #2 <- d(bg + !bc!f)
    }else if($b && !($d && $g)){
      // #3 <- b!(dg)
    }else if(!$b && !$c){
      // #5 <- !b!c
    }else if(!$b && $c && !($d && !$d)){
      // #8 <- !bc!(d!f)
    }
  }
  return $result;
}
?>

 

Now place the code blocks where they belong in the logic:

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){
  // First we shall set up our boolean variables
  $a = empty($m);
  $b = $n == 'one';
  $c = $o == 'two';
  $d = $x < $y;
  $f = $x >= $z;
  $g = $x > $z;

  // #6
  $result = 0;
  // #7
  $value = very_expensive_operation($m, $n, $o);
  if($a){
    // #1 <- 1
    $result = 1;
    $result *= $bar;
  }else{
    // !a
    if($d && ($b && $g || !$b && $c && !$f)){
      // #2 <- d(bg + !bc!f)
      $result = $y * $z + $x;
      $result *= $bar;
    }else if($b && !($d && $g)){
      // #3 <- b!(dg)
      $result = $y / $z - $x;
      $result *= $bar;
    }else if(!$b && !$c){
      // #5 <- !b!c
      $result = $foo;
      $result /= $bar;
    }else if(!$b && $c && !($d && !$d)){
      // #8 <- !bc!(d!f)
      $result = $bar + $value;
      $result /= $foo;
    }
  }
  return $result;
}
?>

 

From this point, it is very easy to finish optimization.  We can see the initial assignment of zero to $result is useless and accomplishes nothing.

 

$value is the result of a very expensive function call, but it is only used in a single place, so we will move it to where it's actually used.  We'll assume in this case the function call doesn't have any side effects, such as writing to disk, that we rely on elsewhere.  So we'll move this call to where it's actually used.

 

Our initial logic tests are simple in this case, but they too could be function calls that take time.  I'll move them inside the else where they're actually used.

 

If this function were not heavily used in the existing code, or was just a logic prototype, we could eliminate the useless $asdf variable.  And most of you caught the multiple assignments or multiplication by 1.

 

Here's the final function:

<?php
function doThis($foo, $bar, $asdf, $x, $y, $z, $m, $n, $o){
  $a = empty($m);
  if($a){
    // #1 <- 1
    $result = $bar;
  }else{
    // !a
    $b = $n == 'one';
    $c = $o == 'two';
    $d = $x < $y;
    $f = $x >= $z;
    $g = $x > $z;
    if($d && ($b && $g || !$b && $c && !$f)){
      // #2 <- d(bg + !bc!f)
      $result = ($y * $z + $x) * $bar;
    }else if($b && !($d && $g)){
      // #3 <- b!(dg)
      $result = ($y / $z - $x) * $bar;
    }else if(!$b && !$c){
      // #5 <- !b!c
      $result = $foo / $bar;
    }else if(!$b && $c && !($d && !$d)){
      // #8 <- !bc!(d!f)
      $result = ($bar + very_expensive_operation($m, $n, $o)) / $foo;
    }
  }
  return $result;
}
?>

[fenway]

Wow, I wish I had that much extra time ;-)

[beansandsausages]

???  ???  ???  ??? what just happend there ??? have no idea what any of that means. If some one will kindly explane please

[Daniel0]

???  ???  ???   ??? what just happend there ??? have no idea what any of that means. If some one will kindly explane please

Huh? roopurt's post is one long explanation.

[448191]

at I'm most interested in is seeing if anyone else was familiar with this technique of refactoring code.

 

I pray to all that is holy that I never get faced with such a mess.

[roopurt18]

Wow, I wish I had that much extra time ;-)

Hah!  About half way through solving that I wished I'd kept my mouth shut.  I must have screwed up my boolean algebra several times (was a bit rusty) and kept thinking, "This is a bastard of a function I wrote."

 

???  ???  ???  ??? what just happend there ??? have no idea what any of that means. If some one will kindly explane please

The shortest explanation I can give is I converted the logic into boolean algebra and simplified each boolean expression.  I then rewrote the code based on the simplified boolean expressions.  As long as I didn't screw up the algebra (or make some other dumb mistake), then the solution is guaranteed to be logically identical to the original function.

 

I pray to all that is holy that I never get faced with such a mess.

The reason I chose this problem as the challenge is I was just faced with a similar situation at work.  Except I had to go from one language to another, the original code was 350 lines long and had as many as 10 (!!!) levels of indentation.  (The final code was only 80 lines long, which doesn't make it any faster for execution, but much easier to maintain.)

 

I hope people found it useful.

[neylitalo]

The reason I chose this problem as the challenge is I was just faced with a similar situation at work.  Except I had to go from one language to another, the original code was 350 lines long and had as many as 10 (!!!) levels of indentation.  (The final code was only 80 lines long, which doesn't make it any faster for execution, but much easier to maintain.)

 

roopurt18, I think I can honestly say that I never want to work at your place of employment.

 

I hope people found it useful.

 

I didn't exactly analyze the whole thing, but I got the general idea - very impressive work. If I ever want to do the same thing or similar, I'll definitely be coming back to this thread.