Winner the cyclist (typ2)

Finish 2006-04-12 09:00:00 UTC

SHletmestop3

by Stijn Helsen

Status: Passed
Results: 85003
CPU Time: 66.4569
Score: 854.083
Submitted at: 2006-04-12 03:48:10 UTC
Scored at: 2006-04-12 06:24:56 UTC

Current Rank: 622nd
Based on: SHletmestop2_2cor (diff)
Basis for: SHletmestop3_2 (diff)

Comments
Stijn Helsen
12 Apr 2006
Help---let me stop
Please login or create a profile.
Code
function moves=solver(board,nMoves)
[rows, cols] = size(board);
mask=board;
moves = ones(nMoves,2);
moves(1,3)=0;
count=0;

% set move calculation parameters
next_move_count = 26;
if rows*cols >= 258
	choke_factor = .951;
	depth_factor = 2.8;
	rot = 1.4;
elseif (rows*cols) > 8.5*nMoves
	choke_factor = .94;
	depth_factor = 3.1;
	rot          = 1.490;
else
	choke_factor = 0.945;
	depth_factor = 2.97;
	rot          = 1.46;
end

% adjust block weights
%board = nthroot(board,rot);
board = board.^(1/rot);
new_board1=board;

depth = ceil(depth_factor*nMoves/10);
flip = floor(0.66*nMoves);
while count<nMoves
	% restore original colour values half-way through game
	%	if count==flip, board = nthroot(board,2/(1+rot)); end
	if count==flip, board = board.^((1+rot)/2); end

	% find highest value moves
	[cell_list,value_list,mask] = CalculateMoves(board,mask);
	if isempty(cell_list),
		[swapmv,board]=CheckForSwap(board,mask);
		if swapmv(1)
			count = count+1;
			moves(count,:) = swapmv;
			continue
		end
		break
	end

	% check future move values and re-weight current moves
	if count<nMoves-1
		[value_list,pos]=sort(value_list,2,'descend');
		cell_list=cell_list(pos);
		max_val=0;
		for k=1:min(numel(cell_list),next_move_count)
			new_board = ProcessMove(board,mask,cell_list(k));
			v=value_list(k);
			[new_cell_list,new_value_list] = CalculateMoves(new_board,mask);

			if (~isempty(new_cell_list))
				depth_ = max(min(depth,nMoves-count-3),1);
				if numel(new_value_list)<=depth_
					v = v + sum(new_value_list);
				else
					new_value_list=sort(new_value_list,2,'descend');
					v = v + sum(new_value_list(1:depth_));
				end
			end
			if k==1
				lim=choke_factor*v;
			elseif v < lim
				break;
			end
			if v>max_val
				max_val=v;
				max_cell=cell_list(k);
				new_board1(:)=new_board(:);
			end
		end
		board(:) = new_board1(:);
	else
		% take new most-valuable move
		[max_val,pos] = max(value_list); %#ok
		max_cell = cell_list(pos);
		board = ProcessMove(board,mask,max_cell);
	end
	count = count+1;
	moves(count,1) = mod(max_cell-1,rows)+1;
	moves(count,2) = ceil(max_cell/rows);
end
moves=moves(1:count,:);

function [cell_list,value_list,mask] = CalculateMoves(board,mask)

[rows,cols] = size(board);

% find first row from top that has non-zeros
first_row = find(any(board,2),1);

if (first_row == 1)
	% first row is non-zero so build column weighted match value
	if board(1)
		mask(1)=1;
	end
	k=1;
	for j=2:cols
		m = k;
		k = k + rows;
		if board(k)
			mask(k) = k;
			if (board(m) == board(k))
				% block to left matches current
				mask(m) = k;
			end
		end
	end
end

% Start at first row (or second if first is top and loop to bottom)
for i = max(2,first_row):rows
	k=i;
	if (board(k))
		% first block in row is non-zero
		mask(k) = k;
		m = k-1;
		if (board(m) == board(k))
			% block above matches current
			n = -1;
			while (n ~= m)
				n = m;
				m = mask(n);
				mask(n) = k;
			end
		end
	end

	% loop through columns and build column+row weighted match value
	for j=2:cols
		m = k;
		k = k + rows;   % move over one column
		if (board(k))
			mask(k) = k;
			if (board(m)==board(k))
				% block to left matches current
				mask(m) = k;
			end
			m = k - 1;
			if (board(m)==board(k))
				% block above matches current
				n = -1;
				while (n ~= m)
					n = m;
					m = mask(n);
					mask(n) = k;
				end
			end
		end
	end
end

cell_list = zeros(1,256);
group_count = 0;
group_count_matrix = zeros(rows, cols);

for i=rows:-1:first_row
	k = i + rows*(cols-1);
	for j=cols:-1:1
		if board(k)
			m = mask(k);
			if (m == k)
				group_count_matrix(k) = 1;
			else
				while group_count_matrix(m) == 0
					m = mask(m);
				end
				mask(k) = mask(m);
				group_block_count = group_count_matrix(m) + 1;
				group_count_matrix(m) = group_block_count;
				if (group_block_count == 2)
					group_count = group_count + 1;
					cell_list(1,group_count) = m;
				end
				mask(m)= k;
			end
		end
		k = k - rows;
	end
end

cell_list = cell_list(1:group_count);
value_list = zeros(1,group_count);

for k = 1:group_count
	m = cell_list(k);
	cell_list(k) = mask(m);
	value_list(k) = group_count_matrix(m) * board(m);
	mask(m) = m;
end

function B=ProcessMove(B,dj,y)
R=size(B,1);B(y)=0;
col=ceil(y/R);
minCol=col;maxCol=col;
while dj(y)~=y
	y=dj(y);
	B(y)=0;
	col=ceil(y/R);
	minCol=min(minCol, col);
	maxCol=max(maxCol, col);
end;
for i=minCol:maxCol,
	k=B(B(:,i)>0,i);
	B(:,i)=0;B(R-numel(k)+1:R,i)=k;
end

function [swapmv,outboard]=CheckForSwap(board,mask)
[rows cols]=size(board);
swapper=[-1 rows 1 -rows];
lentmp=rows*cols;
swapmv=zeros(1,3);
outboard=board;
maxswap=0;
list=find(board~=0)';
nList=numel(list);
for k=1:nList
	jj=list(k);
	for swapdir=1:4
		np=jj+swapper(swapdir);
		if np>0 && np<=lentmp && board(np)>0 && board(np)~=board(jj)
			tboard=DoSwap(board,jj,np);
			[s_ceil,s_value]=CalculateMoves(tboard,mask);
			if (~isempty(s_value))
				if (max(s_value)> maxswap)
					maxswap=max(s_value);
					idxq=jj;idxr=swapdir;idxs=np;
				end
			else
				for k2=max(1,k-20):min(nList,k+20)
					jj2=list(k2);
					for swapdir2=1:4
						np2=jj2+swapper(swapdir2);
						if np2>0 && np2<=lentmp && tboard(np2)>0 && tboard(np2)~=tboard(jj2)
							tboard2=DoSwap(tboard,jj2,np2);
							[s_ceil2,s_value2,s_mask2]=CalculateMoves(tboard2,mask);
							if (~isempty(s_value2) && max(s_value2)>maxswap)
								isok=false;
								[s_max,s_idx]=max(s_value2);
								Y=s_ceil2(s_idx);
								while (s_mask2(Y)~=Y)
									Y = s_mask2(Y);
									if (Y==np || Y==jj)
										isok=true;
									end
								end
								if (Y==np || Y==jj)
									isok=true;
								end
								if (isok)
									maxswap=max(s_value2);
									idxq=jj;idxr=swapdir;idxs=np;
								end
							end
						end
					end
				end
			end
		end
	end
end
if (maxswap>0)
	swapmv = [mod(idxq-1,rows)+1,ceil(idxq/rows),idxr];
	outboard=DoSwap(board,idxq,idxs);
end

function board = DoSwap(board,el1,el2)
board([el1,el2]) = board([el2,el1]);