"Three pitchers with water" problem I don't know what this problem is named, so I can't Google for a solution about it. Here's the image:



There are three pitchers with capacities of 10, 7 and 3 quarts.

We need to move the water from a pitcher (or jar) to another pitcher so it will result in 5, 5 and 0.

I have to print all the steps needed to make the pitchers contains 5, 5 and 0 quarts of water.

Here's my working code. Please review it and tell me how to make it better, faster, shorter, more readable.

class Jar
  attr_accessor :max, :current, :target

  def initialize max, current, target
    @max = max
    @current = current
    @target = target
    raise 'max should not be 0' if max == 0
  end

  def full?
    return @current == @max
  end

  def empty?
    return @current == 0
  end

  def overflow
    return 0 if @current &lt; @max
    over = @current - @max;
    @current = max
    return over
  end

  def move_to o
    o.current += @current
    @current = o.overflow
  end

end

class Quartz
  MAX_STEPS = 12

  def initialize max, init, target
    raise 'max.length must equal init.length' if max.length != init.length
    raise 'max.length must equal target.length' if max.length != target.length
    @ite = (0..(max.length-1))
    @memoize = {}
    @targets = []
    @steps = []
    @all_solutions = []
    @jars = @ite.collect { |x| Jar.new(max[x],init[x],target[x]) }
    @targets = current(:target)
  end

  def recurse step=1
    orig = current
    @steps &lt;&lt; orig
    if orig == @targets 
      p @steps
      return @steps.length
    end
    return false if step&gt;=MAX_STEPS

    @memoize[orig] = step

    @jars.each do |x|
      next if x.empty?
      @jars.each do |y|
        next if x == y
        next if y.full?
        x.move_to y
        done = @memoize[current]
        if done 
          restore orig
          next
        end
        ok = recurse(step+1)
        #return ok if ok # return only first solution
        @steps.pop
        restore orig
      end      
    end

    return false
  end

  def current attr=:current
    @jars.collect{ |x| x.send attr }
  end

  alias_method :to_array, :current

  def restore a
    @ite.each { |i| @jars[i].current = a[i] }
  end

end

q = Quartz.new [10,7,3], [10,0,0], [5,5,0]
p q.recurse


This is the program's output:

[[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], 
 [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]]
Some comments on your code:


def initialize max, current, target. The community consensus seems to be to put always parenthesis on method definitions. I'd definitely do it.
return @current == @max. It's not idiomatic to put explicits return, the last expression of a block/method is returned.
MAX_STEPS = 12. Isn't this kind of cheating? 
raise 'max.length must equal init.length' if max.length != init.length. I wouldn't lose a second validating inputs. If the input data is wrong it's the caller's problem.
[Lots of imperative code which, frankly, I don't understand] When you are dealing with mathematics-related problems (some would argue all computation is a mathematics-related problem) you'll get better algorithms with functional programming.


I'd write it with a depth-first algorithm in functional style. Note that I've created two generic abstractions, Enumerable#map_detect (Facets has it) and Array#merge, so the main algorithm remains as clean and declarative as possible. Granted, it may be difficult to grasp at first if you have only experience with imperative programming, ask if you don't understand something (also, reviews of the review welcomed):

require 'facets/enumerable/map_detect'

class Array
  # [:a, :b, :c, :d].merge_from_hash(1 =&gt; :bb, 3 =&gt; :dd) #=&gt; [:a, :bb, :c, :dd]
  def merge_from_hash(hash)
    map.with_index { |x, idx| hash.fetch(idx, x) }
  end
end

class PitchersProblem &lt; Struct.new(:total)
  def solve(current, final, solution = [])
    if current == final
      solution + [current]
    else
      (candidates(current) - solution).map_detect do |candidate|
        solve(candidate, final, solution + [current])
      end
    end
  end

  def candidates(current)
    (0...total.size).to_a.permutation(2).map do |i1, i2|
      free2 = total[i2] - current[i2]
      if current[i1] &gt; 0 &amp;&amp; free2 &gt; 0
        moved = [current[i1], free2].min
        current.merge_from_hash(i1 =&gt; current[i1] - moved, i2 =&gt; current[i2] + moved)
      end
    end.compact
  end
end

p PitchersProblem.new([10, 7, 3]).solve([10, 0, 0], [5, 5, 0])
#=&gt; [[10, 0, 0], [3, 7, 0], [0, 7, 3], [7, 0, 3], [7, 3, 0], 
#    [4, 3, 3],  [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], 
#    [8, 2, 0],  [5, 2, 3], [5, 5, 0]]


Notes on my code:


solve can be read as: "If the current state is the final, add it to the path solution and we are done. Otherwise, for each permutation of the pitchers, move water from one to the other if possible, and try to find a solution recursively (unless that state is already in our solution path)".
This algorith returns the first solution it gets (size 13), which is not the optimal (size 10?), that's because it's a depth-first algorithm, you can transform it into a breadth-first algorithm to get the shortest solution first.
Ideally solution should be an insertion-ordered data-structure with O(1) lookup (because of solution.include?(new_current)), something like an OrderedSet. An array has O(n) lookup, but anyway, let's leave it just to keep it simple.