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

icky cyc

by Albert

Status: Passed
Results: 7668905 (cyc: 21, node: 659)
CPU Time: 18.448
Score: 19183.9
Submitted at: 2011-04-15 00:00:54 UTC
Scored at: 2011-04-15 00:03:54 UTC

Current Rank: 1333rd (Highest: 49th )
Basis for: NBW endgame 2 (diff)
Basis for: NBW endgame 3 (diff)
Basis for: NBW endgame 4 (diff)

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

boardt = zeros(n,'uint8');
wordsgood = true(size(words));
wordslen = cellfun(@length,words);
score = weights./(wordslen+1);
[~,idx] = sort(score,'descend');
words = words(idx);
weights = weights(idx);
wordslen = wordslen(idx);

j=1;
w = find(wordsgood,1);
word = words{w};
wordsgood(w) = false;
wordlen = wordslen(w);
while wordlen < n-2 && any((wordslen < n-wordlen) & wordsgood)
    shortw = find(wordslen < n-wordlen & wordsgood,1);
    word = [word,0,words{shortw}];
    wordlen = length(word);
    wordsgood(shortw) = false;
end
boardt(1:length(word),j) = word;

i = 1;
while i <= n
    lenaval = n-j+1;
    wfit = find(wordsgood & wordslen<=lenaval);
    for w = 1:length(wfit)
        if words{wfit(w)}(1)==boardt(i,j)
            boardt(i,j:wordslen(wfit(w))+j-1) = words{wfit(w)};
            wordsgood(wfit(w)) = false;
            break;
        end
    end
    if wordsgood(wfit(w)) == false
        i = i+2;
    else
        i = i+1;
    end
end

while j < n
    j = j+1;
    b02 = boardt(:,j-1:j)==0;
    temp = 2*b02(:,2) + b02(:,1);
    spaces = temp==0 | temp==3;
    % idx = find([diff(spaces)==0;0]);       % start of a space
    idx = find([0;diff((spaces==0)*2+(spaces==1))] == -1);
    for k=1:length(idx)
        lenspace = sum(cumprod(single(spaces(idx(k):end))));
        % lenspace = find(spaces(idx(k):end)==0,1)-1;
        matchstr = single(boardt(idx(k):idx(k)+lenspace-1,j));

        wfit = find(wordsgood & wordslen==lenspace);
        for w = 1:length(wfit)
            if all(words{wfit(w)}.*matchstr' == (matchstr').^2)
                boardt(idx(k):idx(k)+lenspace-1,j) = words{wfit(w)};
                wordsgood(wfit(w)) = false;
                break;
            end
        end
    end
    
    lenaval = n-j+1;
    if lenaval<2
        break;
    end
    pos = find(boardt(:,j-1)==0);
    for k=1:length(pos)
        index = [max(pos(k)-1,1):min(pos(k)+1,n)];
        if all(boardt(index([1,end]),j+1)==0) && ...
                ((length(index)==2 && ismember(sum(boardt(index,j)==0),[0,2])) || ...
                (length(index)==3 && ~ismember(sum((boardt(index,j)==0).*[1,2,4]'),[2,3,6])))
            wfit = find(wordsgood & wordslen<=lenaval);
            for w = 1:length(wfit)
                if words{wfit(w)}(1)==boardt(pos(k),j) || boardt(pos(k),j)==0 
                    boardt(pos(k),j:wordslen(wfit(w))+j-1) = words{wfit(w)};
                    wordsgood(wfit(w)) = false;
                    break;
                end
            end
        end
    end
end


board = double(boardt);