This is the forty forth 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 Pizza practice problem from Hash Code 2017 contest organized by Google.

Task description

Introduction

Did you know that at any given time, someone is cutting pizza somewhere around the world? The decision
about how to cut the pizza sometimes is easy, but sometimes it’s really hard: you want just the right amount
of tomatoes and mushrooms on each slice. If only there was a way to solve this problem using technology…

Problem description

Pizza
The pizza is represented as a rectangular, 2-dimensional grid of R rows and C columns. The cells within the
grid are referenced using a pair of 0-based coordinates [r, c] , denoting respectively the row and the
column of the cell.

Each cell of the pizza contains either:
– mushroom, represented in the input file as M ; or
– tomato, represented in the input file as T

Slice
A slice of pizza is a rectangular section of the pizza delimited by two rows and two columns, without holes.
The slices we want to cut out must contain at least L cells of each ingredient (that is, at least L cells of
mushroom and at least L cells of tomato) and at most H cells of any kind in total – surprising as it is, there is
such a thing as too much pizza in one slice.
The slices being cut out cannot overlap. The slices being cut do not need to cover the entire pizza.

Goal
The goal is to cut correct slices out of the pizza maximizing the total number of cells in all slices.
Input data set
The input data is provided as a data set file – a plain text file containing exclusively ASCII characters with
lines terminated with a single ‘\n’ character at the end of each line (UNIX- style line endings).

File format
The file consists of:
– one line containing the following natural numbers separated by single spaces:
— R (1 ≤ R ≤ 1000) is the number of rows,
— C (1 ≤ C ≤ 1000) is the number of columns,
— L (1 ≤ L ≤ 1000) is the minimum number of each ingredient cells in a slice,
— H (1 ≤ H ≤ 1000) is the maximum total number of cells of a slice
– R lines describing the rows of the pizza (one after another). Each of these lines contains C
characters describing the ingredients in the cells of the row (one cell after another). Each character
is either ‘M’ (for mushroom) or ‘T’ (for tomato).

Solution

For every pizza cell we create a non-negative variable representing number of assigned slice. There is at most $RC$ slices. We also simplify problem a little bit and assume that each slice must be a rectangle with at least two rows and two columns, however, code can be easily extended to handle other situations.

using System;
using System.Linq;
using CplexMilpManager.Implementation;
using MilpManager.Abstraction;
using MilpManager.Implementation;

namespace PizzaHashcode2017
{
    class Program
    {
        private static readonly string TestInput = @"3 5 1 6
TTTTT
TMMMT
TTTTT";

        static void Main()
        {
            var input = TestInput;
            var lines = input.Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries).ToArray();
            var numbers = lines.First().Split(' ').Select(int.Parse).ToArray();
            var board = lines.Skip(1).ToArray();

            int rows = numbers[0];
            int columns = numbers[1];
            int minimumIngredientsCount = numbers[2];
            int maximumSize = numbers[3];

            var solver = new CplexMilpSolver(10);

            // Create variables
            var cells =
                Enumerable.Range(0, rows)
                    .Select(
                        r =>
                            Enumerable.Range(0, columns)
                                .Select(
                                    c =>
                                        solver.Create($"{r}_{c}", Domain.PositiveOrZeroInteger)
                                            // Make sure that slice number is not too big
                                            .Set(ConstraintType.LessOrEqual, solver.FromConstant(rows*columns - 1)))
                                .ToArray())
                    .ToArray();

            // Make rectangles
            var places = Enumerable.Range(0, rows)
                .Select(
                    r =>
                        Enumerable.Range(0, columns)
                            .Select(
                                c => solver.FromConstant(0))
                            .ToArray())
                .ToArray();

            for (int row = 0; row < rows; ++row)
            {
                for (int column = 0; column < columns; ++column)
                {
                    var topLeft = new[] {Tuple.Create(1, 0), Tuple.Create(0, 1)};
                    var topRight = new[] {Tuple.Create(1, 0), Tuple.Create(0, -1)};
                    var bottomLeft = new[] {Tuple.Create(-1, 0), Tuple.Create(0, 1)};
                    var bottomRight = new[] {Tuple.Create(-1, 0), Tuple.Create(0, -1)};
                    var top = new[] {Tuple.Create(1, 0), Tuple.Create(0, 1), Tuple.Create(0, -1)};
                    var bottom = new[] {Tuple.Create(-1, 0), Tuple.Create(0, 1), Tuple.Create(0, -1)};
                    var left = new[] {Tuple.Create(1, 0), Tuple.Create(-1, 0), Tuple.Create(0, 1)};
                    var right = new[] {Tuple.Create(1, 0), Tuple.Create(-1, 0), Tuple.Create(0, -1)};
                    var middle = new[] {Tuple.Create(1, 0), Tuple.Create(-1, 0), Tuple.Create(0, -1), Tuple.Create(0, 1) };

                    // Notice - we do not handle slices with row or column shape

                    var diffs = new[]
                    {
                        topLeft, topRight, bottomLeft, bottomRight,
                        top, bottom, left, right,
                        middle
                    };
                    
                    var placeConstraints = diffs
                        .Where(d => d.All(m => row + m.Item1 >= 0 && column + m.Item2 >= 0 && row + m.Item1 < rows && column + m.Item2 < columns))
                        .Select(d => solver.Operation(OperationType.Conjunction, 
                            d.Select(m => cells[row][column].Operation(OperationType.IsEqual, cells[row + m.Item1][column + m.Item2])).ToArray()
                        ))
                        .ToArray();

                    // Only prepare constraints here, make them on later
                    places[row][column] = places[row][column].Operation(OperationType.Disjunction, placeConstraints);
                }
            }

            // Handle slices
            var goal = solver.FromConstant(0);

            for (int slice = 0; slice < rows*columns; ++slice)
            {
                var inThisGroup =
                    cells.Select(
                        r => r.Select(c => c.Operation(OperationType.IsEqual, solver.FromConstant(slice))).ToArray())
                        .ToArray();

                // Do not exceed maximum size
                var sliceSize = solver.Operation(OperationType.Addition, inThisGroup.SelectMany(r => r).ToArray());
                sliceSize.Set(ConstraintType.LessOrEqual, solver.FromConstant(maximumSize));
                var nonTrivialGroup = sliceSize.Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(2));

                for (int row = 0; row < rows; ++row)
                {
                    for (int column = 0; column < columns; ++column)
                    {
                        // If this is non-trivial group then place constraints must be set
                        solver.Operation(OperationType.Condition,
                            nonTrivialGroup.Operation(OperationType.Conjunction, inThisGroup[row][column]),
                            places[row][column],
                            solver.FromConstant(1)).MakeTrue();
                    }
                }


                // Have enough tomatoes and mushrooms
                var tomatoes = solver.FromConstant(0);
                var mushrooms = solver.FromConstant(0);

                for (int row = 0; row < rows; ++row)
                {
                    for (int column = 0; column < columns; ++column)
                    {
                        if (board[row][column] == 'T')
                        {
                            tomatoes = tomatoes.Operation(OperationType.Addition, inThisGroup[row][column]);
                        }
                        else
                        {
                            mushrooms = mushrooms.Operation(OperationType.Addition, inThisGroup[row][column]);
                        }
                    }
                }

                var tomatoesEnough = tomatoes.Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(minimumIngredientsCount));
                var mushroomsEnough = mushrooms.Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(minimumIngredientsCount));
                var ingredientsEnough = tomatoesEnough.Operation(OperationType.Conjunction, mushroomsEnough);

                goal = goal.Operation(OperationType.Addition, solver.Operation(OperationType.Condition, ingredientsEnough, sliceSize, solver.FromConstant(0)));
            }

            solver.AddGoal("GOAL", goal);

            solver.Solve();

            Console.WriteLine(goal.GetValue());
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

using System;

using System.Linq;

using CplexMilpManager.Implementation;

using MilpManager.Abstraction;

using MilpManager.Implementation;

namespace PizzaHashcode2017

{

class Program

{

private static readonly string TestInput = @"3 5 1 6

TTTTT

TMMMT

TTTTT";

static void Main()

{

var input = TestInput;

var lines = input.Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries).ToArray();

var numbers = lines.First().Split(' ').Select(int.Parse).ToArray();

var board = lines.Skip(1).ToArray();

int rows = numbers[0];

int columns = numbers[1];

int minimumIngredientsCount = numbers[2];

int maximumSize = numbers[3];

var solver = new CplexMilpSolver(10);

// Create variables

var cells =

Enumerable.Range(0, rows)

.Select(

r =>

Enumerable.Range(0, columns)

.Select(

c =>

solver.Create($"{r}_{c}", Domain.PositiveOrZeroInteger)

// Make sure that slice number is not too big

.Set(ConstraintType.LessOrEqual, solver.FromConstant(rows*columns - 1)))

.ToArray())

.ToArray();

// Make rectangles

var places = Enumerable.Range(0, rows)

.Select(

r =>

Enumerable.Range(0, columns)

.Select(

c => solver.FromConstant(0))

.ToArray())

.ToArray();

for (int row = 0; row < rows; ++row)

{

for (int column = 0; column < columns; ++column)

{

var topLeft = new[] {Tuple.Create(1, 0), Tuple.Create(0, 1)};

var topRight = new[] {Tuple.Create(1, 0), Tuple.Create(0, -1)};

var bottomLeft = new[] {Tuple.Create(-1, 0), Tuple.Create(0, 1)};

var bottomRight = new[] {Tuple.Create(-1, 0), Tuple.Create(0, -1)};

var top = new[] {Tuple.Create(1, 0), Tuple.Create(0, 1), Tuple.Create(0, -1)};

var bottom = new[] {Tuple.Create(-1, 0), Tuple.Create(0, 1), Tuple.Create(0, -1)};

var left = new[] {Tuple.Create(1, 0), Tuple.Create(-1, 0), Tuple.Create(0, 1)};

var right = new[] {Tuple.Create(1, 0), Tuple.Create(-1, 0), Tuple.Create(0, -1)};

var middle = new[] {Tuple.Create(1, 0), Tuple.Create(-1, 0), Tuple.Create(0, -1), Tuple.Create(0, 1) };

// Notice - we do not handle slices with row or column shape

var diffs = new[]

{

topLeft, topRight, bottomLeft, bottomRight,

top, bottom, left, right,

middle

};

var placeConstraints = diffs

.Where(d => d.All(m => row + m.Item1 >= 0 && column + m.Item2 >= 0 && row + m.Item1 < rows && column + m.Item2 < columns))

.Select(d => solver.Operation(OperationType.Conjunction,

d.Select(m => cells[row][column].Operation(OperationType.IsEqual, cells[row + m.Item1][column + m.Item2])).ToArray()

))

.ToArray();

// Only prepare constraints here, make them on later

places[row][column] = places[row][column].Operation(OperationType.Disjunction, placeConstraints);

}

// Handle slices

var goal = solver.FromConstant(0);

for (int slice = 0; slice < rows*columns; ++slice)

{

var inThisGroup =

cells.Select(

r => r.Select(c => c.Operation(OperationType.IsEqual, solver.FromConstant(slice))).ToArray())

.ToArray();

// Do not exceed maximum size

var sliceSize = solver.Operation(OperationType.Addition, inThisGroup.SelectMany(r => r).ToArray());

sliceSize.Set(ConstraintType.LessOrEqual, solver.FromConstant(maximumSize));

var nonTrivialGroup = sliceSize.Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(2));

for (int row = 0; row < rows; ++row)

{

for (int column = 0; column < columns; ++column)

{

// If this is non-trivial group then place constraints must be set

solver.Operation(OperationType.Condition,

nonTrivialGroup.Operation(OperationType.Conjunction, inThisGroup[row][column]),

places[row][column],

solver.FromConstant(1)).MakeTrue();

}

// Have enough tomatoes and mushrooms

var tomatoes = solver.FromConstant(0);

var mushrooms = solver.FromConstant(0);

for (int row = 0; row < rows; ++row)

{

for (int column = 0; column < columns; ++column)

{

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

{

tomatoes = tomatoes.Operation(OperationType.Addition, inThisGroup[row][column]);

}

else

{

mushrooms = mushrooms.Operation(OperationType.Addition, inThisGroup[row][column]);

}

var tomatoesEnough = tomatoes.Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(minimumIngredientsCount));

var mushroomsEnough = mushrooms.Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(minimumIngredientsCount));

var ingredientsEnough = tomatoesEnough.Operation(OperationType.Conjunction, mushroomsEnough);

goal = goal.Operation(OperationType.Addition, solver.Operation(OperationType.Condition, ingredientsEnough, sliceSize, solver.FromConstant(0)));

}

solver.AddGoal("GOAL", goal);

solver.Solve();

Console.WriteLine(goal.GetValue());

}