2011-04-20 12:00:00 UTC

# A1_5

Status: Failed
Results: Failed (timeout)

Based on: A1_4 (diff)

Code
```function board = solver(words, weights, n, penalty)
% ------------------------------------------------------------
% SOLUTION A1_5 : horizontal and vertical filling + special case
% results: 6784922.00
% time: 60.45
% ------------------------------------------------------------
global dist_global; dist_global = repmat((1:n),n,1); dist_global = dist_global+dist_global';
% warning('off','Images:imshow:magnificationMustBeFitForDockedFigure');

L = get_lengths(words);                 % word lengths
wpl = weights'./L;                      % weights per letter
[wpl,idx] = sort(wpl);
words = words(idx);

% special case
if min(L)==n, board = just_rows(words,wpl,n,penalty); return; end

% W = transform_to_matrix(words,max(L));  % matrix of words

board = zeros(n);
hv = zeros(n); % to store whether at board(i,j) is hor(-1) or ver(+1) word
errors = 0;
i=length(words);

while i>=1 && errors<20

% horizontal placement
[board_h,placed_h,hv_h,b_h] = placeWord_h(board,words{i},n,hv);
% vertical placement
[board_v,placed_v,hv_v,b_v] = placeWord_h(board',words{i},n,-hv');
board_v = board_v';
hv_v = -hv_v';
if placed_h==0 && placed_v==0
errors = errors+1;
else
if b_h>b_v || ( b_h==b_v && rand()>0.5)
board = board_v;
hv = hv_v;
else
board = board_h;
hv = hv_h;
end
end
i = i-1;
%     subplot(1,1,1);imshow(board);title(num2str(errors));drawnow;
%     subplot(2,1,2);imshow(uint8(hv*128+128));title(num2str(errors));drawnow;
end

end

function [board,placed,hv,b] = placeWord_h(board,word,n,hv)
global dist_global;
% horizontal placement
lw = length(word);

% init
possible = true(n);
possible(:,n-lw+2:end) = 0;

% check for actual possible positions
for i=1:lw
possible(:,1:n-lw+1) = possible(:,1:n-lw+1) & ((board(:,i:end-lw+i)==0) | (board(:,i:end-lw+i)==word(i)));
end

% check for space before
possible(:,2:n-lw+1) = possible(:,2:n-lw+1) & (hv(:,1:n-lw)==0);
% check for space after
possible(:,1:n-lw) = possible(:,1:n-lw) & (hv(:,lw+1:end)==0);
% check for space above
for i=1:lw
possible(2:end,1:end-lw+1) = possible(2:end,1:end-lw+1) & (hv(1:end-1,i:end-lw+i)>=0) & (hv(1:end-1,i:end-lw+i)~=3);
end
% check for space below
for i=1:lw
possible(1:end-1,1:end-lw+1) = possible(1:end-1,1:end-lw+1) & (hv(2:end,i:end-lw+i)>=0) & (hv(2:end,i:end-lw+i)~=2);
end
% remove any other horizontal word
possible = possible & hv>=0;

% place to the most top left possible position
dist = dist_global;
dist(~possible) = 3*n;
m = min(min(dist));
[x,y] = find(dist == m);

if ~isempty(x) && m<3*n
placed = 1;
r = ceil(rand()*length(x));
board(x(r),y(r):y(r)+lw-1) = word;
hv(x(r),y(r)) = -2; % starting point of the word
hv(x(r),y(r)+1:y(r)+lw-2) = -1;
hv(x(r),y(r)+lw-1) = -3; % end point of the word
b = m;
return;
end

placed = 0;
b = 3*n;
end

function [board,placed] = placeWord(board,word,n)
lw = length(word);
dir = rand()>.5;
if dir, board = board'; end

placed=0;attempt=0;
while ~placed && attempt<=50
attempt=attempt+1;
% horizontal placement
x = ceil(rand()*n);
y = ceil(rand()*(n-lw+1));
% check validity
if empty(board,x,y-1,n) && empty(board,x,y+lw,n)
valid = 1;
%above
for i=y:y+lw-1, if ~empty(board,x-1,i,n), valid=0; end; end
%below
for i=y:y+lw-1, if ~empty(board,x+1,i,n), valid=0; end; end

if valid
curr = board(x,y:y+lw-1);
if sum((curr==word)+(curr==0)>0)==lw
board(x,y:y+lw-1) = word;
placed = 1;
end
end
end

end

if dir, board = board'; end

end

function bool = empty(board,x,y,n)
bool = 1;
if x<1, return; end
if y<1, return; end
if x>n, return; end
if y>n, return; end
if board(x,y)==0, return; end
bool = 0;
end

function W = transform_to_matrix(words,max_length)
% transform words cell array into matrix
W = zeros(length(words),max_length);
for i=1:length(words)
W(i,1:length(words{i})) = words{i};
end
end

function L = get_lengths(words)
% get lengths of the words
L = zeros(length(words),1);
for i=1:length(words)
L(i) = length(words{i});
end
end

function board = just_rows(words,weights,n,penalty)
% all words has the length of the board => place only horizontal lines
board = zeros(n);
lw = length(words);
A1 = ceil(n/2);
if A1>=lw
for i=1:lw
board(2*i-1,:) = words{i};
end
return;
end
B1 = sum(weights(1:A1));
B2 = sum(weights(1:min(n,lw)))-n*penalty;
if B2>B1
for i=1:min(n,lw), board(i,:) = words{i}; end
return;
else
for i=1:A1, board(2*i-1,:) = words{i}; end
return;
end
end
```