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

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
  • Download Code

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/);
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)