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

solver3c 20

by Markus Buehren

Status: Passed
Results: 4873 (cyc: 6, node: 1046)
CPU Time: 10.238
Score: 4910.48
Submitted at: 2012-11-02 00:06:53 UTC
Scored at: 2012-11-02 00:09:45 UTC

Current Rank: 1554th (Highest: 4th )
Based on: solver3c 16 (diff)

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

%if isempty(params) || ~exist('params', 'var')
  params.N1 = 6;
  params.N2 = 8;
%end

xyOut = xyIn;

[puzzleType, xyMean2] = getPuzzleType(xyIn);
switch puzzleType
  case 1
    xyOut = solver_circles(a, xyOut);
  case 2
    xyOut = solver_lines  (a, xyOut);
  case 3
    xyOut = solver_tight  (a, xyOut, xyMean2, params.N2);
  otherwise
    % unknown puzzle type
end

for n1=1:params.N1
  xyOut = solver_tight (a, xyOut, xyMean2, params.N2);
  for n2=1:params.N2
    xyOut = solver_center(a, xyOut);
  end
end

end

function xyOut = solver_center(a, xyIn)
N = size(xyIn,1);
xyMin = min(xyIn);
padding = 4;
P = padding + 1;
D = repmat(xyMin, N, 1);
xyInT = xyIn - D + P ;
xyOutT = xyInT;
xyMaxT = max(xyOutT);
board = zeros(xyMaxT(1) + padding, xyMaxT(2) + padding);

conn = zeros(N,1);
for n = 1:N
  board(xyOutT(n,1), xyOutT(n,2)) = 1;
  conn(n) = length(find(a(n,:)));
end

[~,sortIndex] = sort(conn, 1, 'descend');
for s = 1:N
  n = sortIndex(s);
  index = find(a(n,:));
  I = length(index);
  %[I xyIn(n,:)]
  tmp = [0, 0];
  for i=1:I
    tmp = tmp + xyOutT(index(i),:);
  end
  tmp = round(tmp / I);
  shift = [0 0; 
           0  1;  0 -1;  1  0; -1  0; 
           1  1;  1 -1; -1  1; -1 -1; 
           0  2;  0 -2;  2  0; -2  0; 
           1  2;  1 -2;  2  1; -2  1;
           2  1;  2 -1;  1  2;  1 -2;
           2  2;  2 -2; -2  2; -2 -2
           0  3;  0 -3;  3  0; -3  0; 
           1  3;  1 -3;  3  1; -3  1; 
           -1 3; -1 -3;  3 -1; -3 -1; 
           3  0; -3  0;  3  0;  0 -3; 
           3  1; -3  1;  3  1;  1 -3; 
           3 -1; -3 -1;  3 -1; -1 -3; 
          ];
  for k = 1:size(shift,1)
    tmp2 = tmp + shift(k,:);
    if board(tmp2(1), tmp2(2)) == 0
      board(xyOutT(n,1), xyOutT(n,2)) = 0;
      board(tmp2  (1), tmp2  (2)) = 1;
      xyOutT(n,:) = tmp2;
      break
    end
  end
end
xyOut = xyOutT + D - P; 
end

function xyOut = solver_tight(a, xyIn, xyMean2, N2)

N = size(xyIn,1);

xyOut = xyIn;

xyMean2    = round(xyMean2);
xyMeanCurr = round(mean(xyIn));

xyDiffCurr = xyIn - repmat(xyMeanCurr, N, 1);
distCurr = sqrt(sum(xyDiffCurr .^ 2, 2));

rangeCurr = max(xyIn) - min(xyIn);
rangeCurr(rangeCurr < 1) = 1;
scale = round(3 * N2 * sqrt(N) ./ rangeCurr);
scale(scale < 1) = 1;

%if length(find(distCurr < sqrt(N))) > 0.7 * N
if any(scale > 1)
  for n = 1:N
    xyOut(n,:) = xyMean2 + (xyIn(n,:) - xyMeanCurr) .* scale;
  end
end

end

function xyOut = solver_lines(a, xyIn)
xyOut = xyIn;
[~, index] = sort(xyIn(:,1));
N = size(xyIn,1);
yMin = min(xyIn(:,2));
yMax = max(xyIn(:,2));
where  = 1;
dir    = 1;

for n = 1:N
  k = index(n);
  
  switch where
    case 0
      xyOut(k,2) = yMin;%xyOut(k,2) - 10;
      where =  1;
      dir   =  1;
    case 1
      where = where + dir;
    case 2
      xyOut(k,2) = yMax;%xyOut(k,2) + 10;
      where =  1;
      dir   = -1;
  end
end

end

function xyOut = solver_circles(a, xyIn)
xyOut = xyIn;
end

function [puzzleType, xyMean2] = getPuzzleType(xyIn)

puzzleType = 0;

N = size(xyIn, 1);

xyMean = mean(xyIn);
xyDiff = xyIn - repmat(xyMean, N, 1);
dist = sqrt(sum(xyDiff .^ 2, 2));
[~, sIndex] = sort(dist);
xyMean2 = mean(xyIn(sIndex(1:round(N/2)),:));

if max(dist) - min(dist) < 0.01 * min(dist)
  puzzleType = 1;
  return
end

[~, indexMinX] = min(xyIn(:,1));
[~, indexMaxX] = max(xyIn(:,1));

allPointsOnLine = 1;
for n=1:N
  if ~haveSameSlope(...
    xyIn(indexMinX,1), ...
    xyIn(indexMinX,2), ...
    xyIn(indexMaxX,1), ...
    xyIn(indexMaxX,2), ...
    xyIn(indexMinX,1), ...
    xyIn(indexMinX,2), ...
    xyIn(n,1) - xyIn(indexMinX,1), ...
    xyIn(n,2) - xyIn(indexMinX,2))
    allPointsOnLine = 0;
    break
  end
end
if allPointsOnLine
  puzzleType = 2;
  return
end
  
xyDiff2 = xyIn - repmat(xyMean2, N, 1);
dist2 = sqrt(sum(xyDiff2 .^ 2, 2));

if length(find(dist2 < sqrt(N))) > 0.7 * N
  puzzleType = 3;
  return
end

end

function bool = haveSameSlope(x1, y1, x2, y2, x3, y3, x4, y4)
bool = abs( (y2 - y1)*(x4 - x3) - (x2 - x1)*(y4 - y3)) < 0.1;
end