crew.cpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2004
 *     Christian Schulte, 2004
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */


#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/set.hh>

using namespace Gecode;

namespace {
  typedef enum {
    Tom, David, Jeremy, Ron,
    Joe, Bill, Fred,
    Bob, Mario, Ed,
    Carol, Janet, Tracy,
    Marilyn, Carolyn, Cathy,
    Inez, Jean, Heather, Juliet
  } Employee;
  const int noOfEmployees = Juliet+1;

  struct Flight {
    int staff;     
    int stewards;  
    int hostesses; 
    int french;    
    int spanish;   
    int german;    
  };

  const char* employeeToName(Employee e);
  extern const int stewards[];
  extern const int noOfStewards;
  extern const int hostesses[];
  extern const int noOfHostesses;
  extern const int spanishSpeaking[];
  extern const int noOfSpanishSpeaking;
  extern const int frenchSpeaking[];
  extern const int noOfFrenchSpeaking;
  extern const int germanSpeaking[];
  extern const int noOfGermanSpeaking;
  extern const Flight requiredCrew[];
  extern const int noOfFlights;
}

class Crew : public Script {
public:
  SetVarArray flight;

  Crew(const Options& opt)
    : Script(opt), flight(*this,noOfFlights,IntSet::empty,0,noOfEmployees-1) {
    IntSet stewardsDS(stewards,noOfStewards);
    IntSet hostessesDS(hostesses,noOfHostesses);
    IntSet spanishDS(spanishSpeaking, noOfSpanishSpeaking);
    IntSet frenchDS(frenchSpeaking, noOfFrenchSpeaking);
    IntSet germanDS(germanSpeaking, noOfGermanSpeaking);

    for (int i=0; i<noOfFlights; i++) {
      // The flight has staff as required by the specification
      rel(*this, cardinality(flight[i]) == requiredCrew[i].staff);

      // Enough members of different categories are on board
      rel(*this, cardinality(flight[i] & stewardsDS) >=
          requiredCrew[i].stewards);
      rel(*this, cardinality(flight[i] & hostessesDS) >=
          requiredCrew[i].hostesses);
      rel(*this, cardinality(flight[i] & spanishDS) >=
          requiredCrew[i].spanish);
      rel(*this, cardinality(flight[i] & frenchDS) >=
          requiredCrew[i].french);
      rel(*this, cardinality(flight[i] & germanDS) >=
          requiredCrew[i].german);
    }

    // No crew member of flight i works on flights i+1 and i+2
    for (int i=0; i<noOfFlights-2; i++) {
      rel(*this, flight[i] || flight[i+1]);
      rel(*this, flight[i] || flight[i+2]);
    }
    rel(*this, flight[noOfFlights-2] || flight[noOfFlights-1]);

    branch(*this, flight, SET_VAR_NONE(), SET_VAL_MIN_INC());
  }

  virtual void
  print(std::ostream& os) const {
    for (int i=0; i<noOfFlights; i++) {
      os << "\tFlight " << i+1 << ":" << std::endl;
      os << "\t\tCrew\tStew.\tHost.\tFrench\tSpanish\tGerman"
         << std::endl << "\t";
      os << "\t" << requiredCrew[i].staff << "\t" << requiredCrew[i].stewards
         << "\t" << requiredCrew[i].hostesses << "\t"
         << requiredCrew[i].spanish
         << "\t" << requiredCrew[i].french << "\t" << requiredCrew[i].german
         << std::endl;

      os << "\t\tSchedule:" << std::endl << "\t\t";
      if (flight[i].assigned()) {
        for (SetVarGlbValues d(flight[i]);d();++d) {
          os << employeeToName(static_cast<Employee>(d.val())) << " ";
        }
      } else {
        os << "\tRequired: ";
        for (SetVarGlbValues d(flight[i]);d();++d) {
          os << employeeToName(static_cast<Employee>(d.val())) << " ";
        }
        os << std::endl << "\t\t\tPossible: ";
        for (SetVarUnknownValues d(flight[i]);d();++d) {
          os << employeeToName(static_cast<Employee>(d.val())) << " ";
        }
      }
      os << std::endl << std::endl;
    }
  }

  Crew(Crew& s)
    : Script(s) {
    flight.update(*this, s.flight);
  }
  virtual
  Space *copy(void) {
    return new Crew(*this);
  }

};

int
main(int argc, char* argv[]) {
  Options o("Crew");
  o.iterations(100);
  o.parse(argc,argv);
  Script::run<Crew,DFS,Options>(o);
  return 0;
}

namespace {

  const char*
  employeeToName(Employee e) {
    switch(e) {
    case Tom : return "Tom";
    case David : return "David";
    case Jeremy: return "Jeremy";
    case Ron: return "Ron";
    case Joe: return "Joe";
    case Bill: return "Bill";
    case Fred: return "Fred";
    case Bob: return "Bob";
    case Mario: return "Mario";
    case Ed: return "Ed";
    case Carol: return "Carol";
    case Janet: return "Janet";
    case Tracy: return "Tracy";
    case Marilyn: return "Marilyn";
    case Carolyn: return "Carolyn";
    case Cathy: return "Cathy";
    case Inez: return "Inez";
    case Jean: return "Jean";
    case Heather: return "Heather";
    case Juliet: return "Juliet";
    default: GECODE_NEVER; return "";
    }
  }

  // these have to be sorted!
  const int stewards[] =
    {Tom, David, Jeremy, Ron, Joe, Bill, Fred, Bob, Mario, Ed};
  const int noOfStewards = sizeof(stewards) / sizeof(int);
  const int hostesses[] =
    { Carol, Janet, Tracy, Marilyn, Carolyn, Cathy, Inez,
      Jean, Heather, Juliet };
  const int noOfHostesses = sizeof(hostesses) / sizeof(int);
  const int frenchSpeaking[] =
    { Bill, Inez, Jean, Juliet };
  const int noOfFrenchSpeaking = sizeof(frenchSpeaking) / sizeof(int);
  const int germanSpeaking[] =
    { Tom, Jeremy, Mario, Cathy, Juliet };
  const int noOfGermanSpeaking = sizeof(germanSpeaking) / sizeof(int);
  const int spanishSpeaking[] =
    { Joe, Bill, Fred, Mario, Marilyn, Inez, Heather };
  const int noOfSpanishSpeaking = sizeof(spanishSpeaking) / sizeof(int);

  const Flight requiredCrew[] =
    { {4,1,1,1,1,1},
      {5,1,1,1,1,1},
      {5,1,1,1,1,1},
      {6,2,2,1,1,1},
      {7,3,3,1,1,1},
      {4,1,1,1,1,1},
      {5,1,1,1,1,1},
      {6,1,1,1,1,1},
      {6,2,2,1,1,1},
      {7,3,3,1,1,1} };

  const int noOfFlights = sizeof(requiredCrew) / sizeof(Flight);
}

// STATISTICS: example-any