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

WordList 04

by Robert Macrae

Status: Passed
Results: 7573039 (cyc: 5, node: 207)
CPU Time: 0.579
Score: 18932.7
Submitted at: 2011-04-13 19:15:36 UTC
Scored at: 2011-04-13 19:28:33 UTC

Current Rank: 1313th (Highest: 1st )

Comments
Robert Macrae
13 Apr 2011
Bugfixed 03
Please login or create a profile.
Code
function board = solver(words, weights, n, penalty)

% Crossword Solver

%{
WordList04 is as 03 but fixes bug (size of next word used to update Col)

WordList03 -- guess at which is best using threshold 3
3  results: 6733024.00  time: 0.23
4  results: 6736803.00  time: 0.13
5  results: 6838005.00  time: 0.20


WordList02 -- all rows
results: 6991690.00
time: 0.27

WordList01 -- alternate rows
results: 7494085.00
time: 0.11
%}

board = zeros(n);

[~,WordLen] = cellfun(@size,words);         % Length of each word
WordPriority = weights ./ (WordLen+1);      % Guess at priority
[WordPriority,Index] = sort(WordPriority,'descend');  % Find words in priority order
WordLen = WordLen(Index);
words = words(Index);                       % ... and sort words to match
Used = false(size(WordLen));

SpacesToHere = cumsum( WordLen+1 );         % Roughly spaces used
HalfFull = find( SpacesToHere> n*n/2, 1, 'first' );
Full = find( SpacesToHere> n*n, 1, 'first' );
ScoreGain = sum( weights(HalfFull:Full) );
ScoreLoss = penalty * n * 3 ;               % Crude guess at penalty?
if ScoreGain>ScoreLoss
    Step = 1;
else
    Step = 2;
end

Next = 1;
for Row = 1:Step:n     % Start by filling alternate rows
    Col = 1;
    while Col < n 
        if n-Col+1 >= WordLen(Next)             % Check!
            board(Row,Col:Col+WordLen(Next)-1) = words{Next};
            Used(Next) = true;                  % Not currently used
            Col = Col+WordLen(Next)+1;
            Next = Next+1;
        else
            Col = n+1;
            % For now ignore possibility of fitting in short words
            % at end
        end
    end
end    
 
end