Reverse recursion

question.md

How would I go about searching this hash of hashes for a wine growing region for the final branch of the tree for the key of Vista Flores.

{
    "Argentina": {
        "Catamarca": [],
        "Cuyo": [],
        "Fiambala": [],
        "Jujuy": [],
        "La Rioja": {
            "Famatina": []
        },
        "Mendoza": {
            "Agrelo": [],
            "Barrancas": [],
            "Las Compuertas": [],
            "Lujan de Cuyo": [],
            "Lunlunta": [],
            "Maipu": [],
            "Perdriel": [],
            "San Martin": [],
            "San Rafael": [],
            "Uco Valley": {
                "Altamira": [],
                "La Consulta": [],
                "San Carlos": [],
                "Tunuyan": [],
                "Tupungato": [],
                "Vista Flores": []
            },
            "Ugarteche": [],
            "Vistalba": []
        },
        "Patagonia": {
            "Neuquen": [],
            "Rio Negro": []
        },
        "Salta": {
            "Cafayate - Calchaqui Valley": [],
            "Molinos": []
        },
        "San Juan": {
            "Pedernal Valley": [],
            "Tulum Valley": [],
            "Zonda Valley": []
        }
    }
}

Once I have that region I then need to recurse back up the tree and build up the tree structure such as:

region_1: Argentina
region_2: Mendoza
region_3: Uco Valley
region_4: Vista Flores

Please know that this is not homework, but rather a real problem I am facing. I am quiet awful at recursion problems such as these.

You can see a previous question that I have asked on the ruby irc before - here

hash = {
    "Argentina" => {
        "Catamarca"=> [],
        "Cuyo"=> [],
        "Fiambala"=> [],
        "Jujuy"=> [],
        "La Rioja"=> {
            "Famatina"=> []
        },
        "Mendoza"=> {
            "Agrelo"=> [],
            "Barrancas"=> [],
            "Las Compuertas"=> [],
            "Lujan de Cuyo"=> [],
            "Lunlunta"=> [],
            "Maipu"=> [],
            "Perdriel"=> [],
            "San Martin"=> [],
            "San Rafael"=> [],
            "Uco Valley"=> {
                "Altamira"=> [],
                "La Consulta"=> [],
                "San Carlos"=> [],
                "Tunuyan"=> [],
                "Tupungato"=> [],
                "Vista Flores"=> []
            },
            "Ugarteche"=> [],
            "Vistalba"=> []
        },
        "Patagonia"=> {
            "Neuquen"=> [],
            "Rio Negro"=> []
        },
        "Salta"=> {
            "Cafayate - Calchaqui Valley"=> [],
            "Molinos"=> []
        },
        "San Juan"=> {
            "Pedernal Valley"=> [],
            "Tulum Valley"=> [],
            "Zonda Valley"=> []
        }
    }
}

class Hash
  def deep_traverse(target_key, &block)
    stack = self.map{ |k,v| [ [k], v ] }

    while not stack.empty?
      key, value = stack.pop
      yield(key, value)

      return key if key.include?(target_key)

      if value.is_a? Hash
        value.each{ |k,v| stack.push [ key.dup << k, v ] }
      end
    end
  end
end

def find_path_to_key(key, hash)
  hash.deep_traverse(key) do |k, v|
    # puts [k, v]
    k.include?(key)
  end
end

key = "Zonda Valley"
if path_to_key = find_path_to_key(key, hash)
  puts "Result:"
  puts path_to_key.to_s
else
  puts "No key found for #{key}"
end