<?php
/**
 * Print the ordered optimial tour for a csv file of landmarks, between
 * the Ibuildings office in London and the Dutch PHP Conference.
 *
 * The algorithm used is based on dynamic programming, whilst not the fastest
 * or lowest memory usage algorithm, it is hopefully the best all-round for the
 * scorings in this challenge.
 *
 * No code standards were specified, so this is assuming lines need not be
 * wrapped, and functions/classes only used if needed.
 *
 * The results for this algorithm on the test results scores the following on my
 * laptop:
 *
 * Duration: ~54 seconds with xdebug disabled
 * Executable line count: 33 (PHP_CodeCoverage)
 * CRAP index: 6 (4 for the function, and 2 for the non-function code)
 *
 * @author Andy Thompson
 * @copyright Copyright (c) 2010 Andy Thompson
 * @license http://www.webtatic.com/license/new-bsd     New BSD License
 */

/**
 * Find the optimal tour for a group of landmarks.
 *
 * @param integer $countUnvisited the number of unvisited nodes
 * @param array $unvisited an array of unvisited nodes
 * @param integer $firstLandmark the key of the first landmark to visit
 * @param array $costs the costs of travelling between edges
 * @return array
 */
function findOptimalTour($countUnvisited, $unvisited, $lastLandmark, $costs)
{
    // check if all the landmarks between start and destination have been visited
    if ($countUnvisited > 0) {
        // preseed the best cost by a suitably high value that shouldn't occur
        $bestTourCost = 255;
        // using dynamic programming, find the cheapest sub-tour joined to the
        // last landmark
        foreach ($unvisited as $nextLandmark) {
            $tour = findOptimalTour($countUnvisited - 1, array_diff($unvisited, array($nextLandmark)), $nextLandmark, $costs);
            $tourCost = $tour[1] += $costs[$nextLandmark + $lastLandmark];

            // find the best tour
            if ($bestTourCost > $tourCost) {
                $tour[0][] = $nextLandmark;
                $bestTour = $tour;
                $bestTourCost = $tourCost;
            }
        }
        return $bestTour;
    } else {
        // return the sub-tour for the start node to the last landmark
        return array(array(), $costs[1 + $lastLandmark]);
    }
}

$landmarkNames = $costs = array();
$landmarks = array(1 => array(deg2rad(51.58701), deg2rad(-0.23029)), 2 => array(deg2rad(52.34139), deg2rad(4.88833)));

// As the challenge gives points for lower CRAP index, and not error
// handling, assume file is readable rather than checking.
$csvHandle = fopen($_SERVER['argv'][1], 'r');
// Trim off the field keys and use them for field lookups.
$fields = array_flip(fgetcsv($csvHandle));
$i = 4;
// Load each landmark from file.
while (($landmark = fgetcsv($csvHandle)) !== false) {
    $landmarkNames[$i] = $landmark[$fields['Landmark']];
    // Convert the latitude and longitude to radians from degrees.
    $landmark = array(deg2rad($landmark[$fields['Latitude']]), deg2rad($landmark[$fields['Longitude']])) ;
    // Get the costs for each node to every other node, except start to end
    // which there is no edge for.
    foreach ($landmarks as $key => $landmarkB) {
        // Find a proportional representation of the distance between
        // landmarks. Exact distance is not needed as each cost would be
        // multiplied by the same amount.
        $a = pow(sin(($landmark[0] - $landmarkB[0]) / 2), 2) + cos($landmark[0]) * cos($landmarkB[0]) * pow(sin(($landmark[1] - $landmarkB[1]) / 2), 2);
        $costs[$key + $i] = atan2(sqrt($a), sqrt(1 - $a));
    }

    // Add the landmark after the cost calculation to prevent calculating an
    // nonexistant edge.
    $landmarks[$i] = $landmark;
    // Use a power of 2 for each key to allow for symetric costs by adding
    // two keys together.
    $i *= 2;
}
fclose($csvHandle);

// The remaining landmarks (excluding the start and end).
$nodes = array_slice(array_keys($landmarks), 2);

$result = findOptimalTour(count($nodes), $nodes, 2, $costs);

// Print out the optimial tour landmark names, a foreach would be simpler but
// would increase CRAP index.
echo join("\n", array_replace(array_fill_keys($result[0], null), $landmarkNames)) . "\n";