/*
 * A delivery robot with a charging detour, using open variable lists.
 *
 * Companion to the post "Planning with open variable lists in Gecode".
 * Written for Gecode 6.5.0.
 *
 * The robot moves between the shelf, the workbench, and the charger, which
 * are connected in a line. It must fetch a packet from the shelf and deliver
 * it to the workbench. Each move uses one unit of charge, and each charge
 * action at the charger adds one unit, up to a capacity of five.
 *
 * The legal steps are listed in a table of transitions. -model state
 * (default) keeps the location, charge, and packet status of each state in
 * open lists, and posts the table as an extensional constraint for each
 * action when its position is created. -model regular instead reads the
 * table as an automaton, and posts a regular constraint on the actions.
 * -branching min (default) tries the lowest action code first, and
 * -branching max the highest. -charge sets the initial charge, and -limit
 * the maximum number of actions.
 *
 * Copyright: Mikael Zayenz Lagerkvist, 2026.
 * Distributed under the MIT license, as is Gecode.
 */

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

#include <algorithm>
#include <vector>

using namespace Gecode;

namespace {

  enum Action {
    ToShelf, ToWorkbench, ToCharger, PickUp, Deliver, Charge
  };
  enum Location {
    Shelf, Workbench, Charger
  };
  enum Packet {
    OnShelf, Carried, Delivered
  };

  const int capacity = 5;

  const char* action_name[] = {
    "to-shelf", "to-workbench", "to-charger", "pick-up", "deliver", "charge"
  };

}

/// Options for the initial charge and the maximum plan length
class DeliveryOptions : public Options {
  Driver::UnsignedIntOption _charge;
  Driver::UnsignedIntOption _limit;
public:
  enum { MODEL_STATE, MODEL_REGULAR };
  enum { BRANCH_MIN, BRANCH_MAX };
  DeliveryOptions(void)
    : Options("Delivery"),
      _charge("charge","initial charge of the battery",1),
      _limit("limit","maximum number of actions",12) {
    add(_charge);
    add(_limit);
    model(MODEL_STATE);
    model(MODEL_STATE,"state","post transitions on explicit state lists");
    model(MODEL_REGULAR,"regular","use a regular constraint over all states");
    branching(BRANCH_MIN);
    branching(BRANCH_MIN,"min","try the lowest action code first");
    branching(BRANCH_MAX,"max","try the highest action code first");
    solutions(0);
  }
  int charge(void) const {
    return std::min(static_cast<int>(_charge.value()),capacity);
  }
  int limit(void) const {
    return static_cast<int>(_limit.value());
  }
};

// The legal steps, as tuples (a, at0, ch0, pk0, at1, ch1, pk1): action a
// leads from state (at0,ch0,pk0) to state (at1,ch1,pk1).
static TupleSet
robot_steps(void) {
  TupleSet t(7);
  // Moving to a neighbouring location uses one unit of charge. A move
  // action has the same code as its destination.
  for (int pk=OnShelf; pk<=Carried; pk++)
    for (int ch=1; ch<=capacity; ch++)
      for (int at=Shelf; at<Charger; at++) {
        t.add({at+1, at, ch, pk, at+1, ch-1, pk});
        t.add({at, at+1, ch, pk, at, ch-1, pk});
      }
  // Charging adds one unit, up to the capacity.
  for (int pk=OnShelf; pk<=Carried; pk++)
    for (int ch=0; ch<capacity; ch++)
      t.add({Charge, Charger, ch, pk, Charger, ch+1, pk});
  // The packet is picked up at the shelf and delivered at the workbench.
  for (int ch=0; ch<=capacity; ch++) {
    t.add({PickUp, Shelf, ch, OnShelf, Shelf, ch, Carried});
    t.add({Deliver, Workbench, ch, Carried, Workbench, ch, Delivered});
  }
  t.finalize();
  return t;
}

static void
post_step(Home home, IntVar a,
          IntVar at0, IntVar ch0, IntVar pk0,
          IntVar at1, IntVar ch1, IntVar pk1) {
  static const TupleSet steps = robot_steps();
  extensional(home, IntVarArgs({a, at0, ch0, pk0, at1, ch1, pk1}), steps);
}

// The plan may end at state i only when the packet has been delivered,
// and once it has been delivered, the plan ends.
static void
post_goal(Home home, IntVar pk, IntVar length, int i) {
  BoolVar done = expr(home, pk == Delivered);
  rel(home, (length == i) >> done);
  rel(home, done >> (length <= i));
}

/// The actions, search, and output shared by both models
class Delivery : public IntMinimizeScript {
protected:
  OpenIntVarList actions;
public:
  Delivery(const DeliveryOptions& opt)
    : IntMinimizeScript(opt),
      actions(*this, IntSet(ToShelf, Charge), opt.limit()) {}
  Delivery(const DeliveryOptions& opt, OpenIntVarList::Transition t)
    : IntMinimizeScript(opt),
      actions(*this, IntSet(ToShelf, Charge), t, opt.limit()) {}
  void branching(const DeliveryOptions& opt) {
    if (opt.branching() == DeliveryOptions::BRANCH_MIN)
      branch(*this, actions, INT_VAR_NONE(), INT_VAL_MIN());
    else
      branch(*this, actions, INT_VAR_NONE(), INT_VAL_MAX());
  }
  Delivery(Delivery& s) : IntMinimizeScript(s) {
    actions.update(*this, s.actions);
  }
  IntVar cost(void) const override {
    return actions.length();
  }
  void print(std::ostream& os) const override {
    os << "Actions: " << actions.length() << "\n  ";
    for (int i=0; i<actions.known_length(); i++)
      os << ' ' << action_name[actions[i].val()];
    os << '\n';
  }
};

/**
 * \brief Explicit states, constructed as the plan grows
 *
 * State i holds before action i and state i+1 after it, so the state lists
 * are one position longer than the action list. Creating action i creates
 * state i+1 and posts the transition between them.
 */
class StateDelivery : public Delivery {
  OpenIntVarList at, charge, packet;
public:
  StateDelivery(const DeliveryOptions& opt)
    : Delivery(opt,
        [](Space& home, OpenIntVarList, int i) {
          static_cast<StateDelivery&>(home).step(i);
        }),
      at(*this, IntSet(Shelf, Charger), opt.limit()+1),
      charge(*this, IntSet(0, capacity), opt.limit()+1),
      packet(*this, IntSet(OnShelf, Delivered), opt.limit()+1) {
    rel(*this, at.length() == actions.length() + 1);
    rel(*this, charge.length() == actions.length() + 1);
    rel(*this, packet.length() == actions.length() + 1);
    rel(*this, at.get(*this, 0), IRT_EQ, Workbench);
    rel(*this, charge.get(*this, 0), IRT_EQ, opt.charge());
    rel(*this, packet.get(*this, 0), IRT_EQ, OnShelf);
    post_goal(*this, packet[0], actions.length(), 0);
    branching(opt);
  }

  void step(int i) {
    at.materialize(*this, i+2);
    charge.materialize(*this, i+2);
    packet.materialize(*this, i+2);
    if (failed())
      return;
    post_step(*this, actions[i],
              at[i], charge[i], packet[i],
              at[i+1], charge[i+1], packet[i+1]);
    post_goal(*this, packet[i+1], actions.length(), i+1);
  }

  StateDelivery(StateDelivery& s) : Delivery(s) {
    at.update(*this, s.at);
    charge.update(*this, s.charge);
    packet.update(*this, s.packet);
  }
  Space* copy(void) override {
    return new StateDelivery(*this);
  }
};

// Number the robot states so that they can be used as automaton states.
static int
state(int at, int ch, int pk) {
  return (pk * (capacity+1) + ch) * 3 + at;
}

// Read the table of steps as an automaton over the actions.
static DFA
robot_dfa(int initial_charge) {
  TupleSet steps = robot_steps();
  std::vector<DFA::Transition> transitions;
  for (int i=0; i<steps.tuples(); i++) {
    // A step is (a, at0, ch0, pk0, at1, ch1, pk1).
    TupleSet::Tuple s = steps[i];
    int action = s[0];
    int from = state(s[1], s[2], s[3]);
    int to = state(s[4], s[5], s[6]);
    transitions.push_back({from, action, to});
  }
  transitions.push_back({-1, 0, 0});
  // The plans end in the states where the packet has been delivered.
  IntArgs delivered;
  for (int ch=0; ch<=capacity; ch++)
    for (int at=Shelf; at<=Charger; at++)
      delivered << state(at, ch, Delivered);
  delivered << -1;
  int start = state(Workbench, initial_charge, OnShelf);
  return DFA(start, transitions.data(), delivered.begin());
}

/// The same plans, with the transitions as a regular constraint
class RegularDelivery : public Delivery {
public:
  RegularDelivery(const DeliveryOptions& opt) : Delivery(opt) {
    extensional(*this, actions, robot_dfa(opt.charge()));
    branching(opt);
  }
  RegularDelivery(RegularDelivery& s) : Delivery(s) {}
  Space* copy(void) override {
    return new RegularDelivery(*this);
  }
};

int
main(int argc, char* argv[]) {
  DeliveryOptions opt;
  opt.parse(argc, argv);
  if (opt.model() == DeliveryOptions::MODEL_STATE)
    Script::run<StateDelivery, BAB, DeliveryOptions>(opt);
  else
    Script::run<RegularDelivery, BAB, DeliveryOptions>(opt);
  return 0;
}