2011-04-20 12:00:00 UTC

# First try with special case

by F G

Status: Passed
Results: 8243590 (cyc: 23, node: 859)
CPU Time: 5.28
Score: 20622.8
Submitted at: 2011-04-14 15:52:05 UTC
Scored at: 2011-04-14 16:19:54 UTC

Current Rank: 1449th (Highest: 53rd )
Based on: First try with postprocessing (diff)

Code
```function board = solver(words, weights, n, penalty)
board = zeros(n);
nwords = length(words);
len = zeros(1, nwords); perf = len;
for i=1:nwords
len(i) = length(words{i});
perf(i) = weights(i)/len(i);
end
for i=2:n
w = find(len==i);
nlen(i) = length(w);
[dum,pos] = sort(weights(w));
wlen{i} = w(pos);
if nlen(i)>0
plen(i) = weights(wlen{i}(nlen(i)));
else
plen(i) = 0;
end
end
if penalty > 0
for r=1:2:n
left = n;
while left >= 2
possib = plen(2:left)./[3:left left];  % Prendre le plus gros ou le plus performant ?
if any(possib > 0)
sel = find(possib == max(possib)); sel=sel(1)+1;
board(r, n-left+(1:sel)) = words{wlen{sel}(nlen(sel))};
nlen(sel) = nlen(sel) - 1;
if nlen(sel)>0
plen(sel) = weights(wlen{sel}(nlen(sel)));
else
plen(sel) = 0;
end
left = left - (sel+1);
else
break;
end
end
end

for i=n:-1:1 % trop couteux de trouver le plus grand maxcontig globalement -> col par col
while 1
flag = board == 0;
flag = flag & [ones(1,n) ; flag(1:n-1,:)] & [flag(2:n,:) ; ones(1,n)] & [ones(n,1) flag(:,1:n-1)] & [flag(:,2:n) ones(n,1)];
[mx,pos] = maxcontig(flag(:,i));
if mx >= 2
possib = plen(2:mx)./[3:mx mx];  % Prendre le plus gros ou le plus performant ?
if any(possib > 0)
sel = find(possib == max(possib)); sel=sel(1)+1;
board(pos-1+(1:sel),i) = words{wlen{sel}(nlen(sel))};
nlen(sel) = nlen(sel) - 1;
if nlen(sel)>0
plen(sel) = weights(wlen{sel}(nlen(sel)));
else
plen(sel) = 0;
end
continue;
end
end
break;
end
end

else

for r=1:n
left = n;
while left >= 2
possib = plen(2:left)./[3:left left];  % Prendre le plus gros ou le plus performant ?
if any(possib > 0)
sel = find(possib == max(possib)); sel=sel(1)+1;
board(r, n-left+(1:sel)) = words{wlen{sel}(nlen(sel))};
nlen(sel) = nlen(sel) - 1;
if nlen(sel)>0
plen(sel) = weights(wlen{sel}(nlen(sel)));
else
plen(sel) = 0;
end
left = left - (sel+1);
else
break;
end
end
end

for i=n:-1:1 % trop couteux de trouver le plus grand maxcontig globalement -> col par col
while 1
flag = board == 0;
flag = flag & [ones(1,n) ; flag(1:n-1,:)] & [flag(2:n,:) ; ones(1,n)] & [ones(n,1) flag(:,1:n-1)] & [flag(:,2:n) ones(n,1)];
[mx,pos] = maxcontig(flag(:,i));
if mx >= 2
possib = plen(2:mx)./[2:mx];  % Prendre le plus gros ou le plus performant ?
if any(possib > 0)
sel = find(possib == max(possib)); sel=sel(1)+1;
board(pos-1+(1:sel),i) = words{wlen{sel}(nlen(sel))};
nlen(sel) = nlen(sel) - 1;
if nlen(sel)>0
plen(sel) = weights(wlen{sel}(nlen(sel)));
else
plen(sel) = 0;
end
continue;
end
end
break;
end
end

end
function [len, pos] = maxcontig(v)
% too slow
%       len = v(end)>0; pos = length(v);
%       curlen = len; curpos = pos-1;
%       while curpos > 0
%          if (curlen > 0) && all(v([curpos curpos+1])>0)
%             curlen = curlen+1;
%             if curlen > len
%                len = curlen;
%                pos = curpos;
%             end
%          else
%             curlen = v(curpos) > 0;
%          end
%          curpos = curpos - 1;
%       end
%       return;

if all(v==0)
len = 0; pos = []; return;
else
len = 1;
end
while 1
w = v(1:end-1) & v(2:end);
if all(w==0)
pos = find(v); pos=pos(1); return;
else
len = len+1;
v = w;
end
end
end

end```