Finish 2011-11-09 12:00:00 UTC

something slightly less buggy

by James White

Status: Passed
Results: 79030742 (cyc: 22, node: 1042)
CPU Time: 8.282
Score: 790437.0
Submitted at: 2011-11-05 07:50:23 UTC
Scored at: 2011-11-05 07:51:18 UTC

Current Rank: 1504th (Highest: 692nd )
Basis for: and cleaner (diff)

Comments
Please login or create a profile.
Code
% submissions/solver_H.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 =[];
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=6;
[MOVES{N}, VINE{N}, SCORE(N)] = winder(board,A, 1, nsew,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));

N=7;
%[MOVES{N}, VINE{N}, SCORE(N)] = winder(board,A', -1, nsew,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));

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=12;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf3(board,A', -1, ewns,[], [], []);


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));

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] = winder(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

board = UPDOWN*board;
visited = zeros(size(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 = find(board(:) == min(board(board(:) > minboard)))';
    
    startnodes = startnodes(1);
 end

% div = 5;
% 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;
occupied = false(size(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
    unoccupied(vine(1)) = false; % 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;
        %alldeadend = true;
        %bob = find(A(vine(k),:));
        for adj = vine(k) + nsew%(randperm(4))
            %for adj = bob
            if adj > 0 && adj <= numel(board) && ( abs(adj - vine(k))==nrows | mod(min(vine(k),adj),nrows) ) && curval == board(adj)
                %assert( any( bob == adj ) );
                %assert(adj > 0 && adj <= numel(board) && ( abs(adj - vine(k))==nrows | mod(min(vine(k),adj),nrows) ));
                %if curval <= board(adj)
                
                %[r,c]=ind2sub(size(board), adj);
                %fprintf('  adj %i (%3i,%3i) is %i \n',adj, r,c, board(adj));
                %assert(edgecount(adj)<4);
                
                edgecount(adj) = region_edges_left(adj, board);
                
                %                 if  alldeadend && edgecount(adj) > 0 % can avoid deadend
                %                     alldeadend = false;
                %                     hi = board(adj);
                %                     next = adj;
                %                     edge_count_lo = edgecount(adj); %edges_left(adj, board);
                %                     continue;
                %                 end
                
                if true %edgecount(adj) > 0 || alldeadend
                    if board(adj) < hi
                        hi = board(adj);
                        next = adj;
                        edge_count_lo = edgecount(adj); %edges_left(adj, board);
                    else if board(adj) == hi && edgecount(adj)
                            %next_outdeg = edgecount(adj);
                            %n = edges_left(adj, board);
                            %n = region_edges_left(adj, board);
                            %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));
                            
                            if edgecount(adj) < edge_count_lo
                                %hi = board(adj);
                                next = adj;
                                edge_count_lo = edgecount(adj);
                            end
                        end
                    end
                end
            end
        end
        
        
        if ~next
            %break;
            tempscore = UPDOWN*score;
            
            %score = UPDOWN*sum(board(vine(1:k)));
            
            if tempscore > bestscore
                bestscore = tempscore;
                bestvine = vine;
                bestlength = k;
            end
            
            %backtrack
            if true% backtracks < 1000

%                 if k == 30
%                     rel = region_edges_left(vine(k), board) 
%                     v = vine(k)
%                     board(v)
%                     board(v-1)
%                     break
%                 end
                % note that all visited nodes have the same board value
                %while k && ~has_neighbor_in_region(vine(k),board,original_board(vine(k)))
                    %fprintf(' r%i',k);
                    score = score -  original_board(vine(k));
                    %board(vine(k)) = original_board(vine(k));
                    k = k-1; % board(vine(k)) is still marked as visited so we will not visit it again       
                    
                    
                %end
                %if k == 0
                %   
                %    break
                %end
                
                if k %&& region_edges_left(vine(k), board)
                    
                    backtracks = backtracks + 1;
                    continue;
                end
            end
            break;
        end
        curval = board(next); % hi;
        k = k+1;
        
        score = score +  board(next); %hi;
        vine(k) = next;
        occupied(next) = true;
        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;
    %score = UPDOWN*sum(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

%score
end

% note that all visited nodes have the same board value
% should not be used to count edges for a visited node
% could pass in original_board to fix
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
    if adj > 0 && adj <= numel(board) && ( abs(adj - node)==nrows | mod(min(node,adj),nrows) ) && board(node) == board(adj) && board(adj) > -Inf
        n = n+1;
    end
end

if nrows == 1 % counting issues if nrows = 1
    n = n/2;
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
    if adj > 0 && adj <= numel(board) && ( abs(adj - node)==nrows | mod(min(node,adj),nrows) ) && board(adj) == regionval
        tf = true;
        return
    end
end

tf = false;

end


% function tf = isBottomOfHill(node, board)
%
% nrows = size(board,1);
% nsew = [ 1 -1 nrows -nrows];
%
% for adj = node + nsew
%     if adj > 0 && adj <= numel(board) && ( abs(adj - node)==nrows | mod(min(node,adj),nrows) ) && board(node) <= board(adj)
%            tf = true;
%            return 
%     end
% end
%
%tf = false;
%
% end