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
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.
Not sure what the nature of your mistake is, because I'm not familiar with the rules of darts, but line 129 is definitely wrong:
if ($x <= 20 || $x == 50 || $x == 25 || ($x % 3 == 0) || ($x <= 40 && ($x % 2 == 0))) {
Either you want to be testing $xx, or you don't want to be re-testing the condition that already led you to that line. At the moment, the inner most loop will always be called so long as the $xx loop is. That's a performance killer. Of course, having a nested loop inside a nested loop usually is, regardless.
Another approach might be to generate a look-up table with answers for all possible scores, as suggested by Arkanon.
But this got me interested so I made my own version of the class to solve this one. As the existing one you gave here looks a bit much complex for the problem at hand. Just wanted to make it simple, and simple should also be fast.
I made some assumptions to start with:
I set property with array that holds all possible shoots and their score. And made method to return all possible throw outs for given score.
I have set up a test for my class to give you some performance numbers. I have run all score values, 1 to 170, one by one in a loop to get all possible checkout results per each.
Here are the results on my machine:
This avg to 42.5 score results per second and avg 62506.5 checkout results per second.
So it returns all possible results, and is much faster. Hope this will be of help. If nothing else at lest maybe give you some idea how to improve your class.
<?php
$darts = new Darts();
$result = $darts->possibleCheckout(60); //gives 3767 results
//var_dump($result);
echo count($result) . "
";
/**
* PHP Dartgame calculating class
* @author Aleksandar Popovic
*/
class Darts
{
/**
* All possible shoots and score per each
* @var array
*/
private $shoot_score = array(
'miss' => 0,
'1' => 1,
'2' => 2,
'3' => 3,
'4' => 4,
'5' => 5,
'6' => 6,
'7' => 7,
'8' => 8,
'9' => 9,
'10' => 10,
'11' => 11,
'12' => 12,
'13' => 13,
'14' => 14,
'15' => 15,
'16' => 16,
'17' => 17,
'18' => 18,
'19' => 19,
'20' => 20,
'D1' => 2,
'D2' => 4,
'D3' => 6,
'D4' => 8,
'D5' => 10,
'D6' => 12,
'D7' => 14,
'D8' => 16,
'D9' => 18,
'D10' => 20,
'D11' => 22,
'D12' => 24,
'D13' => 26,
'D14' => 28,
'D15' => 30,
'D16' => 32,
'D17' => 34,
'D18' => 36,
'D19' => 38,
'D20' => 40,
'T1' => 3,
'T2' => 6,
'T3' => 9,
'T4' => 12,
'T5' => 15,
'T6' => 18,
'T7' => 21,
'T8' => 24,
'T9' => 27,
'T10' => 30,
'T11' => 33,
'T12' => 36,
'T13' => 39,
'T14' => 42,
'T15' => 45,
'T16' => 48,
'T17' => 51,
'T18' => 54,
'T19' => 57,
'T20' => 60,
'Signle-Bull' => 25,
'Double-Bull' => 50
);
/**
* Maximum score
* @var int
*/
private $max_score = 170; // 3 x T20 is max right?
/**
* Return all possible checkouts for given score
* @param int $current_score
* @return array
*/
public function possibleCheckout($current_score)
{
if ($current_score > $this->max_score || $current_score < 1)
{
return false;
}
$checkout = array();
foreach ($this->shoot_score as $shoot1 => $score1)
{
if ($score1 > $current_score)
{
continue;
}
foreach ($this->shoot_score as $shoot2 => $score2)
{
if ($score1 + $score2 > $current_score)
{
continue;
}
foreach ($this->shoot_score as $shoot3 => $score3)
{
if ($score1 + $score2 + $score3 == $current_score)
{
$checkout[] = array($shoot1, $shoot2, $shoot3);
continue;
}
}
}
}
return $checkout;
}
}
If you want to get an additional performance boost, you have to save the results for all possibilities in a database or file and just read the values instead of calculate them each time.
I would suggest the following structure
Table (checkout)
sum (int) | dart1 (int) | dart2 (int) | dart3 (int)
60 | 20 | 20 | 31
all darts pointing to the following table
Table (dart)
pk (int) | bez (varchar)
20 | 20
31 | D10
Here is my try.
The output is sorted lexicographically by ascending individual scores.
It is very fast for 3 moves, but crumbles if you try more than that.
It is possible (theoretically) to compute the possibilities for any number of moves, though you will soon hit the script max execution time :).
The max achievable score is 180 (3x triple 20). You can waste a lot of CPU trying a higher score. It will yeld an empty result.
class darts {
const DATAFILE = "darts-scores.txt"; // score names & values database
static $score_val; // values of scores
static $score_name; // names of scores
static $score_num; // # of score values
static $res; // search result
static $tries; // for statistics
// internal search
static private function moves ($score, $moves, $i=0, &$list = array())
{
self::$tries++; // update stats
// search from the current scores only
for ( ; $i != self::$score_num; $i++)
{
$val = self::$score_val[$i];
if ($val > $score) break; // no need to try these ones
if ($moves == 1) // unrolled the recursion to improve performances
{
if ($score == $val)
{
// found another combination
$list[$moves] = self::$score_name[$i];
self::$res[] = $list;
}
}
else // go down to seek the rest of the combination
{
$list[$moves] = self::$score_name[$i];
self::moves ($score - $val, $moves-1, $i, $list);
}
}
}
// public search function
static function moves_for_score ($score, $moves=3)
{
self::$res = array();
self::$tries=0;
self::moves ($score, $moves);
return self::$res;
}
// turn results into a string
static function flatten ($res)
{
return implode (", ",
array_map (
function ($e){ return "[".implode(':',$e)."]"; },
$res));
}
// initialize scores table
static function init ()
{
if (!file_exists (self::DATAFILE))
{
// you can change the names of the scores with these two lines
$scores = array (
"miss" =>0,
"bull"=>25,
"double bull"=>50);
$type = array (
1=>"S",
2=>"D",
3=>"T");
// generate all scores
for ($t = 1 ; $t <= 3 ; $t++)
for ($i = 1 ; $i <= 20 ; $i++)
{
$scores[$type[$t].$i] = $t * $i;
}
asort ($scores);
foreach ($scores as $name=>$val) $out[] = "$name:$val";
file_put_contents (self::DATAFILE, implode ("
", $out));
}
// read score file
$in = preg_split ("/[:
]/", file_get_contents (self::DATAFILE));
self::$score_num = count($in)/2;
for ($i = 0 ; $i != self::$score_num ; $i++)
{
self::$score_name[$i] = $in[$i*2];
self::$score_val [$i] = (int) $in[$i*2+1];
}
}
}
darts::init();
////////////////////////////////////////////////////
// basic usage
////////////////////////////////////////////////////
$score = 281;
$moves = 5;
$res = darts::moves_for_score ($score, $moves);
echo "Sequences for $score in $moves moves: "
.darts::flatten($res)
."<br>";
echo "<pre>".print_r($res, true)."</pre><br>";
////////////////////////////////////////////////////
// stress test
////////////////////////////////////////////////////
echo "<br>Computing all possible sequences from 0 to 181...";
$start = microtime(true);
$tries = 0;
$max = 0;
for ($i = 0 ; $i <=180 ; $i++)
{
$res = darts::moves_for_score ($i);
$flat = darts::flatten($res);
if (strlen ($flat) > $max)
{
$max = strlen($flat);
$res_max = $res;
$i_max = $i;
}
$tries += darts::$tries;
}
echo "done in ".(microtime(true)-$start)."s, $tries tries<br>";
echo "<br>Longest list of possibilities:<br>$i_max -> "
.darts::flatten ($res_max)."<br>";