Re^3: (Golf) Dependency List Prioritization

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.

Comment on Re^3: (Golf) Dependency List Prioritization Download Code

Replies are listed 'Best First'.
Re: Re^3: (Golf) Dependency List Prioritization by Sidhekin (Priest) on Mar 15, 2002 at 15:39 UTC
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]

Replies are listed 'Best First'.

Re: Re^3: (Golf) Dependency List Prioritization
by Sidhekin (Priest) on Mar 15, 2002 at 15:39 UTC

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]