Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Two Buckets One Tap
function Bucket(capacity, level){
this.capacity = capacity;
this.level = level || 0;
}
Bucket.prototype.fill = function(){
this.level = this.capacity;
}
Bucket.prototype.discard = function(){
this.level = 0;
}
Bucket.prototype.pourInto = function(other){
var pourAmount = Math.min(this.level, other.capacity - other.level);
this.level -= pourAmount;
other.level += pourAmount;
}
Bucket.prototype.clone = function(){
return new Bucket(this.capacity, this.level);
}
function State(){
this.a = new Bucket(43);
this.b = new Bucket(47);
this.history = [];
}
State.prototype.clone = function(){
var state = new State();
state.a = this.a.clone();
state.b = this.b.clone();
state.history = this.history.slice(0);
return state;
}
State.prototype.fillA = function(){ this.a.fill(); }
State.prototype.fillB = function(){ this.b.fill(); }
State.prototype.discardA = function(){ this.a.discard(); }
State.prototype.discardB = function(){ this.b.discard(); }
State.prototype.pourAintoB = function(){ this.a.pourInto(this.b); }
State.prototype.pourBintoA = function(){ this.b.pourInto(this.a); }
State.endStateFound = false;
State.endState = null;
State.operations = ['fillA', 'fillB', 'discardA', 'discardB', 'pourAintoB', 'pourBintoA'];
State.dictionary = {};
State.freshStates = [];
State.hasFreshStates = function(){ return State.freshStates.length > 0; }
State.isEndState = function(state){ return state.a.level == 46 || state.b.level == 46; }
State.key = function(state){ return state.a.level + ':' + state.b.level; }
State.isFresh = function(state){ return !(State.key(state) in State.dictionary); }
State.store = function(state){
if(State.isFresh(state)) {
if(State.isEndState(state)){
State.endStateFound = true;
State.endState = state;
}
State.dictionary[State.key(state)] = state;
State.freshStates.push(state);
}
}
State.tryNextOperations = function(){
var state = State.freshStates.shift();
if(!state) return;
for(operation in State.operations) {
var childState = State.operate(state, State.operations[operation]);
State.store(childState);
}
}
State.operate = function(parentState, operation){
var state = parentState.clone();
state[operation]();
state.history.push(operation + ' (' + State.key(state) + ')');
return state;
}
State.store(new State());
while(!State.endStateFound && State.hasFreshStates()) State.tryNextOperations();
if(State.endStateFound) console.log('Solution found!\n' + State.endState.history.join('\n'));
else console.log('No solutions found.');
@deckar01

This comment has been minimized.

Copy link
Owner Author

@deckar01 deckar01 commented Jul 16, 2015

Solution found!
fillA (43:0)
pourAintoB (0:43)
fillA (43:43)
pourAintoB (39:47)
discardB (39:0)
pourAintoB (0:39)
fillA (43:39)
pourAintoB (35:47)
discardB (35:0)
pourAintoB (0:35)
fillA (43:35)
pourAintoB (31:47)
discardB (31:0)
pourAintoB (0:31)
fillA (43:31)
pourAintoB (27:47)
discardB (27:0)
pourAintoB (0:27)
fillA (43:27)
pourAintoB (23:47)
discardB (23:0)
pourAintoB (0:23)
fillA (43:23)
pourAintoB (19:47)
discardB (19:0)
pourAintoB (0:19)
fillA (43:19)
pourAintoB (15:47)
discardB (15:0)
pourAintoB (0:15)
fillA (43:15)
pourAintoB (11:47)
discardB (11:0)
pourAintoB (0:11)
fillA (43:11)
pourAintoB (7:47)
discardB (7:0)
pourAintoB (0:7)
fillA (43:7)
pourAintoB (3:47)
discardB (3:0)
pourAintoB (0:3)
fillA (43:3)
pourAintoB (0:46)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment