Problems? Is your data what you think it is? PerlMonks

### having fun with RE - was: Re: One Zero variants_without_repetition

by oha (Friar)
 on Aug 08, 2007 at 15:14 UTC ( #631326=note: print w/replies, xml ) Need Help??

in reply to One Zero variants_without_repetition

some fun, at least for me!
```\$_ = "00111";
do { print "\$_\n"; }
while ( s/(1*?)(0*?)01/\$2\${1}10/ );

00111
01011
10011
01101
10101
11001
01110
10110
11010
11100
Oha

edit: feel free to change \$2\${1}10 with \$2\$1\Q10 :-)

• Comment on having fun with RE - was: Re: One Zero variants_without_repetition

Replies are listed 'Best First'.
Re: having fun with RE - was: Re: One Zero variants_without_repetition
by oha (Friar) on Sep 21, 2007 at 13:08 UTC
i had some time, and just for fun i optimized the above RE: this is faster by avoiding alot of backtracking.
```\$_ = "00001111";
print "\$_\n" while (s/(1*)0(0*)1/\$2\${1}10/);
Oha
Re: having fun with RE - was: Re: One Zero variants_without_repetition
by wind (Priest) on Aug 13, 2007 at 18:46 UTC
Using the same algorithm approach, but reversing the output:
```\$_ = "11100";
do { print "\$_\n"; }
while ( s/(.*)10(0*)(1*)/\${1}01\$3\$2/ );

11100
11010
11001
10110
10101
10011
01110
01101
01011
00111
- Miller
Re: having fun with RE - was: Re: One Zero variants_without_repetition
by thenetfreaker (Friar) on Aug 08, 2007 at 18:07 UTC
You couldn't have been more understanding :)
that the shortest and the code the strikes right in the dot.
though i feel extremly sad to agree with ohcamacj and admit my failure that i won't live long enough to see it finish with that much ones and zeroes.

originally i was trying to make an de/coder that reads some bytes from a file, for every 26 bytes (at least) counts how many zeroes and one are there and the MD5 of the original binary string( of 26*8 bits) and writes it to a new file in the format of (for every previouse 26 bytes) "\$ones,\$zeroes,MD5x16\n"
then when it should decode the new file, it reads every string, checks for all the possibilities of strings containing these numbers of 1's and 0's checking their MD5 comparing it to the read one, if it fits it writes the original file by printing the ord('B8', \$every_8_ones_or_zeroes_after_split) .

but now i understand i'll wait forever to decode few bytes.

P.S.: the beauty of such a compression, is first that it's a some sort of logic interpretation of almost random strings( of 1/0), and secondly, i can compress the compressed file until i reach it's minimal length (<= 26).
first, my regex is not perfect, there are ways to make it faster (making it greedy and starting only from start is a good start). but anyway it's slow.

regarding what you are going to do: first you want to use a 16bit MD5 and the count of ones and zeros. the worst case is having all 26 ones or zeroes, so you need 5 bits for that information: that mean for 26 bit of data, you'll get 5+16 bit result. that's about 20% compression.

unfortunately, you can't guarantee that for a given MD5 and number of ones, you'll have only 1 possibile 26bit data. you could analize it and findout how many case you can have at worst and i fear it's more then 32 (if it was 32, you had need another 5bit and the total of data would be 26)

Oha

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://631326]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?