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

solver2

by Markus Buehren

Status: Passed
Results: 77809 (cyc: 6, node: 902)
CPU Time: 1.187
Score: 77840.6
Submitted at: 2012-11-01 15:56:54 UTC
Scored at: 2012-11-01 21:05:52 UTC

Current Rank: 1675th (Highest: 39th )

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

xyOut = xyIn;

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

xyOut = solver_center(a, xyOut,  wts);
xyOut = solver_center(a, xyOut,  wts);
xyOut = solver_center(a, xyOut,  wts);
xyOut = solver_center(a, xyOut,  wts);
xyOut = solver_center(a, xyOut,  wts);

end

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

conn = zeros(N,1);
for n = 1:N
  board(xyInT(n,1), xyInT(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 + xyInT(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];
  found = 0;
  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;
      found = 1;
      break
    end
  end
end
xyOut = xyOutT + D - P; 
end

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

N = size(xyIn,1);

xyOut = xyIn;
xyMean2 = round(xyMean2);
for n = 1:N
  xyOut(n,:) = xyMean2 + (xyIn(n,:) - xyMean2) * 3;
end

end

function xyOut = solver_lines(a, xyIn, wts)
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) = xyOut(k,2) - 10;
      where =  1;
      dir   =  1;
    case 1
      where = where + dir;
    case 2
      xyOut(k,2) = xyOut(k,2) + 10;
      where =  1;
      dir   = -1;
  end
end

end

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

function [puzzleType, xyMean2] = getPuzzleType(xyIn)

puzzleType = 0;
xyMean2 = [NaN NaN];

N = size(xyIn, 1);

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