Prog Battle: Round 1

[thetan]

I've played this game at other challenge sites in the past and i'd like to start it off here.

So this is a series of programming challenges that have no definitive answer. Anyone is welcome to submit solutions at any time, there are no winners and losers just good times and lulz. Challenges will progressively get more challenging over time.

You get points for creativity, for efficiency and for having fun.

Round 1 - Compression
This round asks you to create a primitive compression algorithm. Specifically an algorithm that takes a string of characters and reduces it such that all recurring characters are represented as the character prefixed by the repetition count. If the repetition count is 1, then the repetition count should be omitted for that character

IE:

Code: Select all

print compress("aaabbccdefffgg");
// would output 3a2b2cde3f2g


Also, you must write an accompanying decompression algorithm one that would take the compressed string and restore it to it's original form.

Such that:

Code: Select all

print decompress("3a2b2cde3f2g");
// would output aaabbccdefffgg


With that said, welcome to fight club


Let the fun begin.

[Bren2010]

w00t! First done!

Code: Select all

<?php
function compress($string) {
   $string = str_split($string);
   
   array_push($string, NULL);
   
   $currChar = $string[0];
   $count = -1;
   $answer = '';

   foreach ($string as $char) {
      if ($char == $currChar) {
         ++$count;
      } else {
         if ($count > 0) {
            $answer .= ($count + 1);
         }
         
         $answer .= $currChar;
         $count = 0;
      }
      
      $currChar = $char;
   }
   
   return $answer;
}

function decompress($string) {
   $string = str_split($string);
   $iterateArray = array();
   $bit = "";
   
   foreach ($string as $char) {
      if (!ctype_digit($char)) {
         $bit .= $char;
         array_push($iterateArray, $bit);
         $bit = '';
      } else {
         $bit .= $char;
      }
   }
   
   $answer = '';
   
   foreach ($iterateArray as $numChar) {
      $len = strlen($numChar);
      
      if ($len == 1) {
         $answer .= $numChar;
      } else {
         $char = substr($numChar, -1, 1);
         $num = substr($numChar, 0, -1);
         $i = 1;
         
         for ($i = 1;$i <= $num;++$i) {
            $answer .= $char;
         }
      }
   }
   
   return $answer;
}

print "Compression:\nFound:  " . compress("aaabbccdefffgg") . "\nRight:  3a2b2cde3f2g\n\nDecompression:\nFound:  " . decompress("3a2b2cde3f2g") . "\nRight:  aaabbccdefffgg\n";
?>

[OnlyHuman]

Well, I was already beat on the PHP angle, so here's a crude RLE in C++

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
#include <ctype.h>

template <class T>
std::string toStr(T t)
{
   std::stringstream tmp;
   tmp << t;
   return( tmp.str() );
}

std::string compress(std::string str)
{
   std::string result = "";

   for(int i = 0; i < str.size(); i++)
   {
      int count = 0;
      int p = i;

      while( str[i] == str[p++] )
      {
         count++;
      }

      if( count > 1 )
      {
         result += toStr( count );
         result += str[i];
         i += (count -1);
      }
      else
      {
         result += str[i];
      }
   }

   return( result );

}

std::string decompress(std::string str)
{
   std::string result = "";

   for(int i = 0; i < str.size(); i++)
   {
      int count = 0;
      if( isdigit( str[i] ) )
      {
         sscanf(&str[i],"%d",&count);

         for(int j = 0; j < count-1; j++)
            result += str[i+1];
      }
      else
      {
         result += str[i];
      }
   }

   return( result );

}

int main()
{

   std::cout << compress("aaabbccdefffgg") << std::endl;
   std::cout << decompress("3a2b2cde3f2g") << std::endl;
   return(0);

}


And again in C.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <memory.h>

void compress(char *dst, char *src)
{
   int i = 0;
   char c, t;

   while( *src )
   {
      i = 0;
      c = *src;

      do
      {
         i++;

      }while( c == *(++src) );

      if( i > 1 )
      {
         t = i + 0x30;
         strncat(dst,&t,1);
         strncat(dst,&c,1);
      }
      else
      {
         strncat(dst,&c,1);
      }

   }

}

void decompress(char *dst, char *src)
{
   int count = 0;
   char c;

   while( *src )
   {
      if( isdigit(*src) )
      {
         sscanf(src,"%d",&count);
         c = *(++src);
         while( (--count) > 0 )
         {
            strncat(dst,&c,1);
         }
      }
      else
      {
         c = *(src++);
         strncat(dst,&c,1);
      }
   }
}

int main()
{
   char  result1[255];
   char  result2[255];

   char  test1[] = "aaabbccdefffgg";
   char  test2[] = "3a2b2cde3f2g";

   memset((void*)&result1[0],0,255 * sizeof(char));
   memset((void*)&result2[0],0,255 * sizeof(char));

   compress(result1,test1);
   decompress(result2,test2);

   printf("%s\n%s\n",result1,result2);

   return(0);
}


Damn this was fun. Maybe too fun though.
I somehow feel compelled to keep going on this same one until I've absolutely mastered it.

[thetan]

Here are my php one liners for RLE meant to be ran from CLI

rle-compress.php

Code: Select all

<?php
echo preg_replace('/(.)(\1+)/e', 'strlen(\'\2\')+1 . \'\1\'', $argv[1]) . "\n";


rle-decompress.php

Code: Select all

<?php
echo preg_replace('/([0-9]+)([a-zA-Z])/e', 'implode(array_fill(0, \1, \'\2\'))', $argv[1]) . "\n";


[Goatboy]

Let's take this one step further. Compress this string: aa77abb5ccdefff111gg
Tiny step further than that: Determine the compression ratio (should be pretty trivial).

Thetan, let me know if my suggestions are bastardizing the spirit of the game.

[Assassian360]

Let's take this one step further. Compress this string: aa77abb5ccdefff111gg
Tiny step further than that: Determine the compression ratio (should be pretty trivial).

Thetan, let me know if my suggestions are bastardizing the spirit of the game.

If you're going to start looking at compression ratio. Wouldn't it be better to have a variety of different strings, perhaps of varying lengths too? Or just one much larger one. Otherwise the amount you can do to compress is quite minimal unless the compression code uses a data dictionary that matches exactly what is there.

[Goatboy]

The flaw in your logic is that you are thinking about that string as the challenge. The implied challenge was to modify the code to be able to handle numbers as well as letters in the string. The string was only an example; it could very easily be extended out to 500+ characters.

[OnlyHuman]

How should the ratio be expressed? Should it be a comparison of the length of the input string vs. that of the output string, or a sum of the savings offered by compressing an individual run of identical characters? I could see it going a few different ways here, though given that the encoded characters still consume space in the output string, the first seems more accurate.

[Goatboy]

That's part of the challenge. Implement your own algorithm.

[OnlyHuman]

Okay, well the ratio was super easy, at least for me. But, the possibility of back-to-back digits left me in the need of a pivot. Sort of like the way RLE is implemented for PCX images (i.e. if value > predefined then it's the REAL value and not a run). For the pivot, I chose 5, since it only appears once in Goatboy's challenge string. The only problem with this is, it fails to compress runs of the character '5'. So, a string like "aa77abb555ccdefff111gg", will compress to "2a27a2b5552cde3f312g" instead of "2a27a2b352cde3f312g". I suppose a look ahead parser, coupled with some additional branching could have made it possible without the pivot, but come on man, this is round 1.

Code: Select all

#include <stdio.h>
#include <memory.h>

float compress(char *dst, char *src)
{

   int i = 0;
   char c, t;

   char *pdst = dst;
   char *psrc = src;

   float ratio = 0.0f;

   if( (pdst != NULL) && (psrc != NULL) )
   {

      while( *psrc )
      {

         i = 0;
         c = *psrc;

         do
         {
            i++;

         }while( c == *(++psrc) );

         if( c == 0x35 )
            psrc -= (i - 1);

         if( (i > 1) && (c != 0x35) )
         {
            t = i + 0x30;
            *(pdst++) = t;
            *(pdst++) = c;
         }
         else
         {
               *(pdst++) = c;
         }

      }

   }

   i = psrc - src;

   if( i != 0 )
      ratio = (float)i / (float)(pdst - dst);

   return( ratio );

}

void decompress(char *dst, char *src)
{

   int  d = 0;
   char c;

   if( (dst != NULL) && (src != NULL) )
   {

      while( *src )
      {

         c = *src;

         if( (c <= 0x39) && (c >= 0x30) && (c != 0x35) )
         {

            d = (c ^ 0x30);
            c = *(++src);

            do
            {
               *(dst++) = c;

            }while( (--d) > 0 );

         }
         else
         {
            *dst++ = c;
         }

         src++;

      }

   }

}

int main()
{

   char  result1[255];
   char  result2[255];

   char  test1[] = "aa77abb5ccdefff111gg";

   float ratio = 0.0f;

   memset((void*)&result1[0],0,255 * sizeof(char));
   memset((void*)&result2[0],0,255 * sizeof(char));

   ratio = compress(result1,test1);
   decompress(result2,result1);

   printf("Original\tCompressed\n");
   printf("%s\t%s\n\n",test1,result1);

   printf("Original\tDecompressed\n");
   printf("%s\t%s\n\n",result1,result2);

   printf("Compression Ratio:%g\n\n",ratio);

   return(0);

}