How can I improve my PHP code to make it more efficient?

Question

I've written a simple PHP script which checks if a random value is a valid Rugby Union score. It works quite nicely but isn't particularly efficient, any advice on improving it would be most welcome.

$score = rand(0, 60);

/* Rugby Union
 * 
 * Try = 5 points
 * Conversion = 2 points
 * Penalty = 3 points
 * Drop goal = 3 points
 * 
 */

echo "<h1>Score: ".$score."</h1>";

for ($tries = 0; $tries <= 12; $tries++)
{
 for ($conversions = 0; $conversions <= 30; $conversions++)
  {
  for ($dropgoals = 0; $dropgoals <= 20; $dropgoals++)
   {
    if ($conversions > $tries)
    {
     //echo "<br />Illegal score";
    }
    else
    {
     $testscore = ($tries * 5) + ($conversions * 2) + ($dropgoals * 3);
     if ($testscore == $score)
     {
      if ($dropgoals == 0)
      {
       echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals." drop goals.<br />";
      }
      else
      {
       echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals." drop goals or penalties.<br />";
      }
     }
    }
   }
  }
}

Okay, here's the revised solution as it stands, it'd be nice to reduce the amount of nested for loops if possible...

echo "<h1>Score: ".$score."</h1>";

for ($tries = 0; $tries <= 12; $tries++) {
    for ($conversions = 0; $conversions <= $tries; $conversions++) {
        for ($dropgoals = 0; $dropgoals <= 20; $dropgoals++){
      if ($conversions <= $tries) {
        $testscore = ($tries * 5) + ($conversions * 2) + ($dropgoals * 3);
                    if ($testscore == $score) {
          echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals.($dropgoals == 0 ? " drop goals.<br />" : " drop goals or penalties.<br />");
         }
      }
        }
    }
}

Answer 1

Well for a start

for ($conversions = 0; $conversions <= 30; $conversions++)

can change to

for ($conversions = 0; $conversions <= $tries; $conversions++)

Answer 2

Practically speaking, there are only a finite number of possible scores, right? A quick Google shows that the record is 164 points. So why not generate, one time, a list of every possible score, up to a certain max (300? 500?), and hard-code it in your app. Then, at runtime, just check if the supplied score is in the list. I think that will be, by far, the most efficient solution.

Edit: This method will still work if you also want to output tries, penalties, and drop goals--just generate those values, too--one time--and keep them in the list as well (as a two-dimensional array or an associative array).

Answer 3

When you say "efficient", please define what you mean.

Is the code executing too slowly? How fast is it running now, and how fast do you need it to run? If you can't define "not fast enough" then you don't have a goal.

Before you go guessing at what to speed up, and before all the respondents here do you a disservice by encouraging you to make scattershot speedups, you need to profile your code to see where most of the time is being spent.

Answer 4

A slightly modified version. I wish I knew more about rugby.

$score = rand(0, 60);

/* Rugby Union
 * 
 * Try = 5 points
 * Conversion = 2 points
 * Penalty = 3 points
 * Drop goal = 3 points
 * 
 */

echo "<h1>Score: ".$score."</h1>";

for ($tries = 0; $tries <= 12; $tries++){
    for ($conversions = 0; $conversions <= $tries; $conversions++){
     for ($dropgoals = 0; $dropgoals <= 20; $dropgoals++){
      else{
       $testscore = ($tries * 5) + ($conversions * 2) + ($dropgoals * 3);
       if ($testscore == $score){
        if ($dropgoals == 0){
         echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals." drop goals.<br />";
        }
        else{
         echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals." drop goals or penalties.<br />";
        }
       }
      }
     }
    }
    if ($conversions > $tries){
     echo "<br />Illegal score";
    }
}

Answer 5

your if else function should be inverted. Make the most probable scenario comme into the if(){} clause, and the exceptional error in the else{}

if ($conversions < $tries)
                        {
                                $testscore = ($tries * 5) + ($conversions * 2) + ($dropgoals * 3);
                                if ($testscore == $score)
                                {
                                        if ($dropgoals == 0)
                                        {
                                                echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals." drop goals.<br />";
                                        }
                                        else
                                        {
                                                echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals." drop goals or penalties.<br />";
                                        }
                                }
                        }
                        else
                        {
                              // echo "illegal score";
                        }

Answer 6

This will clean things up a bit.

echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals.($dropgoals == 0 ? " drop goals.<br />" : " drop goals or penalties.<br />");

Answer 7

You can also break out of the loops when you've found a solution:

if ($testscore == $score) 
{
  echo "Found a way to achieve ....";
  break 3;
}

The number specifies the number of loops to break out of, so at time of writing there were 3 for loops to exit.

Answer 8

Yeah 3 foor loops seem to be too much for such a problem. But as you want to find a combination x,y,z, such that n = x*5 + y*3 + z*2 with x>=z, I don't think there is a simpler solution. You can however reduce the number of iterations.
And it would be good to know if you want to get all possible combinations or just an answer like 'Yes, this is a valid score'.

Anyway, this is my suggestions:

$score = rand(0, 60);

/* Rugby Union
 * 
 * Try = 5 points
 * Conversion = 2 points
 * Penalty = 3 points
 * Drop goal = 3 points
 * 
 */

// compute how often the points fit into the score
$maxTries = intval($score / 5);
$maxConversions = min(intval($score / 2),$maxTries);
$maxDrops = intval($score / 3);

$valid = false;
for ($tries = 0; $tries <= $maxTries; $tries++)
{   
    // this way, you avoid recomputing the value over and over again in the third loop 
    $scoreTries = $tries * 5;
    for ($conversions = 0; $conversions <= $maxConversions; $conversions++)
    {
        $scoreCons = $scoreTries  + $conversions * 2;
        for ($dropgoals = 0; $dropgoals <= $maxDrops; $dropgoals++)
        {
            $scoreTotal = $scoreCons + $dropgoals * 3
            if ($scoreTotal == $score)
            {
               echo 'Found a way to achieve score with '.$tries.' tries '.$conversions.' conversions and '.$dropgoals.' drop goals or penalties.<br />';
               $valid = true;
               // write 'break 3' here if you are satisfied with one answer                
            }
        }
    }
}

if (!$valid){
    echo "<br />Illegal score";
}

I don't know how much the efficiency improves but in general it is always good to enclose strings in single quotes ('string') if you use the 'dot' syntax to connect them. This way, PHP does not evaluate the strings for variables to substitute which is, in my opinion, a cleaner approach.

Edit:

Oh and I don't distinguish between $dropgoals == 0, because there is logically no differences between e.g. ...and 0 drop goals. and ...and 0 drop goals or penalties.

Answer 9

It's the same problem as finding out how change for a given amount can be made up of coins from a given set of denominations. Here's an implementation in PHP. I doubt if it's very efficient, but it's more general than the nested loop version.

<?php

f(
  30, // points scored in match
  array( // rugby union scoring structure
    "Converted Tries" => 7,
    "Unconverted Tries" => 5,
    "Drop Goals/Penalties" => 3,
  )
);

function f($points_left, $scoring_structure, $scores_so_far = array()){
  if($points_left==0){
    print_score($scores_so_far);
  }else if($points_left>0){
    if($scoring_structure){
      list($score_type, $points_for_score_type) =
        first_element($scoring_structure);

      // Option 1: Use a highest-denomination coin,
      // and make change for the rest.
      if($points_for_score_type <= $points_left){
        f(
          $points_left-$points_for_score_type,
          $scoring_structure,
          increment($scores_so_far,$score_type)
        );  
      }

      // Option 2: Attempt to make change for the full amount without
      // using the highest denomination coin at all.
      f(
        $points_left,
        all_except_first_element($scoring_structure),
        $scores_so_far
      );
    }
  }else{
    exit("Error: Should never reach here!\n");
  }
}

function increment($arr, $key){
 $arr[$key]++;
 return $arr;
}

function all_except_first_element($arr){
  list($k, $v) = first_element($arr);
  unset($arr[$k]);
  return $arr;
}

function first_element($arr){
  foreach($arr as $k=>$v){
    return array($k, $v);
  }
}

function print_score($scores_so_far){
  $parts = array();
  foreach($scores_so_far as $k=>$v){
    $parts[]= "$k: $v";
  }
  echo implode(", ", $parts), "\n";
}

Answer 10

Your approach can be improved further - instead of looking through all combinations of the three variables - tries, conversions and dropgoals, you can only look at those combinations that do not exceed $score. Though you still have the nested loops, the number of times the code inside the loop is executed is decreased. See below.

echo "<h1>Score: ".$score."</h1>";

$triesScore = 5;
$conversionsScore = 2;
$dropgoalsScore = 3;

for ($tries = 0; $tries <= $score/$triesScore; $tries++) {
    for ($conversions = 0; $conversions <= ($score-$triesScore*$tries)/$conversionsScore; $conversions++) {
        for ($dropgoals = 0; $dropgoals <= ($score-$triesScore*$tries-$conversionsScore*$conversions)/$dropgoalsScore; $dropgoals++){
            $testscore = ($tries * $triesScore) + ($conversions * $conversionsScore) + ($dropgoals * $dropgoalsScore);
            if ($testscore == $score) {
                echo "Found a way to achieve score with ".$tries." tries ".$conversions." conversions and ".$dropgoals.($dropgoals == 0 ? " drop goals.<br />" : " drop goals or penalties.<br />");
            }
        }
    }
}

Though in reality, for a max-score of 60, the improvements are very small, that they may be unnoticeable.

Answer 11

Precompute! Thought I doubt that the performance kills your app, but just in case. There are 1911 possible combinations, and 141 valid scores, so you can easily precompute the data, and store it on disk and load it whenever required.

Precomputing:

$scores = array();
for ($tries = 0; $tries <= 12; $tries++) {
    for ($conversions = 0; $conversions <= $tries; $conversions++) {
        for ($dropgoals = 0; $dropgoals <= 20; $dropgoals++){
            $score = ($tries * 5) + ($conversions * 2) + ($dropgoals * 3);
            if( !array_key_exists($score,$scores) ) $scores[$score] = array();
            $scores[$score][] = array( $tries, $conversions, $dropgoals );
        }
    }
}

echo "number of unique possible scores is " . count($scores) . "\n";
$number_combinations = 0;
foreach( $scores as $score => $combinations ) {
    echo "Score " . $score . " has " . count($combinations) . " combinations\n";
    $number_combinations += count($combinations);
}
echo "number of unique combinations is " . $number_combinations . "\n";

// store
file_put_contents("scores.txt",serialize($scores));

Lookup:

$scores=unserialize(file_get_contents("scores.txt"))
$number_of_combinations_for_score_23 = array_key_exists(23,$scores) ? count($scores[23]) : 0;

You could even reduce the scores array to contain only a "valid or not" bool on the right side. This saves a little bit lookup time and space.