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

something new with the code included

by James White

Status: Passed
Results: 77288449 (cyc: 21, node: 1611)
CPU Time: 46.033
Score: 773010.0
Submitted at: 2011-11-06 00:17:57 UTC
Scored at: 2011-11-06 00:20:51 UTC

Current Rank: 1219th (Highest: 555th )
Based on: something new (diff)

Comments
Please login or create a profile.
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);
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows ];
%ewns = [ nrows -nrows 1 -1 ];
ewns = [  -nrows -1 nrows 1 ];
% 


% %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?
% % 
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))
        for adj = neighbors
            %if adj > 0 && adj <= numel(board) && ( abs(adj - vine(k))==nrows | mod(min(vine(k),adj),nrows) ) && currentregion == board(adj)
            %% assert( any( bob == adj ) );
            %% assert(adj > 0 && adj <= numel(board) && ( abs(adj - vine(k))==nrows | mod(min(vine(k),adj),nrows) ));
            %if currentregion == board(adj) % check occupancy
            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)
                    if edgecount(adj) < edge_count_lo || adjacent_to_vine(adj,vine(k),board) 
                        %hi = board(adj);
                        next = adj;
                        edge_count_lo = edgecount(adj);
                    end
                    
                end
            end
            
            %end % occupancy check
        end
        

            
        % animate(aflag, moves,vine(1:k),original_board);
        % visualizevines(
        % drawnow
        % disp
        % figure
        % fprintf()
        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
    if adj > 0 && adj <= numel(board) && ( abs(adj - node)==nrows | mod(min(node,adj),nrows) ) && original_board(node) == board(adj)
        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
    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 = adjacent_to_vine(node, i_dont_count,board)

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

% counting issues if nrows = 1
for adj = node + nsew
    if adj ~= i_dont_count && adj > 0 && adj <= numel(board) && ( abs(adj - node)==nrows | mod(min(node,adj),nrows) )  && board(adj) == -Inf
        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
            if adj > 0 && adj <= numel(board) && ( abs(adj - vine(k))==nrows | mod(min(vine(k),adj),nrows) ) && curval <= board(adj) 
                %[r,c]=ind2sub(size(board), adj);
                %% fprintf('  adj %i (%3i,%3i) is %i \n',adj, r,c, board(adj));

                if board(adj) < hi
                    hi = board(adj);
                    next = adj;
                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