6
\$\begingroup\$

At some point, I bumped into an SO question asking how to implement Perl's trivial hash-of-hashes data structure in Java.

For those who don't know Perl, the hash value can be a scalar or another hash, or technically speaking hash reference. Arbitrary depth. Additional feature offered by Perl is autovivification - assigning an element 4 layers deep will automatically create correct hashes with proper keys 4 levels deep, without Java's need to assign hash object on level 1, then hash object on level 2 (being added to the first hash as a value) etc...

So, Perl code to assign a value to N-level hash at a known depth is

my $myHash; # initialization isn't required due to autovivification
$myHash->{$key1}->{$key2}->{$key3}->{$key4} = $value;

And to retrieve it

my $value = $myHash->{$key1}->{$key2}->{$key3}->{$key4};

The more generic code to assign a hash by arbitrary set of keys can be implemented by 5-10 line subroutine done properly; or 2-3 lines golf hack with eval.

Not being anywhere near a Java expert, my SO answer was ~30 lines of code that implemented a fixed-depth 3 level hash of hash of hashes.

Your mission, should you choose to accept it, is to produce the smallest code in a strongly typed language which implements Perl equivalent data structure which is a hashmap of hashmaps of ...; of arbitrary and non-uniform depth (basically, a tree); with hasmap keys being of String type; and leaf-level values String or Integer. The code should support 100% of what the Perl hash-of-hashes code does, including:

  • Retrieving a value based on a list of keys

  • Assigning a value based on a list of keys

    • As part of this, you should be able to replace a scalar leaf level node with an internal hashmap node, if your list of keys leads to that.

      E.g. set("val1","k1","k2");set("val2","k1","k2","k3") basically erases "val1" from existence after second call as it's replaced by a 3rd level hashmap.

The code should be resilient, e.g. no null exceptions etc... even for the bad input (simply return NULL)

You can use any strongly typed language other than Java, though I would personally prefer Java answers due to how/why this question originated.

Caveat: using some 3rd party library that implements equivalent of Perl hashes is NOT acceptable. 100% of the code must be using only the native core capabilities of the language.

\$\endgroup\$
  • 1
    \$\begingroup\$ Come to think of it, this would also be possible in Python and other weakly or dynamically typed languages that have a concept of classes. Would those be allowed as well? \$\endgroup\$ – Alex A. Mar 25 '16 at 3:32
  • \$\begingroup\$ @AlexA. - no, sorry. As I noted in my comment (now deleted), doing it in a language without strong typing (especially Perl-influenced ones like Python or Ruby) is too easy and basically defeats the purpose of the challenge. \$\endgroup\$ – DVK Mar 25 '16 at 3:45
  • \$\begingroup\$ Ah right, sorry. \$\endgroup\$ – Alex A. Mar 25 '16 at 3:54
  • \$\begingroup\$ Out of interest (since I wouldn't have used a strongly typed language) what's the result of get("k1", "k2") after the two set operations in the question? \$\endgroup\$ – Neil Mar 25 '16 at 9:15
  • \$\begingroup\$ You should add some test cases for people to ensure that their code works. \$\endgroup\$ – LegionMammal978 Mar 25 '16 at 10:55
2
\$\begingroup\$

Scala, 231 214 199 193 bytes

Immutability always wins! (turns out the long package name of collection.mutable.Map wasn't worth the hassle...)

class A{var a=Map[String,Any]()
def g(s:String*):Any={val y=s(0);if(s.size>1)g(y).asInstanceOf[A].g(s.drop(1):_*)else if(a.contains(y))a(y)else{a+=y->new A;a(y)}}
def s(s:String,v:Any)=a+=s->v}

Only thing that's problematic is the need to cast back to A... but having another method entirely that'd return a.type is actually longer (and with cannot be used).

Example:

val a = new A()
a.g("hey").asInstanceOf[A].s("foo", "bar")
a.g("hey").asInstanceOf[A].s("int", 3)
println(a.g("hey").asInstanceOf[A].g("foo"))
println(a.g("hey", "foo"))
println(a.g("hey", "int"))
a.s("hey", 42)
println(a.g("hey"))

Output:

bar
bar
3
42
\$\endgroup\$
1
\$\begingroup\$

C#, 215 bytes

class A:System.Collections.Generic.Dictionary<string,object>{public void B(string a,object b){if(ContainsKey(a))this[a]=b;else Add(a,b);}public dynamic C(string a){if(!ContainsKey(a))Add(a,new A());return this[a];}}

The class is named A. Use hash.B("key", "val"); to set a value, and hash.C("key"); to get a value. Nested keys can be achieved through, e.g., hash.C("k1").C("k2").C("k3").B("k4", "value");.

\$\endgroup\$
  • \$\begingroup\$ What is "dynamic" used for? I don't know C# enough to understand why it is required. \$\endgroup\$ – coredump Mar 25 '16 at 13:59
  • 1
    \$\begingroup\$ @coredump It's (from a quick look) used here as a 'generic type' that isn't known until its resolved in the runtime. We don't know what the function return type is, so let's return an unknown type :D \$\endgroup\$ – Yytsi Mar 25 '16 at 20:50
  • \$\begingroup\$ @TuukkaX I just used it so that it could be easily chained without having to cast objects back to As. \$\endgroup\$ – LegionMammal978 Mar 25 '16 at 21:03
  • \$\begingroup\$ @LegionMammal978 Oh. I see. Thanks for clarifying! \$\endgroup\$ – Yytsi Mar 25 '16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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