2011-11-09 12:00:00 UTC

# something new

Status: Failed
Results: Failed (execution): Undefined function or variable ''nsew''.

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

% *8*8*4*8*8*3*7*7*18*7*7*8*8*8*8*7*24*8*8*8*8*8
SCORE = -Inf * ones(1,25);
VINE = cell(1,25);
MOVES = cell(1,25);

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

%A =[];
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
% N=2;
% d=0;
% VINE{N} =[];
% %while d == numel(VINE{N})
% %  d=d+1;
% d=2;
% [MOVES{N}, VINE{N}, SCORE(N)] = dfs(board,A,d);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
% %fprintf('%2i %2i %i\n',d,  numel(VINE{N}), SCORE(N));
%
% %end
N=3;
[MOVES{N}, VINE{N}, SCORE(N)]   = greedy(board,A,1);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));

N=4;
[MOVES{N}, VINE{N}, SCORE(N)]  = greedy(board,A, -1);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
% %
% % 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?
% %
% % nrows = size(board,1);
% % nsew = [ 1 -1 nrows -nrows ];
% % %ewns = [ nrows -nrows 1 -1 ];
% % ewns = [  -nrows -1 nrows 1 ];
% % %
N=7;
[MOVES{N}, VINE{N}, SCORE(N)] = winder3(board,A, 1, nsew,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));

N=8;
[MOVES{N}, VINE{N}, SCORE(N)] = winder3(board,A', -1, nsew,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
%
%
% % these do well on a few nasty boards. probably luck.
%  N=10;
%  [MOVES{N}, VINE{N}, SCORE(N)] = reverse_warnsdorff3(board,A');
%  check(MOVES{N},VINE{N},board,limit, SCORE(N));
%
% N=11;
% [MOVES{N}, VINE{N}, SCORE(N)] = warnsdorff3(board,A');
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
%
% N=15;
% [MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A, 1, nsew,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
% N=16;
% [MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A', -1, nsew,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
% N=17;
% [MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A, 1, ewns,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
% N=18;
% [MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A', -1, ewns,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
%
% % N=19;
% %[MOVES{N}, VINE{N}, SCORE(N)] = greedorf3(board,A', -1, ewns,[], [], []);% score is buggy
% %check(MOVES{N},VINE{N},board,limit, SCORE(N));
%
% N=24;
% [MOVES{N}, VINE{N}, SCORE(N)] = greedorf(board,A, 1);
% N=25;
% [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 A = graph_from_board(board)

A = sparse(numel(board),numel(board));

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] = winder3(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 64 issue
aflag = false;
board = UPDOWN*board;

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

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

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

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 = find(board(:) == min(board(board(:) > minboard)))';

%startnodes = startnodes(1);
end

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

% currentregion = minboard;
% % adjacency matrix for this region only, try positive copy
% rA = A;
% rA(board(:) ~= currentregion,:) = 0;
% rA(:, board(:) ~= currentregion) = 0;

% edgecount = sum(rA,2); % outdegree
% edgecount(edgecount == 0) = Inf;
% [ignore,startnodes] = min(edgecount);

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

original_board = board;

for i = startnodes
board = original_board;

currentregion = board(i);

% adjacency matrix for this region only, try positive copy
rA = A;
rA(board(:) ~= currentregion,:) = 0;
rA(:, board(:) ~= currentregion) = 0;

vine(1) = i;
score = board(i);

edgecount = sum(rA,2); % outdegree
neighbors = find(rA(:, vine(1))); % nodes pointing to vine
edgecount(neighbors) = edgecount(neighbors)-1;

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

k = 1;
min_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;

neighbors = find(rA(vine(k),:)); % nodes that vine points to
neighbors = neighbors(board(neighbors) ~= VISITED); % occpancy check
%for adj = vine(k) + nsew%(randperm(4))
%assert( any( bob == adj ) );
%if currentregion == board(adj) % check occupancy
end

end
end

%end % occupancy check
end

animate(aflag, moves,vine(1:k),original_board);

if ~next

%tempscore = UPDOWN*score;
tempscore = UPDOWN*sum(original_board(vine(1:k)));
%assert(tempscore == UPDOWN*score);

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

%backtrack
%last_split = find(edgecount(vine(1:k)) < 1,1,'last');

last_k = k;
last_score = score;

while k>=min_k && edgecount(vine(k)) < 1
score = score - original_board(vine(k));
%animate(aflag,moves,vine(1:k),original_board);
%board(vine(k)) = original_board(vine(k)); % unvisit
k = k-1; % board(vine(k)) is still marked as visited so we will not visit it again
end

%k_same = max( min_k-1,find(edgecount(vine(1:last_k)) >=1,1,'last') );
%assert( isempty(k_same) || k == k_same);

if k>= min_k
%backtracks = backtracks + 1;
%rA(vine(k),vine(k+1)) = 0; % permits unvisiting

continue
end
% the backtracking was pointless so go forward again
k=last_k;
score = last_score;
rA = A;
rA(:,board(:) == VISITED) = 0;

edgecount = sum(rA,2); % outdegree
k = find(edgecount(vine(1:k)) > 0,1, 'last');

if k>=min_k
currentregion = original_board(vine(k));
board(original_board > original_board(vine(k))) = original_board(original_board > original_board(vine(k)));

% couldn't backtrack; can we get to another region?
neighbors = find(A(vine(k),:));
neighbors = neighbors(board(neighbors) ~= VISITED); % occupancy check
if any(board(neighbors) > currentregion)
[lo, idx] = min(board(neighbors));
next = neighbors(idx); % only one, could pass all as startnodes

currentregion = lo;

% adjacency matrix for this region only, try positive copy
rA = A;
rA(board(:) ~= currentregion,:) = 0;
rA(:, board(:) ~= currentregion) = 0;
edgecount = sum(rA,2); % outdegree

min_k = k+1; % don't backtrack beyond here
end
else
break
end
end

k = k+1;
score = score +  board(next);
vine(k) = next;

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

%score = UPDOWN*score;
%assert(sum(original_board(vine(1:k))) == score);
score = UPDOWN*sum(original_board(vine(1:k)));

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

% note that all visited nodes have the same board value
% pass in original_board to keep "visited" nodes from forming a "region"
function n = region_edges_left(node, board,original_board)
n = 0;
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows];

for adj = node + nsew
n = n+1;
end
end

if nrows == 1
n = n/2; % fix double counting when nrows = 1
end
end

function tf = has_neighbor_in_region(node, board, regionval)

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

% counting issues if nrows = 1
for adj = node + nsew
tf = true;
return
end
end

tf = false;

end

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

% counting issues if nrows = 1
for adj = node + nsew
tf = true;
return
end
end

tf = false;

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

```