develooper Front page | perl.fwp | Postings from July 2003

RE: Was Fun - Each character at most once

July 25, 2003 12:17
RE: Was Fun - Each character at most once
Message ID:
From: Adam Rice [] 
> Quoting A. Pagaltzis (
> > 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

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
	$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. 


PS.  Anyone for a up a UniqPerl@home 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

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. Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About