Re: How to get a ideal hash

In your post (OP) you specify that all numbers other than "-1" are "unique" - but what exactly do you mean? Do you mean that

each number appears only once on the left side of (x, y)?
do you mean that there is a unique path to each number except -1? That is, if we find $h{2}{6}{4} we will never find a sequence of pairs such that $h{7}{11}{6}{4}.

The two statements are quite different. Unless you are absolutely certain a priori that (2) is true, your algorithm is going to need to check for multiple paths to each number. Then you will have to decide whether those multiple paths are an error or not. Assuming that multiple paths to each number are an error, your code will need to keep track of each path found to each number.

I posted code below to illustrate the point, mainly as a contrast to BrowserUk's elegant solution. I do so with reservations. Bloodnok is right - it is considered bad form on Perl Monks to post a question without at least trying to show your own efforts. But BrowserUK is right too - the OP has posted a difficult problem. We aren't trying to be mean when we say do it yourself: it is just that we are donating our time so others can learn. Trying to solve the problem on your own is essential to really understanding the solution. For further discussion of the point, see The path to mastery.

use strict;
use warnings;
use YAML;

my $hIn= {
(4,-1),
(2,6),
(6,4),
(3,5),
(5,-1),
(99,-1),
};

my $hOut = {};

#keep track of the one and only path to each number
#except -1.
my %hPaths;

while (my ($k,$v) = each(%$hIn)) {

  # have we already found the path to $v
  # and if so do we have more than one path?
  my $aPath = $hPaths{$v};
  if ($aPath) {
    #value was already found - either warn about two paths
    #or patch its path so it starts with the key
    unless ($#$aPath == 0) {
      die "More than one path to <$v>: <@$aPath> and <$k $v>";
    }

    $hPaths{$v} = [ $k, @$aPath];
    $aPath = $hPaths{$k};
    if (!$aPath) {
      $hPaths{$k} = [ $k ];
    } elsif ($#$aPath != 0) {
      die "More than one path to <$k>: <@$aPath> and <$k>";
    }

    $hOut->{$k} = {$v => $hOut->{$v}};
    delete $hOut->{$v};
    next;
  }

  #find the path to $k
  $aPath = $hPaths{$k};
  $hPaths{$k} = $aPath = [ $k ] unless $aPath;

  #follow path to hash for key $k
  my $hNode=$hOut;
  my $i=0;
  $hNode=$hNode->{$aPath->[$i++]} while $i< $#$aPath;

  #add pair to hash
  if ($v == -1) {
    $hNode->{$k} = $v;
  } else {
    $hNode->{$k} = {$v=>{}};
    $hPaths{$v} = [ @$aPath, $v ];
  }
}

# a prettier dumper
print YAML::Dump($hOut);
[download]

Best, beth

Update: added my agreement with BrowserUk's observation about difficulty below.

Comment on Re: How to get a ideal hash Select or Download Code

Replies are listed 'Best First'.
Re^2: How to get a ideal hash by BrowserUk (Patriarch) on Apr 03, 2009 at 15:04 UTC
I do so with reservations. Bloodnok is right - it is considered bad form on Perl Monks to post a question without at least trying to show your own efforts. For simple problems I might agree, but this is decidely non-trivial. Should people refrain from asking if they have a difficult problem and have no idea how to start to solve it? Personally, I think this is an interesting problem, clearly defined and it deserved an answer. I also find that many of the "what have you tried" missives are self-serving. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply]
Re^3: How to get a ideal hash by dwm042 (Priest) on Apr 03, 2009 at 16:26 UTC
browserUk++. "What have you tried" but also "This looks like homework", which of course, begs the question of what classes someone may have had who is thoroughly self taught. I've answered questions others regarded as simple, trivial, or homework simply because I found the problem to be interesting. And who is to say what any individual finds interesting? Mikhail Tal, for one, delighted in chess problems designed for children.	[reply]
Re^3: How to get a ideal hash by Argel (Prior) on Apr 03, 2009 at 21:12 UTC
Looking at some of pysome's previous posts I'm guessing English is not his first language. That may be one reason why he limits what he asks in posts. In fact, it's probably less confusing for us if he does that. I think it's important that we keep in mind that we have people from other parts of the world and people from other professions. Certainly the question could have been presented better but that may be too much to ask of pysome. So kudos to you for finding it interesting enough to answer it! Elda Taluta; Sarks Sark; Ark Arks	[reply]
Re^4: How to get a ideal hash by pysome (Scribe) on Apr 07, 2009 at 02:36 UTC
you are right.;-) English is not my mother language. pls forgive my pool expression.	[reply]
Re^5: How to get a ideal hash by Argel (Prior) on Apr 09, 2009 at 21:39 UTC


P is for Practical
	PerlMonks