From the latest commit to my
scouting program (pages/strength.act.php):
PHP Code:
/** Gaussian elimination solver with partial pivoting.
* Originally written in Java by Robert Sedgewick and Kevin Wayne:
* @see http://www.cs.princeton.edu/introcs/95linear/GaussianElimination.java.html
*
* Ported to PHP by Paul Meagher
* @see http://www.phpmath.com/home?op=perm&nid=82
*
* @modified June 12/2007 reimplemented as a GaussianElimination.php class
* @modified March 26/2007 implemented as a function gauss($A, $b)
* @version 0.3
*/
/** Implements gaussian elimination solver with partial pivoting.
*
* @param double[][] $A coefficient matrix
* @param double[] $b output vector
* @return double[]$x solution vector
*/
function solve($A, $b) {
// number of rows
$N= count($b);
// forward elimination
for ($p=0; $p<$N; $p++) {
// find pivot row and swap
$max = $p;
for ($i = $p+1; $i < $N; $i++)
if (abs($A[$i][$p]) > abs($A[$max][$p]))
$max = $i;
$temp = $A[$p]; $A[$p] = $A[$max]; $A[$max] = $temp;
$temp = $b[$p]; $b[$p] = $b[$max]; $b[$max] = $temp;
// check if matrix is singular
if (abs($A[$p][$p]) <= 1e-10) throw new Exception("Matrix is singular or nearly singular");
// pivot within A and b
for ($i = $p+1; $i < $N; $i++) {
$alpha = $A[$i][$p] / $A[$p][$p];
$b[$i] -= $alpha * $b[$p];
for ($j = $p; $j < $N; $j++)
$A[$i][$j] -= $alpha * $A[$p][$j];
}
}
// zero the solution vector
$x = array_fill(0, $N-1, 0);
// back substitution
for ($i = $N - 1; $i >= 0; $i--) {
$sum = 0.0;
for ($j = $i + 1; $j < $N; $j++)
$sum += $A[$i][$j] * $x[$j];
$x[$i] = ($b[$i] - $sum) / $A[$i][$i];
}
return $x;
}
// Get score data from database
switch ($_REQUEST['method']){
case 'linear_points':
$sql = <<<SQL
SELECT teamnum, SUM(IF(points IS NULL,score,points)) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.alliance=a.alliance AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
case 'linear_score':
$sql = <<<SQL
SELECT teamnum, SUM(score) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.alliance=a.alliance AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
case 'linear_difference':
$sql = <<<SQL
SELECT teamnum, SUM(CAST(IF(points IS NULL,score,points) AS SIGNED)*IF(m.alliance=a.alliance,1,-1)) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
case 'linear_penalty':
$sql = <<<SQL
SELECT teamnum, SUM(IF(penalty IS NULL,0,penalty)) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
}
$i = 0;
$matrix = $score = $team = $rows = array();
// Put scores into an array and index team numbers
foreach($db->Execute($sql) as $row){
$team[$i] = $row['teamnum'];
$score[$i] = $row['p'];
$i++;
}
$sql = <<<SQL
SELECT a.teamnum AS a, b.teamnum AS b, COUNT(a.matchid) AS count
FROM team_match a, team_match b
WHERE a.eventid=6 AND b.eventid=6 AND a.matchid=b.matchid AND a.alliance=b.alliance
GROUP BY a.teamnum, b.teamnum
ORDER BY a.teamnum, b.teamnum
SQL;
// Organize returned database data
foreach($db->Execute($sql) as $row){
$rows[$row['a']][$row['b']] = $row['count'];
}
// Build n-by-n matrix of teams
foreach($team as $i=>$row){
foreach($team as $j=>$cell) $matrix[$i][$j] = $rows[$row][$cell];
}
// Solve for solution matrix and convert that to SQL
$rows = array();
foreach(solve($matrix, $score) as $i=>$strength) $rows[] = '('.$team[$i].','.round($strength,1).')';
// Put the data back into the database
$db->Execute("CREATE TEMPORARY TABLE tmp_team_strength (`teamnum` int(10) unsigned NOT NULL, `strength` float NOT NULL, PRIMARY KEY (`teamnum`))");
$db->Execute("INSERT INTO tmp_team_strength VALUES ".implode(',',$rows));
$db->Execute("UPDATE team_event d, tmp_team_strength s SET d.strength=s.strength WHERE d.eventid=$eventid AND d.teamnum=s.teamnum");
$db->Execute("DROP TEMPORARY TABLE tmp_team_strength");
The solve function I found after I tried programming my own. It runs surprisingly quick for a 50x50 matrix operation compared to the function I wrote (no more then a tenth of a second I think, I didn't do any tests), and far better then the SQL-only script this code replaced (which was basically a really fancy average). All of my work here I declare public domain, the solve function I assume is posted for general use too. And of course, the SQL and functions that call it (I use ADODB here) may require changing.
Wow, 4 pages of arguments over water......
Is it the off season or what? - Botsup [more] 
03-10-2008, 17:34
Similar Threads
Robot Inspector
Linear Mode
