in reply to (Golf) Fragment Reassembly
I am surprised that nobody pointed out how this is related
to Golf: Embedded In Order and (Golf) Ordered Combinations. From there we can define
two helper functions:
which have bodies of 34 and 49 respectively. Plus 14 for the surrounding pieces. So we are at 97 characters. And then it is easy to finish off withsub c{@r='';@r=map{$c=$_;map$c.$_,@r}@_ for 1..shift;@r} sub i{($t=pop)=~s/./.*\Q$&/gs;pop=~/$t/s}
whose body has 76 characters for 173 characters. (Note that I added 5 characters to allow it to be called twice without retaining state.)sub assemble { my$n;{for(c($n++,map{split//}@_)){$v=$_;map{i($v,$_)||next}@_;return$_ +}redo} }
This is a theoretically correct solution, but be warned that it is not polynomial either in speed or memory requirements. So it isn't a very useful solution.
In fact it raises questions about what a solution is. This will not run on my machine with either of the original data sets. I do not have such a machine to test on, but I do not believe that even if you try to compile Perl on a 64-bit machine with a very large amount of memory that it will succeed. So while the algorithm is fine on paper, it cannot work on the stated data set.
Is a correct algorithm that will not finish on practical machines considered a solution?
My test data is:
which cheerfully finds "owaf" as its answer.print assemble(qw(oa af wf wa));
In Section
Meditations