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

Re: Prog Battle: Round 1

Post by thetan on Sun Jan 02, 2011 3:28 am
([msg=51528]see Re: Prog Battle: Round 1[/msg])

In C++
Code: Select all
#include <iostream>
#include <sstream>
#include <string>

void append(std::ostream& o, char curr, int count)
{
        if(count > 1) o << count;
        o << curr;
}

void encode(std::ostream& o, char *str, char curr = (char) 0, int count = 0)
{
        if (*str)
        {
                if (*str == curr || !curr) encode(o, str + 1, *str, ++count);
                else
                {
                        append(o, curr, count);
                        encode(o, str);
                }
                return;
        }
        if (curr) append(o, curr, count);
       
}

void decode(std::istream& i, std::ostream& o)
{
        for (;;)
        {
                char curr;
                int count;
                i >> count;
                if (i.fail())
                {
                        count = 1;
                        i.clear();
                }
                i >> curr;
                if (i.eof()) break;
                while (count--) o << curr;
        }
}

int main(int argc, char **argv)
{
        char str[] = "rrraaawwrrwhatsgood";
        std::stringstream ss("3r3a2w2rwhatsg2od");
        encode(std::cout, str);
        std::cout << std::endl;
        decode(ss, std::cout);
}


I'll add Goatboys accommodations next round
"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 goluhaque on Sun Jan 02, 2011 7:27 am
([msg=51533]see Re: Prog Battle: Round 1[/msg])

thetan wrote:In C++
Code: Select all
#include <iostream>
#include <sstream>
#include <string>

void append(std::ostream& o, char curr, int count)
{
        if(count > 1) o << count;
        o << curr;
}

void encode(std::ostream& o, char *str, char curr = (char) 0, int count = 0)
{
        if (*str)
        {
                if (*str == curr || !curr) encode(o, str + 1, *str, ++count);
                else
                {
                        append(o, curr, count);
                        encode(o, str);
                }
                return;
        }
        if (curr) append(o, curr, count);
       
}

void decode(std::istream& i, std::ostream& o)
{
        for (;;)
        {
                char curr;
                int count;
                i >> count;
                if (i.fail())
                {
                        count = 1;
                        i.clear();
                }
                i >> curr;
                if (i.eof()) break;
                while (count--) o << curr;
        }
}

int main(int argc, char **argv)
{
        char str[] = "rrraaawwrrwhatsgood";
        std::stringstream ss("3r3a2w2rwhatsg2od");
        encode(std::cout, str);
        std::cout << std::endl;
        decode(ss, std::cout);
}


I'll add Goatboys accommodations next round

feels nice tohave you back, man
(23:45:03) hauk: I guess you are over the best part of your life when 4-year-olds say "Are you an evil man?"
(23:46:19) hauk: and "Ima punch you in the pecker"
User avatar
goluhaque
Poster
Poster
 
Posts: 153
Joined: Mon Apr 13, 2009 12:08 am
Location: India
Blog: View Blog (0)


Re: Prog Battle: Round 1

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

I think I'm having the same problem as OnlyHuman, if I put a single digit into my string it all falls apart.
Code: Select all
#!/usr/bin/env python

import re
from decimal import *
getcontext().prec = 2

def main():
   start = 'a22aa666bbccd777efffgga888bbbcccccdeff999fffffg22'
   encrypted = compress(start)
   decrypted = decompress(encrypted)
   print 'Compress = '+ encrypted
   print 'Decompress = '+ decrypted   
   results = start == decrypted
   if results:
      print 'Strings Match = True'
      ratio = (Decimal(len(encrypted))/len(start))*100
      print 'Compression = '+ str(ratio) + '%'
   else:
      print 'Fail'
   return 0

def compress(input):
   encrypted = ''
   letters = ''   
   pad = ' '   
   input = input + pad
   for i in range(0,len(input)-1):
      if input[i] == input[i+1]:
         continue
      else:
         letters = letters + input[i]   
   for ch in letters:
      c = re.compile(ch+'+')
      cc = c.match(input)
      start,end = cc.span()
      num = end-start
      input = input[num:]
      if num == 1: num = ''         
      encrypted = encrypted + str(num) + ch
   return encrypted

def decompress(encrypted):
   i=0
   decrypted = ''
   length = len(encrypted)   
   while i < length:
      if encrypted[i].isalpha():
         decrypted += encrypted[i]
         i+=1   
      else:
         count = int(encrypted[i])
         for j in range(0,count):
            decrypted += encrypted[i+1]                  
         i+=2
   return decrypted

if __name__ == '__main__':
   main()

Edit: Changed something I didn't like.
Never stop learning.
User avatar
mojo1948
Experienced User
Experienced User
 
Posts: 60
Joined: Sun Jul 18, 2010 5:45 am
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by Assassian360 on Sun Jan 02, 2011 8:04 pm
([msg=51574]see Re: Prog Battle: Round 1[/msg])

Seeing as C and C++ have already had a number done of them I figured I might as well write it in Java.

Code: Select all
class Compression
{
    public static String encode(String str)
    {
        String result = "";
       
        for(int i = 0; i < str.length(); i++) {
            char next = str.charAt(i);
           
            // handle single characters
            if(((i+1) < str.length() && str.charAt(i+1) != next) || i+1 == str.length())  {
                if(Character.isDigit(next)) {
                    result += "1" + next;
                } else {
                    result += next;
                }
            } else {
                int count = 1;
                while(i+1 != str.length() && str.charAt(i+1) == next) {
                    count++;
                    i++;
                }
               
                int split = count / 9;
                count = count % 9;
                for(int j = 0; j < split; j++) {
                    result += "9" + next;       
                }
                if(count != 0) {
                    result += count + "" + next;
                }
            }
        }
       
        return result;
    }
   
    public static String decode(String str)
    {
        String result = "";
       
        for(int i = 0; i < str.length(); i++) {
             if(Character.isDigit(str.charAt(i))) {
                int count = Integer.parseInt(str.charAt(i) + "");
                i++;
                char next = str.charAt(i);
                for(int j = 0; j < count; j++) {
                    result += next;
                }
            } else {
                result += str.charAt(i);
            }
        }
       
        return result;
    }
   
    public static void main(String[] args)
    {
        String encoded = encode("aa77abb5ccdefff111gg");   
        String decoded = decode(encoded);
       
        System.out.println("Encoded string is: " + encoded);
        System.out.println("Decoded string is: " + decoded);
       
        double enlength = encoded.length();
        double delength = decoded.length();
        double ratio = (1 - enlength / delength) * 100;
        System.out.println("Deflation: " + ratio + "%");
    }
}


This handles Goatboy's suggestion with the numbers in it as well as the original problem.

Code: Select all
Encoded string is: 3a2b2cde3f2g
Decoded string is: aaabbccdefffgg
Deflation: 14.28571428571429%


Code: Select all
Encoded string is: 2a27a2b152cde3f312g
Decoded string is: aa77abb5ccdefff111gg
Deflation: 5.000000000000004%


The code also handles the scenario where there are more than 9 of a character in a row. It just splits them into groups of 9. eg:
Code: Select all
Encoded string is: 9a9a7a95759b7b919161
Decoded string is: aaaaaaaaaaaaaaaaaaaaaaaaa5555555555555555bbbbbbbbbbbbbbbb111111111111111111111111
Deflation: 75.30864197530865%
Assassian360
Poster
Poster
 
Posts: 135
Joined: Sat Jun 26, 2010 1:37 am
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by mojo1948 on Sun Jan 02, 2011 11:28 pm
([msg=51579]see Re: Prog Battle: Round 1[/msg])

This will compress up to 127 repeated characters, if you have more get your cat off the keyboard. :lol:
Code: Select all
#!/usr/bin/env python

import re
from decimal import *
getcontext().prec = 3

def main():
   start = 'a22aa6616bbccd777eaaaaaaaaaaaaaaaaaaaaaaaaaaaafffgga888a1'
   encrypted = compress(start)   
   decrypted = decompress(encrypted)
   print 'Compressed Values = ',encrypted
   print 'Decompressed = ', decrypted
   print 'Start String = ',start      
   results = start == decrypted
   if results:
      print 'Strings Match = True'
      ratio = (Decimal(len(encrypted))/len(start))*100
      print 'Compression = '+ str(ratio) + '%'
   else:
      print 'Fail'
   return 0

def compress(input):
   encrypted = []
   letters = ''   
   pad = ' '
   input = input + pad   
   length =    len(input)-1
   for i in range(0,length):
      if input[i] == input[i+1]:
         continue
      else:
         letters = letters + input[i]            
   for ch in letters:
      c = re.compile(r'('+ch+'+)')
      cc = c.match(input)
      start,end = cc.span()
      num = end-start
      input = input[num:]
      if num > 1:   
         encrypted.append(num+128)
      encrypted.append(ord(ch))
   return encrypted

def decompress(encrypted):
   i=0
   result = ''
   decrypted = []
   length = len(encrypted)   
   while i < length:
      if encrypted[i] < 128:
         decrypted.append(encrypted[i])
         i+=1   
      else:
         count = encrypted[i]%128
         for j in range(0,count):
            decrypted.append(encrypted[i+1])      
         i+=2
   for val in decrypted:
      result += chr(val)
   return result

if __name__ == '__main__':
   main()


Output:
Code: Select all
Compressed Values =  [97, 130, 50, 130, 97, 130, 54, 49, 54, 130, 98, 130, 99, 100, 131, 55, 101, 156, 97, 131, 102, 130, 103, 97, 131, 56, 97, 49]
Decompressed =  a22aa6616bbccd777eaaaaaaaaaaaaaaaaaaaaaaaaaaaafffgga888a1
Start String =  a22aa6616bbccd777eaaaaaaaaaaaaaaaaaaaaaaaaaaaafffgga888a1
Strings Match = True
Compression = 49.1%
Never stop learning.
User avatar
mojo1948
Experienced User
Experienced User
 
Posts: 60
Joined: Sun Jul 18, 2010 5:45 am
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by tucak on Mon Jan 03, 2011 9:56 am
([msg=51582]see Re: Prog Battle: Round 1[/msg])

I wrote this in Python.
Code: Select all
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#              _-----_                 
#  Lord       /  _    \_               
#  ________  //|| ||\ ./               
# /__  ___/ // || || :_|               
#    | | ____ _____   __   __         
#    | | |||| |  __/ /__\  | |//       
#    |/  \__/ |___/ /_||_\ |_|\\       
#
# Notice the nice ascii art up there...
import sys

def encrypt(inp):
  i=0
  r=""
  while i<len(inp):
    l=inp[i]
    j=0
    while (len(inp)>i) and (j<0xFF) and (inp[i]==l):
      j+=1
      i+=1
    r=r+chr(j)+l
  return r

def decrypt(inp):
  if len(inp)%2==1: return "WTF srsly..."
  i=0
  r=""
  while (i<len(inp)):
    r=r+inp[i+1]*ord(inp[i])
    i+=2
  return r

if __name__ == '__main__':
  if (len(sys.argv))!=3:
    sys.stderr.write("Usage: "+sys.argv[0]+" encrypt|decrypt FILE")
    sys.exit()
  try:
    f=open(sys.argv[2],"rb")
  except IOError:
    sys.stderr.write('f'*7+'u'*14+'\nCannot open file!\n')
    sys.exit(1)
  data=f.read()
  f.close()
  if sys.argv[1][0] in ('e','E'):
    e=encrypt(data)
    sys.stdout.write(e) # no stupid \n!
    # Compress ratio?
    sys.stderr.write("Ratio: "+str(float(len(e))/float(len(data)))+'\n')
    if float(len(e))/float(len(data))>1:
      sys.stderr.write("Problem?\n")
  if sys.argv[1][0] in ('d','D'):
    sys.stdout.write(decrypt(data))

I'm not sure about the ratio thing.
Do you like it Goatboy?
tucak
New User
New User
 
Posts: 47
Joined: Wed Jun 04, 2008 12:20 pm
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by tgoe on Tue Jan 04, 2011 2:05 am
([msg=51634]see Re: Prog Battle: Round 1[/msg])

I haven't really looked at any of the others but here's my own drunken submission:

Code: Select all
#!/usr/bin/env python

import string
from itertools import groupby

def encode(S):
    def J(T):
        if T[0] >= 4:
            if 47 < ord(T[1]) < 58:
                return "%c%s%c%c" % (0x1E, str(T[0]), 0x1F, T[1])
            else:
                return "%c%s%c" % (0x1E, str(T[0]), T[1])
        else:
            return "%s" % ("%c" % T[1] * T[0])
    return "".join(map(J, [(len(list(n)), c) for c,n in groupby(S)]))

def decode(S):
    NS = ""
    for op in S.split("%c" % 0x1E):
        if op:
            op = op.split("%c" % 0x1F)
            if len(op) == 1:
                op = op[0]
                if 47 < ord(op[0]) < 58:
                    ind = len(op) - len(op.lstrip(string.digits))
                    NS += op[ind:ind+1] * int(op[:ind]) + op[ind+1:]
                else:
                    NS += op
            else:
                NS += op[1][0] * int(op[0]) + op[1][1:]
    return NS

if __name__ == '__main__':
    import sys

    S = open(sys.argv[1], "rb").read()
    enc = encode(S)
    open(sys.argv[1]+".enc", 'w').write(enc)
    open(sys.argv[1]+".dec", 'w').write(decode(enc))


Simple RLE of any printable ASCII text file as its argument. Minimum run length is 4 instead of 2.

@thetan
This might be cheating but the "max function" without control structures from some other thread seemed interesting...
I'd choose JavaScript:

Code: Select all
function G(a, b) { var g; return g = a / b > 1 && a || b; }

That seems to work with numbers 0 or greater.
User avatar
tgoe
Contributor
Contributor
 
Posts: 718
Joined: Sun Sep 28, 2008 2:33 pm
Location: q3dm7
Blog: View Blog (0)


Re: Prog Battle: Round 1

Post by thetan on Tue Jan 04, 2011 11:25 pm
([msg=51703]see Re: Prog Battle: Round 1[/msg])

tgoe wrote:@thetan
This might be cheating but the "max function" without control structures from some other thread seemed interesting...
I'd choose JavaScript:

Code: Select all
function G(a, b) { var g; return g = a / b > 1 && a || b; }

That seems to work with numbers 0 or greater.

You misunderstood the question in the other thread. It wasn't just max() without control structures, it's also max with only arithmetic operators as in the only operators you can use are + - / and *. Your use of logical and comparison operators would disqualify you. Also, for clarity, it would be acceptable to use assignment operators to make the code easier to follow.
"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 yourmysin on Wed Jan 12, 2011 10:51 am
([msg=52043]see Re: Prog Battle: Round 1[/msg])

Good challenge TheTan. I didn't submit a solution, but I'm proposing another, more challenging, challenge.

Given some set (Which may contain duplicates) write a program to generate all permutations of the set. Also, write a function f(n) which will compute the cardinality of the set containing all permutations.

Also, to take this one step further, find a real world application where such a problem may occur. Use your method to determine a solution to such problem.
A+, Network+, MCTS(70-620), Security+, CCNA
yourmysin
Experienced User
Experienced User
 
Posts: 83
Joined: Mon Apr 21, 2008 9:02 pm
Location: Newport, Maine, USA
Blog: View Blog (0)


Previous

Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests