tryagain01

function board = solver(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
isets_=find(lwords_(1:end-1)+1==lwords_(2:end));
sn_=numel(isets_);
snwords_=2*min(nwords_(isets_),nwords_(isets_+1));
slwords_=lwords_(isets_+1);

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
        %     for snword_=find(snwords_>1&slwords_<=c),
        %         m=min(r,snwords_(snword_));
        %         m2=ceil(m/2);
        %         C=weights_{isets_(snword_)}(m2) + weights_{isets_(snword_)+1}(m-m2) - penalty*(slwords_(snword_)-1) + E(rc-m*(slwords_(snword_)+1),Twn);
        %         if C>Cmax,
        %             Imax=[orientation,3,snword_,m];
        %             Cmax=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
    
%     imagesc(board);
%     for n1=1:size(borders,1),rectangle('position',borders(n1,[2,1,4,3])-[.5,.5,.5,.5]); end
%     drawnow;
%     pause
end


end

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