Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

PHP Dart game calculation slow performance

I've made a class to calculate the throw outs based on a score.

For example if the score is currently 140 the class returns a array with collection of possible throw outs:

[10] => Array
    (
        [0] => T18
        [1] => T18
        [2] => D16
    )

[11] => Array
    (
        [0] => T18
        [1] => T16
        [2] => D19
    )

[13] => Array
    (
        [0] => T17
        [1] => T17
        [2] => D19
    )

[14] => Array
    (
        [0] => 50
        [1] => 50
        [2] => D20

But calculating such things is pretty slow. Is there somehow I can optimize this class?

<?php
/**
 * PHP Dartgame calculating class
 * @author Youri van den Bogert
 */

class Darts {

    /**
     * @var string
     */
    public static $notation_triple = 'T';

    /**
     * @var string
     */
    public static $notation_double = 'D';

    /**
     * @var int
     */
    private static $maxCheckout = 170;

    /**
     * @var string
     */
    private static $doubleBull = 'Bull';

    /**
     * @var string
     */
    private static $singleBull = 'Single';

    /**
     * @var array
     */
    private static $scoreSheet = array('1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '25', '50');

    /**
     * Get a total thrown score
     * @param $score1
     * @param $score2
     * @param $score3
     * @return array
     */
    public static function getTotalScore ($score1, $score2, $score3) {
        return array(
          'dart1' => self::getScoreOfDart($score1),
          'dart2' => self::getScoreOfDart($score2),
          'dart3' => self::getScoreOfDart($score3),
          'total' => self::getScoreOfDart($score1) + self::getScoreOfDart($score2) + self::getScoreOfDart($score3)
        );
    }


    /**
     * Get score of a single dart
     * @param $score
     * @return mixed
     */
    public static function getScoreOfDart ($score) {

        if (is_numeric($score)) {
            return $score;
        }

        if ($score[0] == self::$notation_triple) {
            $multiplier = 3;
        } elseif ($score[0] == self::$notation_double) {
            $multiplier = 2;
        } else {
            $multiplier = 1;
        }

        $correctScore = filter_var($score, FILTER_SANITIZE_NUMBER_INT);

        return ($correctScore * $multiplier);

    }

    public static function getScoreSheet () {

        return self::$scoreSheet;

    }

    public static function calculatePossibleCheckout ($currentScore) {

        // We cant checkout higher then $maxCheckout
        if ($currentScore > self::$maxCheckout || $currentScore == 1) {
            return false;
        }

        // Return bull
        if ($currentScore == 50) {
            return array(
                'dart1' => self::$doubleBull
            );
        }

        if ($currentScore == self::$maxCheckout) {
            return array(
                'dart1' => self::$notation_triple . '20',
                'dart2' => self::$notation_triple . 'T20',
                'dart3' => 'Bull'
            );
        }

        $lastScore = $currentScore;
        $lastPossibleThrow = 0;
        $checkOut = array();

        // Can current score be checked out?
        if (self::canScore($currentScore) == true) {

            return array(
                'dart1' => self::$notation_double . ($currentScore / 2)
            );

        // Current score can't be checked out - calculate what to throw
        } else {

            for ($x=60; $x >= 0; --$x) {

                if ($x <= 20 || $x == 50 || $x == 25 || ($x % 3 == 0) || ($x <= 40 && ($x % 2 == 0))) {

                    for ($xx=60; $xx >= 0; --$xx) {

                        if ($x <= 20 || $x == 50 || $x == 25 || ($x % 3 == 0) || ($x <= 40 && ($x % 2 == 0))) {

                            for ($xxx=50; $xxx > 0; $xxx = $xxx - 2) {

                                if ($xxx == 48) {
                                    $xxx = 40;
                                }

                                if (self::checkIfScoreExists($xxx) == true && self::checkIfScoreExists($xx) == true && self::checkIfScoreExists($x) == true && ($xxx + $xx + $x) == $currentScore) {

                                    $score_1 = self::getCorrectDartName($xxx);
                                    $score_2 = self::getCorrectDartName($xx);
                                    $score_3 = self::getCorrectDartName($x, true);

                                    if ($score_1[0] == 'D' || $score_2[0] == 'D' || $score_3[0] == 'D') {
                                        $nextKey = (count($checkOut)+1);
                                        if ($xxx != 0) $checkOut[$nextKey][] = $score_1;
                                        if ($xx != 0) $checkOut[$nextKey][] = $score_2;
                                        if ($x != 0) $checkOut[$nextKey][] = $score_3;

                                        usort($checkOut[$nextKey], function($a, $b) {
                                            if (is_int($a) || is_float($a)) {
                                                if (is_int($b) || is_float($b)) {
                                                    return $a - $b;
                                                }
                                                else
                                                    return -1;
                                            }
                                            elseif (is_int($b) || is_float($b)) {
                                                return 1;
                                            }
                                            else {
                                                return strcmp($b, $a);
                                            }
                                        });
                                    }

                                }
                            }
                        }
                    }
                }
            }

        }

        return array_unique($checkOut, SORT_REGULAR);

    }

    public static function getCorrectDartName ($total, $isLast = false) {

        if ($total == 25 || $total == 50) {
            return $total;
        }

        if ($total < 20 && $isLast == false) {
            return $total;
        }

        if ($total %3 == 0) {
            return self::$notation_triple . ($total/3);
        } elseif ($total %2 == 0) {
            return self::$notation_double . ($total/2);
        }

        return $total;


    }

    /**
     * Check if score exists
     * @param $score
     * @return bool
     */
    public static function checkIfScoreExists ($score) {

        if ($score == 50 || $score == 25 || $score == 0) return true;

        $possibleScores = array_merge(range(1,20));

        foreach ($possibleScores as $posScore) {
            if ($score == self::getScoreOfDart(self::$notation_double . $posScore) || $score == self::getScoreOfDart(self::$notation_triple . $posScore) || $score == $posScore) {
                return true;
            }
        }

        return false;

    }

    /**
     * Check if a specific score can be thrown by one dart
     * @param $score
     * @return bool
     */
    public static function canScore ($score) {
        if ($score == 50) {
            return true;
        } elseif ($score < 40 || $score == 40) {

            if ($score % 2 == 0) {
                return true; // Score is even - so its possible to throw
            } else {
                return false;
            }
        }

        return false;
    }


} 

Link to class: https://gist.github.com/YOUR1/8509498

like image 554
Youri Avatar asked Jan 19 '14 19:01

Youri


1 Answers

I've used basic permutation generation and it's super fast (0.06 seconds). It can certainly be optimized but I see no point since it's already so fast.

<?php

class DartUtils {

    private static $possible_points;

    public static function getPossibleThrowsForScore($score) {

        // generate all possible single throws and their score
        // I didn't want to write them all out
        // but it's certainly an option (and faster)
        self::$possible_points = array();
        for ($i = 1; $i <= 20; $i += 1) {
            self::$possible_points["S" . $i] = $i; // S = single
            self::$possible_points["D" . $i] = $i * 2;
            self::$possible_points["T" . $i] = $i * 3;
        }
        self::$possible_points["bull"] = 25;
        self::$possible_points["double bull"] = 50;
        // self::$possible_points["miss"] = 0;

        $throws = self::findSatisfyingThrowsForScore($score, 3, array());
        foreach ($throws as $i => $serialized_throw) {
            $throws[$i] = unserialize($serialized_throw);
        }
        return $throws;
    }

    private static function findSatisfyingThrowsForScore($score, $num_throws, $base_notation) {
        $possible_throws = array();
        foreach (self::$possible_points as $notation => $value) {
            if ($num_throws === 1) { // we've done all throws
                if ($score - $value === 0) { // we satisfied the score
                    $throw = array_merge($base_notation, array($notation));
                    sort($throw);
                    $possible_throws[] = serialize($throw);
                }
            } else {
                // so long as there are num_throws, recurse with all possible throws
                $possible_throws = array_merge($possible_throws,
                  self::findSatisfyingThrowsForScore($score - $value, $num_throws - 1, array_merge($base_notation, array($notation))));
            }
        }
        $possible_throws = array_unique($possible_throws);
        sort($possible_throws);
        return $possible_throws;
    }

}

var_dump(DartUtils::getPossibleThrowsForScore(140));

The output is:

array(21) {
  [0]=>
  array(3) {
    [0]=>
    string(3) "D10"
    [1]=>
    string(3) "T20"
    [2]=>
    string(3) "T20"
  }
  [1]=>
  array(3) {
    [0]=>
    string(3) "D13"
    [1]=>
    string(3) "T18"
    [2]=>
    string(3) "T20"
  }
  [2]=>
  array(3) {
    [0]=>
    string(3) "D13"
    [1]=>
    string(3) "T19"
    [2]=>
    string(3) "T19"
  }
  [3]=>
  array(3) {
    [0]=>
    string(3) "D15"
    [1]=>
    string(3) "T20"
    [2]=>
    string(11) "double bull"
  }
  [4]=>
  array(3) {
    [0]=>
    string(3) "D16"
    [1]=>
    string(3) "T16"
    [2]=>
    string(3) "T20"
  }
  [5]=>
  array(3) {
    [0]=>
    string(3) "D16"
    [1]=>
    string(3) "T17"
    [2]=>
    string(3) "T19"
  }
  [6]=>
  array(3) {
    [0]=>
    string(3) "D16"
    [1]=>
    string(3) "T18"
    [2]=>
    string(3) "T18"
  }
  [7]=>
  array(3) {
    [0]=>
    string(3) "D18"
    [1]=>
    string(3) "T18"
    [2]=>
    string(11) "double bull"
  }
  [8]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T14"
    [2]=>
    string(3) "T20"
  }
  [9]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T15"
    [2]=>
    string(3) "T19"
  }
  [10]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T16"
    [2]=>
    string(3) "T18"
  }
  [11]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T17"
    [2]=>
    string(3) "T17"
  }
  [12]=>
  array(3) {
    [0]=>
    string(3) "D20"
    [1]=>
    string(11) "double bull"
    [2]=>
    string(11) "double bull"
  }
  [13]=>
  array(3) {
    [0]=>
    string(3) "D20"
    [1]=>
    string(3) "D20"
    [2]=>
    string(3) "T20"
  }
  [14]=>
  array(3) {
    [0]=>
    string(3) "S20"
    [1]=>
    string(3) "T20"
    [2]=>
    string(3) "T20"
  }
  [15]=>
  array(3) {
    [0]=>
    string(3) "T10"
    [1]=>
    string(3) "T20"
    [2]=>
    string(11) "double bull"
  }
  [16]=>
  array(3) {
    [0]=>
    string(3) "T11"
    [1]=>
    string(3) "T19"
    [2]=>
    string(11) "double bull"
  }
  [17]=>
  array(3) {
    [0]=>
    string(3) "T12"
    [1]=>
    string(3) "T18"
    [2]=>
    string(11) "double bull"
  }
  [18]=>
  array(3) {
    [0]=>
    string(3) "T13"
    [1]=>
    string(3) "T17"
    [2]=>
    string(11) "double bull"
  }
  [19]=>
  array(3) {
    [0]=>
    string(3) "T14"
    [1]=>
    string(3) "T16"
    [2]=>
    string(11) "double bull"
  }
  [20]=>
  array(3) {
    [0]=>
    string(3) "T15"
    [1]=>
    string(3) "T15"
    [2]=>
    string(11) "double bull"
  }
}

The throws I added are: 1-20 single, double or triple, bull and double bull. If there are more, or special throws you can add them.

The sort+serialization is a trick to quickly remove duplicates. For throw validation purposes it might actually be beneficial to leave the duplicates in.

You could consider accepting the notation as a string, like: S10D20BULL or DBULLDBULLT20. If you introduce the S for singles you can never have confusion. D112T20 is ambigous, is it D11S2T20 or D1S12T20? Strings are easier to work with so you might even gain performance. Splitting the string-notation back into it's parts is a little tricky but doable.

Note that I didn't add special checks for >170 or 1 because the list will simply be empty. This is an optimization you could apply.

You can optionally add the miss throw with a score of 0.


I don't quite understand your code, it's too complex. I think you're losing a lot of time doing sorting and converting between notation. As you can see in my solution I build the result set quickly and do the score calculation and notation generation at the same time.


I should also mention that I'm not too familiar with dart rules. I assumed bull and double bull but if single bull and bull is accurate feel free to correct me.

like image 186
Halcyon Avatar answered Oct 12 '22 23:10

Halcyon