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

Shake it up !

by Amitabh Verma

Status: Passed
Results: 7037621 (cyc: 41, node: 3959)
CPU Time: 103.519
Score: 17684.3
Submitted at: 2011-04-16 00:53:40 UTC
Scored at: 2011-04-16 00:59:18 UTC

Current Rank: 967th (Highest: 1st )

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

% Nick & Alfanso solvers

[board1, score1] = solver_alfonso(words, weights, n, penalty);

[board2, score2] = solver_nick(words, weights, n, penalty);

if score1<score2
    board=board1;
else
    board=board2;
end

end


function [board, score] = solver_nick(words, weights, n, penalty)

nword = numel(words);
wlen = cellfun(@numel,words);
if (min(wlen) == n)
    maxlen = max(wlen);
    pwords = cellfun(@(a)[a 0 repmat(-1,1,maxlen-numel(a))],words,'UniformOutput',false);
    wmat = cat(1,pwords{:});
    wmat = wmat(:,1:end-1);
    m = cell(n);
    for i = 1:maxlen
        m{i,1} = double(sparse(bsxfun(@eq,wmat(:,i),wmat(:,1)')));
        m{3,i} = double(sparse(bsxfun(@eq,wmat(:,3),wmat(:,i)')));
    end;
    rwords = zeros(1,n);
    cwords = zeros(1,n);
    
    i = 1;
    pm = ones(nword);
    ppm = pm&(m{i,1}*m{3,i});
    while (i < n) && any(ppm(:))
        pm = ppm;
        i = i+2;
        if (i < n)
            ppm = pm&(m{i,1}*m{3,i});
        end;
    end;
    icross = i;
    board = zeros(n);
    open = true(1,nword);
    [i1,i3] = find(pm);
    i1 = i1(1);
    i3 = i3(1);
    open(i1) = false;
    open(i3) = false;
    board(1,1:wlen(i1)) = words{i1};
    board(3,1:wlen(i3)) = words{i3};
    rwords(1) = i1;
    rwords(3) = i3;
    for i = 1:2:icross
        iword = find((m{i,1}(i1,:).*m{3,i}(:,i3)')&open);
        if ~isempty(iword)
            iword = iword(1);
            cwords(i) = iword;
            board(1:wlen(iword),i) = words{iword}';
            open(iword) = false;
        end;
    end;
    
    % fill in remaining crosses, if possible.
    fcwords = cwords(cwords>0);
    height = max(wlen(fcwords));
    open = open';
    votes = zeros(n);
    for i = 5:height
        cols = find(board(i,:)~=0);
        matches = bsxfun(@eq,wmat(:,cols),board(i,cols))|(wmat(:,cols)<0);
        [~,bm] = max(open.*sum(matches,2));
        votes(i,cols) = 2*matches(bm,:)-1;
    end;
    bad = sum(votes)<0;
    badword = cwords(bad(1:icross));
    open(nonzeros(badword)) = true;
    board([2 4:end],bad) = 0;
    cwords(bad) = 0;
    i = 5;
    while (i <= height)
        cols = find(board(i,:)~=0);
        row = find(open&all(bsxfun(@eq,wmat(:,cols),board(i,cols))|(wmat(:,cols)<0),2),1);
        if ~isempty(row)
            open(row) = false;
            board(i,1:wlen(row)) = words{row};
            rwords(i) = row;
            i = i+2;
        else
            i = i+1;
        end;
    end;
    s0 = sum(weights(open));
    board0 = board;
   
    % now try full fill
    openr = rwords==0;
    openc = cwords==0;
    goodc = ~openc;
    votes = zeros(n);
    for c = find(openc)
        rows = find(board(:,c)~=0);
        matches = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
        [~,bm] = max(open.*sum(matches,2));
        votes(rows,c) = 2*matches(bm,:)-1;
    end;
    bad = sum(votes,2)<-sum(goodc);
    badwords = rwords(bad);
    open(nonzeros(badwords)) = true;
    board(openr,bad) = 0;
    for c = find(openc)
        rows = find(board(:,c)~=0);
        matches = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
        wi = find(open&all(matches,2),1);
        if ~isempty(wi)
            open(wi) = false;
            board(1:wlen(wi),c) = words{wi};
            cwords(c) = wi;
        end;
    end;

    openr = rwords==0;
    openc = cwords==0;
    goodr = ~openr;
    votes = zeros(n);
    for r = find(openr)
        cols = find(board(r,:)~=0);
        matches = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
        [~,bm] = max(open.*sum(matches,2));
        votes(r,cols) = 2*matches(bm,:)-1;
    end;
    bad = sum(votes,2)<-sum(goodr);
    badwords = cwords(bad);
    open(nonzeros(badwords)) = true;
    board(bad,openc) = 0;
    for r = find(openr)
        cols = find(board(r,:)~=0);
        matches = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
        wi = find(open&all(matches,2),1);
        if ~isempty(wi)
            open(wi) = false;
            board(r,1:wlen(wi)) = words{wi};
            rwords(r) = wi;
        end;
    end;
    
    board(board==0) = 1;
    s1 = sum(weights(open))+penalty*(sum(rwords==0)+sum(cwords==0));
    if (s1<s0)
        board0 = board;
        s0 = s1;
    end;
else
    board0 = zeros(n);
    s0 = sum(weights);
end;

board = zeros(n);
wcost = weights./(wlen+1);
[~,r] = sort(-wcost);
wlen = wlen(r);
words = words(r);
open = true(1,numel(words));
w = 0;
for i = [1:2:n,2:2:n]
    j = 0;
    k = find(open&(wlen<=n-j),1);
    while ~isempty(k)
        open(k) = false;
        word = words{k};
        board(i,j+1:j+numel(word)) = word;
        j = j+numel(word)+1;
        w = w+weights(r(k));
        k = find(open&(wlen<=n-j),1);
    end;
end;
board2 = zeros(n);
w2 = 0;
open = true(1,numel(words));
for i = 1:2:n
    j = 0;
    k = find(open&(wlen<=n-j),1);
    while ~isempty(k)
        open(k) = false;
        word = words{k};
        board2(i,j+1:j+numel(word)) = word;
        j = j+numel(word)+1;
        w2 = w2+weights(r(k));
        k = find(open&(wlen<=n-j),1);
    end;
end;
pboard = [board;zeros(1,n)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
if penalty*ntrans>w-w2
    board = board2;
    s = sum(weights)-w2;
else
    s = sum(weights)-w+penalty*ntrans;
end;

board2 = zeros(n);
w2 = 0;
open = true(1,numel(words));
filled = zeros(1,n);
filled(2:2:end) = 1;
brk = false;
while (filled(1)<n)
    wlen2 = wlen.*open;
    wlen2(~open) = 1;
    nlen = (accumarray(wlen2(:),ones(nword,1)));
    k = find(open&(wlen<=n-filled(1)-1)&(nlen(wlen)'>=n),1);
    if isempty(k)
        brk = true;
        break;
    end;
    targ = wlen(k);
    board2(1,filled(1)+1:filled(1)+targ) = words{k};
    open(k) = false;
    w2 = w2+weights(r(k));
    for i = 2:n
        k = find(open&(wlen==targ),1);
        board2(i,filled(i)+1:filled(i)+targ) = words{k};
        open(k) = false;
        w2 = w2+weights(r(k));
    end;
    filled = filled+targ+1;
end;
if (brk)
    % try two half-sets
    brk = false;
    while (filled(1)<n)
        wlen2 = wlen.*open;
        wlen2(~open) = 1;
        nlen = (accumarray(wlen2(:),ones(nword,1)));
        ldir = 2*(filled(1)>filled(2))-1;
        nlen(1) = 0;
        k = find(open&(wlen<=n-filled(1)-1)&(nlen(wlen)'>=ceil(n/2))&(nlen(wlen+ldir)'>=ceil(n/2)),1);
        if isempty(k)
            brk = true;
            break;
        end;
        targ = wlen(k);
        board2(1,filled(1)+1:filled(1)+targ) = words{k};
        open(k) = false;
        w2 = w2+weights(r(k));
        for i = 2:n
            idir = ldir*(mod(i,2)==0);
            k = find(open&(wlen==targ+idir),1);
            board2(i,filled(i)+1:filled(i)+targ+idir) = words{k};
            open(k) = false;
            w2 = w2+weights(r(k));
        end;
        filled = filled+targ+1;
    end;
end;
if (brk)
    % try two half-sets off by 2
    brk = false;
    while (filled(1)<n)
        wlen2 = wlen.*open;
        wlen2(~open) = 1;
        nlen = (accumarray(wlen2(:),ones(nword,1)));
        nlen(1) = 0;
        nlen(end+2) = 0;
        k0 = find(open&(wlen<=n-filled(1)-2)&(nlen(wlen)'>=ceil(n/2))&(nlen(wlen+2)'>=ceil(n/2)),1);
        if isempty(k0)
            brk = true;
            break;
        end;
        if filled(1)>=filled(2)
            targ = repmat(wlen(k0),1,n);
            targ(2:2:end) = wlen(k0)+2;
        else
            targ = repmat(wlen(k0)+2,1,n);
            targ(2:2:end) = wlen(k0);
        end;
        for i = 1:n
            k = find(open&(wlen==targ(i)),1);
            board2(i,filled(i)+1:filled(i)+targ(i)) = words{k};
            open(k) = false;
            w2 = w2+weights(r(k));
        end;
        filled = filled+targ+1;
    end;
end;
if (brk&&any(board2(:)))
    % finish filling board normally
    for i = 1:n
        k = find(open&(wlen<=n-filled(i)),1);
        while ~isempty(k)
            open(k) = false;
            word = words{k};
            board2(i,filled(i)+1:filled(i)+numel(word)) = word;
            filled(i) = filled(i)+numel(word)+1;
            w2 = w2+weights(r(k));
            k = find(open&(wlen<=n-filled(i)),1);
        end;
    end;
end;
pboard = [board2;zeros(1,n)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
if sum(weights)+penalty*ntrans-w2<s
    board = board2;
    s = sum(weights)+penalty*ntrans-w2;
end;

if (s0 < s)
    board = board0;
    s     = s0;
end;

score = s;

end
 
function [board,score] = solver_alfonso(words, weights, n, penalty)

board = zeros(n);
nwords=numel(words);
wordlength=zeros(1,nwords);
for nword=1:nwords, wordlength(nword)=numel(words{nword}); end
[wordlength,idxwords]=sort(wordlength);
idxpart=[0,find(diff(wordlength)),nwords];
nwords_=diff(idxpart);              % number of words for each wordlength
lwords_=wordlength(idxpart(2:end)); % list of wordlengths

n_=numel(lwords_);
words_=cell(1,n_);
weights_=words_;
weights0_=words_;
for nword_=1:n_,
    idx1=idxwords(idxpart(nword_)+1:idxpart(nword_+1));
    [w,idx2]=sort(weights(idx1),2,'descend');
    weights0_{nword_}=w;            % cumulative gains
    words_{nword_}=idx1(idx2);      % sorted words
    weights_{nword_}=cumsum(w);     % cumulative gains
end

borders=[1,1,n,n];

while size(borders,1)>0,
    border=borders(1,:);
    
    ntwn=sum(prod(border(:,3:4),2),1);
    Twn=zeros(1,ntwn);tn=0;twn=0;
    for nword_=find(nwords_>0),
        t=nwords_(nword_);
        Twn(tn+(1:t)*lwords_(nword_))=twn+weights0_{nword_};
        tn=tn+t*lwords_(nword_);
        if tn>=ntwn,break;end
    end
    Twn=cumsum(Twn);
    
    Cmax=-inf;
    for orientation=1:2,
        r=border(3);
        c=border(4);
        rc=r*c;
        for nword_=find(nwords_>0&lwords_<=c),
            m=min(r,nwords_(nword_));
            C=weights_{nword_}(m) - penalty*lwords_(nword_) + E(rc-min(r,m+1)*(lwords_(nword_)+1),Twn);
            if C(1)>0&&sum(C)>Cmax,
                Imax=[orientation,1,nword_,m];
                Cmax=sum(C);
            end
            m=min(ceil(r/2),nwords_(nword_));
            C=weights_{nword_}(m) + E(rc-min(r,2*m)*(lwords_(nword_)+1),Twn);
            if C(1)>0&&sum(C)>Cmax,
                Imax=[orientation,2,nword_,m];
                Cmax=sum(C);
            end
        end

        border=border([2,1,4,3]);
    end
    
    if Cmax>0
    
        if Imax(1)==2, board=board'; borders=borders(:,[2,1,4,3]); end
        border=borders(1,:);
        switch(Imax(2))
            case 1
                nword_=Imax(3);
                m=Imax(4);
                for nw=1:m,
                    board(border(1)+nw-1,border(2)+(0:lwords_(nword_)-1))=words{words_{nword_}(nw)};
                end
                words_{nword_}=words_{nword_}(m+1:end);
                weights0_{nword_}=weights0_{nword_}(m+1:end);
                weights_{nword_}=weights_{nword_}(m+1:end)-weights_{nword_}(m);
                nwords_(nword_)=nwords_(nword_)-m;
                nwords=nwords-m;
                if m<border(3)-1,
                    borders(1,:)=border+[0,lwords_(nword_)+1,m-border(3),-(lwords_(nword_)+1)];
                    borders=cat(1,border+[m+1,0,-(m+1),0],borders);
                else
                    borders(1,:)=border+[0,lwords_(nword_)+1,0,-(lwords_(nword_)+1)];
                end
            case 2
                nword_=Imax(3);
                m=Imax(4);
                for nw=1:m,
                    board(border(1)+2*nw-2,border(2)+(0:lwords_(nword_)-1))=words{words_{nword_}(nw)};
                end
                words_{nword_}=words_{nword_}(m+1:end);
                weights0_{nword_}=weights0_{nword_}(m+1:end);
                weights_{nword_}=weights_{nword_}(m+1:end)-weights_{nword_}(m);
                nwords_(nword_)=nwords_(nword_)-m;
                nwords=nwords-m;
                if 2*m-1<border(3)-1,
                    borders(1,:)=border+[0,lwords_(nword_)+1,2*m-1-border(3),-(lwords_(nword_)+1)];
                    borders=cat(1,border+[2*m,0,-2*m,0],borders);
                else
                    borders(1,:)=border+[0,lwords_(nword_)+1,0,-(lwords_(nword_)+1)];
                end
            case 3
        end
        if Imax(1)==2, board=board'; borders=borders(:,[2,1,4,3]); end
        
        borders(any(borders(:,3:4)<=0,2),:)=[];
    else
        borders(1,:)=[];
    end
    
end

[remainInDictionary, ~, bogus] = ...
        runSolution(board, n, words, weights);
score = scoresolution(remainInDictionary, bogus, penalty);
    
end

function c=E(S,Twn)
if S>0
    c=[0,Twn(ceil(S/2))];
else
    c=[0,0]; 
end
end


function [remainInDictionary, inPuzzle, bogus] = runSolution(board, boardSize, dictionary, weights)
%runSolution: parses the solution returned by the solver to determine the
% words it contains. Three structures are returned:
%
%  * remainInDictionary.words: words that remain in the dictionary
%  * remainInDictionary.points: points for each unused dictionary word
%  * remainInDictionary.hash: hash value used internally for searching
%
%  * inPuzzle.words: valid dictionary words used in the solution
%  * inPuzzle.points: points for each valid word
%
%  * bogus.words: words in the solution that aren't in the dictionary
%  * bogus.locations: linear indices of all letters in each word

% Initialize outputs
remainInDictionary = struct('words',{dictionary}, 'weights',{weights}, ...
    'hash', {cellfun(@applyHash, dictionary)});
inPuzzle = struct('words',{{}}, 'weights',{[]});
bogus = struct('words',{{}}, 'locations',{{}});

% Find words going across and down. dir = 1 for across, 2 for down.
for dir = 1:2
    for n = 1:boardSize
        % Get the current row / column to process
        if dir == 1
            curLine = board(n,:);
        else
            curLine = board(:,n).';
        end
        
        % Split current line of the board by locations of zeros
        zeroLoc = find(curLine == 0);
        idx1 = [1, zeroLoc+1];
        idx2 = [zeroLoc-1, boardSize];
        
        % Process the words on the current line
        for m = 1:numel(idx1)
            % Get the linear indices that make up the current word
            idxRange = idx1(m):idx2(m);
            idxConst = repmat(n, 1, numel(idxRange));
            if dir == 1
                linearWordIdx = sub2ind([boardSize, boardSize], idxConst, idxRange);
            else
                linearWordIdx = sub2ind([boardSize, boardSize], idxRange, idxConst);
            end
            
            % Current word to process
            curWord = board(linearWordIdx);
            
            if isscalar(curWord)
                % Get the indices of the adjacent squares - above,
                % below, left, and right.
                [r, c] = ind2sub([boardSize, boardSize], linearWordIdx);
                rows = [r-1, r+1, r,   r];
                cols = [c,   c,   c-1, c+1];
                outOfRange = (rows < 1) | (rows > boardSize) | ...
                    (cols < 1) | (cols > boardSize);
                rows(outOfRange) = [];
                cols(outOfRange) = [];
                adjacentIdx = sub2ind([boardSize, boardSize], rows, cols);
                
                % Treat a lone floating letter as invalid both across
                % and down. We assume that the dictionary never
                % contains any single letter words.
                if all(board(adjacentIdx) == 0)
                    bogus = addBogusWord(bogus, curWord, linearWordIdx);
                end
            elseif ~isempty(curWord) % Skip empty words - nothing to process
                % Determine if the word is in the dictionary
                dictionaryLoc = findWord(curWord, remainInDictionary.words, ...
                    remainInDictionary.hash);
                if isempty(dictionaryLoc)
                    % Bogus word - add to bogus word list
                    bogus = addBogusWord(bogus, curWord, linearWordIdx);
                else
                    % Legit word - move to inPuzzle list
                    [remainInDictionary, inPuzzle] = moveValidWord( ...
                        remainInDictionary, inPuzzle, dictionaryLoc);
                end
            end
        end
    end
end
end

function val = applyHash(word)
% applyHash: A rudimentary hashing function to speed up looking for words
% in the dictionary

n = min(5, ceil(numel(word)/2));
m1 = [1e10, 1e9, 1e8, 1e7, 1e6];
m2 = [1e4, 1e3, 1e2, 1e1, 1e0];

val = 1e12*sum(word) + sum(word(1:n).*m1(1:n)) + sum(word(end-n+1:end).*m2(1:n));
end

function idx = findWord(word, dictionary, dictionaryHash)
% findWord: Find word in dictionary using hash table. An empty matrix is
% return if the word does not exist in the dictionary

% Initialize output - assume word won't be found
idx = [];

% Find possible matches
possibleIdx = find(dictionaryHash == applyHash(word));

% Check all possible matches. If none is an actual match, we'll return empty
for n = 1:numel(possibleIdx)
    if isequal(dictionary{possibleIdx(n)},word)
        idx = possibleIdx(n);
        return;
    end
end

end

function bogus = addBogusWord(bogus, newWord, wordLoc)
%addBogusWord: add a word to the list of bogus words

bogus.words{end+1} = newWord;
bogus.locations{end+1} = wordLoc;
end

function [inDictionary, inPuzzle] = moveValidWord(inDictionary, inPuzzle, dictionaryLoc)
%moveValidWord: moves a word from the list of unused dictionary words to
% the list of words used in the puzzle solution

% Add word to list of words in the puzzle solution
inPuzzle.words{end+1} = inDictionary.words{dictionaryLoc};
inPuzzle.weights(end+1) = inDictionary.weights(dictionaryLoc);

% Remove word for list of unused dictionary words
inDictionary.words(dictionaryLoc) = [];
inDictionary.weights(dictionaryLoc) = [];
inDictionary.hash(dictionaryLoc) = [];
end

function score = scoresolution(remainInDictionary, bogus, penalty)
% SCORESOLUTION Calculates the score for the solution.

score = sum(remainInDictionary.weights) + penalty * numel(bogus.words);
end

% Amitabh Verma