sub f {
my%s;%r=@_;map{$m{$_}={map{$m{$_}||={};$_=>1}@{$r{$_}}}}keys%r;
reverse sort{($a->{$b})-($b->{$a})}keys%m;
}
[download]

#!/usr/bin/perl

my @list = (
     a => [ 'b', 'c' ],
     b => [ 'c', 'd' ],
     c => [ 'd' ],
     e => [ 'b', 'a' ],
     f => undef,
);

print join (',', map { "'$_'" } f(@list)),"\n";
[download]

'd','c','b','a','f','e'

This looks more like obfuscation to me. You declare a lexical that you don't use, and you use symbolic references ... and so your solution does not hold. Try this test harness:

my @list = (
     a => [ 'r', 'c' ],
     r => [ 'c', 'd' ],
     c => [ 'd' ],
     e => [ 'r', 'a' ],
     f => undef,
);
[download]

... and you get the following list:

'd','r','c','a','f','e'

And of course, everything is even more undefined if any of your components are called '^H', 'INC, 'ENV', or 'SIG' :-)

Update: Is this a trick? Could tadman not wait until April 1st? It seems to me no other test harness will give the right answer here. The sort function always returns 0, since those hashes it access has never been set ... :-\

Nice choice of test harness, tadman!

The Sidhekin
print "Just another Perl ${\(trickster and hacker)},"

Coincidence, I assure you. It was an error when I golfified my original solution, which was structured a little differently internally allowing for the larger amount of data stored within the hash.

Though it is funny that it worked out perfectly. The example I used was one that I was working through by hand on paper just to make sure it matched.

Perhaps this is more appropriate:

sub f {
%r=@_;map{$m{$_}={map{$m{$_}||={};$_=>1}@{$r{$_}}}}keys%r;
reverse sort{$m{$b}{$a}-$m{$a}{$b}}keys%m;
}
[download]

Which is an increasingly disappointing 101 characters.

Thanks for pointing out the nature of my delusions.

I'm hoping that this isn't more complicated than, say, (Golf) Shortest Graph Distance.

sub f{
#23456789_123456789_123456789_123456789_123456789_123456789_123456789_
+123456789_123456789_123456789_123456789_123456789_123456789_123
%h=@_;$h{$_}||=[]for map@$_,values%h;for(@k=keys%h){for$x(@k){push@{$h
+{$x}},@{$h{$_}}for@{$h{$x}}}}sort{-1+2*grep$_ eq$b,@{$h{$a}}}@k
}
[download]

When I finally came up with something "workable", I had my doubts about it, though I wasn't sure exactly why. It did work on my test data, both as posted, and as used, though for reasons that must surely be "dumb luck".

Following the chain is exactly what I was missing out on. Thanks for pointing that out.

can you please list a solid example input and output and give the reasons why the output is associated with the input? Looking at what you have, it doesn't look like that sample output would be matched with that input, but it could be. And if it was, i would have no idea why, as i've never dealt with such lists before. Also i haven't installed PSI::ESP so i don't know what you mean by 'ordered by precedence'.

Please advise,
jynx

Maybe a little more verbosity would help.

To speak in terms of Perl, if you have a module Foo which requires module Bar to operate, then there is a dependency. Bar must be installed before Foo. In some cases, such as with RPM, you just can't install Foo until Bar is in place. With Perl, you can install Foo, but it will fail, as it is missing its beloved Bar, and your program won't run.

Maybe Foo also needs the module Baz to run, so that is a second dependency. If you also had a Foo::Bar module, which needed Foo, then you have a second dependency. Perhaps Bar also needs something, say, Fubar, to do its thing.

This leads to a dependency structure that looks like this:

my %dep = (
     'Foo'      => [ 'Bar','Baz' ],
     'Foo::Bar' => [ 'Foo' ],
     'Bar'      => [ 'Fubar' ],
);
[download]

Now the idea is to, based on this specification, figure out what order they can be installed in such that each module is only installed when all of its dependencies are satisfied. One such order is:

'Fubar','Bar','Baz','Foo','Foo::Bar'

If you install them in this order, there should be no problems. An invalid ordering would be something like:

'Fubar','Foo','Bar','Baz','Foo::Bar'

In this case Foo does not have either Bar or Baz available, so it can't work. Foo must come after both Bar and Baz.

To answer a question, the order of the dependencies is not relevant. If Foo requires Bar and Baz, you can list Bar and Baz in any order. After all, they just have to be present and accounted for. Apart from that, nothing else matters. This means that the following are equivalent:

'a' => [ 'b','c' ]
'a' => [ 'c','b' ]
[download]

These both specify that 'a' requires 'b' and 'c'. It's like saying that a 'car' needs 'gas' and 'tires' to run. As long as you have both, you're good to go. Procedure is irrelevant, as you're not going anywhere until both are present anyway.

What's interesting about this problem is that at first, it seems quite difficult to solve, but with a bit of creative thinking it was really straightforward. It seems to be a matter of perspective.

Thanks for making such an accessible golf problem (at least it feels so to me). here's 116 (my first golf):

sub f{my%h=@_;for(values %h){for(@$_){$h{$_}=[]if!$h{$_}}}
print join(', ',sort{(grep /^$b$/,@{$h{$a}})?1:-1}keys%h)}
[download]

sub f{%h=@_;for(values %h){for(@$_){$h{$_}=[]if!$h{$_}}}
sort{(grep /^$b$/,@{$h{$a}})?1:-1}keys%h}
[download]

I think i'm getting the hang of this. Here's 90:

sub f{%h=@_;for(values %h){for(@$_){$h{$_}||=[]}}
sort{(grep /^$b$/,@{$h{$a}})?1:-1}keys%h}
[download]

Nice idea.

A few minor nits though. First is that it is customary to only count the body of the sub, so you actually did slightly better than you thought! A second minor issue is that your grep is not quite right - the string "fooey\n" will match /^fooey$/ so you don't really have an equality test.

Further than that, there are some mechanical tricks that can be used to improve scores. Such as using an inline for loop, using map to avoid double loops, and the like. Using those I can take your answer to 75 fairly easily:

sub f{
#23456789_123456789_123456789_123456789_123456789_123456789_123456789_
+12345     
%h=@_;$h{$_}||=[]for map@$_,values%h;sort{-1+2*grep$_ eq$b,@{$h{$a}}}k
+eys%h     
}
[download]

UPDATE
Oops. I didn't notice the lack of transitivity in your code. This is a fatal flaw as you see with the following data set.

my @list = (
  a => ['b'],
  b => ['c'],
  c => ['d'],
  d => ['e'],
);
[download]

Assuming the test harness provided, I doubt anyone can beat this:

sub f{d,c,b,a,f,e}
[download]

Try this for a test harness:

my @list = (
     a => [ 'b', 'c', 'e' ],
     b => [ 'd' ],
     c => [ 'b', 'd' ],
     f => [ 'a' ],
);
print join (',', map { "'$_'" } f(@list)),"\n";
[download]

Your code produces 'd','b','c','f','e','a', which does not reflect the fact that 'f' depends on 'a'.

So, I am afraid your solution holds only for a limited set of test harnesses -- and is certainly not the shortest among such solutions.

The Sidhekin
print "Just another Perl ${\(trickster and hacker)},"

I hope you don't mind me removing a few bytes:

sub f{for(values(%h=@_)){$h{$_}||=[]for@$_}sort{(grep/^$b$/,@{$h{$a}})
+||-1}keys%h}
[download]

(Note: I didn't test)

U28geW91IGNhbiBhbGwgcm90MTMgY
W5kIHBhY2soKS4gQnV0IGRvIHlvdS
ByZWNvZ25pc2UgQmFzZTY0IHdoZW4
geW91IHNlZSBpdD8gIC0tIEp1ZXJk

Okay, after having complained that other people's solutions don't work, at last I have a reasonably short version of my own. 113 characters:

sub f{
#       10        20        30        40        50        60        70
+        80        90       100       110
#23456789.123456789.123456789.123456789.123456789.123456789.123456789.
+123456789.123456789.123456789.123456789.123
my%r;%i=@_;@{$r{$_}}{map{$_,keys%{$r{$_}}}@{$i{$_}}}=0for(@i=keys%i)x@
+i;sort{keys%{$r{$a}}<=>keys%{$r{$b}}}keys%r
}
[download]

I think it will work on all correct data, but localtime is 02:20, which tends to leave me vulnerable, so I might have a different opinion in the morning. One thing I shall probably see in the morning is how to shorten that sort block. :-\

Update:Told you I'd shorten it -- at 111 characters:

sub f{
#       10        20        30        40        50        60        70
+        80        90       100       110
#23456789.123456789.123456789.123456789.123456789.123456789.123456789.
+123456789.123456789.123456789.123456789.1
sub Q{keys%{$_[0]}}my%r;%i=@_;@{$r{$_}}{map{$_,Q$r{$_}}@{$i{$_}}}=0for
+(@i=Q\%i)x@i;sort{Q($r{$a})- Q$r{$b}}Q\%r
}
[download]

The Sidhekin
print "Just another Perl ${\(trickster and hacker)},"

sub f {
$h{$_}||=[]for map@$_,%h=@_;sub x{my$x=1;$x+=x($_)for@{@h{@_}||[]};$x}
+sort{x($a)<=>x$b}keys%h
}
[download]

sub f {
  $h{$_}||=[]for map@$_,%h=@_;
  sub x {
    my$x=1;
    $x+=x($_)for@{@h{@_}||[]};
    $x
  }
  sort{x($a)<=>x$b}keys%h
}
[download]

  sub x {
    1,map{x($_)}@{@h{@_}||0}
  }
[download]