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

WhyCatCantRead?

by Sergey Y.

Status: Passed
Results: 7931992 (cyc: 30, node: 905)
CPU Time: 81.268
Score: 19855.5
Submitted at: 2011-04-13 23:54:51 UTC
Scored at: 2011-04-13 23:59:05 UTC

Current Rank: 1367th (Highest: 10th )
Basis for: NBW WhyCatCantRead? (diff)

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

words_ori=words;
weights_ori=weights;

board = zeros(n);

le=zeros(1,length(words));

for t=1:length(words)
    le(t)=length(words{t});
end

[w, wind]=sort(weights./le,'descend');

words=words(wind);

sl_end=zeros(n,1);
do=1;
wordN=1;
ch=-1;
reached_end=0;
extra=0;
while do
    for t=1:ceil(n/2)
        if ch==-1
            if t*2-1<n+1
                if n-sl_end(t*2-1)>=length(words{wordN})
                    
                    board(t*2-1,sl_end(t*2-1)+1:sl_end(t*2-1)+length(words{wordN}))=words{wordN};
                    sl_end(t*2-1)=sl_end(t*2-1)+length(words{wordN})+1;
                    wordN=wordN+1;
                    if t*2-1>1
                        sl_end(t*2-1-1)=max(sl_end(t*2-1-1),sl_end(t*2-1)-1);
                    end
                    if t*2-1<n
                        sl_end(t*2-1+1)=max(sl_end(t*2-1+1),sl_end(t*2-1)-1);
                    end
                    
                else
                    reached_end=reached_end+1;
                    if n-sl_end(t*2-1)>2
                        extra=extra+1;
                    end
                    
                end
            end
        else
            if t*2<n+1
                
                if n-sl_end(t*2)>=length(words{wordN})
                    board(t*2,sl_end(t*2)+1:sl_end(t*2)+length(words{wordN}))=words{wordN};
                    sl_end(t*2)=sl_end(t*2)+length(words{wordN})+1;
                    wordN=wordN+1;
                    if t*2>1
                        sl_end(t*2-1)=max(sl_end(t*2-1),sl_end(t*2)-1);
                    end
                    if t*2<n
                        sl_end(t*2+1)=max(sl_end(t*2+1),sl_end(t*2)-1);
                    end
                    
                else
                    reached_end=reached_end+1;
                    if n-sl_end(t*2)>2
                        extra=extra+1;
                    end
                end
            end
        end
%         imagesc(board);
%         pause
        if reached_end>n-1
            do=0;
        end
    end
    ch=-ch;
end

board(board<0)=0;


board1=board;
wordN1=wordN;


%*****************************************************
words=words_ori;
weights=weights_ori;

board = zeros(n);

le=zeros(1,length(words));

for t=1:length(words)
    le(t)=length(words{t});
end

le3=find(le==3);
lene3=find(le~=3);


[w, wind]=sort(weights(lene3)./(le(lene3)),'descend');
wordsne3=words(lene3(wind));

words3=words(le3);

for r=1:length(wordsne3)
    wordsne3{r}=[wordsne3{r} 0];
end
a=[0 wordsne3{:}];

spind=find(a==0);

u0=1;
for t=1:ceil(n/2)
    u=find(spind>spind(u0) & spind<spind(u0)+n+2,1,'last');
        board(t*2-1,1:length(a(spind(u0)+1:spind(u)-1)))=a(spind(u0)+1:spind(u)-1);
    u0=u;    
end

wordN2=u;

for t=1:ceil(n/2)-1
    r=t*2;
    for c=1:n
        no1=board(r-1,c);
        no2=board(r+1,c);
        if board(r,c)>-1
        for ch=1:length(words3)
            if words3{ch}(1)==no1 && words3{ch}(3)==no2
                board(r,c)=words3{ch}(2);
                wordN2=wordN2+1;
                words3{ch}(1:3)=NaN;
                if r>2
                    board(r-2,c)=-1;
                end    
                if r<n-1    
                    board(r+2,c)=-1;                    
                end
                if c>2
                    board(r,c-1)=-1;
                end    
                if c<n-1    
                    board(r,c+1)=-1;                    
                end 
                break
            end
        end
        end        
    end
end

board(board==-1)=0;

if wordN1>wordN2
    board=board1;
end

end