2011-04-20 12:00:00 UTC

faster brute force plus

by Lucy

Status: Passed
Results: 8657557 (cyc: 18, node: 588)
CPU Time: 21.829
Score: 21652.4
Submitted at: 2011-04-14 02:16:05 UTC
Scored at: 2011-04-14 02:19:13 UTC

Current Rank: 1576th (Highest: 45th )

Code
```function board = solver(words, weights, n, penalty)

% Sample solver

% Copyright 2011 The MathWorks, Inc.

board = zeros(n);

% complexity check
% t = mtree('solver.m','-file');
% length(t.nodesize)
% mlint -cyc solver.m

Lengths = cellfun('length',words);
if std(Lengths) == 0 && Lengths(1) == n
% disp('vertical or dot')
[dummy,index] = sort(weights,'descend');
if penalty == 0
for i = 1:n
board(i,:) = words{index(i)};
end
else
for i = 1:floor(n/2)
board(i*2,:) = words{index(i)};
end
end
elseif std(weights) == 0
% disp('horizontal')
% try to fit several in a line (greedy)
[SortedL,index] = sort(Lengths);
SortedWords = words(index);
[board,SortedWords] = build_lines(SortedWords,SortedL);
board = fit_vertical(board,SortedWords);
else
% disp('other')
% try to fit several in a line (greedy)
[SortedW,index] = sort(weights,'descend');
SortedWords = words(index);
SortedL = Lengths(index);
[board,SortedWords] = build_lines(SortedWords,SortedL);
board = fit_vertical(board,SortedWords);
end

function [board,SortedWords,SortedL] = build_lines(SortedWords,SortedL)
board = zeros(n);
WordsLeft = numel(words);
k = 1;
while WordsLeft > 0 && k <= n
L = cumsum(SortedL + 1);
L(1) = L(1) - 1;
OnOneLine = find(L<=n);
WordsLeft = WordsLeft - numel(OnOneLine);
LineWords = [];
for j = 1:numel(OnOneLine)
LineWords = [LineWords, SortedWords{j} 0];
end

board(k,1:numel(LineWords)) = LineWords;

SortedWords = SortedWords(OnOneLine(end)+1:end);
SortedL = SortedL(OnOneLine(end)+1:end);

if penalty == 0
k = k + 1;
else
k = k + 2;
end
end
end

function board = fit_vertical(board,SortedWords)
for j = 1:20 %numel(SortedWords)
w = SortedWords{j}';
nw = length(w);
match_found = false;
k = 1;
while k <= n % check each column for a possible place
t = board(:,k);
incolumn = 1;
while incolumn+nw-1 <= n && ~match_found
candidate = t(incolumn:incolumn+nw-1);
match_index = candidate > 0;
if all(candidate(match_index) == w(match_index))
comp1 = false;
if incolumn == 1, comp1 = true;
elseif t(incolumn-1) == 0, comp1 = true;
end
comp2 = false;
if incolumn+nw-1 == n, comp2 = true;
elseif t(incolumn+nw) == 0, comp2 = true;
end
comp3 = false;
if k == 1, comp3 = true;
else
left_neighbours = board...
(incolumn:incolumn+nw-1,k-1);
if left_neighbours(~match_index) == 0
comp3 = true;
end
end
comp4 = false;
if k == n, comp4 = true;
else
right_neighbours = board...
(incolumn:incolumn+nw-1,k+1);
if right_neighbours(~match_index) == 0
comp4 = true;
end
end

if comp1 && comp2 && comp3 && comp4
match_found = true;
board(incolumn:incolumn+nw-1,k) = w;
end
end
incolumn = incolumn + 1;

end
k = k + 2;
end
end
end
end
```