Finish 2012-11-07 16:00:00 UTC

Twilight entry

by Victoria

Status: Passed
Results: 369518 (cyc: 25, node: 1151)
CPU Time: 93.163
Score: 382783.0
Submitted at: 2012-11-02 11:52:00 UTC
Scored at: 2012-11-02 11:56:31 UTC

Current Rank: 1798th (Highest: 156th )

Comments
Please login or create a profile.
Code
function xyOut = solver(a, xyIn, wts)

% Solver by Victoria

% Copyright 2012 The MathWorks, Inc.

xyOut = xyIn;
xyPrevious = xyIn;
xyNext = xyIn;

NodesNum = length(wts);

if NodesNum <= 100
    scorePrevious = scoreSolution(xyOut, a, xyIn, wts);
    for I = 1:13
        Node = floor(rand*NodesNum) + 1;
        DRand = floor(rand*4) + 1;
        if (DRand == 1)
            Direction = [1 0];
        end
        if (DRand == 2)
            Direction = [0 1];
        end
        if (DRand == 3)
            Direction = [-1 0];
        end
        if (DRand == 4)
            Direction = [0 -1];
        end
        xyNext(Node,:) = xyPrevious(Node,:) + Direction;
        if validateSolution(xyIn,xyNext)
            scoreNext = scoreSolution(xyNext, a, xyIn, wts);
            if scoreNext < scorePrevious
                xyPrevious = xyNext;
            end
        end
    end
end

xyOut = xyPrevious;

% Score estimation

    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)
        pass = true;
        
        % Check that points are integers
        if ~isequal(XYnew,round(XYnew))
            %             error('XY coordinates must be at integer locations')
            pass = false;
        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')
            pass = false;
        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')
            pass = false;
        end
    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: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));
        A = A - mean(A,2)*ones(1,size(A,2));
        S = full(dot(A,A,1));
        %         D = bsxfun(@plus,S,S')-full(2*(A'*A));
        D = ones(size(S,2),1)*S + S'*ones(1,size(S,2)) - full(2*(A'*A));
    end
end