深くネストされたハッシュのチェーンを見つける

Question

メソッド#find_chainsで次のクラスが与えられた場合、問題は与えられたkey_to_findにつながるすべてのチェーンを見つけることです。

class HashDeepUtils 
    def initialize(hash) 
    @hash = hash 
    @chains = [[]] 
    end 

    def find_chains(key_to_find) 
    if hash.has_key?(key_to_find) 
     @chains[0] << key_to_find 
     @chains.unshift([]) 
    else 
     @hash.each_key do |key| 
     deep_utils = HashDeepUtils.new(@hash[key]) 
     probable_chains = deep_utils.find_chains(key_to_find) 
     if probable_chains.any? 
      @chains[0] << key 
      @chains[0] += probable_chains[0] 
     end 
     end 
    end 

    return @chains 
    end 
end 

以下のテストは、この動作をテストするために私が作成しました。

class TestChainFinding < Minitest::Test 
    def test_finds_single_chain 
    hash = {test: 'test'} 
    deep_utils = HashDeepUtils.new(hash) 
    assert_equal [[:test]], deep_utils.find_chains(:test) 
    end 

    def test_finds_nested_chain 
    hash = {test: {foo: 'bar'}} 
    deep_utils = HashDeepUtils.new(hash) 
    assert_equal [[:test, :foo]], deep_utils.find_chains(:foo) 
    end 

    def test_finds_multiple_nested_chains 
    hash = {test: {foo: 'bar'}, foo: 'baz'} 
    deep_utils = HashDeepUtils.new(hash) 
    assert_equal [[:test, :foo], [:foo]], deep_utils.find_chains(:foo) 
    end 
end 

Answer 1

あなたは絶対に不要なクラスを作成することによってOOPを悪用しています。

Answer 2

def chains(hash, key, path = [], memo = []) 
    hash.each_with_object(memo) do |(k, v), acc| 
    memo.push(path + [k]) if k == key 
    chains(v, key, (path + [k]), memo) if v.is_a?(Hash) 
    end 
end 

hash = {test: {foo: 'bar'}, foo: 'baz'} 
chains(hash, :foo) 
#⇒ [[:test, :foo], [:foo]] 

chains({test: {foo: {baz: 'baz', foo: 'foo'}}, foo: 'foo'}, :foo) 
#⇒ [[:test, :foo], [:test, :foo, :foo], [:foo]] 

再帰的方法

def chains(hash, key) 
    hash.each_with_object([]) do |(k,v), arr| 
    arr.concat([[k]]) if k == key 
    if v.is_a?(Hash) 
     a = chains(hash[k], key) 
     arr.concat(a.map { |b| [k, *b] }) unless a.empty? 
    end 
    end 
end 

例

chains({ test: {foo: 'bar'}, foo: 'baz' }, :foo) 
    #=> [[:test, :foo], [:foo]] 

chains({ test: { foo: { baz: 'baz', foo: 'foo' } }, foo: 'foo' }, :foo) 
    #=> [[:test, :foo], [:test, :foo, :foo], [:foo]] 

説明

：純粋な再帰関数は、完全にタスクを解決します

putsステートメントを挿入して、再帰的メソッドで実行されるステップと計算を表示しました。

def chains(hash, key, lvl=0) 
    level_indent = ' '*(4*lvl) 
    loop_indent = ' '*(4*lvl + 2) 
    puts "\n#{level_indent}lvl=#{lvl}" 
    puts "#{level_indent}entered chains(#{hash}, #{key})" 
    puts "#{level_indent}hash=#{hash}" 
    hash.each_with_object([]) do |(k,v), arr| 
    puts "#{loop_indent}k=#{k}, v=#{v}, arr=#{arr}" 
    puts "#{loop_indent}#{k}==#{key} is #{k==key}" 
    arr.concat([[k]]) if k == key 
    puts "#{loop_indent}arr=#{arr}" if k == key 
    puts "#{loop_indent}#{v}.is_a?(Hash) = #{v.is_a?(Hash)}" 
    if v.is_a?(Hash) 
     puts "#{loop_indent}calling chains(#{hash[k]}, #{key}, #{lvl+1})" 
     a = chains(hash[k], key, lvl+1) 
     puts "#{loop_indent}a=#{a} returned from lvl #{lvl+1}" 
     puts "#{loop_indent}a.map { |b| [k, *b] }= #{a.map { |b| [k, *b] }}" 
     arr.concat(a.map { |b| [k, *b] }) unless a.empty? 
     puts "#{loop_indent}arr=#{arr}" 
    end 
    end 
end 

chains({ test: {foo: 'bar'}, foo: 'baz' }, :foo) 
    # lvl=0 
    # entered chains({:test=>{:foo=>"bar"}, :foo=>"baz"}, foo) 
    # hash={:test=>{:foo=>"bar"}, :foo=>"baz"} 
    # k=test, v={:foo=>"bar"}, arr=[] 
    # test==foo is false 
    # {:foo=>"bar"}.is_a?(Hash) = true 
    # calling chains({:foo=>"bar"}, foo, 1) 

#  lvl=1 
    #  entered chains({:foo=>"bar"}, foo) 
    #  hash={:foo=>"bar"} 
    #  k=foo, v=bar, arr=[] 
    #  foo==foo is true 
    #  arr=[[:foo]] 
    #  bar.is_a?(Hash) = false 

# a=[[:foo]] returned from lvl 1 
    # a.map { |b| [k, *b] }= [[:test, :foo]] 
    # arr=[[:test, :foo]] 
    # k=foo, v=baz, arr=[[:test, :foo]] 
    # foo==foo is true 
    # arr=[[:test, :foo], [:foo]] 
    # baz.is_a?(Hash) = false 
    #=> [[:test, :foo], [:foo]] 

chains({ test: { foo: { baz: 'baz', foo: 'foo' } }, foo: 'foo' }, :foo) 
    # lvl=0 
    # entered chains({:test=>{:foo=>{:baz=>"baz", :foo=>"foo"}}, :foo=>"foo"}, foo) 
    # hash={:test=>{:foo=>{:baz=>"baz", :foo=>"foo"}}, :foo=>"foo"} 
    # k=test, v={:foo=>{:baz=>"baz", :foo=>"foo"}}, arr=[] 
    # test==foo is false 
    # {:foo=>{:baz=>"baz", :foo=>"foo"}}.is_a?(Hash) = true 
    # calling chains({:foo=>{:baz=>"baz", :foo=>"foo"}}, foo, 1) 

#  lvl=1 
    #  entered chains({:foo=>{:baz=>"baz", :foo=>"foo"}}, foo) 
    #  hash={:foo=>{:baz=>"baz", :foo=>"foo"}} 
    #  k=foo, v={:baz=>"baz", :foo=>"foo"}, arr=[] 
    #  foo==foo is true 
    #  arr=[[:foo]] 
    #  {:baz=>"baz", :foo=>"foo"}.is_a?(Hash) = true 
    #  calling chains({:baz=>"baz", :foo=>"foo"}, foo, 2) 

#   lvl=2 
    #   entered chains({:baz=>"baz", :foo=>"foo"}, foo) 
    #   hash={:baz=>"baz", :foo=>"foo"} 
    #   k=baz, v=baz, arr=[] 
    #   baz==foo is false 
    #   baz.is_a?(Hash) = false 
    #   k=foo, v=foo, arr=[] 
    #   foo==foo is true 
    #   arr=[[:foo]] 
    #   foo.is_a?(Hash) = false 

#  a=[[:foo]] returned from lvl 2 
    #  a.map { |b| [k, *b] }= [[:foo, :foo]] 
    #  arr=[[:foo], [:foo, :foo]] 

# a=[[:foo], [:foo, :foo]] returned from lvl 1 
    # a.map { |b| [k, *b] }= [[:test, :foo], [:test, :foo, :foo]] 
    # arr=[[:test, :foo], [:test, :foo, :foo]] 
    # k=foo, v=foo, arr=[[:test, :foo], [:test, :foo, :foo]] 
    # foo==foo is true 
    # arr=[[:test, :foo], [:test, :foo, :foo], [:foo]] 
    # foo.is_a?(Hash) = false 
    #=> [[:test, :foo], [:test, :foo, :foo], [:foo]]