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
|
