From: Adam Rice [mailto:[EMAIL PROTECTED]
> Quoting A. Pagaltzis ([EMAIL PROTECTED]):
> > I don't see the problem. You have 36 (or 120) pairs or encoded
> > characters to allocate, and up to that many input characters. Looks
> > like just one straightforward mapping.
>
> The problem is that there are
> 371993326789901217467999448150835200000000
> possible arrangements of the 36 characters. If most of those
> work then you'll find one pretty quickly, but if there's only
> one solution, it'll take something like a million million
> million million years to find it with a brute force approach.
> I've thought of some ways of making a brute-force approach a
> bit smarter and reduce the search space a bit, but I haven't
> found a quick way of determining if there's a solution or
> not. For now, the only way to determine that something like
>
> print"............................."
>
> is unencodable is to try every possible arrangement of characters.
There's still a few more gotcha's to consider
1) How do you check if the code you are about to test doesn't execute `sudo
rm -R *` or some other malicious code instead of printing your desired
output.
2) What about the Touring problem? Many of your possible test code will
generate infinite loops (not to mention syntax errors). Touring proved you
can't write a program to check if another program will halt on a given
input. So you'd need to run all the tests in parallel to ensure you don't
get stuck.
3) Which leads on to another problem. If there is a valid solution will you
find it in time. Suppose the only encoding which is valid turns out to be
something that evals this string;
sleep 1e1000;print "."x29
or
$n++ while( substr($PI, $n, 10) eq '1234567890');print "."x29
# Anyone know if the decimal expansion of pi has 1234567890 as a
substring yet?
Given what the aliens in the golf list can do in 36 bytes, I can't imagine
what wonders a brute force algorithm would do ;-)
.... It'll all end in tears I tell you.
Alistair
PS. Anyone for a up a [EMAIL PROTECTED] program :-)
-----------------------------------------------------------------------
Registered Office:
Marks & Spencer p.l.c
Michael House, Baker Street,
London, W1U 8EP
Registered No. 214436 in England and Wales.
Telephone (020) 7935 4422
Facsimile (020) 7487 2670
www.marksandspencer.com
Please note that electronic mail may be monitored.
This e-mail is confidential. If you received it by mistake, please let us know and
then delete it from your system; you should not copy, disclose, or distribute its
contents to anyone nor act in reliance on this e-mail, as this is prohibited and may
be unlawful.
The registered office of Marks and Spencer Financial Services PLC, Marks and Spencer
Unit Trust Management Limited, Marks and Spencer Life Assurance Limited and Marks and
Spencer Savings and Investments Limited is Kings Meadow, Chester, CH99 9FB. These
firms are authorised and regulated by the Financial Services Authority.
