| 4 | 4 | // |
| 5 | 5 | |
| 6 | 6 | export class TwoBucket { |
| 7 | | constructor() { |
| 8 | | throw new Error('Remove this line and implement the function'); |
| 7 | constructor(size1, size2, goal, startBucket) { |
| 8 | this.size1 = size1; |
| 9 | this.size2 = size2; |
| 10 | this.goal = goal; |
| 11 | this.startBucket = startBucket; |
| 9 | 12 | } |
| 10 | 13 | |
| 11 | 14 | solve() { |
| 12 | | throw new Error('Remove this line and implement the function'); |
| 15 | // Edge Case: Goal is 0 (cannot measure 0 liters by filling buckets) |
| 16 | if (this.goal === 0) { |
| 17 | throw new Error('impossible'); |
| 18 | } |
| 19 | |
| 20 | // Edge Case: Goal is larger than both buckets |
| 21 | if (this.goal > Math.max(this.size1, this.size2)) { |
| 22 | throw new Error('impossible'); |
| 23 | } |
| 24 | |
| 25 | // Edge Case: Goal equals one of the bucket sizes and that bucket is the start bucket |
| 26 | if (this.goal === this.size1 && this.startBucket === 'one') { |
| 27 | return { moves: 1, goalBucket: 'one', otherBucket: 0 }; |
| 28 | } |
| 29 | if (this.goal === this.size2 && this.startBucket === 'two') { |
| 30 | return { moves: 1, goalBucket: 'two', otherBucket: 0 }; |
| 31 | } |
| 32 | |
| 33 | // Edge Case: Goal equals one of the bucket sizes but that bucket is not the start bucket |
| 34 | if (this.goal === this.size1 && this.startBucket === 'two') { |
| 35 | // Fill the other bucket first (1 move), then pour to bucket one (1 move) |
| 36 | return { moves: 2, goalBucket: 'one', otherBucket: this.size2 }; |
| 37 | } |
| 38 | if (this.goal === this.size2 && this.startBucket === 'one') { |
| 39 | // Fill the other bucket first (1 move), then pour to bucket two (1 move) |
| 40 | return { moves: 2, goalBucket: 'two', otherBucket: this.size1 }; |
| 41 | } |
| 42 | |
| 43 | // Edge Case: One bucket has zero capacity |
| 44 | if (this.size1 === 0) { |
| 45 | if (this.goal === 0) { |
| 46 | return { moves: 1, goalBucket: 'one', otherBucket: 0 }; |
| 47 | } |
| 48 | if (this.goal === this.size2) { |
| 49 | return { moves: 1, goalBucket: 'two', otherBucket: 0 }; |
| 50 | } |
| 51 | throw new Error('impossible'); |
| 52 | } |
| 53 | if (this.size2 === 0) { |
| 54 | if (this.goal === 0) { |
| 55 | return { moves: 1, goalBucket: 'two', otherBucket: 0 }; |
| 56 | } |
| 57 | if (this.goal === this.size1) { |
| 58 | return { moves: 1, goalBucket: 'one', otherBucket: 0 }; |
| 59 | } |
| 60 | throw new Error('impossible'); |
| 61 | } |
| 62 | |
| 63 | // BFS to find the minimum number of moves |
| 64 | const queue = []; |
| 65 | const visited = new Set(); |
| 66 | |
| 67 | // Initial state based on which bucket to fill first |
| 68 | let initialState; |
| 69 | if (this.startBucket === 'one') { |
| 70 | initialState = { bucket1: this.size1, bucket2: 0, moves: 1 }; |
| 71 | } else { |
| 72 | initialState = { bucket1: 0, bucket2: this.size2, moves: 1 }; |
| 73 | } |
| 74 | |
| 75 | queue.push(initialState); |
| 76 | visited.add(`${initialState.bucket1},${initialState.bucket2}`); |
| 77 | |
| 78 | // Edge Case: Starting state already meets goal |
| 79 | if (initialState.bucket1 === this.goal) { |
| 80 | return { moves: initialState.moves, goalBucket: 'one', otherBucket: initialState.bucket2 }; |
| 81 | } |
| 82 | if (initialState.bucket2 === this.goal) { |
| 83 | return { moves: initialState.moves, goalBucket: 'two', otherBucket: initialState.bucket1 }; |
| 84 | } |
| 85 | |
| 86 | // Forbidden state: start bucket empty and other bucket full |
| 87 | const forbiddenState = this.startBucket === 'one' |
| 88 | ? `${0},${this.size2}` |
| 89 | : `${this.size1},${0}`; |
| 90 | |
| 91 | while (queue.length > 0) { |
| 92 | const current = queue.shift(); |
| 93 | |
| 94 | // Generate all possible next states |
| 95 | const nextStates = []; |
| 96 | |
| 97 | // 1. Fill bucket1 |
| 98 | if (current.bucket1 < this.size1) { |
| 99 | nextStates.push({ |
| 100 | bucket1: this.size1, |
| 101 | bucket2: current.bucket2, |
| 102 | moves: current.moves + 1 |
| 103 | }); |
| 104 | } |
| 105 | |
| 106 | // 2. Fill bucket2 |
| 107 | if (current.bucket2 < this.size2) { |
| 108 | nextStates.push({ |
| 109 | bucket1: current.bucket1, |
| 110 | bucket2: this.size2, |
| 111 | moves: current.moves + 1 |
| 112 | }); |
| 113 | } |
| 114 | |
| 115 | // 3. Empty bucket1 |
| 116 | if (current.bucket1 > 0) { |
| 117 | nextStates.push({ |
| 118 | bucket1: 0, |
| 119 | bucket2: current.bucket2, |
| 120 | moves: current.moves + 1 |
| 121 | }); |
| 122 | } |
| 123 | |
| 124 | // 4. Empty bucket2 |
| 125 | if (current.bucket2 > 0) { |
| 126 | nextStates.push({ |
| 127 | bucket1: current.bucket1, |
| 128 | bucket2: 0, |
| 129 | moves: current.moves + 1 |
| 130 | }); |
| 131 | } |
| 132 | |
| 133 | // 5. Pour from bucket1 to bucket2 |
| 134 | if (current.bucket1 > 0 && current.bucket2 < this.size2) { |
| 135 | const pourAmount = Math.min(current.bucket1, this.size2 - current.bucket2); |
| 136 | nextStates.push({ |
| 137 | bucket1: current.bucket1 - pourAmount, |
| 138 | bucket2: current.bucket2 + pourAmount, |
| 139 | moves: current.moves + 1 |
| 140 | }); |
| 141 | } |
| 142 | |
| 143 | // 6. Pour from bucket2 to bucket1 |
| 144 | if (current.bucket2 > 0 && current.bucket1 < this.size1) { |
| 145 | const pourAmount = Math.min(current.bucket2, this.size1 - current.bucket1); |
| 146 | nextStates.push({ |
| 147 | bucket1: current.bucket1 + pourAmount, |
| 148 | bucket2: current.bucket2 - pourAmount, |
| 149 | moves: current.moves + 1 |
| 150 | }); |
| 151 | } |
| 152 | |
| 153 | for (const state of nextStates) { |
| 154 | const stateKey = `${state.bucket1},${state.bucket2}`; |
| 155 | |
| 156 | // Edge Case: Skip forbidden state |
| 157 | if (stateKey === forbiddenState) { |
| 158 | continue; |
| 159 | } |
| 160 | |
| 161 | // Edge Case: Skip already visited states |
| 162 | if (visited.has(stateKey)) { |
| 163 | continue; |
| 164 | } |
| 165 | |
| 166 | // Edge Case: Check if we've reached the goal |
| 167 | if (state.bucket1 === this.goal) { |
| 168 | return { moves: state.moves, goalBucket: 'one', otherBucket: state.bucket2 }; |
| 169 | } |
| 170 | if (state.bucket2 === this.goal) { |
| 171 | return { moves: state.moves, goalBucket: 'two', otherBucket: state.bucket1 }; |
| 172 | } |
| 173 | |
| 174 | visited.add(stateKey); |
| 175 | queue.push(state); |
| 176 | } |
| 177 | } |
| 178 | |
| 179 | // Edge Case: Impossible to reach the goal |
| 180 | throw new Error('impossible'); |
| 13 | 181 | } |
| 14 | 182 | } |