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

penalty box

by Michael Bindschadler

Status: Passed
Results: 8298041 (cyc: 12, node: 431)
CPU Time: 4.71
Score: 20747.5
Submitted at: 2011-04-15 06:05:58 UTC
Scored at: 2011-04-15 06:08:33 UTC

Current Rank: 1465th (Highest: 112th )
Basis for: penalty box 2 (diff)

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

if nargin<4
    %reinterpret inputs as follows
    testsuite = words;
    if nargin<2
        t = testsuite;
    else
        ind = weights;
        t = testsuite(ind);
    end
    words = t.words;
    weights = t.weights;
    n = t.n;
    penalty = t.penalty;
end

board = zeros(n);

penaltyThresh = 5;

% Determine word lengths and weight per letter
lengths = zeros(size(weights));
for i = 1:length(words)
    lengths(i) = length(words{i});
    wtPerLetter = weights./(lengths+1);
end

% get rid of any oversize words
mask = lengths>n;
lengths(mask) = [];
words(mask) = [];
wtPerLetter(mask) = [];
weights(mask) = [];

% Sort by weight per letter, descending
[sWtPerLetter,sInds] = sort(wtPerLetter,'descend');
sWeights = weights(sInds);
sWords = words(sInds);
sLengths = lengths(sInds);

% number of spaces available for words (rows only, with blank lines)
if penalty <= penaltyThresh
    minNumBlankRows = 0; %no problem if bogus words
else
    minNumBlankRows = floor(n/2);
end
extraBlankRows = 0; %thinking about this as a parameter
desiredExtraSpacesPerRow = 0; %because sliding might be good!
numWordRows = n-minNumBlankRows-extraBlankRows;
numSpaces = (n+1-desiredExtraSpacesPerRow)*numWordRows; % n+1 because I'm pretending even full-length words pretend to need a space after them

% Pick words from the top of the list until all spaces are exhausted
wordRowsCell = cell(numWordRows,1);
%wordRowsLengths = zeros(numWordRows,ceil(numWordsToFitInRows/numWordRows));
spacesLeftForMoreWords = repmat(n+1-desiredExtraSpacesPerRow,numWordRows,1);
nextSWordInd = 1;
nextWordRow = 1;
keepgoing = 1;
while keepgoing
    curSWordInd = nextSWordInd;
    curWordRow = nextWordRow;
    lengthCurWord = sLengths(curSWordInd);
    % Is there room on this row?
    if lengthCurWord+1 <= spacesLeftForMoreWords(curWordRow)
        % add it!
        indWithinRow = length(wordRowsCell{curWordRow})+1;
        wordRowsCell{curWordRow}{indWithinRow} = curSWordInd;
        spacesLeftForMoreWords(curWordRow) = spacesLeftForMoreWords(curWordRow)-(lengthCurWord+1);
        
        %wordRowsLengths;
        nextWordRow = curWordRow+1;
        nextSWordInd = curSWordInd+1;
        if nextWordRow>numWordRows
            nextWordRow = 1;
        end
        if nextSWordInd>length(sWords)
            keepgoing = false;
        end
    else 
        % running out of room, decide what to do next
        % For now, just stop
        keepgoing = false;
        %keyboard
    end
end
    


% assemble the board from the wordRowsCell representation
if penalty<= penaltyThresh
    wordRowBoardInds = 1:numWordRows;
else
    wordRowBoardInds = (1:numWordRows)*2-1;
end


for wordRowCellInd = 1:numWordRows
    %reset row and column indices
    r = wordRowBoardInds(wordRowCellInd);
    c = 1;
    for wordInRowInd = 1:length(wordRowsCell{wordRowCellInd})
        curSInd = wordRowsCell{wordRowCellInd}{wordInRowInd};
        curWord = sWords{curSInd};
        curWordLength = sLengths(curSInd);
        board(r,c:c+curWordLength-1) = curWord;
        c = c+curWordLength+1;
    end
end




end