| Code: | function [connections] = solver(Pins);
% function connections = Wiring(Pins);
% AUTHOR : Michael Peake
% DATE : 1st May 2008
% MATLAB CONTEST, Northern Spring 2008
%
%
% Input : Pins is an array.
% Non-zero values are pins
% Aim to join pins of equal non-zero value
%
% Output : connections is an nx4 array
% listing connections between adjacent pins
% : [r1 c1 r2 c2]
% : a connection with equal start and endpoints
% is a bridge, costing 25 normal connections
if nargin == 1,
Depth = 2;
end;
Output = zeros(0,4);
MaxVal = max(Pins(:));
Values = 0:MaxVal;
% Surround the array with a hard wall
PINS = zeros(2+size(Pins))+1+max(Pins(:));
PINS(2:end-1,2:end-1) = Pins;
for Depth = 1:3,
% Find which values appear in the grid
[StartHighCosts,KeyValues] = CountValue(Pins);
CONNECTIONS = PINS;
Output = zeros(0,4);
for Connection = 1:100,
SavedValue = 0;
% Form connected regions from the as-yet-unconnected pins
ZeroSubRegions = ConnectedRegions(CONNECTIONS == 0);
% For now, run them in order
% select from the ten most dominant values for the next connection
for vi = 1:Depth;%sum(StartHighCosts ~= 0 ),
ThisValue = KeyValues(vi);
AvailablePins = find(Pins == ThisValue);
% Join any subregions linked by these pins
SubRegions = ReconnectRegions(ZeroSubRegions,CONNECTIONS == ThisValue);
NRegions = max(SubRegions(:));
% pick the region with highest pin score
HC = zeros(1,NRegions);
for r = 1:NRegions
SubPins = PINS .* (SubRegions == r);
[HighCosts,KeyPins] = CountValue(SubPins);
HC(r) = HighCosts(1);
KP(r) = KeyPins(1);
end;
% What is the highest cost that can be connected
[HighestCost,ThisRegion] = max(HC);
% Keep the best as current-most-likely ?
if HighestCost > SavedValue,
SavedValue = HighestCost;
SavedRegion = SubRegions == ThisRegion;
PinValue = ThisValue;
end;% IF HIGHEST COST > SAVED
end;% FOR VALUE
% If you have run out of improvements, then stop
if SavedValue == 0,
break;
end; % IF ~ SAVEDVALUE
% connect the selected pins
[NewInstructions,NewConnections] = ...
MakeConnect(SavedRegion, PINS == PinValue);
Output = [Output;NewInstructions];
CONNECTIONS(find(NewConnections)) = PinValue;
a = find(PinValue == KeyValues);
KeyValues(a) = [];
end;% FOR CONNECTIONS
% Allow for the 'hard border'
connections{Depth} = Output-1;
score(Depth) = sum(sum(PINS.*~CONNECTIONS)) + size(connections{Depth},1);
end;
[a,b] = min(score);
connections = connections{b};
function Hist = IntHist(Array);
% SUBROUTINE IntHist
% Input: array of non-negative integers
% Output: Histogram, counting from 0 to MAX
Array = sort(Array(:));
Steps = [1;1+find(diff(Array))];
Hist = zeros(1,1+max(Array));
Hist(Array(Steps)+1) = diff([Steps;1+length(Array)]);
function Regions = ConnectedRegions(Array);
% SUBROUTINE : ConnectedRegions
% INPUT : 2-d Array
% Output : Non-zero entries numbered by connected region
Array = Array ~= 0;
Regions = Array;
NewRegions = Array .* reshape(1:length(Array(:)),size(Array));
Y = find(Array);
Started = 0;
while ~Started | any(NewRegions(:) ~= Regions(:)),
Started = 1;
Regions = NewRegions;
% Compare with four neighbours
A = max(Regions(2:end-1,2:end-1),Regions(1:end-2,2:end-1));
A = max(A,Regions(3:end,2:end-1));
A = max(A,Regions(2:end-1,3:end));
NewRegions(2:end-1,2:end-1) = max(A,Regions(2:end-1,1:end-2));
% don't spread into already-used regions
NewRegions = NewRegions .* Array;
NewRegions(Y) = NewRegions(NewRegions(Y));
NewRegions(Y) = NewRegions(NewRegions(Y));
end;
% Renumber regions
UsedNumbers = IntHist(Regions);
UsedNumbers(find(UsedNumbers)) = 0:sum(~~UsedNumbers)-1;
Regions = UsedNumbers(Regions+1);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [HighCosts,KeyValues] = CountValue(Pins);
% Subroutine CountValue
% Find which values appear in the grid
ValueCounts = IntHist(Pins);
% Ignore any solo pins
ValueCounts(ValueCounts == 1) = 0;
% The total amount saved by connecting pins for each value
Costs = ValueCounts .* [0:length(ValueCounts)-1];
% Pick out the value most likely to help
[HighCosts,KeyValues] = sort(-Costs);
HighCosts = -HighCosts;
KeyValues = KeyValues - 1;
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
function [InstructionList,ConnectedPins] = MakeConnect(EmptyPins,RequiredPins);
% SUBROUTINE MakeConnect
% Input: Array of available squares,
% and list of squares to connect
% : Assume available squares are edge-connected
% Output : List of moves to connect them
InstructionList = zeros(0,4);
RequiredPins = RequiredPins & EmptyPins;
PinList = find(RequiredPins);
NPins = length(PinList);
for p = 2:NPins
[Distances{p},From{p}] = GrowNeighbours(EmptyPins,PinList(p));
end;
% Crystallize the set
ThisPin = PinList(1);
ConnectedPins = EmptyPins*0;
ConnectedPins(ThisPin) = 1;
Unconnected = 2:NPins;
while length(Unconnected) > 0
ConnectedIndex = find(ConnectedPins);
Distance = zeros(1,length(Unconnected));
for q = 1:length(Unconnected)
p = Unconnected(q);
Distance(q) = min(Distances{p}(ConnectedIndex));
end;
[a,b] = min(Distance);
p = Unconnected(b);
[ConnectedPins,NewInstructions] = Append(...
ConnectedPins,PinList(p),Distances{p},From{p});
Unconnected(b) = [];
InstructionList = [InstructionList;NewInstructions];
end;
%%%%%%%%%%%
function [Distances,From] = GrowNeighbours(EmptyPins,PinPoint);
% Subroutine GrowNeighbours
% Input: EmptyPins, PinPoint
% Output: Distances,From
[R,C] = size(EmptyPins);
Distances = EmptyPins + 999;
Distances(PinPoint) = 0;
From = zeros(size(EmptyPins));
A = PinPoint;
for d = 1:100,
if ~length(A),break;end;
Possibles = [A+1; A-1; A+R; A-R];
PossibleFroms = ones(size(A))*[1 2 3 4];
Successful = find(Distances(Possibles)==1000);
NewNeighbours = Possibles(Successful);
Distances(NewNeighbours) = d;
From(NewNeighbours) = PossibleFroms(Successful);
% Remove duplicates from NewNeighbours;
A = sort(NewNeighbours);
if length(A)>1,
A = A([1; 1+find(diff(A))]);
end;
end;
%%%%%%%%%%%%%%%%
function [ConnectedPins,Instructions] = Append(ConnectedPins,NewPin,Distances,From);
% function Append
[R,C] = size(ConnectedPins);
CP = find(ConnectedPins);
[a,b] = min(Distances(CP));
Instructions = zeros(a,4);
ThisCell = CP(b);
Offset = [1 -1 R -R];
for d = a:-1:1,
Instructions(d,1:2) = Subscripts(R,ThisCell);
ThisCell = ThisCell - Offset(From(ThisCell));
Instructions(d,3:4) = Subscripts(R,ThisCell);
ConnectedPins(ThisCell) = 1;
end;
%%%%%%%%%%%%%%%
function xy = Subscripts(SizeArray,Index);
xy = zeros(1,2);
xy(1) = 1+rem(Index-1,SizeArray(1));
xy(2) = ceil(Index/SizeArray(1));
return;
%%%%%%%%%%%%%%%%%
function Regions = ReconnectRegions(ZeroSubregions,Connectors);
% FUNCTION ReconnectRegions
Regions = ZeroSubregions;
R = size(ZeroSubregions,1);
Pins = find(Connectors);
Neighbours = [ZeroSubregions(Pins-1) ...
ZeroSubregions(Pins+1) ...
ZeroSubregions(Pins-R) ...
ZeroSubregions(Pins+R)];
% Pins are now part of the region
for n = 1:size(Neighbours,1),
Regions(Pins(n)) = max(Neighbours(n,:));
if ~Regions(Pins(n)),
Regions(Pins(n)) = max(Regions(:))+1;
end;
end;
% Ignore pins with a single neighbouring subregion
Neighbours(sum(Neighbours>0,2)<2,:) = [];
for n = 1:size(Neighbours,1),
a = Neighbours(n,:);
a = a(find(a));
for m = 1:length(a),
Regions(Regions==a(m)) = a(1);
end;
end;
% Renumber regions
UsedNumbers = IntHist(Regions);
UsedNumbers(find(UsedNumbers)) = 0:sum(~~UsedNumbers)-1;
Regions = UsedNumbers(Regions+1);
|