Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: (Golf) Minimizing the Bacon Number

by MeowChow (Vicar)
on May 14, 2001 at 23:08 UTC ( #80295=note: print w/ replies, xml ) Need Help??


in reply to (Golf) Minimizing the Bacon Number

Damn you and your NP-complete problems! =) Well, I'm lazy, and decided to implement a greedy, suboptimal heuristic:

sub bacon { my%t=@_;(sort{@{$t{$b}}<=>@{$t{$a}}}keys%t)[0] }
At least it's fast, if not correct. :)
   MeowChow                                   
               s aamecha.s a..a\u$&owag.print


Comment on Re: (Golf) Minimizing the Bacon Number
Download Code
Re: Re: (Golf) Minimizing the Bacon Number
by Masem (Monsignor) on May 14, 2001 at 23:35 UTC
    This problem shouldn't be NP-complete. A well-rounded algorithm is going to be, I believe, O(N^2) or O(N^3). However, the golf solution will probably be NP.
    Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
      Sorry to ask but my curiosity is too big...
      What is NP (or NP-complete) ?
      Thanks.

      BobiOne KenoBi ;)


        An NP problem is a programming problem that can only be solved by the theoretical nondeterministic Turing machine (NP stands for Nondeterministic Polynomial). An NP-Complete problem has the property that if you can find a polynomial running time solution to this problem than you can find a polynomial solution to all other NP problems as well. Unfortunately, that works both ways, if you prove that there is no polynomial solution to the problem than all other NP problems don't have a polynomial runtime as well.

        For more information, look here.

        Hope This Helps,
        jynx

        Update: D'oh! Beaten by MeowChow...

        Search Google: NP-complete

        Update: Didn't see the above posts...whoops.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://80295]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (9)
As of 2014-08-01 10:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Who would be the most fun to work for?















    Results (0 votes), past polls