4
\$\begingroup\$

This challenge is to calculate how to measure 4 liters of water with just two unevenly sized buckets, one of 3 liters and another of 5 liters, in minimum number of steps. To extend and generalize this, write a program to evaluate the minimum number of steps to measure “X” liters of water, with “Y” buckets each having a separate denomination.

Assumptions:

  1. Each bucket used for measuring water should be unique in denomination and the number of buckets will be <= 3
  2. The target amount to be reached has to finally reside in a single bucket (at the end of the measuring activity).
  3. The bucket capacities and target amount will be <= 99
  4. If there are multiple ways to measure the same amount, only one single way, having the minimum number of steps is required.
  5. Ties will be broken by the smallest program.

Examples:

2,3,5,4
Implies that there are 2 buckets of capacity 3 and 5 each and the target amount desired is 4.

3,4,6,9,7
Implies that there are 3 buckets of capacity 4, 6 and 9 each and the target amount desired is 7.

Answers:

2,3,5,4
Fill 5
Move 5 to 3
Empty 3
Move 5 to 3
Fill 5
Move 5 to 3

3,4,6,9,7
Fill 4
Move 4 to 6
Fill 9
Move 9 to 6

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to CodeGolf.SE! Could you stop posting willy-nilly and spend a little time fixing the challenges you have already posted, please. As PhiNotPi said in a comment to your first post these are not up to spec. They do not specify a winning condition, and are difficult to read. Take some time to look at previous, well received challenges, and consider using the meta sandbox (a place to get suggestions before posting) in the future. \$\endgroup\$ – dmckee --- ex-moderator kitten Apr 6 '12 at 15:39
  • 2
    \$\begingroup\$ This has such promise...it would be a shame if it was abandoned in this state. \$\endgroup\$ – dmckee --- ex-moderator kitten Apr 7 '12 at 4:17
  • 5
    \$\begingroup\$ I agree with @dmckee. This could actually be a pretty fun challenge if it were better specified. \$\endgroup\$ – PhiNotPi Apr 7 '12 at 12:07
4
\$\begingroup\$

Python, 363 chars

Golfed it, not sure if it is golf or not. The map P maps a reachable state to the instructions used to get to that state. Keeps enumerating reachable states until it finds one with the target amount of water in it.

I=input()
B=I[1:-1]
R=range(I[0])
P={(0,)*I[0]:""}
while P:
 Q={}
 for s in P:
  if I[-1]in s:print P[s];P=Q={};break
  for i in R:
   Q[s[:i]+(0,)+s[i+1:]]=P[s]+"Empty %d "%B[i];Q[s[:i]+(B[i],)+s[i+1:]]=P[s]+"Fill %d "%B[i]
   for d in R:m=min(s[i],B[d]-s[d]);Q[tuple(s[j]-[0,m][j==i]+[0,m][j==d]for j in R)]=P[s]+"Move %d to\
 %d "%(B[i],B[d])
 Q.update(P);P=Q
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'm pretty sure, the OP hasn't made the input specification mandatory. if you use space separated values, you can use gets.split \$\endgroup\$ – st0le Apr 10 '12 at 6:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.