Prob C

by ipark

HTML

<h2>
Prob C. 
</h2>
<ul> 입력
  <li> 3<br>3 3<br>7 7<br>10 0</li>
</ul>
<ul> 생성 결과
  <li> Expected: <span id="extected1">1</span>, Actual: <span id="actual1"></span> </li>
</ul>
<ul> 결과
  <li> Case1: <span id="result1"></span> </li>
</ul>

JavaScript

//-------------------------------------------------
// Utility Fn
//
var sqrt = Math.sqrt;

function square( v ) {
  return Math.pow( v, 2 );
}

function diff( v1, v2 ) {
  return Math.abs( v1 - v2 );
}

function getDistance( p1, p2 ) {
  return sqrt( square( diff(p1.x, p2.x) ) + square( diff(p1.y, p2.y) ) );
}

function True( value ) {
  return true === value;
}

function board(n, value) {
  var result = [];
  for (var i = 0; i < n; i++) {
    result.push(range(n, value));
  }
  return result;
}

function range(n, value) {
  var result = Array(n);
  for (var i = 0; i < n; i++) {
    result[i] = value;
  }
  return result;
}

function pointize( value ) {
  var p = value.split(' ');
  return {
    x: p[0],
    y: p[1]
  };
}

function print( ref, path ) {
  return path.map(function(pos) {
    return '('+ref[pos].x+','+ref[pos].y+')';
  }).join(' -> ');
}
//-------------------------------------------------
// Business Logic
//
function makeMap( list ) {
  var len = list.length,
      map = board( len, 0 );
      
  // use upper-right triangle
	for( var i = 0; i < len; i++ ) {
    for( var j = i+1; j < len; j++ ) {
      map[i][j] = getDistance( list[i], list[j] );
    }
  }
  return map;
}

function getPathValue( path, min ) {
  var sum = 0, p;
  path = [ 0 ].concat( path, path.length+1 );
  for( var i = 0, len = path.length-1; i < len; i++ ) {
    p = ( path[i] < path[i+1] ) ? { u: path[i], v: path[i+1] } : { u: path[i+1], v: path[i] };
    sum +=  map[p.u][p.v];
    if( sum > min ) break;
  }
  return sum;
}

function solve( list ) {
  var dist, path, result,
      min = 99999;
  
  for( var i = 0; i < list.length; i++ ) {
    path = list[i];
    dist = getPathValue( path, min );

    if( dist < min ) {
      min = dist;
      result = path;
    }
  }
  
  return [ 0 ].concat( result, result.length+1 );
}
//-------------------------------------------------
// Main Fn
//
var inputs = [
  [3, '3 3', '7 7', '10 0']
];
var perm = [
  [1, 2, 3], [1, 3, 2], [2, 1, 3],...