Two Bucket - expected results are not optimal

Exercism
1

My solution for TwoBucket failed in 3 cases :

  •   Expected: ({String goalBucket, int moves, int otherBucket}):<(goalBucket: two, moves: 8, otherBucket: 3)>   Actual: ({String goalBucket, int moves, int otherBucket}):<(goalBucket: one, moves: 6, otherBucket: 5)>

  •   Expected: ({String goalBucket, int moves, int otherBucket}):<(goalBucket: two, moves: 18, otherBucket: 7)>     Actual: ({String goalBucket, int moves, int otherBucket}):<(goalBucket: one, moves: 16, otherBucket: 11)>

  •   Expected: ({String goalBucket, int moves, int otherBucket}):<(goalBucket: two, moves: 10, otherBucket: 0)>    Actual: ({String goalBucket, int moves, int otherBucket}):<(goalBucket: two, moves: 4, otherBucket: 6)>

I use a ‘zero’ bucket to have only one move type (pouring). At fisrt bucket ‘zero’ is full and it’s size is ‘one’ + ‘two’.
Filling bucket 'one or ‘two’ is equivalent to pouring from ‘zero’ and emptying bucket ‘one’ or ‘two’ is equivalent pouring into ‘zero’.

My results are valid as all moves are legal.
More, I think my solution is better than the one used for the tests because it requires less moves in some cases.

Let’s analyse first case.

input : bucketOne: 3, bucketTwo: 5, goal: 1, startBucket: “two”
result : goalBucket: one, moves: 6, otherBucket: 5 (Expected: goalBucket: two, moves: 8, otherBucket: 3)

my sequence:

  1. initial state : 0/3|0/5
  2. fill ‘two’ → 0/3|5/5
  3. pour ‘two’ into ‘one’ → 3/3|2/5
  4. empty ‘two’ → 3/3|0/5
  5. pour ‘one’ into ‘two’ → 0/3|3/5
  6. fill ‘one’ → 3/3|3/5
  7. pour ‘one’ into ‘two’ → 1/3|5/5

Here is my code :

import 'dart:math';

typedef Result = ({int moves, String goalBucket, int otherBucket});
typedef Sequence = List<State>;
typedef Move = (int, int);

class Bucket {
  static List<String> names = ['zero', 'one', 'two'];
  Bucket({required this.size, this.content = 0});
  final int size;
  final int content;
  int get space => size - content;
  bool get isEmpty => content == 0;
  bool get isFull => content == size;
  static Bucket get none => Bucket(size: 0);
  Bucket add(int qty) => Bucket(size: size, content: content + qty);
  @override
  String toString() => '$content/$size';
}

class State {
  Map<int, Bucket> buckets = {for (int i = 0; i <= 2; i++) i: Bucket.none};
  int get count => buckets.length;
  int size(int i) => buckets[i]!.size;
  int content(int i) => buckets[i]!.content;
  State();
  State.fromStart({required int bucketOne, required int bucketTwo}) {
    buckets[0] = Bucket(size: bucketOne + bucketTwo, content: bucketOne + bucketTwo);
    buckets[1] = Bucket(size: bucketOne);
    buckets[2] = Bucket(size: bucketTwo);
  }
  bool canMove(Move move) => !(buckets[move.$1]!.isEmpty || buckets[move.$2]!.isFull);
  bool matchesSolution(int goal) => buckets[1]!.content == goal || buckets[2]!.content == goal;
  int goalBucketIndex(int goal) => buckets.entries.lastWhere((e) => e.value.content == goal).key;
  int otherBucketContent(int goal) => buckets[count - goalBucketIndex(goal)]!.content;
  State move(Move move) {
    State newState = State();
    var (a, b) = move;
    var c = count - a - b;
    var qty = min(buckets[a]!.content, buckets[b]!.space);
    newState.buckets[a] = buckets[a]!.add(-qty);
    newState.buckets[b] = buckets[b]!.add(qty);
    newState.buckets[c] = buckets[c]!;
    return newState;
  }

  static final List<Move> allMoves = [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)];
  List<Move> get availableMoves => allMoves.where((e) => canMove(e)).toList();

  @override
  String toString() => '${buckets[1]}|${buckets[2]}';

  @override
  bool operator ==(Object other) => other is State && '$this' == '$other';

  @override
  int get hashCode => toString().hashCode;
}

class TwoBucket {
  final int bucketOne;
  final int bucketTwo;
  final int goal;
  final String startBucket;
  late State initialState;
  Sequence solution = [];
  List<Sequence> solutions = [];
  TwoBucket({required this.bucketOne, required this.bucketTwo, required this.goal, required this.startBucket}) {
    initialState = State.fromStart(bucketOne: bucketOne, bucketTwo: bucketTwo);
  }
  Result measure() {
    solutions.clear();
    var candidate = [initialState.move((0, Bucket.names.indexOf(startBucket)))];
    explore([candidate]);
    if (solutions.isEmpty) throw ArgumentError('impossible');
    solution = solutions.reduce((a, b) => a.length < b.length ? a : b);
    return (
      moves: solution.length,
      goalBucket: Bucket.names[solution.last.goalBucketIndex(goal)],
      otherBucket: solution.last.otherBucketContent(goal)
    );
  }

  void explore(List<Sequence> candidates) {
    if (candidates.isEmpty) return;
    List<Sequence> newCandidates = [];
    for (var candidate in candidates) {
      var lastState = candidate.last;
      if (lastState.matchesSolution(goal)) {
        solutions.add(candidate);
      } else {
        for (var move in lastState.availableMoves) {
          var nextState = lastState.move(move);
          if (!candidate.contains(nextState)) {
            newCandidates.add([...candidate, nextState]);
          }
        }
      }
    }
    explore(newCandidates);
  }
}
1 Like
2

" * After an action, you may not arrive at a state where the initial starting bucket is empty and the other bucket is full."

State 3 in your sequence is not permitted.

2 Likes
3

You’re right, I missed that rule.
Thank you! :+1:

1 Like