[ create a new paste ] login | about

Link: http://codepad.org/24r2qP2Q    [ raw code | output | fork ]

mohit_at_codepad - C++, pasted on Mar 14:
// http://d.hatena.ne.jp/Nabetani/20111207/p1


#include <iostream>
#include <vector>
#include <cstdlib>
#include <deque>
#include <set>
#include <algorithm>

std::vector<int> capacity;
int bucket_count;
int wanted;
//#define GET_ANSWER_IN_FIRST_BUCKET
class bucket_state {
public: 
  bool operator ==(const bucket_state &that) const {
    return std::equal( state.begin(), state.end(), that.state.begin() );
  }
  bool operator !=(const bucket_state &that) const {
    return (*this != that);
  }
  bool operator <(const bucket_state &that) const {
    for(std::vector<int>::const_iterator it = state.begin(), jt = that.state.begin();
      it != state.end(); ++it, ++jt) if(*it != *jt) return *it < *jt;
    return false;
  }
  bool can_pour(size_t from, size_t to) const {
    if(state[from] == 0) return false;
    return (state[to] < capacity[to]);
  }
  void pour(size_t from, size_t to) {
    const int state_can_have = capacity[to] - state[to];
    const int xfer = std::min(state[from], state_can_have);
    state[from] -= xfer, state[to] += xfer;
    steps.push_back( std::make_pair(from, to) );
  }
  std::vector< std::pair<int,int> > steps;
  std::vector<int> state;
}answer;

std::set<bucket_state> intermediates;

bool bucket_can_be_added_to_intermediates(bucket_state &bs) {
  if( intermediates.find(bs) != intermediates.end() ) return false;
  bucket_state copy = bs;
  copy.steps.clear();
  intermediates.insert(copy);
  return true;
}

void perform_bfs(bucket_state bs) {
  //std::queue<bucket_state> bfs;
  std::deque<bucket_state> bfs;
  bfs.push_back(bs);
  bucket_can_be_added_to_intermediates(bs);
  while(!bfs.empty() ) {
    bucket_state &this_state = bfs.front();
    for(int i = 0; i < bucket_count - 1; ++i) 
    for(int j = i + 1; j < bucket_count; ++j) {
      if( this_state.can_pour(i, j) ) {
        bucket_state new_state = this_state;
        new_state.pour(i, j);
#ifdef GET_ANSWER_IN_FIRST_BUCKET
        if(new_state.state[0] == wanted) {
#else
        if(new_state.state[i] == wanted || new_state.state[j] == wanted) {
#endif
          answer = new_state;
          return;
        }
        if( bucket_can_be_added_to_intermediates( new_state ) ) bfs.push_back(new_state);
      }
      if( this_state.can_pour(j, i) ) {
        bucket_state new_state = this_state;
        new_state.pour(j, i);
#ifdef GET_ANSWER_IN_FIRST_BUCKET
        if(new_state.state[0] == wanted) {
#else
        if(new_state.state[i] == wanted || new_state.state[j] == wanted) {
#endif
          answer = new_state;
          return;
        }
        if( bucket_can_be_added_to_intermediates( new_state ) ) bfs.push_back(new_state);
      }
    }
    bfs.pop_front();
  }
}

// Assumption: all numbers are positive
int main(int argc, char *const *argv) {
  if(argc < 4) {
    // dummy sample 50 1234 321 100
    wanted = 50;
    capacity.push_back( 1234 );
    capacity.push_back(  321 );
    capacity.push_back(  100 );
  } else {
    wanted = atoi(argv[1]);
    for(int i = 2; i < argc; ++i) capacity.push_back( atoi(argv[i]) );
  }
  bucket_state bs;
  bucket_count = static_cast<int>( capacity.size() );
  bs.state.resize(bucket_count);
  bs.state[0] = capacity[0];
  perform_bfs(bs);
  if( answer.state.empty() ) std::cout << "Impossible" << std::endl;
  else {
    std::vector< std::pair<int,int> > &steps = answer.steps;
    std::cout << steps.size() << " steps"
          << ':';
    for(size_t i = 0; i < steps.size(); ++i) {
      std::cout << steps[i].first << "->"
            << steps[i].second << ' ';
    }
    std::cout << std::endl;
  }
  return 0;
}


Output:
1
418 steps:0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 2->0 1->2 0->1 1->2 2->0 1->2 2->0 1->2 


Create a new paste based on this one


Comments: