in reply to Re: (Golf) Dependency List Prioritization
in thread (Golf) Dependency List Prioritization

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)},"

Replies are listed 'Best First'.
Re^3: (Golf) Dependency List Prioritization
by tadman (Prior) on Mar 14, 2002 at 21:19 UTC
    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.
[reply]
[d/l]

      No, sorry -- that is not good enough either. Given my test harness,

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

      [download]

      ... your code produces 'd','b','c','a','f','e', which fails to reflect that 'a' depends on 'e'.

      perl's sort() requires more information. It first compares the "f" and "e" elements -- and you have not produced for sort() any way for it to know which of these comes first. Your sort function returns 0 for $a="f" and $b="e", and perl's sort() arbitrarily places "f" before "e" -- wich is the wrong choice, since "e" must come before "a" must come before "f".

      So the sort() fails in the first test, and never recovers. You will have to implement something like this yourself in order to solve this -- perl's sort(), and indeed Perl's sort(), does not.

      One way to reveal your delusions to yourself before posting them here, is to add warnings to your sort functions (while testing) -- like so, for example:

      sub f {
%r=@_;map{$m{$_}={map{$m{$_}||={};$_=>1}@{$r{$_}}}}keys%r;
reverse sort{my$t=$m{$b}{$a}-$m{$a}{$b};warn"$a,$b:$t";$t}keys%m;
}

      [download]

      Now with your test harness I see these warnings (plus script name and line number ...):

      f,e:0 at ...
a,f:0 at ...
b,a:1 at ...
c,b:1 at ...
d,c:1 at ...

      [download]

      And so you can see that it is rather undefined how perl sorts "a" and "e" -- which is a poor sign, since "e" depends on "a" (this is with your test harness, remember). It is just dumb luck that it gets it "right".

      And yes, your problem has set me pondering old tricks with graph theory. I have yet to produce anything short that actually works.

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

[reply]
[d/l]
[select]

In Section Meditations