Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Re (tilly) 1: (Golf) Fragment Reassembly

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


in reply to Re (tilly) 1: (Golf) Fragment Reassembly
in thread (Golf) Fragment Reassembly

I had considered explicitly stating that solutions such as yours, which iterate through all possible strings, would be rated in a seperate class. This makes me wonder, however, if there is a class of optimization problems for which iterating brute-force through the entire solution space is faster (algorithmically) than directly computing a solution.

You are a bit mistaken in choosing Golf: Embedded In Order, however, since that is not the same thing as a substring:

print assemble(qw(oa af wf wa)); # owaf - a wrong answer # oafwfwa - a right answer
If you change that into an index, things work out bettter (and with less code):
sub c{@r='';@r=map{$c=$_;map$c.$_,@r}@_ for 1..shift;@r} sub assemble { my$n;{for(c($n++,map{split//}@_)){$v=$_;map{1+index$v,$_ or next}@_;re +turn$_}redo} } print assemble(qw(oa af fa afa));
   MeowChow                                   
               s aamecha.s a..a\u$&owag.print


Comment on Re: Re (tilly) 1: (Golf) Fragment Reassembly
Select or Download Code
Re(tilly) 3: (Golf) Fragment Reassembly
by tilly (Archbishop) on May 03, 2001 at 06:14 UTC
    Oops, my misreading.

    As for the question, there actually are well-explored areas where the best known algorithms (by various criteria) are found by randomly guessing something with certain characteristics and then testing whether it really was a solution...

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (12)
As of 2015-07-07 00:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (85 votes), past polls