Prog Battle: Round 1

Discuss how to write good code, break bad code, your current pet projects, or the best way to approach novel problems

Prog Battle: Round 1

Post by thetan on Sat Jan 01, 2011 4:42 pm
([msg=51484]see Prog Battle: Round 1[/msg])

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
Image

Let the fun begin.
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by Bren2010 on Sat Jan 01, 2011 5:38 pm
([msg=51486]see Re: Prog Battle: Round 1[/msg])

w00t! First done! :D

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";
?>
User avatar
Bren2010
Poster
Poster
 
Posts: 340
Joined: Fri Sep 19, 2008 3:23 pm
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by OnlyHuman on Sat Jan 01, 2011 6:29 pm
([msg=51489]see Re: Prog Battle: Round 1[/msg])

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.
OnlyHuman
Poster
Poster
 
Posts: 191
Joined: Sat Aug 22, 2009 1:37 am
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by thetan on Sat Jan 01, 2011 9:23 pm
([msg=51495]see Re: Prog Battle: Round 1[/msg])

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";
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by Goatboy on Sat Jan 01, 2011 11:27 pm
([msg=51503]see Re: Prog Battle: Round 1[/msg])

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.
Assume that everything I say is or could be a lie.
User avatar
Goatboy
Expert
Expert
 
Posts: 2865
Joined: Mon Jul 07, 2008 9:35 pm
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by Assassian360 on Sun Jan 02, 2011 12:21 am
([msg=51508]see Re: Prog Battle: Round 1[/msg])

Goatboy wrote: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.
Assassian360
Poster
Poster
 
Posts: 135
Joined: Sat Jun 26, 2010 1:37 am
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by Goatboy on Sun Jan 02, 2011 12:34 am
([msg=51511]see Re: Prog Battle: Round 1[/msg])

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.
Assume that everything I say is or could be a lie.
User avatar
Goatboy
Expert
Expert
 
Posts: 2865
Joined: Mon Jul 07, 2008 9:35 pm
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by OnlyHuman on Sun Jan 02, 2011 1:11 am
([msg=51515]see Re: Prog Battle: Round 1[/msg])

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.
OnlyHuman
Poster
Poster
 
Posts: 191
Joined: Sat Aug 22, 2009 1:37 am
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by Goatboy on Sun Jan 02, 2011 1:21 am
([msg=51518]see Re: Prog Battle: Round 1[/msg])

That's part of the challenge. Implement your own algorithm.
Assume that everything I say is or could be a lie.
User avatar
Goatboy
Expert
Expert
 
Posts: 2865
Joined: Mon Jul 07, 2008 9:35 pm
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by OnlyHuman on Sun Jan 02, 2011 2:39 am
([msg=51524]see Re: Prog Battle: Round 1[/msg])

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

}
OnlyHuman
Poster
Poster
 
Posts: 191
Joined: Sat Aug 22, 2009 1:37 am
Blog: View Blog (0)


Next

Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests