Plutor · December 10, 2011 17:01
diff --git a/find_roadtrip.php b/find_roadtrip.php
 <?php

 require 'limitedminheap.php';

 $teams = array(
    "Angels"    => 1 << 0,  "Astros"    => 1 << 1,
    "Athletics" => 1 << 2,  "Blue Jays" => 1 << 3,
    "Braves"    => 1 << 4,  "Brewers"   => 1 << 5,
    "Cardinals" => 1 << 6,  "Cubs"      => 1 << 7,
    "Diamondbacks" => 1 << 8,  "Dodgers"   => 1 << 9,
    "Giants"    => 1 << 10, "Indians"   => 1 << 11,
    "Mariners"  => 1 << 12, "Marlins"   => 1 << 13,
    "Mets"      => 1 << 14, "Nationals" => 1 << 15,
    "Orioles"   => 1 << 16, "Padres"    => 1 << 17,
    "Phillies"  => 1 << 18, "Pirates"   => 1 << 19,
    "Rangers"   => 1 << 20, "Rays"      => 1 << 21,
    "Reds"      => 1 << 22, "Red Sox"   => 1 << 23,
    "Rockies"   => 1 << 24, "Royals"    => 1 << 25,
    "Tigers"    => 1 << 26, "Twins"     => 1 << 27,
    "White Sox" => 1 << 28, "Yankees"   => 1 << 29 );

 $max_days_between_games = 3;
 $schedule_file = 'MLB-2012-schedule.csv';
 $numparts = 4;
 $queuesize = 19; // Interpreted as 2^n-1 -- 2^19 = 512k

 class PlanList extends LimitedMinHeap {
    protected function compare($i, $j) {
        if ($i == $j or
            $this->list[$i]["length"] == $this->list[$j]["length"]) return 0;

        $ilegs = count($this->list[$i])-3; // 2 are length and bitmap
        $jlegs = count($this->list[$j])-3;

        $iv = 0;
        $jv = 0;
        if ($ilegs > 0)
            $iv = $this->list[$i]["length"] / pow($ilegs, 2);
        if ($jlegs > 0)
            $jv = $this->list[$j]["length"] / pow($jlegs, 2);

        return ($iv < $jv) ? -1 : 1;
    }
 }

 $schedule = get_schedule($schedule_file, $max_days_between_games);
 $options = getopt("", array("part::", "jobs::", "queuesize::"));

 if (isset($options["jobs"]))
    $numparts = $options["jobs"];
 if (isset($options["queuesize"]))
    $queuesize = $options["queuesize"];

 $parts = array();
 $bestplan = array();

 if (isset($options["part"])) {
    # What part are we running for? --part=n/m
    $parts = split('/', $options["part"]);
    $partsize = count($schedule) / $parts[1];
    $startgame = floor(($parts[0]-1) * $partsize);
    $endgame = floor($parts[0] * $partsize);

    runpart($startgame, $endgame);
 } else {
    # Run 4 parts
    runmaster($argv[0], $numparts);
 }

 # =============================================================================

 function get_schedule($schedule_file, $max_days_between_games, $quiet = 1) {
    global $teams;
    $rv = array();
    $adj = 0;

    $handle = fopen($schedule_file, "r");
    if ($handle == FALSE) return;

    # Drop the first line
    fgetcsv($handle, 1000);
    while (($data = fgetcsv($handle, 1000)) !== FALSE) {
        $date = date_to_jd($data[0]);
        $game_index = count($rv);
        $bitmap = $teams[$data[1]] | $teams[$data[2]];
        $game = array( "game_index" => $game_index, "date" => $date,
                       "date_str" => $data[0],
                       "away" => $data[1], "home" => $data[2],
                       "lat" => $data[4], "lon" => $data[5],
                       "bitmap" => $bitmap, "next_games" => array() );
        $rv[] = $game;

        # Find all valid previous games
        foreach ($rv as $previndex => $prevgame) {
            if ($prevgame["date"] < $game["date"] and
                $game["date"] - $prevgame["date"] <= $max_days_between_games and
                ($game["bitmap"] & $prevgame["bitmap"]) == 0) {
                # Within the time window and no shared teams - okay!
                # Precalculate leg distances
                $legdist = get_distance($prevgame["lat"], $prevgame["lon"],
                                        $game["lat"], $game["lon"]);

                # Also a max of 500 miles of travel per day
                if (($game["date"] - $prevgame["date"]) * 500 <= $legdist)
                    continue;

                $rv[$previndex]["next_games"][] = array($legdist, $game_index);
                $adj++;
            }
        }
    }
    fclose($handle);


    if (!$quiet) {
        echo "Got " . count($rv) . " games, and " . $adj . " valid edges\n";
    }

    return $rv;
 }

 function date_to_jd($date) {
    $dparts = preg_split("/-/", $date);
    return cal_to_jd(CAL_GREGORIAN, $dparts[1], $dparts[2], $dparts[0]);
 }

 function show_plan($plan) {
    global $schedule;

    echo "*** Better " . count($plan) . " game plan:\n";
    $prevgame = null;
    $totdist = 0;
    foreach ($plan as $i => $gameindex) {
        $game = $schedule[$gameindex];

        if ($prevgame) {
            $dist = get_distance($prevgame["lat"], $prevgame["lon"],
                                 $game["lat"], $game["lon"]);
            echo "    Travel " . round($dist, 1) . " mi\n";
            $totdist += $dist;
        }

        echo $game["date_str"] . ": ";
        echo $game["away"] . " @ " . $game["home"];
        echo "\n";

        $prevgame = $game;
    }
    echo "Total distance: " . round($totdist,1) . " mi\n\n";
 }

 // Returns the distance in mi
 function get_distance($lat1, $lon1, $lat2, $lon2) {
    $dLat = deg2rad($lat1 - $lat2);
    $dLon = deg2rad($lon1 - $lon2);
    $lat1 = deg2rad($lat1);
    $lat2 = deg2rad($lat2);

    $a = pow(sin($dLat/2), 2) + pow(($dLon/2), 2) *
         cos($lat1) * cos($lat2); 
    $c = 2 * atan2(sqrt($a), sqrt(1-$a));
    $distance = 3963 * $c;

    return $distance;
 }

 function show_time($sec) {
    $sec = floor($sec);

    if ($sec < 3600) {
        return sprintf("%d:%02d", floor($sec/60), $sec % 60);
    } else {
        return sprintf("%d:%02d:%02d", floor($sec/3600), floor($sec/60) % 60, $sec % 60);
    }
 }

 function set_status($part, $elapsed, $info) {
    global $numparts, $parts, $bestplan;

    # iterations, queuelen, shortest plan distance, shortest plan games
    if (isset($part) and isset($info))
        $parts[$part]["info"] = $info;

    # Display status
    $total_iters = 0;
    $total_queue = 0;
    for ($p=0; $p<$numparts; ++$p) {
        if (isset($parts[$p]["info"])) {
            $total_iters += $parts[$p]["info"][0];
            $total_queue += $parts[$p]["info"][1];
        }
    }

    if ($total_iters % 25000 == 0 or !isset($part)) {
        $pph = floor($total_iters/$elapsed*3.6);

        print "[" . show_time($elapsed) . "] $total_iters iterations (" . $pph .
            "k per hr), q=$total_queue";
        print "\n";
    }
 }

 # =============================================================================

 function runpart($startgame, $endgame) {
    global $schedule, $queuesize, $bestplan;
    $start = time();

    #echo "status,Running $startgame to $endgame\n";

    # First build the branch-and-bound queue with one plan for each game
    $bb_queue = new PlanList(pow(2,$queuesize)-1);
    for ($game_index = $startgame; $game_index < $endgame; ++$game_index) {
        $game = $schedule[$game_index];
        $plan = array( "length" => 0,
                       "bitmap" => $game["bitmap"] );
        $plan[] = $game_index;
        $bb_queue->insert($plan);
    }

    $iterations = 0;
    $goalsize = 15;
    while($bb_queue->count() > 0) {
        # Remove the shortest plan
        $shortest_plan = $bb_queue->get_min();

        $legs = count($shortest_plan) - 3;
        if (!isset($bestplan[$legs]) or
            $shortest_plan["length"] < $bestplan[$legs]["length"]) {
            $bestplan[$legs] = $shortest_plan;
            $showplan = $shortest_plan;
            $planlen = $shortest_plan["length"];
            unset($showplan["length"]);
            unset($showplan["bitmap"]);
            echo "plan," . join(",", $showplan) . ",$planlen\n";
        }

        # Otherwise, find all valid 'next games' for this plan
        $lastgame_index = end($shortest_plan);
        $lastgame = $schedule[$lastgame_index];
        foreach ($lastgame["next_games"] as $nextgame_index => $nextgame_info) {
            $nextgame_index = $nextgame_info[1];
            $nextgame = $schedule[$nextgame_index];
            if (($nextgame["bitmap"] & $shortest_plan["bitmap"]) == 0) { # okay
                # Add the new game to this schedule and add that plan to the queue
                $newplan = $shortest_plan;
                $newplan[] = $nextgame_index;
                $newplan["length"] += $nextgame_info[0];
                $newplan["bitmap"] |= $nextgame["bitmap"];
                $bb_queue->insert($newplan);
            }
        }

        if ($iterations > 0 and $iterations % 1000 == 0) {
            # iterations, queuelen, shortest plan distance, shortest plan games
            echo "status,$iterations," . $bb_queue->count() . ",";
            echo "" . round($shortest_plan["length"], 1) . ",";
            echo "" . (count($shortest_plan)-2) . "\n";
        }
        $iterations++;
    }

    echo "status,$iterations," . $bb_queue->count() . ",999999,0\n";
 }

 function runmaster($script, $numparts) {
    global $parts, $bestplan, $queuesize;

    # Start n parts
    echo "Starting $numparts children\n";
    for ($p = 0; $p < $numparts; ++$p) {
        $cmd = "php $script --part=" . ($p+1) . "/" . $numparts .
                " --queuesize=" . $queuesize;
        $phandle = popen($cmd, "r");
        $parts[$p] = array( "handle" => $phandle );
    }

    $start = time();
    $partsrunning = 4;
    while ($partsrunning > 0) {
        $partsrunning = 0;
        for ($p = 0; $p < $numparts; ++$p) {
            if (isset($parts[$p]) and isset($parts[$p]["handle"])) {
                $part = $parts[$p];
                if (feof($part["handle"])) {
                    # Part is done -- clean up
                    unset($parts[$p]["handle"]);
                } else {
                    # Part is still running -- get output
                    $out = rtrim(fgets($part["handle"], 4096));
                    if (isset($out) and $out != "") {
                        $out = split(",", $out);
                        $outtype = array_shift($out);
                        $elapsed = time() - $start + 1;
                        $head = "[$p, " . show_time($elapsed) . "]";

                        if ($outtype == "plan") {
                            # Save the plan
                            $planlen = array_pop($out); # last element is length
                            $plan_games = count($out);

                            if (!isset($bestplan[$plan_games])) {
                                # First plan of this length
                                $bestplan[$plan_games] = array(
                                    "length" => $planlen,
                                    "plan" => $out
                                );
                                show_plan($out);
                            } elseif ($bestplan[$plan_games]["length"] > $planlen) {
                                # Shortest plan of this length yet
                                $bestplan[$plan_games]["length"] = $planlen;
                                $bestplan[$plan_games]["plan"] = $out;
                                show_plan($out);
                            }
                        } elseif ($outtype == "status") {
                            # Save/show the status
                            set_status($p, $elapsed, $out);
                        }
                    }

                    $partsrunning++;
                }
            }
        }
        
        # Don't want to active spin
        sleep(1);
    }

    set_status(null, time() - $start, null);
 }

 ?>
diff --git a/MLB-2012-schedule.csv b/MLB-2012-schedule.csv
	<?php

	require 'limitedminheap.php';

	$teams = array(
	"Angels" => 1 << 0, "Astros" => 1 << 1,
	"Athletics" => 1 << 2, "Blue Jays" => 1 << 3,
	"Braves" => 1 << 4, "Brewers" => 1 << 5,
	"Cardinals" => 1 << 6, "Cubs" => 1 << 7,
	"Diamondbacks" => 1 << 8, "Dodgers" => 1 << 9,
	"Giants" => 1 << 10, "Indians" => 1 << 11,
	"Mariners" => 1 << 12, "Marlins" => 1 << 13,
	"Mets" => 1 << 14, "Nationals" => 1 << 15,
	"Orioles" => 1 << 16, "Padres" => 1 << 17,
	"Phillies" => 1 << 18, "Pirates" => 1 << 19,
	"Rangers" => 1 << 20, "Rays" => 1 << 21,
	"Reds" => 1 << 22, "Red Sox" => 1 << 23,
	"Rockies" => 1 << 24, "Royals" => 1 << 25,
	"Tigers" => 1 << 26, "Twins" => 1 << 27,
	"White Sox" => 1 << 28, "Yankees" => 1 << 29 );

	$max_days_between_games = 3;
	$schedule_file = 'MLB-2012-schedule.csv';
	$numparts = 4;
	$queuesize = 19; // Interpreted as 2^n-1 -- 2^19 = 512k

	class PlanList extends LimitedMinHeap {
	protected function compare($i, $j) {
	if ($i == $j or
	$this->list[$i]["length"] == $this->list[$j]["length"]) return 0;

	$ilegs = count($this->list[$i])-3; // 2 are length and bitmap
	$jlegs = count($this->list[$j])-3;

	$iv = 0;
	$jv = 0;
	if ($ilegs > 0)
	$iv = $this->list[$i]["length"] / pow($ilegs, 2);
	if ($jlegs > 0)
	$jv = $this->list[$j]["length"] / pow($jlegs, 2);

	return ($iv < $jv) ? -1 : 1;
	}
	}

	$schedule = get_schedule($schedule_file, $max_days_between_games);
	$options = getopt("", array("part::", "jobs::", "queuesize::"));

	if (isset($options["jobs"]))
	$numparts = $options["jobs"];
	if (isset($options["queuesize"]))
	$queuesize = $options["queuesize"];

	$parts = array();
	$bestplan = array();

	if (isset($options["part"])) {
	# What part are we running for? --part=n/m
	$parts = split('/', $options["part"]);
	$partsize = count($schedule) / $parts[1];
	$startgame = floor(($parts[0]-1) * $partsize);
	$endgame = floor($parts[0] * $partsize);

	runpart($startgame, $endgame);
	} else {
	# Run 4 parts
	runmaster($argv[0], $numparts);
	}

	# =============================================================================

	function get_schedule($schedule_file, $max_days_between_games, $quiet = 1) {
	global $teams;
	$rv = array();
	$adj = 0;

	$handle = fopen($schedule_file, "r");
	if ($handle == FALSE) return;

	# Drop the first line
	fgetcsv($handle, 1000);
	while (($data = fgetcsv($handle, 1000)) !== FALSE) {
	$date = date_to_jd($data[0]);
	$game_index = count($rv);
	$bitmap = $teams[$data[1]] \| $teams[$data[2]];
	$game = array( "game_index" => $game_index, "date" => $date,
	"date_str" => $data[0],
	"away" => $data[1], "home" => $data[2],
	"lat" => $data[4], "lon" => $data[5],
	"bitmap" => $bitmap, "next_games" => array() );
	$rv[] = $game;

	# Find all valid previous games
	foreach ($rv as $previndex => $prevgame) {
	if ($prevgame["date"] < $game["date"] and
	$game["date"] - $prevgame["date"] <= $max_days_between_games and
	($game["bitmap"] & $prevgame["bitmap"]) == 0) {
	# Within the time window and no shared teams - okay!
	# Precalculate leg distances
	$legdist = get_distance($prevgame["lat"], $prevgame["lon"],
	$game["lat"], $game["lon"]);

	# Also a max of 500 miles of travel per day
	if (($game["date"] - $prevgame["date"]) * 500 <= $legdist)
	continue;

	$rv[$previndex]["next_games"][] = array($legdist, $game_index);
	$adj++;
	}
	}
	}
	fclose($handle);


	if (!$quiet) {
	echo "Got " . count($rv) . " games, and " . $adj . " valid edges\n";
	}

	return $rv;
	}

	function date_to_jd($date) {
	$dparts = preg_split("/-/", $date);
	return cal_to_jd(CAL_GREGORIAN, $dparts[1], $dparts[2], $dparts[0]);
	}

	function show_plan($plan) {
	global $schedule;

	echo "*** Better " . count($plan) . " game plan:\n";
	$prevgame = null;
	$totdist = 0;
	foreach ($plan as $i => $gameindex) {
	$game = $schedule[$gameindex];

	if ($prevgame) {
	$dist = get_distance($prevgame["lat"], $prevgame["lon"],
	$game["lat"], $game["lon"]);
	echo " Travel " . round($dist, 1) . " mi\n";
	$totdist += $dist;
	}

	echo $game["date_str"] . ": ";
	echo $game["away"] . " @ " . $game["home"];
	echo "\n";

	$prevgame = $game;
	}
	echo "Total distance: " . round($totdist,1) . " mi\n\n";
	}

	// Returns the distance in mi
	function get_distance($lat1, $lon1, $lat2, $lon2) {
	$dLat = deg2rad($lat1 - $lat2);
	$dLon = deg2rad($lon1 - $lon2);
	$lat1 = deg2rad($lat1);
	$lat2 = deg2rad($lat2);

	$a = pow(sin($dLat/2), 2) + pow(($dLon/2), 2) *
	cos($lat1) * cos($lat2);
	$c = 2 * atan2(sqrt($a), sqrt(1-$a));
	$distance = 3963 * $c;

	return $distance;
	}

	function show_time($sec) {
	$sec = floor($sec);

	if ($sec < 3600) {
	return sprintf("%d:%02d", floor($sec/60), $sec % 60);
	} else {
	return sprintf("%d:%02d:%02d", floor($sec/3600), floor($sec/60) % 60, $sec % 60);
	}
	}

	function set_status($part, $elapsed, $info) {
	global $numparts, $parts, $bestplan;

	# iterations, queuelen, shortest plan distance, shortest plan games
	if (isset($part) and isset($info))
	$parts[$part]["info"] = $info;

	# Display status
	$total_iters = 0;
	$total_queue = 0;
	for ($p=0; $p<$numparts; ++$p) {
	if (isset($parts[$p]["info"])) {
	$total_iters += $parts[$p]["info"][0];
	$total_queue += $parts[$p]["info"][1];
	}
	}

	if ($total_iters % 25000 == 0 or !isset($part)) {
	$pph = floor($total_iters/$elapsed*3.6);

	print "[" . show_time($elapsed) . "] $total_iters iterations (" . $pph .
	"k per hr), q=$total_queue";
	print "\n";
	}
	}

	# =============================================================================

	function runpart($startgame, $endgame) {
	global $schedule, $queuesize, $bestplan;
	$start = time();

	#echo "status,Running $startgame to $endgame\n";

	# First build the branch-and-bound queue with one plan for each game
	$bb_queue = new PlanList(pow(2,$queuesize)-1);
	for ($game_index = $startgame; $game_index < $endgame; ++$game_index) {
	$game = $schedule[$game_index];
	$plan = array( "length" => 0,
	"bitmap" => $game["bitmap"] );
	$plan[] = $game_index;
	$bb_queue->insert($plan);
	}

	$iterations = 0;
	$goalsize = 15;
	while($bb_queue->count() > 0) {
	# Remove the shortest plan
	$shortest_plan = $bb_queue->get_min();

	$legs = count($shortest_plan) - 3;
	if (!isset($bestplan[$legs]) or
	$shortest_plan["length"] < $bestplan[$legs]["length"]) {
	$bestplan[$legs] = $shortest_plan;
	$showplan = $shortest_plan;
	$planlen = $shortest_plan["length"];
	unset($showplan["length"]);
	unset($showplan["bitmap"]);
	echo "plan," . join(",", $showplan) . ",$planlen\n";
	}

	# Otherwise, find all valid 'next games' for this plan
	$lastgame_index = end($shortest_plan);
	$lastgame = $schedule[$lastgame_index];
	foreach ($lastgame["next_games"] as $nextgame_index => $nextgame_info) {
	$nextgame_index = $nextgame_info[1];
	$nextgame = $schedule[$nextgame_index];
	if (($nextgame["bitmap"] & $shortest_plan["bitmap"]) == 0) { # okay
	# Add the new game to this schedule and add that plan to the queue
	$newplan = $shortest_plan;
	$newplan[] = $nextgame_index;
	$newplan["length"] += $nextgame_info[0];
	$newplan["bitmap"] \|= $nextgame["bitmap"];
	$bb_queue->insert($newplan);
	}
	}

	if ($iterations > 0 and $iterations % 1000 == 0) {
	# iterations, queuelen, shortest plan distance, shortest plan games
	echo "status,$iterations," . $bb_queue->count() . ",";
	echo "" . round($shortest_plan["length"], 1) . ",";
	echo "" . (count($shortest_plan)-2) . "\n";
	}
	$iterations++;
	}

	echo "status,$iterations," . $bb_queue->count() . ",999999,0\n";
	}

	function runmaster($script, $numparts) {
	global $parts, $bestplan, $queuesize;

	# Start n parts
	echo "Starting $numparts children\n";
	for ($p = 0; $p < $numparts; ++$p) {
	$cmd = "php $script --part=" . ($p+1) . "/" . $numparts .
	" --queuesize=" . $queuesize;
	$phandle = popen($cmd, "r");
	$parts[$p] = array( "handle" => $phandle );
	}

	$start = time();
	$partsrunning = 4;
	while ($partsrunning > 0) {
	$partsrunning = 0;
	for ($p = 0; $p < $numparts; ++$p) {
	if (isset($parts[$p]) and isset($parts[$p]["handle"])) {
	$part = $parts[$p];
	if (feof($part["handle"])) {
	# Part is done -- clean up
	unset($parts[$p]["handle"]);
	} else {
	# Part is still running -- get output
	$out = rtrim(fgets($part["handle"], 4096));
	if (isset($out) and $out != "") {
	$out = split(",", $out);
	$outtype = array_shift($out);
	$elapsed = time() - $start + 1;
	$head = "[$p, " . show_time($elapsed) . "]";

	if ($outtype == "plan") {
	# Save the plan
	$planlen = array_pop($out); # last element is length
	$plan_games = count($out);

	if (!isset($bestplan[$plan_games])) {
	# First plan of this length
	$bestplan[$plan_games] = array(
	"length" => $planlen,
	"plan" => $out
	);
	show_plan($out);
	} elseif ($bestplan[$plan_games]["length"] > $planlen) {
	# Shortest plan of this length yet
	$bestplan[$plan_games]["length"] = $planlen;
	$bestplan[$plan_games]["plan"] = $out;
	show_plan($out);
	}
	} elseif ($outtype == "status") {
	# Save/show the status
	set_status($p, $elapsed, $out);
	}
	}

	$partsrunning++;
	}
	}
	}

	# Don't want to active spin
	sleep(1);
	}

	set_status(null, time() - $start, null);
	}

	?>