2011-04-20 12:00:00 UTC

# Five golden rings

Status: Passed
Results: 8302695 (cyc: 59, node: 1064)
CPU Time: 13.291
Score: 20806.8
Submitted at: 2011-04-14 15:28:03 UTC
Scored at: 2011-04-14 15:51:45 UTC

Current Rank: 1485th (Highest: 64th )
Based on: J.R.R. (diff)

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

% the cyclist solver

% Copyright 2011 the cyclist, Not Inc.

% Sort the words in order of descending weight
[weights indexToWeightSorting] = sort(weights,2,'descend');
words = words(indexToWeightSorting);

% Determine word lengths
numberWords = length(words);
lengthWords = nan(numberWords,1);
for ii=1:numberWords
lengthWords(ii) = length(words{ii});
end

% Preallocate the board with zeros
board = zeros(n,n);

% Fill in every other row, beginning with top row. Iterate the following algorithm:
% -- Find highest-weight word that will fit in the line
% -- Place it, with a blank next to i
% -- Repeat

for row = 1:ceil(n/2)
currentLength = 0;

while (currentLength <= n)
indexToWordsThatFit = find(lengthWords<=(n-currentLength));
weightOfWordsThatFit = weights(indexToWordsThatFit);
indexToMaxWeightFitWords = find(weightOfWordsThatFit==max(weightOfWordsThatFit));
lengthMaxWeightFitWords = lengthWords(indexToWordsThatFit(indexToMaxWeightFitWords));
[minLengthMaxWeightFitWords indexToMinLengthMaxWeightFitWords] = min(lengthMaxWeightFitWords);
indexToWordToUse = indexToWordsThatFit(indexToMaxWeightFitWords(indexToMinLengthMaxWeightFitWords));
if not(isempty(indexToWordToUse))
wordToUse = words{indexToWordToUse};
lengthWords(indexToWordToUse) = Inf;
lengthWordToUse = numel(wordToUse);
board(2*row-1,currentLength+1:currentLength+lengthWordToUse) = wordToUse;
currentLength = currentLength + lengthWordToUse + 1;
else
break
end
end

end

% After the above, there will be a ragged right column. Fill down this column with highest-weight words that fit.
blanksInRightmostColumn = find(board(:,n-1)==0&board(:,n)==0&[nan;board(1:n-1,n)]==0&[board(2:n,n);nan]==0);
numberBlanks = numel(blanksInRightmostColumn);
if numberBlanks>0
lengthToFit = 0;
anchor = blanksInRightmostColumn(1);
for nb = 1:numberBlanks-1
lengthToFit = lengthToFit+1;
if blanksInRightmostColumn(nb+1)==blanksInRightmostColumn(nb)+1
continue
else
indexToWordToUse = find(lengthWords<=lengthToFit,1,'first');
if not(isempty(indexToWordToUse))
wordToUse = words{indexToWordToUse};
lengthWords(indexToWordToUse) = Inf;
lengthWordToUse = numel(wordToUse);
board(anchor:anchor+lengthWordToUse-1,n) = wordToUse;
end
anchor = blanksInRightmostColumn(nb+1);
lengthToFit = 0;
end
end
end

% Find 3-letter words that we are going to sneak in.
word3Array = words(find(lengthWords==3))';
numberLength3Words = length(word3Array);
word3 = nan(3,numberLength3Words);
for jj=1:numberLength3Words
word3(:,jj)=word3Array{jj}';
end

% Anywhere we can fit, place a 3-letter word
for row = 1:n-2
for col = 1:n
if (row==1||board(row-1,col)==0) ...
&& (col==1||board(row+1,col-1)==0) && board(row+1,col)==0  && (col==n||board(row+1,col+1)==0) ...
&& (row==n-2||board(row+3,col)==0)
topVal = board(row,  col);
botVal = board(row+2,col);
indexToWordToUse = find(word3(1,:)==topVal&word3(3,:)==botVal,1,'first');
if any(indexToWordToUse)
board(row+1,col) = word3(2,indexToWordToUse);
word3(:,indexToWordToUse) = [];
end
end
end
end

% Find 5-letter words that we are going to sneak in.
word5Array = words(find(lengthWords==5))';
numberLength5Words = length(word5Array);
word5 = nan(5,numberLength5Words);
for jj=1:numberLength5Words
word5(:,jj)=word5Array{jj}';
end

% Anywhere we can fit, place a 5-letter word
for row = 1:n-4
for col = 1:n
if (row==1||board(row-1,col)==0) ...
&& (col==1||board(row+1,col-1)==0) && board(row+1,col)==0  && (col==n||board(row+1,col+1)==0) ...
&& (col==1||board(row+3,col-1)==0) && board(row+3,col)==0  && (col==n||board(row+3,col+1)==0) ...
&& (row==n-4||board(row+5,col)==0)
topVal = board(row,  col);
midVal = board(row+2,col);
botVal = board(row+4,col);
indexToWordToUse = find(word5(1,:)==topVal & word5(3,:)==midVal & word5(5,:)==botVal,1,'first');
if any(indexToWordToUse)
board([row+1 row+3],col) = word5([2 4],indexToWordToUse);
word5(:,indexToWordToUse) = [];
end
end
end
end

% Find 2-letter words that we are going to sneak in.
word2Array = words(find(lengthWords==2))';
numberLength2Words = length(word2Array);
word2 = nan(2,numberLength2Words);
for jj=1:numberLength2Words
word2(:,jj)=word2Array{jj}';
end

% Anywhere there is room, place a stalagmite down from a main row
for row = 1:2:n-3
indexToTwoSpots = find(board(row+2,:)==0);

for nt = indexToTwoSpots
if (nt==1||board(row+1,nt-1)==0) && (nt==n||board(row+1,nt+1)==0) && (row==1||board(row-1,nt)==0)
topTwoValue = board(row,nt);
indexToLengthTwoWordThatFits = find(word2(1,:)==topTwoValue,1,'first');
if any(indexToLengthTwoWordThatFits)
board(row:row+1,nt) = word2(:,indexToLengthTwoWordThatFits);
word2(:,indexToLengthTwoWordThatFits) = [];
end
end
end
end

% Anywhere there is room, place a stalactite up from a main row
for row = 3:2:n
indexToTwoSpots = find(board(row-2,:)==0);

for nt = indexToTwoSpots
if (nt==1||board(row-1,nt-1)==0) && (nt==n||board(row-1,nt+1)==0) && (row==n||board(row+1,nt)==0)
botTwoValue = board(row,nt);
indexToLengthTwoWordThatFits = find(word2(2,:)==botTwoValue,1,'first');
if any(indexToLengthTwoWordThatFits)
board(row-1:row,nt) = word2(:,indexToLengthTwoWordThatFits);
word2(:,indexToLengthTwoWordThatFits) = [];
end
end
end
end

end```