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

The Last Monkey in 1000 nodes

by Fel

Status: Passed
Results: 7133725 (cyc: 14, node: 1000)
CPU Time: 4.638
Score: 17839.3
Submitted at: 2011-04-19 15:56:29 UTC
Scored at: 2011-04-19 16:37:51 UTC

Current Rank: 1095th (Highest: 724th )

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

% board1                  = solver_press(words, weights, n, penalty);
% [board2, result2]       = solver_columns(board, words, weights, n, sumw);

% if result2 < result1
%     board1  = board2;
%     result1 = result2;
%     idx1    = 2;
% else
%     idx1    = 1;
% end

% figure(2), imagesc(board1), pause(0.2)
% end

% function board = solver_press(words, weights, n, penalty)

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        = 0*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 = zeros(2);
    if ~isempty(w2l)
        C1 = C(:,1);
        [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C1, alphaix);
    end
    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);
isUnplayed2 = true(1,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;

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)};
            isUnplayed2(index(wi))    = false;
        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

wordlengths2    = wordlengths(isUnplayed);
weights2        = weights(isUnplayed);
board           = james_sub_solver(board,wordlengths2,weights2,isUnplayed2,words,n,penalty);

end

function [sq, isUnplayed, hopeless]    = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq)

ii_valid = w2l(isUnplayed(w2l) & ~hopeless(w2l));

for ii = ii_valid, % w2l must be a row vector here
    
    
    sq(1,:) = words{ii};
    isUnplayed(ii) = false;
    
    % only iterate over reasonable letters
    conda  = C1 == sq(1,1);
    a1     = find(conda,1);
    a2     = find(conda,1,'last');
    w21jj  = w2l(sort(alphaix(a1:a2)));
    
    condb  = C1 == sq(1,2);
    b1     = find(condb,1);
    b2     = find(condb,1,'last');
    
    w21kk  = w2l(sort(alphaix(b1:b2)));
    
    for jj = w21jj
        
        % eval order? also checks could be elim
        if isUnplayed(jj) && ~hopeless(jj)
            
            sq(2,1) = words{jj}(2);
            isUnplayed(jj) = false;
            
            condc = C1 == sq(2,1);
            
            c1=find(condc,1);
            c2=find(condc,1,'last');
            w21ll = w2l(sort(alphaix(c1:c2)));
            
            for kk = w21kk
                
                if isUnplayed(kk)
                    
                    sq(2,2)         = words{kk}(2);
                    isUnplayed(kk)  = false;
                    
                    for ll =  w21ll
                        
                        if isUnplayed(ll) && all(sq(2,:) == words{ll})
                            
                            isUnplayed(ll) = false;
                            
                            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
    
end

sq = zeros(2);


end


function board  = james_sub_solver(board,wordlengths,weights,isUnplayed,words,n,penalty)

wordlengths2 = wordlengths(isUnplayed);
weights2     = weights(isUnplayed);
words        = words(isUnplayed);
[~,idx_sort] = sort(wordlengths2 - weights2/max(weights2) );

tres_ceros   = board(3:end,1)==0 & board(2:end-1,2)==0 & board(1:end-2,1)==0;
r_ini        = find(tres_ceros) + 1;

xx = (board(n,1)==0)*(board(n-1,1)==0);
if  xx
    r_ini = [r_ini; n];
end

k = 1;

% cometer_penalty = penalty*wordlengths2(idx_sort(1)) < weights2(idx_sort(1))*sum(diff(r_ini)==1)/2;
cometer_penalty = penalty*wordlengths2(idx_sort(1)) < weights2(idx_sort(1))*sum(diff(r_ini)==1)/3;

for p = 1:length(r_ini)
    
    r = r_ini(p);
    
    cp = cometer_penalty && p>1 && r == r_ini(p-1)+1;
    
    
    if board(r-1,1)==0 || cp
        
        c = 1;
        while c < n && (board(r-1,c)==0 || cp)
            
            word_n = words{idx_sort(k)};
            c2     = c + numel(word_n);
            
            if c2-1 <= n && (board(r-1,c2-1)==0 || (cp && sum(board(r-1,c:c2-1)==0) < 2 ))
                board(r,c:c2-1) = word_n;
                k = k + 1;
            end
            c = c2 + 1;
        end
    end
end

end