function [score, numKnots] = grade(XYnew, A, XYold, wts)
% GRADE scores the solution for a given problem for the Knots Contest
%
% The MATLAB Contest Team
% Copyright 2012 The MathWorks, Inc.
[score, numKnots] = scoreSolution(XYnew, A, XYold, wts);
end
function [score,score1] = scoreSolution(XYnew, A, XYold, wts)
% The total score for a puzzle consists of two parts. The primary part is
% the number of knots. The second part is determined by the work (or
% energy) required to move your nodes around. This enery score is
% normalized by a very large energy, so it should generally be less than
% one. Therefore, it's most important to remove knots, and tie breakers in
% the number of knots will be broken by who does the least amount of work
% moving nodes around. The score is given by the following equation:
%
% Score = nKnots + E/E_max
%
% where
% E = sum(d.*wts)
% E_max = D*sum(wts)
% Check that solution is valid
validateSolution(XYold,XYnew);
% Main score component: number of knots
score1 = numKnots(XYnew,A);
% Secondary score component: normalized energy
d = moved_dist(XYold,XYnew);
D = max_dist(XYold);
E = sum(d.*wts');
E_max = D*sum(wts);
score2 = E/E_max;
% Total score is the sum of two components
score = score1 + score2;
end
function pass = validateSolution(XYold,XYnew)
% Check that points are integers
if ~isequal(XYnew,round(XYnew))
error('XY coordinates must be at integer locations')
end
% Check that number of points is correct
nPoints = size(XYold,1);
nNewPoints = size(XYnew,1);
if ~isequal(nPoints,nNewPoints)
error('Number of points is not the same as original number of points')
end
% Check that point coordinates are unique
nUniquePoints = size(unique(XYnew,'rows'),1);
if ~isequal(nPoints,nUniquePoints)
error('Each point must have a unique location')
end
pass = true;
end
function N = numKnots(XY,A)
% This function finds the number of knots in a network of points XY whose
% connectivity is given by A.
% Consider only unique lines (A is symmetric with ones on diagonal)
A = triu(A,1);
nLines = nnz(A);
% Find xy coordinates for first and second point on each line
[p1i,p2i] = find(A);
p1 = XY(p1i,:);
p2 = XY(p2i,:);
% Check each pair of lines for an intersection
N = 0;
for i = 1:nLines-1
line1 = [p1(i,:) p2(i,:)]; %[x1 y1 x2 y2]
for j = i+1:nLines
line2 = [p1(j,:) p2(j,:)]; %[x1 y1 x2 y2]
if areIntersecting(line1,line2)
N = N + 1;
end
end
end
function bool = areIntersecting(line1, line2)
% Determine if two line segments intersect.
%
% line1 = [x1, y1, x2, y2]
% line2 = [x3, y3, x4, y4]
%
% This function is robust to floating point precision issues assuming all
% input coordinates are integer-valued. If all coordinates have absolute
% values that do not exceed x, then the arithmetic operations used in this
% function could, as an intermediate step, produce a value with magnitude
% as large as 8*x^4. For double-precision floating point, this implies
% that the following must be satisfied:
%
% 8*x^4 < 2^53
%
% or equivalently, x < 5792.
%
% http://en.wikipedia.org/wiki/Line-line_intersection
x1 = line1(1);
y1 = line1(2);
x2 = line1(3);
y2 = line1(4);
x3 = line2(1);
y3 = line2(2);
x4 = line2(3);
y4 = line2(4);
% Test to see if the lines share exactly one endpoint. If so, the lines
% intersect if either of the free points lies on the line segment formed by
% the other two points.
if isequal([x1, y1], [x3, y3]) && ~isequal([x2, y2], [x4, y4])
bool = isPointOnSegment(x2, y2, x1, y1, x4, y4) || isPointOnSegment(x4, y4, x1, y1, x2, y2);
elseif isequal([x1, y1], [x4, y4]) && ~isequal([x2, y2], [x3, y3])
bool = isPointOnSegment(x2, y2, x1, y1, x3, y3) || isPointOnSegment(x3, y3, x1, y1, x2, y2);
elseif isequal([x2, y2], [x3, y3]) && ~isequal([x1, y1], [x4, y4])
bool = isPointOnSegment(x1, y1, x2, y2, x4, y4) || isPointOnSegment(x4, y4, x1, y1, x2, y2);
elseif isequal([x2, y2], [x4, y4]) && ~isequal([x1, y1], [x3, y3])
bool = isPointOnSegment(x1, y1, x2, y2, x3, y3) || isPointOnSegment(x3, y3, x1, y1, x2, y2);
% Next we check for parallel and coincident lines. Parallel lines
% obviously don't intersect. Coincident lines intersect if an endpoint from
% one of the lines lies on the other segment.
elseif haveSameSlope(x1, y1, x2, y2, x3, y3, x4, y4)
if haveSameIntercept(x1, y1, x2, y2, x3, y3, x4, y4) % lines are coincident
bool = (isPointBetween(x3, x4, x1, 1) && isPointBetween(y3, y4, y1, 1)) || ...
(isPointBetween(x3, x4, x2, 1) && isPointBetween(y3, y4, y2, 1)) || ...
(isPointBetween(x1, x2, x3, 1) && isPointBetween(y1, y2, y3, 1)) || ...
(isPointBetween(x1, x2, x4, 1) && isPointBetween(y1, y2, y4, 1));
else % lines are parallel
bool = false;
end
% If we get this far, we're in the general case of two well-defined
% non-parallel lines. The lines formed by the two segments must intersect
% somewhere. Find this intersection point and determine if it lies on the
% segments.
else % general case
% To avoid precision issues, represent point of intersection as a ratio
% of two integers: (Px, Py) = (Px_n/Px_d, Py_n/Py_d)
Px_n = (x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4);
Px_d = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4);
Py_n = (x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4);
Py_d = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4);
bool = isPointBetween(x1, x2, Px_n, Px_d) && ...
isPointBetween(y1, y2, Py_n, Py_d) && ...
isPointBetween(x3, x4, Px_n, Px_d) && ...
isPointBetween(y3, y4, Py_n, Py_d);
end
end
function bool = haveSameIntercept(x1, y1, x2, y2, x3, y3, x4, y4)
bool = (x4 - x3)*(y1*(x2 - x1) - x1*(y2 - y1)) == ...
(x2 - x1)*(y3*(x4 - x3) - x3*(y4 - y3));
end
function bool = haveSameSlope(x1, y1, x2, y2, x3, y3, x4, y4)
bool = (y2 - y1)*(x4 - x3) == (x2 - x1)*(y4 - y3);
end
function bool = isPointOnSegment(x1, y1, x2, y2, x3, y3)
% Determine if point (x1, y1) is on the segment formed by (x2, y2) and (x3, y3).
bool = haveSameSlope(x2, y2, x1, y1, x1, y1, x3, y3) && ...
isPointBetween(x2, x3, x1, 1) && ...
isPointBetween(y2, y3, y1, 1);
end
function bool = isPointBetween(pt1, pt2, num, den)
% Determine if either of the following is satisfied:
% pt1 <= num/den <= pt2
% pt1 >= num/den >= pt2
bool = ((pt1*den <= num) && (num <= pt2*den)) || ...
((pt1*den >= num) && (num >= pt2*den));
end
end
function d = moved_dist(XYold,XYnew)
% This function calculates the distance each node has moved based on the
% starting and ending positions of each node.
dXY = XYnew-XYold;
d = sqrt(dXY(:,1).^2 + dXY(:,2).^2);
end
function D = max_dist(XY)
% This function finds the maximum distance (D) between two points in the
% point set given for the contest.
x = XY(:,1);
y = XY(:,2);
% D = max(pdist(XY(k,:))); % <--Only works if you have Stats Toolbox
D = sqrt(max(max( sqdistance(XY') )));
end
function D = sqdistance(A)
% Adapted from the File Exchange function here:
% http://www.mathworks.com/matlabcentral/fileexchange/24599-pairwise-distance-matrix
% Compute square Euclidean distances between all pair of vectors.
% A: d x n1 data matrix
% D: n1 x n2 pairwise square distance matrix
% Written by Michael Chen (sth4nth@gmail.com).
A = bsxfun(@minus,A,mean(A,2));
S = full(dot(A,A,1));
D = bsxfun(@plus,S,S')-full(2*(A'*A));
end