ILP Part 90 — Turkey – Random IT Utensils

This is the ninetieth 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 Turkey riddle. We have some shape which we need to cut in two halves which are exactly the same shapes.

We’ll solve just the last part of it: verifying if two parts are the same shapes. Everything else is rather straightforward and was explained on this blog many times. So let’s take the solution first:

     O
   O O
 O O       X X
 O O O     O X X
   O O O O O X
     X X O X X
       X X X X
         X X

O O

O O X X

O O O O X X

O O O O O X

X X O X X

X X X X

X X

We’re going to develop a generic solution capable of working with any shape and array of any size. The idea is: we’ll extract the part of Xs, shift it left and up by some delta calculated by the solver. We are going to do the same for all four possible rotations. Finally, we just add the goal that Os must match at least one of the shifted and rotated Xs. The code:

var O = new[]{
	new []{0,0,1,0,0,0,0,0},
	new []{0,1,1,0,0,0,0,0},
	new []{1,1,0,0,0,0,0,0},
	new []{1,1,1,0,0,1,0,0},
	new []{0,1,1,1,1,1,0,0},
	new []{0,0,0,0,1,0,0,0},
	new []{0,0,0,0,0,0,0,0},
	new []{0,0,0,0,0,0,0,0}
};

var X = new[]{
	new []{0,0,0,0,0,0,0,0},
	new []{0,0,0,0,0,0,0,0},
	new []{0,0,0,0,0,1,1,0},
	new []{0,0,0,0,0,0,1,1},
	new []{0,0,0,0,0,0,1,0},
	new []{0,0,1,1,0,1,1,0},
	new []{0,0,0,1,1,1,1,0},
	new []{0,0,0,0,1,1,0,0}
};

Func<int[][], IVariable[][]> toVars = a => a.Select(r => r.Select(c => solver.FromConstant(c)).ToArray()).ToArray();

var Ovars = toVars(O);
var Xvars = toVars(X);

Func<IVariable[][], IVariable[][]> rows = a => a.Select(r => r).ToArray();		
Func<IVariable[][], IVariable[][]> columns = a => Enumerable.Range(0, a[0].Length).Select(c => Enumerable.Range(0, a.Length).Select(r => a[r][c]).ToArray()).ToArray();

Func<IVariable[][], IVariable[][]> rotateCounterClockwise = a => columns(a).Reverse().ToArray();

Func<IVariable[], IVariable, IVariable[]> shiftLeft = (array, shift) => Enumerable.Range(0, array.Length).Select(i => solver.CompositeOperation<	ArrayGet>(new ArrayGetParameters
	{
		Index = solver.Operation<Addition>(shift, solver.FromConstant(i)).Operation<Remainder>(solver.FromConstant(array.Length))
	}, array).ToArray().First()).ToArray();
	
Func<IVariable[][], IVariable, IVariable[][]> shiftLeftMultiple = (array, shift) => rows(array).Select(r => shiftLeft(r, shift)).ToArray();
Func<IVariable[][], IVariable, IVariable[][]> shiftUpMultiple = (array, shift) => rotateCounterClockwise(rotateCounterClockwise(rotateCounterClockwise(shiftLeftMultiple(rotateCounterClockwise(array), shift))));

Func<IVariable[][], IVariable[][], IVariable> areEqual = (first, second) => solver.Operation<Conjunction>(Enumerable.Range(0, first.Length).SelectMany(r => Enumerable.Range(0, first[0].Length).Select(c => solver.Operation<IsEqual>(first[r][c], second[r][c]))).ToArray());

var width = O[0].Length;
var height = O.Length;

var hasSolution = solver.FromConstant(0);
var currentXvars = Xvars;

var movedXs = new List<IVariable[][]>();

for(int i=0;i<4;++i){
	var targetLeftShift = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessThan>(solver.FromConstant(width));
	var targetUpShift = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessThan>(solver.FromConstant(height));		
	var movedX = shiftUpMultiple(shiftLeftMultiple(currentXvars, targetLeftShift), targetUpShift);
	
	movedXs.Add(movedX);
	
	hasSolution = hasSolution.Operation<Disjunction>(areEqual(Ovars, movedX));
	
	currentXvars = rotateCounterClockwise(currentXvars);
}

hasSolution.Set<Equal>(solver.FromConstant(1));

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

Action<IVariable[][]> print = array => Console.WriteLine(string.Join("\n", rows(array).Select(r => string.Join(" ", r.Select(c => (int)solver.GetValue(c))))) + "\n");

print(Ovars);
foreach(var movedX in movedXs) print(movedX);

var O = new[]{

new []{0,0,1,0,0,0,0,0},

new []{0,1,1,0,0,0,0,0},

new []{1,1,0,0,0,0,0,0},

new []{1,1,1,0,0,1,0,0},

new []{0,1,1,1,1,1,0,0},

new []{0,0,0,0,1,0,0,0},

new []{0,0,0,0,0,0,0,0},

new []{0,0,0,0,0,0,0,0}

};

var X = new[]{

new []{0,0,0,0,0,0,0,0},

new []{0,0,0,0,0,1,1,0},

new []{0,0,0,0,0,0,1,1},

new []{0,0,0,0,0,0,1,0},

new []{0,0,1,1,0,1,1,0},

new []{0,0,0,1,1,1,1,0},

new []{0,0,0,0,1,1,0,0}

};

Func<int[][], IVariable[][]> toVars = a => a.Select(r => r.Select(c => solver.FromConstant(c)).ToArray()).ToArray();

var Ovars = toVars(O);

var Xvars = toVars(X);

Func<IVariable[][], IVariable[][]> rows = a => a.Select(r => r).ToArray();

Func<IVariable[][], IVariable[][]> columns = a => Enumerable.Range(0, a[0].Length).Select(c => Enumerable.Range(0, a.Length).Select(r => a[r][c]).ToArray()).ToArray();

Func<IVariable[][], IVariable[][]> rotateCounterClockwise = a => columns(a).Reverse().ToArray();

Func<IVariable[], IVariable, IVariable[]> shiftLeft = (array, shift) => Enumerable.Range(0, array.Length).Select(i => solver.CompositeOperation< ArrayGet>(new ArrayGetParameters

{

Index = solver.Operation<Addition>(shift, solver.FromConstant(i)).Operation<Remainder>(solver.FromConstant(array.Length))

}, array).ToArray().First()).ToArray();

Func<IVariable[][], IVariable, IVariable[][]> shiftLeftMultiple = (array, shift) => rows(array).Select(r => shiftLeft(r, shift)).ToArray();

Func<IVariable[][], IVariable, IVariable[][]> shiftUpMultiple = (array, shift) => rotateCounterClockwise(rotateCounterClockwise(rotateCounterClockwise(shiftLeftMultiple(rotateCounterClockwise(array), shift))));

Func<IVariable[][], IVariable[][], IVariable> areEqual = (first, second) => solver.Operation<Conjunction>(Enumerable.Range(0, first.Length).SelectMany(r => Enumerable.Range(0, first[0].Length).Select(c => solver.Operation<IsEqual>(first[r][c], second[r][c]))).ToArray());

var width = O[0].Length;

var height = O.Length;

var hasSolution = solver.FromConstant(0);

var currentXvars = Xvars;

var movedXs = new List<IVariable[][]>();

for(int i=0;i<4;++i){

var targetLeftShift = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessThan>(solver.FromConstant(width));

var targetUpShift = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessThan>(solver.FromConstant(height));

var movedX = shiftUpMultiple(shiftLeftMultiple(currentXvars, targetLeftShift), targetUpShift);

movedXs.Add(movedX);

hasSolution = hasSolution.Operation<Disjunction>(areEqual(Ovars, movedX));

currentXvars = rotateCounterClockwise(currentXvars);

}

hasSolution.Set<Equal>(solver.FromConstant(1));

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

solver.Solve();

Action<IVariable[][]> print = array => Console.WriteLine(string.Join("\n", rows(array).Select(r => string.Join(" ", r.Select(c => (int)solver.GetValue(c))))) + "\n");

print(Ovars);

foreach(var movedX in movedXs) print(movedX);

We start with encoding Os and Xs (lines 1-26). Next, we implement a couple of helper functions to manipulate the arrays. Two extractors for iterating via rows or columns (28, 29), and one function to rotate the array in a counter-clockwise direction (31).

Next, we implement the shifts. Shift left is rather straightforward, we just iterate over rows and move them to the left (lines 33-38). We could implement shift up the same way but we’ll use rotations instead: first rotate the array counter-clockwise, shift it left, and then rotate it counter-clockwise three more times (line 39).

We then implement a comparison function (line 41).

That’s it for helpers, now we implement the business logic. We iterate over all rotations (lines 51-61), shift left and up the Xs (lines 52,54), and compare the result with Os (58). Finally, we make sure that at least one of the transformations matched Os (line 63).

Output:

Tried aggregator 3 times.
MIP Presolve eliminated 20571 rows and 7689 columns.
MIP Presolve modified 64587 coefficients.
Aggregator did 30849 substitutions.
Reduced MIP has 39757 rows, 18574 columns, and 99670 nonzeros.
Reduced MIP has 18118 binaries, 456 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.39 sec. (182.55 ticks)
Probing fixed 960 vars, tightened 432 bounds.
Probing changed sense of 48 constraints.
Probing time = 4.28 sec. (1003.45 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 14491 rows and 8006 columns.
MIP Presolve modified 9006 coefficients.
Aggregator did 65 substitutions.
Reduced MIP has 25201 rows, 10503 columns, and 66670 nonzeros.
Reduced MIP has 10047 binaries, 456 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.30 sec. (128.42 ticks)
Probing fixed 2516 vars, tightened 401 bounds.
Probing changed sense of 8 constraints.
Probing time = 1.28 sec. (252.44 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 6841 rows and 3258 columns.
MIP Presolve modified 318 coefficients.
Reduced MIP has 18358 rows, 7245 columns, and 48338 nonzeros.
Reduced MIP has 6903 binaries, 342 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.13 sec. (54.56 ticks)
Probing time = 0.63 sec. (96.71 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 115 rows and 102 columns.
MIP Presolve modified 41 coefficients.
Reduced MIP has 18243 rows, 7143 columns, and 48042 nonzeros.
Reduced MIP has 6801 binaries, 342 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.11 sec. (46.81 ticks)
Probing time = 0.39 sec. (64.60 ticks)
Clique table members: 31024.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.61 sec. (273.60 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000  3502                      0.0000        8
*     0+    0                            0.0000        0.0000     1849    0.00%
      0     0        cutoff              0.0000        0.0000     1849    0.00%
Elapsed time = 12.76 sec. (3997.00 ticks, tree = 0.00 MB, solutions = 1)

GUB cover cuts applied:  86
Clique cuts applied:  511
Cover cuts applied:  205
Implied bound cuts applied:  557
Flow cuts applied:  9
Mixed integer rounding cuts applied:  139
Zero-half cuts applied:  369
Gomory fractional cuts applied:  1

Root node processing (before b&c):
  Real time             =   12.78 sec. (3998.88 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) =   12.78 sec. (3998.88 ticks)
0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0
1 1 0 0 0 0 0 0
1 1 1 0 0 1 0 0
0 1 1 1 1 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 0 0 0
1 0 1 1 0 0 0 1
1 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 1 1 1 1
1 0 0 1 0 0 1 1
1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0
0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 1
0 0 0 0 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0
1 1 0 0 0 0 0 0
1 1 1 0 0 1 0 0
0 1 1 1 1 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

100

101

102

103

104

105

106

107

108

109

Tried aggregator 3 times.

MIP Presolve eliminated 20571 rows and 7689 columns.

MIP Presolve modified 64587 coefficients.

Aggregator did 30849 substitutions.

Reduced MIP has 39757 rows, 18574 columns, and 99670 nonzeros.

Reduced MIP has 18118 binaries, 456 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.39 sec. (182.55 ticks)

Probing fixed 960 vars, tightened 432 bounds.

Probing changed sense of 48 constraints.

Probing time = 4.28 sec. (1003.45 ticks)

Tried aggregator 2 times.

MIP Presolve eliminated 14491 rows and 8006 columns.

MIP Presolve modified 9006 coefficients.

Aggregator did 65 substitutions.

Reduced MIP has 25201 rows, 10503 columns, and 66670 nonzeros.

Reduced MIP has 10047 binaries, 456 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.30 sec. (128.42 ticks)

Probing fixed 2516 vars, tightened 401 bounds.

Probing changed sense of 8 constraints.

Probing time = 1.28 sec. (252.44 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 6841 rows and 3258 columns.

MIP Presolve modified 318 coefficients.

Reduced MIP has 18358 rows, 7245 columns, and 48338 nonzeros.

Reduced MIP has 6903 binaries, 342 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.13 sec. (54.56 ticks)

Probing time = 0.63 sec. (96.71 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 115 rows and 102 columns.

MIP Presolve modified 41 coefficients.

Reduced MIP has 18243 rows, 7143 columns, and 48042 nonzeros.

Reduced MIP has 6801 binaries, 342 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.11 sec. (46.81 ticks)

Probing time = 0.39 sec. (64.60 ticks)

Clique table members: 31024.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.61 sec. (273.60 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 3502 0.0000 8

* 0+ 0 0.0000 0.0000 1849 0.00%

0 0 cutoff 0.0000 0.0000 1849 0.00%

Elapsed time = 12.76 sec. (3997.00 ticks, tree = 0.00 MB, solutions = 1)

GUB cover cuts applied: 86

Clique cuts applied: 511

Cover cuts applied: 205

Implied bound cuts applied: 557

Flow cuts applied: 9

Mixed integer rounding cuts applied: 139

Zero-half cuts applied: 369

Gomory fractional cuts applied: 1

Root node processing (before b&c):

Real time = 12.78 sec. (3998.88 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) = 12.78 sec. (3998.88 ticks)

0 0 1 0 0 0 0 0

0 1 1 0 0 0 0 0

1 1 0 0 0 0 0 0

1 1 1 0 0 1 0 0

0 1 1 1 1 1 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0

0 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 0 0 1 1 0 0 0

0 0 0 1 0 0 0 0

1 0 1 1 0 0 0 1

1 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 1 1 1 1 1

1 0 0 1 0 0 1 1

1 0 0 0 0 0 0 1

0 0 0 0 0 0 1 1

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0

0 0 0 0 0 1 1 0

0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 1

0 0 0 0 1 0 0 0

0 0 0 1 1 0 0 0

0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 1 1 0 0 0 0 0

1 1 0 0 0 0 0 0

1 1 1 0 0 1 0 0

0 1 1 1 1 1 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0

We can see that the first array (Os) matches the last one (Xs).