ILP Part 91 — Golf – Random IT Utensils

This is the ninetieth first part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve the Golf riddle. We are playing golf on a piece of paper. We have numbers indicating fields where we start putts. A number tells us how long the shot was. It cannot end on a blocked field (indicated as blue water). If the putt didn’t get to the final point then we carry on with a shot of a length decreased by one. The next shot cannot go backwards.

Let’s start with our board representation:

var board = new []{
	@"   D     3",
	@" 6XXX   4 ",
	@"  D X D   ",
	@"    4  XX ",
	@" D  XX X  ",
	@" 4  X 2X  ",
	@" X  X    D",
	@"4X     DXX",
	@" XX  D   X",
	@"  4   D  X"
};

var board = new []{

@" D 3",

@" 6XXX 4 ",

@" D X D ",

@" 4 XX ",

@" D XX X ",

@" 4 X 2X ",

@" X X D",

@"4X DXX",

@" XX D X",

@" 4 D X"

};

Letters D indicate destinations. Letters X indicate water. Digits shows starting points.

The solution is:

int width = board[0].Length;
int height = board.Length;

var wasUsed = board.SelectMany(r => r.Select(c => solver.FromConstant(0))).ToArray();
var isFinal = board.SelectMany(r => r.Select(c => solver.FromConstant(c == 'D' ? 1 : 0))).ToArray();
var isBlocked = board.SelectMany(r => r.Select(c => solver.FromConstant(c != ' ' && c != 'D' ? 1 : 0))).ToArray();

for(int row=0;row<board.Length;++row){
	for(int column=0;column<board[row].Length;++column){
		int segmentsCounts;
		if(int.TryParse(board[row][column].ToString(), out segmentsCounts)){
			IVariable oldRDiff = solver.FromConstant(0);
			IVariable oldCDiff = solver.FromConstant(0);
			IVariable oldIfContinue = solver.FromConstant(1);
			
			IVariable r = solver.FromConstant(row);
			IVariable c = solver.FromConstant(column);
			IVariable fieldIndex = null;
			
			
			while(segmentsCounts > 0){
				IVariable rDiff = solver.CreateAnonymous(Domain.AnyInteger)
					.Set<LessOrEqual>(solver.FromConstant(1))
					.Set<GreaterOrEqual>(solver.FromConstant(-1));
				IVariable cDiff = solver.CreateAnonymous(Domain.AnyInteger)
					.Set<LessOrEqual>(solver.FromConstant(1))
					.Set<GreaterOrEqual>(solver.FromConstant(-1));
				IVariable ifContinue = solver.CreateAnonymous(Domain.BinaryInteger).Set<LessOrEqual>(oldIfContinue);
					
				rDiff
					.Operation<AbsoluteValue>()
					.Operation<Addition>(
						cDiff
						.Operation<AbsoluteValue>()
					)
					.Set<Equal>(ifContinue);
				rDiff
					.Operation<Addition>(oldRDiff)
					.Operation<AbsoluteValue>()
					.Operation<Addition>(
						cDiff
						.Operation<Addition>(oldCDiff)
						.Operation<AbsoluteValue>()
					)
					.Set<GreaterOrEqual>(ifContinue);
					
				for(int step = 0; step < segmentsCounts; ++step){
					r = r.Operation<Addition>(rDiff);
					c = c.Operation<Addition>(cDiff);
					fieldIndex = r.Operation<Multiplication>(solver.FromConstant(width)).Operation<Addition>(c).Operation<AbsoluteValue>();
					
					r.Set<GreaterOrEqual>(solver.FromConstant(0)).Set<LessOrEqual>(solver.FromConstant(height - 1));
					c.Set<GreaterOrEqual>(solver.FromConstant(0)).Set<LessOrEqual>(solver.FromConstant(width - 1));
					
					solver.CompositeOperation<ArrayGet>(new ArrayGetParameters
					{
						Index = fieldIndex
					}, wasUsed).ToArray().First().Set<Equal>(ifContinue.Operation<BinaryNegation>());
					
					solver.CompositeOperation<ArraySet>(new ArraySetParameters
					{
						Index = fieldIndex,
						Value = solver.FromConstant(1)
					}, wasUsed);
				}
				
				solver.CompositeOperation<ArrayGet>(new ArrayGetParameters
				{
					Index = fieldIndex
				}, isBlocked).ToArray().First().Set<Equal>(solver.FromConstant(0));
				
				oldRDiff = rDiff;
				oldCDiff = cDiff;
				oldIfContinue = ifContinue;
				segmentsCounts --;
			}
			
			solver.CompositeOperation<ArrayGet>(new ArrayGetParameters
			{
				Index = fieldIndex
			}, isFinal).ToArray().First().Set<Equal>(solver.FromConstant(1));
		}
	}
}

solver.AddGoal("g", solver.FromConstant(0));
solver.Solve();

for(int row=0;row<board.Length;++row){
	for(int column=0;column<board[row].Length;++column){
		if(board[row][column] == ' '){
			Console.Write(solver.GetValue(wasUsed[row*width + column]) > 0.5 ? '*' : ' ');
		}else{
			Console.Write(board[row][column]);
		}
	}
	Console.WriteLine();
}

int width = board[0].Length;

int height = board.Length;

var wasUsed = board.SelectMany(r => r.Select(c => solver.FromConstant(0))).ToArray();

var isFinal = board.SelectMany(r => r.Select(c => solver.FromConstant(c == 'D' ? 1 : 0))).ToArray();

var isBlocked = board.SelectMany(r => r.Select(c => solver.FromConstant(c != ' ' && c != 'D' ? 1 : 0))).ToArray();

for(int row=0;row<board.Length;++row){

for(int column=0;column<board[row].Length;++column){

int segmentsCounts;

if(int.TryParse(board[row][column].ToString(), out segmentsCounts)){

IVariable oldRDiff = solver.FromConstant(0);

IVariable oldCDiff = solver.FromConstant(0);

IVariable oldIfContinue = solver.FromConstant(1);

IVariable r = solver.FromConstant(row);

IVariable c = solver.FromConstant(column);

IVariable fieldIndex = null;

while(segmentsCounts > 0){

IVariable rDiff = solver.CreateAnonymous(Domain.AnyInteger)

.Set<LessOrEqual>(solver.FromConstant(1))

.Set<GreaterOrEqual>(solver.FromConstant(-1));

IVariable cDiff = solver.CreateAnonymous(Domain.AnyInteger)

.Set<LessOrEqual>(solver.FromConstant(1))

.Set<GreaterOrEqual>(solver.FromConstant(-1));

IVariable ifContinue = solver.CreateAnonymous(Domain.BinaryInteger).Set<LessOrEqual>(oldIfContinue);

rDiff

.Operation<AbsoluteValue>()

.Operation<Addition>(

cDiff

.Operation<AbsoluteValue>()

)

.Set<Equal>(ifContinue);

rDiff

.Operation<Addition>(oldRDiff)

.Operation<AbsoluteValue>()

.Operation<Addition>(

cDiff

.Operation<Addition>(oldCDiff)

.Operation<AbsoluteValue>()

)

.Set<GreaterOrEqual>(ifContinue);

for(int step = 0; step < segmentsCounts; ++step){

r = r.Operation<Addition>(rDiff);

c = c.Operation<Addition>(cDiff);

fieldIndex = r.Operation<Multiplication>(solver.FromConstant(width)).Operation<Addition>(c).Operation<AbsoluteValue>();

r.Set<GreaterOrEqual>(solver.FromConstant(0)).Set<LessOrEqual>(solver.FromConstant(height - 1));

c.Set<GreaterOrEqual>(solver.FromConstant(0)).Set<LessOrEqual>(solver.FromConstant(width - 1));

solver.CompositeOperation<ArrayGet>(new ArrayGetParameters

{

Index = fieldIndex

}, wasUsed).ToArray().First().Set<Equal>(ifContinue.Operation<BinaryNegation>());

solver.CompositeOperation<ArraySet>(new ArraySetParameters

{

Index = fieldIndex,

Value = solver.FromConstant(1)

}, wasUsed);

}

solver.CompositeOperation<ArrayGet>(new ArrayGetParameters

{

Index = fieldIndex

}, isBlocked).ToArray().First().Set<Equal>(solver.FromConstant(0));

oldRDiff = rDiff;

oldCDiff = cDiff;

oldIfContinue = ifContinue;

segmentsCounts --;

}

solver.CompositeOperation<ArrayGet>(new ArrayGetParameters

{

Index = fieldIndex

}, isFinal).ToArray().First().Set<Equal>(solver.FromConstant(1));

}

solver.AddGoal("g", solver.FromConstant(0));

solver.Solve();

for(int row=0;row<board.Length;++row){

for(int column=0;column<board[row].Length;++column){

if(board[row][column] == ' '){

Console.Write(solver.GetValue(wasUsed[row*width + column]) > 0.5 ? '*' : ' ');

}else{

Console.Write(board[row][column]);

}

Console.WriteLine();

}

We will solve this by emulating shots.

First, we assign three state variables to each field (lines 4-6): whether a field was used in any shot, whether it is a final destination, and whether it is blocked (water>

Next, we iterate over the board and when we find a starting point (line 11) we do the magic.

We start with initializing the state. We’ll get a random direction for the putt and then mark all fields as used. So our initial direction (lines 12-13) is null. We’ll also keep a flag if we continue or not (line 14).

We also need to keep a track of where we are (lines 16-18).

We start making shots. As long as we can take a shot (line 21) we calculate new direction lines 22-27) and also make a chocie whether we move or not (line 28).

Next, we make sure that the shot goes either horizontal or vertical (30-36) and also that it doesn’t go backwards (37-45).

Now, we take fields one by one (lines 47-53) and mark them as used. We first get the existing flag of the field (line 55-58) and make sure it was set to “not used” previously. Next, we update it to “used” (lines 60-64).

The shot cannot land in the water so we make sure of that in lines 67-70.

Finally, after all shots we make sure that we ended in the final position (78-81).

Output:

Tried aggregator 5 times.
MIP Presolve eliminated 151426 rows and 87882 columns.
MIP Presolve modified 305898 coefficients.
Aggregator did 77667 substitutions.
Reduced MIP has 129299 rows, 63667 columns, and 328048 nonzeros.
Reduced MIP has 63487 binaries, 180 generals, 0 SOSs, and 0 indicators.
Presolve time = 3.80 sec. (1889.26 ticks)
Probing fixed 63487 vars, tightened 391 bounds.
Probing changed sense of 2 constraints.
Probing time = 58.80 sec. (11564.69 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 129299 rows and 63667 columns.
All rows and columns eliminated.
Presolve time = 0.08 sec. (54.74 ticks)

Root node processing (before b&c):
  Real time             =   63.89 sec. (14005.08 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =   63.89 sec. (14005.08 ticks)
***D     3
*6XXX***4*
* D*X*D***
****4**XX*
*D  XX*X**
*4**X*2X**
*X**X****D
4X*****DXX
 XX  D***X
  4***D  X

Tried aggregator 5 times.

MIP Presolve eliminated 151426 rows and 87882 columns.

MIP Presolve modified 305898 coefficients.

Aggregator did 77667 substitutions.

Reduced MIP has 129299 rows, 63667 columns, and 328048 nonzeros.

Reduced MIP has 63487 binaries, 180 generals, 0 SOSs, and 0 indicators.

Presolve time = 3.80 sec. (1889.26 ticks)

Probing fixed 63487 vars, tightened 391 bounds.

Probing changed sense of 2 constraints.

Probing time = 58.80 sec. (11564.69 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 129299 rows and 63667 columns.

All rows and columns eliminated.

Presolve time = 0.08 sec. (54.74 ticks)

Root node processing (before b&c):

Real time = 63.89 sec. (14005.08 ticks)

Parallel b&c, 8 threads:

Real time = 0.00 sec. (0.00 ticks)

Sync time (average) = 0.00 sec.

Wait time (average) = 0.00 sec.

------------

Total (root+branch&cut) = 63.89 sec. (14005.08 ticks)

***D 3

*6XXX***4*

* D*X*D***

****4**XX*

*D XX*X**

*4**X*2X**

*X**X****D

4X*****DXX

XX D***X

4***D X