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

Square Star Sky

by Victoria

Status: Passed
Results: 7232304 (cyc: 18, node: 571)
CPU Time: 9.359
Score: 18089.3
Submitted at: 2011-04-14 20:21:02 UTC
Scored at: 2011-04-14 20:23:17 UTC

Current Rank: 1191st (Highest: 1st )
Based on: High to Low (diff)
Basis for: Real Crosswords!!! (diff)
Basis for: Intermediate (diff)
Basis for: Crossword! (diff)
...and 1 other.

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

% Victoria's solver

PThresh = 0.15;
board = zeros(n);

QWords = numel(words);
WordsInUse = false(1,QWords);

L = zeros(1,QWords);
for i=1:QWords;
    L(i)=numel(words{i});
end

SpecificWeights = weights./(L + 1);
[~,IndWS] = sort(SpecificWeights,'descend');

SpecLCum = zeros(1,QWords);
SpecLCum(1) = L(IndWS(1)) + 1;
for i=2:QWords;
    SpecLCum(i) = SpecLCum(i-1) + L(IndWS(i)) + 1;
end

MaxQ = numel(find(SpecLCum <= n.*(n+1)));
GoodWeight = sum(weights(IndWS(1:MaxQ)));
BadGoodCoef = n.*penalty./GoodWeight;

P = BadGoodCoef > PThresh;
if P
    slots = ones(1,ceil(n/2));
    MaxQ = numel(find(SpecLCum <= (n+1).^2/2));
else
    slots = ones(1,n);
end

MaxQ = MaxQ - 3;

LoL = min(L(IndWS(1:MaxQ)));
HiL = max(L(IndWS(1:MaxQ)));
IndL = [];
for i = HiL:-1:LoL
    IndL = [IndL find(L(IndWS(1:MaxQ))==i)];
end
IndWS(1:MaxQ) = IndWS(IndL);

i = 1;
while min(slots) < n && i <= QWords

    Space = n - L(IndWS(i)) + 1 - slots;
    if any(~Space)
        SlotIndex = find(~Space,1);
    else
        if any(Space > 0)
            [~,SlotIndex] = max(Space);
        else
            SlotIndex = [];
        end
    end
    
    if ~isempty(SlotIndex)
        board(RowIndex(SlotIndex),slots(SlotIndex):slots(SlotIndex) + ...
            L(IndWS(i)) - 1) = words{IndWS(i)};
        slots(SlotIndex) = slots(SlotIndex) + L(IndWS(i)) + 1;
        
        WordsInUse(IndWS(i)) = true;
    end
    
    i=i+1;
end

if P
    for i = 1:QWords
        CurInd = IndWS(i);
        CurL = L(CurInd);
        if ~WordsInUse(CurInd) && (CurL/2 ~= round(CurL/2))
            [I,J] = find(board(1:n - CurL + 1,:) == words{CurInd}(1));
            if ~isempty(I)
                j = 1;
                while ~WordsInUse(CurInd) && (j <= numel(I))
                    if all(words{CurInd}(1:2:end) == ...
                            board(I(j):2:I(j) + CurL - 1,J(j))')
                        board(I(j):I(j) + CurL - 1,J(j)) = words{CurInd}';
                        
                        WordsInUse(IndWS(i)) = true;
                    end
                    j = j + 1;
                end
            end
        end
    end
end

    function Ind = RowIndex(SI)
        if P
            Ind = 2*SI - 1;
        else
            Ind = SI;
        end
    end

end