Cody

# Problem 1631. Criss-Cross: NHL - Optimize Matrix Size

Solution 258288

Submitted on 9 Jun 2013 by Richard Zapor
• Size: 420
• This is the leading solution.
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

### Test Suite

Test Status Code Input and Output
1   Pass
%% feval(@assignin,'caller','score',625);

2   Pass
%% dict={'avalanche' 'bluejackets' 'blackhawks' 'blues' 'bruins' 'canadiens' 'canucks' 'capitals' 'coyotes' 'devils' 'ducks' 'flames' 'flyers' 'hurricanes' 'islanders' 'jets' 'kings' 'lightning' 'mapleleafs' 'oilers' 'panthers' 'penguins' 'predators' 'rangers' 'redwings' 'sabres' 'senators' 'sharks' 'stars' 'wild'}; t1 = cputime; H=criss_cross(dict) fprintf('Elapsed Time %.2f\n',cputime-t1) fprintf('size of H %i %i\n',size(H)); score=prod(size(H)); % if valid % Perform Validation : words a=H; % Ned's gridWords = {}; for i = 1:2 a = a'; for j = 1:size(a,1) tk = regexp(a(j,:),'(\w\w+)','tokens'); gridWords = [gridWords tk]; end end dictFound = cell(length(gridWords),1); for i = 1:length(gridWords) dictFound{i} = gridWords{i}{1}; end dictFound = sort(dictFound); dictGiven = sort(dict); assert(isequal(dictGiven,dictFound),sprintf('Invalid/Missing words')) % Perform Validation: Connected Achar=H; m= (Achar-96); m(m>0)=Inf; % expand m and encircle with 0 [nr, nc]=size(m); m=[zeros(nr,1) m zeros(nr,1)]; m=[zeros(1,nc+2); m; zeros(1,nc+2)]; nr=size(m,1); off_vec=[-1 1 -nr nr]; % Initialize start location ptr=find(m==Inf,1,'first'); curval=1; m(ptr)=curval; while ~isempty(ptr) % adjacent expansion search sequence curval=curval+1; Moff_vec=repmat(ptr,1,4)+repmat(off_vec,size(ptr,1),1); m(Moff_vec)=min(curval*ones(size(Moff_vec)), m(Moff_vec)); ptr=find(m==curval); end invalid=any(m(:)==Inf); % Any unconnected from start point will be Inf assert(~invalid,sprintf('Not fully connected')) Hscore=numel(H); feval(@assignin,'caller','score',Hscore);

H = bluejackets`b````j``` ``````o```t`r````e``m ``````y```a`u`r``t``a ````c`o`hurricanes``p ````a`t```s`n`n`````l c```n`e`a```s`g`w```e a`blues`v`p``devils`l n`l`c```a`e```r`l`a`e a`a`k`islanders`d`b`a ducks```a`g``e````r`f i`k`````n`u``d`flyers e`h`l```c`i``w`l``s`` n`a`i```h`n``i`a`s``` s`w`g```e`s``n`m`e``` ``k`h````k```g`e`n``` ``s`t```oilers`sharks ````n````n```````t``` ````i````g`predators` ``panthers```````r``` ````g`````capitals``` Elapsed Time 47.88 size of H 20 21