what happens with my result array here? i expected the size of the result array to be equal to the input array, but its missing 3 entries.. where did they go? they didn't go to $ret , as they were supposed to..
code:
<?php
init();
$list_xy = array(
0 => array(
'id' => '308',
'x' => '37',
'y' => '63'
),
1 => array(
'id' => '963',
'x' => '38',
'y' => '134'
),
2 => array(
'id' => '385',
'x' => '39',
'y' => '132'
),
3 => array(
'id' => '1231',
'x' => '50',
'y' => '199'
),
4 => array(
'id' => '788',
'x' => '51',
'y' => '59'
),
5 => array(
'id' => '1151',
'x' => '53',
'y' => '61'
),
6 => array(
'id' => '671',
'x' => '55',
'y' => '60'
),
7 => array(
'id' => '1487',
'x' => '55',
'y' => '55'
)
);
$sorted_list_xy = sort_by_xy_distance($list_xy);
$sorted_list_xy_size = count($sorted_list_xy, COUNT_NORMAL);
$list_xy_size = count($list_xy, COUNT_NORMAL);
var_dump($sorted_list_xy_size == $list_xy_size ? "looks right" : "something is wrong", $sorted_list_xy_size, $list_xy_size);
die("died");
function sort_by_xy_distance($input_list)
{
$ret = array();
$a = $input_list[0];
array_push($ret, $input_list[0]);
$input_list[0] = null;
$i = 1;
for ($i = 1; $i < count($input_list); ++$i) {
if ($input_list[$i] == null) {
echo 'already added to list..';
continue;
}
$ii = 1;
$tmpdistance = 0;
$nearest = array(
'index' => -1,
'distance' => PHP_INT_MAX
);
for ($ii = 1; $ii < count($input_list); ++$ii) {
if ($input_list[$ii] == null || $ii == $i) {
//echo 'already added to list..';
continue;
}
$tmpdistance = abs($input_list[$ii]['x'] - $a['x']) + abs($input_list[$ii]['y'] - $a['y']);
if ($tmpdistance < $nearest['distance']) {
$nearest['index'] = $ii;
$nearest['distance'] = $tmpdistance;
}
}
assert($nearest['index'] != -1);
array_push($ret, $input_list[$nearest['index']]);
$a = $input_list[$nearest['index']];
$input_list[$nearest['index']] = null;
}
return $ret;
}
function init()
{
error_reporting(E_ALL);
set_error_handler("exception_error_handler");
}
function exception_error_handler($errno, $errstr, $errfile, $errline)
{
if (!(error_reporting() & $errno)) {
// This error code is not included in error_reporting
return;
}
throw new ErrorException($errstr, 0, $errno, $errfile, $errline);
}
output:
already added to list..already added to list..already added to list..string(18) "something is wrong" int(5) int(8) died
expected output: (something similar to)
already added to list..already added to list..already added to list..string(11) "looks right" int(8) int(8) died
what i expected the list to turn in to: a list where the difference to the next's [x][y] is as little as possible, which would be:
array(8) {
[0]=>
array(3) {
["id"]=>
string(3) "308"
["x"]=>
string(2) "37"
["y"]=>
string(2) "63"
}
[1]=>
array(3) {
["id"]=>
string(3) "788"
["x"]=>
string(2) "51"
["y"]=>
string(2) "59"
}
[2]=>
array(3) {
["id"]=>
string(4) "1151"
["x"]=>
string(2) "53"
["y"]=>
string(2) "61"
}
[3]=>
array(3) {
["id"]=>
string(3) "671"
["x"]=>
string(2) "55"
["y"]=>
string(2) "60"
}
[4]=>
array(3) {
["id"]=>
string(4) "1487"
["x"]=>
string(2) "55"
["y"]=>
string(2) "55"
}
[5]=>
array(3) {
["id"]=>
string(3) "385"
["x"]=>
string(2) "39"
["y"]=>
string(3) "132"
}
[6]=>
array(3) {
["id"]=>
string(3) "963"
["x"]=>
string(2) "38"
["y"]=>
string(3) "134"
}
[7]=>
array(3) {
["id"]=>
string(4) "1231"
["x"]=>
string(2) "50"
["y"]=>
string(3) "199"
}
}
I suck at making graphical illustrations, but ill give it a go. This is my map: map http://imagizer.imageshack.us/a/img633/3521/E0HGRe.png
i need to visit all the black dots.
This is my current path:
this path is not very optimal..
here is the path i want:
and that's what the sort function is trying to find, the shortest path to visit all the black dots.
