using System;
using System.Collections.Generic;
using System.Linq;
using MilpManager.Abstraction;
using MilpManager.Implementation;
using MilpManager.Implementation.CompositeOperations;
using OrToolsMilpManager.Implementation;
namespace WolfGoatCabbage
{
class Program
{
static void Main()
{
var solver = new OrToolsMilpSolver(5);
// Weights, they need to be separate in order to hash state easily
int farmerWeight = 1<<3;
int wolfWeight = 1<<2;
int cabbageWeight = 1<<1;
int goatWeight = 1<<0;
// In order to track changes
var farmerVariables = new List< IVariable>();
var wolfVariables = new List< IVariable>();
var cabbageVariables = new List< IVariable>();
var goatVariables = new List< IVariable>();
// State in the previous turn
IVariable oldSide = null;
// At start farmer is on the left side
int farmerSide = 0;
var result = solver.CompositeOperation(CompositeOperationType.Loop, new LoopParameters
{
// We have at most 2^4 states
MaxIterations = 2*2*2*2,
Body = new Func< IVariable, IVariable[], IVariable>[]
{
(counter, all) =>
{
// We hash current state
IVariable newSum = solver.Operation(OperationType.Addition, all[0].Operation(OperationType.Multiplication, solver.FromConstant(farmerWeight)),
all[1].Operation(OperationType.Multiplication, solver.FromConstant(wolfWeight)),
all[2].Operation(OperationType.Multiplication, solver.FromConstant(cabbageWeight)),
all[3].Operation(OperationType.Multiplication, solver.FromConstant(goatWeight)));
// We sum variables in order to know how many palyers are on the right side
IVariable newSide = solver.Operation(OperationType.Addition, all);
// If this is another iteration
if (oldSide != null)
{
// Disable states
newSum.Set(CompositeConstraintType.NotFromSet, null,
// Cabbage and goat alone on the right side
solver.FromConstant(cabbageWeight + goatWeight),
// Wolf and goat alone on the right side
solver.FromConstant(wolfWeight + goatWeight),
// Farmer on the left side, all the others on the right side
solver.FromConstant(wolfWeight + cabbageWeight + goatWeight),
// Farmer on the right side, all the others on the left side
solver.FromConstant(farmerWeight),
// Wolf and goat alone on the left side
solver.FromConstant(farmerWeight + cabbageWeight),
// Goad and cabbage alone on the left side
solver.FromConstant(farmerWeight + wolfWeight)
);
// Who moved right
var onlyRightMoves = solver.Operation(OperationType.Conjunction,
all[0].Operation(OperationType.Subtraction, farmerVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),
all[1].Operation(OperationType.Subtraction, wolfVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),
all[2].Operation(OperationType.Subtraction, cabbageVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),
all[3].Operation(OperationType.Subtraction, goatVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0))
);
// Who moved left
var onlyLeftMoves = solver.Operation(OperationType.Conjunction,
all[0].Operation(OperationType.Subtraction, farmerVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),
all[1].Operation(OperationType.Subtraction, wolfVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),
all[2].Operation(OperationType.Subtraction, cabbageVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),
all[3].Operation(OperationType.Subtraction, goatVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0))
);
// At most two players can move in this turn
// We know that if someone moves, it is farmer with someone else
newSide.Operation(OperationType.Subtraction, oldSide).Operation(OperationType.AbsoluteValue).Set(ConstraintType.LessOrEqual, solver.FromConstant(2));
// We allow only coherent moves (all from left to right or all from right to left)
onlyRightMoves.Operation(OperationType.Disjunction, onlyLeftMoves).MakeTrue();
}
// Farmer changes side
farmerSide = 1 - farmerSide;
var newFarmer = all[0].Operation(OperationType.BinaryNegation);
farmerSide = 1 - farmerSide;
// Store existing state
oldSide = newSide;
farmerVariables.Add(all[0]);
wolfVariables.Add(all[1]);
cabbageVariables.Add(all[2]);
goatVariables.Add(all[3]);
// Return new variable
return newFarmer;
},
(counter, all) => solver.CreateAnonymous(Domain.BinaryInteger),
(counter, all) => solver.CreateAnonymous(Domain.BinaryInteger),
(counter, all) => solver.CreateAnonymous(Domain.BinaryInteger)
}
},
solver.FromConstant(0), // farmer on the left side
solver.FromConstant(0), // wolf on the left side
solver.FromConstant(0), // cabbage on the left side
solver.FromConstant(0) // goat on the left side
).ToArray();
var moves = result.Reverse().First();
oldSide.Set(ConstraintType.Equal, solver.FromConstant(4)); // everyone on the right side
solver.AddGoal("minimizeMoves", moves.MakeGoal(GoalType.Minimize));
solver.Solve();
for (int i = 0; i <= (int)moves.GetValue(); ++i)
{
Console.WriteLine(
$"Iteration: {i}\nFarmer: {Side(farmerVariables[i].GetValue())}, Wolf: {Side(wolfVariables[i].GetValue())}, Cabbage: {Side(cabbageVariables[i].GetValue())}, Goat: {Side(goatVariables[i].GetValue())}");
}
}
private static string Side(double value)
{
return (int)Math.Round(value) == 0 ? "Left" : "Right";
}
}
}