broken_weights.cs

//
// Copyright 2012 Hakan Kjellerstrand
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Linq;
using Google.OrTools.ConstraintSolver;

public class BrokenWeights
{
    /**
     *
     * Broken weights problem.
     *
     * From http://www.mathlesstraveled.com/?p=701
     * """
     * Here's a fantastic problem I recently heard. Apparently it was first
     * posed by Claude Gaspard Bachet de Meziriac in a book of arithmetic problems
     * published in 1612, and can also be found in Heinrich Dorrie's 100
     * Great Problems of Elementary Mathematics.
     *
     *   A merchant had a forty pound measuring weight that broke
     *   into four pieces as the result of a fall. When the pieces were
     *   subsequently weighed, it was found that the weight of each piece
     *   was a whole number of pounds and that the four pieces could be
     *   used to weigh every integral weight between 1 and 40 pounds. What
     *   were the weights of the pieces?
     *
     * Note that since this was a 17th-century merchant, he of course used a
     * balance scale to weigh things. So, for example, he could use a 1-pound
     * weight and a 4-pound weight to weigh a 3-pound object, by placing the
     * 3-pound object and 1-pound weight on one side of the scale, and
     * the 4-pound weight on the other side.
     * """
     *
     * Also see http://www.hakank.org/or-tools/broken_weights.py
     *
     */
    private static void Solve(int m = 40, int n = 4)
    {
        Solver solver = new Solver("BrokenWeights");

        Console.WriteLine("Total weight (m): {0}", m);
        Console.WriteLine("Number of pieces (n): {0}", n);
        Console.WriteLine();

        //
        // Decision variables
        //

        IntVar[] weights = solver.MakeIntVarArray(n, 1, m, "weights");
        IntVar[,] x = new IntVar[m, n];
        // Note: in x_flat we insert the weights array before x
        IntVar[] x_flat = new IntVar[m * n + n];
        for (int j = 0; j < n; j++)
        {
            x_flat[j] = weights[j];
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                x[i, j] = solver.MakeIntVar(-1, 1, "x[" + i + "," + j + "]");
                x_flat[n + i * n + j] = x[i, j];
            }
        }

        //
        // Constraints
        //

        // symmetry breaking
        for (int j = 1; j < n; j++)
        {
            solver.Add(weights[j - 1] < weights[j]);
        }

        solver.Add(weights.Sum() == m);

        // Check that all weights from 1 to n (default 40) can be made.
        //
        // Since all weights can be on either side
        // of the side of the scale we allow either
        // -1, 0, or 1 of the weights, assuming that
        // -1 is the weights on the left and 1 is on the right.
        //
        for (int i = 0; i < m; i++)
        {
            solver.Add((from j in Enumerable.Range(0, n) select weights[j] * x[i, j]).ToArray().Sum() == i + 1);
        }

        //
        // The objective is to minimize the last weight.
        //
        OptimizeVar obj = weights[n - 1].Minimize(1);

        //
        // Search
        //
        DecisionBuilder db = solver.MakePhase(x_flat, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        solver.NewSearch(db, obj);

        while (solver.NextSolution())
        {
            Console.Write("weights:  ");
            for (int i = 0; i < n; i++)
            {
                Console.Write("{0,3} ", weights[i].Value());
            }
            Console.WriteLine();
            for (int i = 0; i < 10 + n * 4; i++)
            {
                Console.Write("-");
            }
            Console.WriteLine();
            for (int i = 0; i < m; i++)
            {
                Console.Write("weight {0,2}:", i + 1);
                for (int j = 0; j < n; j++)
                {
                    Console.Write("{0,3} ", x[i, j].Value());
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }

        Console.WriteLine("\nSolutions: {0}", solver.Solutions());
        Console.WriteLine("WallTime: {0}ms", solver.WallTime());
        Console.WriteLine("Failures: {0}", solver.Failures());
        Console.WriteLine("Branches: {0} ", solver.Branches());

        solver.EndSearch();
    }

    public static void Main(String[] args)
    {
        int m = 40;
        int n = 4;

        if (args.Length > 1)
        {
            m = Convert.ToInt32(args[1]);
        }

        if (args.Length > 2)
        {
            n = Convert.ToInt32(args[2]);
        }

        Solve(m, n);
    }
}