2011-11-09 12:00:00 UTC

# solver_G marginally faster, marginally smarter

Status: Passed
Results: 77035340 (cyc: 23, node: 1566)
CPU Time: 31.0
Score: 770498.0
Submitted at: 2011-11-04 15:56:15 UTC
Scored at: 2011-11-04 16:13:56 UTC

Current Rank: 1178th (Highest: 237th )
Based on: solver_F giddap (diff)

Code
```% submissions/solver_G.m
% James White
function [moves, vine] = solver(board, limit)

SCORE = -Inf * ones(1,25);
VINE = cell(1,25);
MOVES = cell(1,25);

%[MOVES{1}, VINE{1}, SCORE(1)]  = initial_solver(board, limit);

A = graph_from_board(board);

roughhist = hist(board(:), min(board(:):max(board(:))));
if sum(roughhist>0) < 50,

[regionboard, regioncounts, regionA] = regionfinder3(board);
else
regionboard = [];
regioncounts= [];
regionA = [];

end
% [MOVES{2}, VINE{2}, SCORE(2)] = dfs(board,A,7);
% %check(MOVES{2},VINE{2},board,limit, SCORE(2));
%
[MOVES{3}, VINE{3}, SCORE(3)]  = greedy(board,A,1);
% % check(MOVES{3},VINE{3},board,limit, SCORE(3));
[MOVES{4}, VINE{4}, SCORE(4)] = greedy(board,A, -1);
% % check(MOVES{4},VINE{4},board,limit, SCORE(4));

N=5;
%[MOVES{N}, VINE{N}, SCORE(N)] = warnsdorff3(board,A);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));

N=6;
%[MOVES{N}, VINE{N}, SCORE(N)] = reverse_warnsdorff3(board,A);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));

% why are these guys with A' doing better?
N=15;
%[MOVES{N}, VINE{N}, SCORE(N)] = reverse_warnsdorff3(board,A');
%check(MOVES{N},VINE{N},board,limit, SCORE(N));

N=16;
%[MOVES{N}, VINE{N}, SCORE(N)] = warnsdorff3(board,A');
%check(MOVES{N},VINE{N},board,limit, SCORE(N));

nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows ];
%ewns = [ nrows -nrows 1 -1 ];
ewns = [  -nrows -1 nrows 1 ];
%
%
N=8;
[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A, 1, nsew,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=9;
[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A', -1, nsew,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=10;
[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A, 1, ewns,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=11;
[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A', -1, ewns,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));

N=20;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf(board,A, 1);
N=21;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf(board,A', -1);

[result, vine_idx]          = max(SCORE);
%fprintf('%i',vine_idx);
vine                   = VINE{vine_idx};
moves                  = MOVES{vine_idx};
%out = double(board);

end

%function [moves, vine, score] = initial_solver(board, limit)
%
%moves = [];
%[score,vine] = max(board(:));
%
%end

function A = graph_from_board(board)

A = sparse(numel(board),numel(board),0);
nrows = size(board,1);

for i = 1:numel(board)

if i+1 <= numel(board) && mod(i,nrows) % smaller index must not be at end of a column
A(i,i+1    ) = board(i) <= board(i+1);
end

if i > 1 && mod(i-1,nrows) % smaller index must not be at end of a column
A(i,i-1    ) = board(i) <= board(i-1);
end

if i + nrows <= numel(board)
A(i,i+nrows) = board(i) <= board(i+nrows);
end

if i > nrows
A(i,i-nrows) = board(i) <= board(i-nrows);
end

end

end

% function flag = isconnected(a,b,m)
% % a,b:  Absolute indices
% % m,n:  Size of board
% % flag: True if indices a and b are four connected
% d = abs(a(:)-b(:));
% flag = (d == m) | (d == 1 & mod(min(a(:),b(:)), m));
% end
function [moves, bestvine, bestscore] = greedy(board,A, UPDOWN)
% UPDOWN = 1 to walk uphill, -1 to walk downhill

board = UPDOWN*board;
VISITED = -Inf;
moves = [];
vine = zeros(numel(board),1);
bestscore = -Inf;

%startnodes = 1:numel(board); % all

startnodes = find(board(:) == min(board(:)))'; % maybe not the best strategy

if numel(startnodes) > 50,
startnodes = startnodes(1:floor(numel(startnodes)/50):end);
end
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows];

original_board = board;

for i = startnodes
board = original_board;
vine(1) = i;
score = board(vine(1));
curval = board(vine(1));
board(vine(1)) = VISITED; % mark as visited
k = 1;

while(1)
%fprintf('round %i\n',k);
%fprintf('  vine(%i) = %i\n',k, vine(k));

hi = Inf;
next = 0;
for adj = vine(k) + nsew

end
end
end

if ~next
break;
end

curval = hi;
k = k+1;

score = score + hi;
vine(k) = next;
board(vine(k)) = VISITED; % mark as visited
end

score = UPDOWN*score;

if score > bestscore
bestscore = score;
bestvine = vine;
bestlength = k;
end

end

if UPDOWN == 1
bestvine = bestvine(1:bestlength);
else
bestvine = bestvine(bestlength:-1:1);
end

end

function [moves, bestvine, bestscore] = greedorf2(board,A, UPDOWN, nsew, regionboard, regioncounts, regionA)
% UPDOWN = 1 to walk uphill, -1 to walk downhill
% try to stay in current region and try to wind

board = UPDOWN*board;
%A = graph_from_board(board);

VISITED = -Inf;
moves = [];
vine = zeros(numel(board),1);
bestscore = -Inf;

%startnodes = 1:numel(board); % all
minboard = min(board(:));

%if board(1,:) == min
startnodes = find(board(:) == minboard)'; % maybe not the best strategy
edgecount = sum(A,2); % outdegree

%[ec, idx] = sort(edgecount(startnodes));

[ignore,idx] = min(edgecount(startnodes));
startnodes = startnodes(idx);

if false%regionboard
numregions = numel(regioncounts);
indeg = full(sum(regionA,1));

for k = find(indeg == 0)'
startnodes = [startnodes; find(regionboard(:) == k)];
end
startnodes = startnodes';
else

[minboard, startnodes] = min(board); % maybe not the best strategy
%startnodes = find(board(:) == minboard)';
%startnodes = startnodes(1);
end

div = 3;
if numel(startnodes) > div,
startnodes = startnodes(1:ceil(numel(startnodes)/div):end);
end

nrows = size(board,1);
%nsew = [ nrows -nrows 1 -1 ];
%nsew = [ nrows -nrows 1 -1 ];
%nsew = [  -nrows 1 nrows -1 ];
original_board = board;

for i = startnodes

board = original_board;
edgecount = sum(A,2); % outdegree

backtracks = 0;
vine(1) = i;
score = board(vine(1));
curval = board(vine(1));
neighbors = find(A(:, vine(1))); % nodes pointing to vine
edgecount(neighbors) = edgecount(neighbors)-1;

board(vine(1)) = VISITED; % mark as visited
k = 1;

%next = 0;
%hi = Inf;

while(1)
%fprintf('round %i\n',k);
%fprintf('  vine(%i) = %i\n',k, vine(k));
edge_count_lo = Inf;
hi = Inf;
next = 0;
%bob = find(A(vine(k),:));
for adj = vine(k) + nsew%(randperm(4))
%assert( any( bob == adj ) );

%                     continue;
%                 end

%assert(n<4,'next_outdeg = %i, n = %i, vine(%i) = %i,adj = %i',next_outdeg, n,k, vine(k), adj);%%%%%%%%%%
%assert(next_outdeg == n, 'next_outdeg = %i, n = %i',next_outdeg, n);
%assert(next_outdeg<4,'next_outdeg = %i, n = %i',next_outdeg, n);%%%%%%%%%%
%assert(k < numel(board));

end
end
end
end
end
end

if ~next
score = UPDOWN*score;

if score > bestscore
bestscore = score;
bestvine = vine;
bestlength = k;
end

%backtrack
if backtracks < 20
%while k >0 && edges_left(vine(k), board) == 0
k = k-1; % note that vine(k) is marked as visited so we will not visit it again
%end

if k

backtracks = backtracks + 1;
continue;
end
end
break;
end
curval = board(next); % hi;
k = k+1;

score = score +  board(next); %hi;
vine(k) = next;

neighbors = find(A(:, vine(k))); % nodes pointing to vine
edgecount(neighbors) = edgecount(neighbors)-1;
board(vine(k)) = VISITED; % mark as visited
end

score = UPDOWN*score;

if score > bestscore
bestscore = score;
bestvine = vine;
bestlength = k;
end

end

if UPDOWN == 1
bestvine = bestvine(1:bestlength);
else
bestvine = bestvine(bestlength:-1:1);
end

end

% function n = region_edges_left(node, board)
% n = 0;
% nrows = size(board,1);
% nsew = [ 1 -1 nrows -nrows];
%
% % counting issues if nrows = 1
% for adj = node + nsew
%         n = n+1;
%     end
% end
%
% if nrows == 1 % counting issues if nrows = 1
%     n = n/2;
% end
% end

% function tf = isBottomOfHill(node, board)
%
% nrows = size(board,1);
% nsew = [ 1 -1 nrows -nrows];
%
% for adj = node + nsew
%         return true
%     end
% end
%
% return false;
%
% end
function [regionboard, counts, regionA] = regionfinder3(board)
% iterative version because recursion depth was getting big
% also returns the region adjacency matrix regionA

regionboard = zeros(size(board));
regionnumber = 0;
regionA = sparse(numel(board),numel(board));
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows];

% d and to_visit form a stack
to_visit = zeros(10000,1);
d = 0;

for k = 1:numel(board)
if regionboard(k) == 0, % new region
regionnumber = regionnumber + 1;
d=d+1;
to_visit(d) = k;
while(d > 0)
[regionboard, to_visit,d,regionA] = regionfinder_r(board, regionboard, regionnumber, to_visit,d,regionA);

%             % pop next square to visit
%             i = to_visit(d);
%             d = d-1;
%
%             regionboard(i) = regionnumber; % mark as visited
%
%             for next = i + nsew
%                 if next > 0 && next <= numel(board) && ( abs(next - i)==nrows | mod(min(i,next),nrows) )
%                     if regionboard(next) == 0 %&& A(vine(d),next)
%                         if board(i) == board(next)
%                             % push
%                             d = d+1;
%                             to_visit(d) = next;
%                         end
%                     end
%                 end
%             end
end
end
end

counts = hist(regionboard(:), 1:regionnumber);
regionA = regionA(regionnumber,regionnumber);
end

% i is the index  of the starting square for filling the region
function [regionboard, to_visit,d,regionA] = regionfinder_r(board, regionboard, regioncount, to_visit,d,regionA)

% pop next square to visit
i = to_visit(d);
d = d-1;

regionboard(i) = regioncount; % mark as visited
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows];

%neighbors = i + nsew;
%neighbors = neighbors(neighbors > 0 & neighbors <= numel(board));
for next = i + nsew %neighbors
if next > 0 && next <= numel(board) && ( abs(next - i)==nrows | mod(min(i,next),nrows) )
%if ( abs(next - i)==nrows | mod(min(i,next),nrows) )
if board(i) == board(next)
if regionboard(next) == 0 %&& A(vine(d),next)
d = d+1;
to_visit(d) = next;
%regionboard = regionfinder_r(board, regionboard, next,regioncount);
end
else
if regionboard(next) > 0
if board(i) < board(next)
regionA(regionboard(i), regionboard(next)) = 1;
else
regionA(regionboard(next),regionboard(i)) = 1;
end
end
end
end
end
end

```