Ruby
The following code gives a ruby implementation of the task described above. The specification is as follows:
Input: A list of integers on STDIN, where the first one is the number n of buckets available, followed by n distinct bucket denominations, followed by the target amount of water.
Output: A list of operations needed to reach the target amount in any bucket or a corresponding message if that is not possible.
Task: Start with n empty buckets each of different integer denomination. In each step you can do one of the following:
- Fill X: fills the bucket with denomination X with water such that it contains exactly X water
- Empty Y: empty the bucket with denomination Y, i.e. no water inside after this operation
- Move A to B: take any water in bucket with denomination A and put it into bucket with denomination B up to the point where bucket B is full. (Example: Bucket 5 has 4 liters in it and bucket 3 has 2. Then Move 5 to 3 will transfer 1 liter leaving bucket 5 with 3 liters while bucket 3 is full afterwards.)
The algorithm used is quite straightforward. On a list of bucket configurations (i.e. a list of buckets with their corresponding fill levels) perform all possible operations. Each one will lead to a new configuration. Keep those which you didn't had already in previous steps (i.e. those that are really novel). This way we get a list of configurations reachable be 1 step, 2 steps, ... . Whenever we reach a configuration where one bucket is filled with exactly the target amount we are done.
Since we have a constructive algorithm, i.e. we know in each step which operation we perform, we can simultaneously build the list of operations in textual representation for any bucket configuration.
Example: 3 buckets with denominations 7, 9 and 11. Target amount of water is 1.
Input:
3, 7, 9, 11, 1
Output:
Solution found with 7 steps:
Fill 7 Move 7 to 11 Fill 7 Move 7 to 11 Move 7 to 9 Fill 7 Move 7 to 9
Code:
# get input as list of integers
input = gets.split(/,/).map{|s| s.to_i}
count = input.shift
start = (1..count).map{[input.shift, 0]}
target = input.shift
# a bucket configuration is a list of buckets, each represented as
# array [denomination, fill level], i.e. initial configurations
# is e.g. [[3, 0], [5, 0]] for empty buckets of size 3 and 5
configurations = {start => ""}
step = 0
solution = nil
current = configurations.keys
while current.size > 0 do
# debug output (each configuration rechable within step)
puts "- #{step} ------------------------------------------"
current.each{|k| puts "#{k.to_s} #{configurations[k]}"}
puts
# test current configurations if target amount is included
solution = current.select{|k| k.any?{|b| b[1] == target}}[0]
break if solution
step += 1
new_configurations = {}
# for all configurations for all buckets
current.each{|k|
k.size.times{|i|
# do a fill operation on this bucket
kn = Marshal.load(Marshal.dump(k)) # make deep copy
# increase fill level to bucket denomination
kn[i][1] = kn[i][0]
new_configurations[kn] = "#{configurations[k]} Fill #{kn[i][0]}"
# do an empty operation on this bucket
kn = Marshal.load(Marshal.dump(k)) # make deep copy
# set fill level to zero
kn[i][1] = 0
new_configurations[kn] = "#{configurations[k]} Empty #{kn[i][0]}"
# do a move operation on any other bucket
k.size.times{|j|
kn = Marshal.load(Marshal.dump(k)) # make deep copy
# amount movable is current amount or space left in other bucket
h = [kn[i][1], kn[j][0]-kn[j][1]].min
kn[i][1] -= h
kn[j][1] += h
new_configurations[kn] = "#{configurations[k]} Move #{kn[i][0]} to #{kn[j][0]}"
}
}
}
# remove any configuration already reachable with less steps
new_configurations.keep_if{|conf| !configurations[conf]}
# merge new configurations
configurations.merge!(new_configurations)
current = new_configurations.keys
end
if solution
puts "Solution found with #{step} steps:"
puts configurations[solution]
else
puts "Impossible to reach target"
end
