Finish 2011-04-20 12:00:00 UTC

CrossCat7

by Sergey Y.

Status: Passed
Results: 7116831 (cyc: 12, node: 978)
CPU Time: 65.475
Score: 17795.9
Submitted at: 2011-04-19 15:59:57 UTC
Scored at: 2011-04-19 16:50:12 UTC

Current Rank: 1078th (Highest: 714th )

Comments
Please login or create a profile.
Code
function board = solver(words, weights, n, penalty)

% words = words(weights>0);
% weights = weights(weights>0);

 lengths                 = cellfun('length',words);
% [~,idx]                 = sortrows([weights'./lengths'  weights'],[-1 -2]);
% words                   = words(idx);
% weights                 = weights(idx);


%sumw = sum(weights);
%[BOARD{1}, result(1)] = solver_columns(words, weights, n, penalty, sumw); 
for k=1:2:21
idx1=randperm(numel(words));
words1                   = words(idx1);
weights1                 = weights(idx1);
lengths1                 = lengths(idx1);
[~,idx2]                 = sortrows([weights1'./lengths1'  weights1'],[-1 -2]);
% words1                   = words1(idx2);
% weights1                 = weights1(idx2);


[BOARD{k}, result(k)] = solver_columns(words1(idx2), weights1(idx2), n, sum(weights),lengths1(idx2));     
[BOARD{1+k},  result(1+k)] = solver_press(words1(idx2), weights1(idx2), n, penalty, sum(weights),lengths1(idx2)); 
end
  
[~, board_idx]          = min(result);
board                   = BOARD{board_idx};

% 
% if result1 < result
%     board = board1;
% end

end

function [board, result] = solver_press(words, weights, n, penalty, result,wordlengths)

board = zeros(n);

%wordlengths = cellfun('length',words);

[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
last2letterword = find(B(:,1)>2,1)-1;

w2l = index(1:last2letterword)'; % should be row vector for for

isUnplayed = true(size(words));
%hopeless = false(size(words));

hopeless=~isUnplayed;
[C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC

c=1;
r=1;
L = 2; % dim of sq
while r+L-1 <= n,
        [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C, alphaix);
        if ~sq,
           break; % no more 2x2s
        end
        board(r+(0:L-1),c+(0:L-1)) = sq;        
        c=c+L+1;
        if c > n-(L-1),
            r =r+L+1;
            c=1;
        end
end
result = result - sum(weights(~isUnplayed));


% eliminate words that have already been played
[B,index] = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
words = words(isUnplayed);
nwords=numel(words);
%isUnplayed = true(size(nwords));

k=1;

% play remaining unused 2 letter words here?


% index of last word to play in current row
stop_index = min(nwords, n*k-c+1); % check that we haven't run out of words
start_index = 1;
wi=[];
while (r+B(stop_index,1)-1) <= n, % if the new row fits

    words_left = stop_index - start_index + 1; % num words to play in this row
    current_row_points = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols

    if current_row_points > 0,    
        for cc = c:min(n,words_left+c-1),
            %fprintf('\n* r=%2i,c=%2i\n',r,c);
            wi = start_index-c+cc; % word index
            %board(r:(r+B(wi,1)-1),cc)'
            %char(words{index(wi)})
            board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
        end
        
        % the row is unplayed I think it will simply be blank
    end
    
    c=1;
    result = result - current_row_points;
    r=r+B(stop_index,1)+1; % increment row location

    k=k+1; % increment row number
    start_index=stop_index+1;
    stop_index = min(nwords, stop_index+n);

end


%*************
% if isempty(wi)
%     return;
% end
if ~isempty(wi)
for www=wi+1:nwords

    if r<n+1
        if c+numel(words{index(www)})<n+2
        board(r,c:c+numel(words{index(www)})-1)=words{index(www)};
%                   imagesc(board);
%         pause;

        c=c+numel(words{index(www)})+1;
        else
            c=1;
            r=r+2;
        end
    
    else
        break;
    end
end




end


end

% should mark words that didn't work out to avoid retrying them
% hopeless marks words that won't work i positions 1 or 2 (1 across and 1
% down). word 1 is equivalent to word 2, and word 3 is equivalent to word 4
% however, words 1 and 2 are not equivalent to words 3 and 4
function [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C, alphaix)
sq = zeros(2);

% try excluding words with letter frequencies of 1
% ordering words by first and second letter would help

for ii = w2l, % w2l must be a row vector here

    %fprintf('ii = %i\n',ii);

    if ~isUnplayed(ii) || hopeless(ii),
        continue;
    end
    
    sq(1,:) = words{ii};
    isUnplayed(ii) = false;
    
    % fprintf('letter = %s\n',char(sq(1,:)));
    % char(words{w2l(alphaix(a1:a2))})
    % only iterate over reasonable letters
    a1=find(C(:,1) == sq(1,1),1); a2=find(C(:,1) == sq(1,1),1,'last');

    for jj = w2l(sort(alphaix(a1:a2))),
        %fprintf('        jj = %i\n',ii,jj);
        %assert(sq(1,1) == words{jj}(1));
        if isUnplayed(jj) && ~hopeless(jj), % eval order? also checks could be elim
            sq(2,1) = words{jj}(2);
            isUnplayed(jj) = false;
            
            b1=find(C(:,1) == sq(1,2),1); b2=find(C(:,1) == sq(1,2),1,'last');
            c1=find(C(:,1) == sq(2,1),1); c2=find(C(:,1) == sq(2,1),1,'last');
            
            for kk = w2l(sort(alphaix(b1:b2))),
                %assert(sq(1,2) == words{kk}(1));
                if isUnplayed(kk),
                    sq(2,2) = words{kk}(2);
                    isUnplayed(kk) = false;

                    for ll =  w2l(sort(alphaix(c1:c2))),
                         if isUnplayed(ll) && all(sq(2,:) == words{ll}),
                            isUnplayed(ll) = false;
                            
                            %fprintf('1 %s\n2 %s\n3 %s\n4 %s\n\n',char(words{ii}),char(words{jj}),char(words{kk}),char(words{ll}));
                            %disp(char(sq))
                            
                            return; % press completed!
                         end
                    end
                    isUnplayed(kk) = true;
                end
            end
            isUnplayed(jj) = true;
        end
    end
    isUnplayed(ii) = true;
    % should mark words that didn't work out to avoid retrying them
    hopeless(ii) = true; % hopeless in positions 1 or 2
    %fprintf('%s (%i) is hopeless\n',char(words{ii}),ii);
end
sq=zeros(2); % no result

end


function [board, result] = solver_columns(words, weights, n,  result,wordlengths)
% to do:
%  use dead space at the bottom of a column more effectively
%  use better value for wpl
%  consider penalty

board = zeros(n);

% for k = 1:length(words),
%     wordlengths(k)=length(words{k});
% end
%wordlengths = cellfun('length',words);

%wpl = weights./(wordlengths); % weight per letter, maybe should also consider blanks; +1 for blank at end of word acutally lowered result?

%[~,ix] = sort(wpl,'descend'); % so now s_wpl = wpl(ix) % possible sign tricks?

w = 1;
for col = 1:2:min(n,length(words)),
    r = 1;
%     while r + wordlengths(ix(w))-1 <= n
%         board(r:(r-1+wordlengths(ix(w))),col) = words{ix(w)};
%         result = result - weights(ix(w));
%         r = r + 1 + wordlengths(ix(w));
%         w = w + 1;
%     end
    
   while r + wordlengths(w)-1 <= n
        board(r:(r-1+wordlengths(w)),col) = words{w};
        result = result - weights(w);
        r = r + 1 + wordlengths(w);
        w = w + 1;
    end
    
end

end