Quantcast

Maximum PC

It is currently Wed Jul 23, 2014 11:26 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 51 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
 Post subject:
PostPosted: Sun Aug 08, 2004 12:45 pm 
Thunderbird
Thunderbird
User avatar

Joined: Wed Jul 07, 2004 1:13 pm
Posts: 817
Location: Missouri
Dude-X wrote:
I would try this in C++, but standard C++ has no real useful string manipulation libraries.
Maybe I should invest some time and look at the Boost libraries and try something with that.


I thought the same thing. I am considering coding it in Java first to see how it goes. I am going to try C++ first nonetheless just for the challenge. :D


Top
  Profile  
 
 Post subject:
PostPosted: Sun Aug 08, 2004 6:06 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dude-X wrote:
I would try this in C++, but standard C++ has no real useful string manipulation libraries.
Maybe I should invest some time and look at the Boost libraries and try something with that.

The fastest solution on TC was 32 minutes in C++. Not a pretty solution, but effective. And if you're thinking that this should have been a Java or C# win - you're right!

I modified this version some to make it a tad easier. I think this problem is one of about three or four that I've come across that make a very good string practice problem.

BTW, check out this guys stats. Shows you what patience and effort buys - he just recognized as the 'Coder of the Month'. Not everyone can start out like SnapDragon or Tomek... :)


Top
  Profile  
 
 Post subject:
PostPosted: Sun Aug 08, 2004 6:08 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
baldeagle wrote:
Dude-X wrote:
I would try this in C++, but standard C++ has no real useful string manipulation libraries.
Maybe I should invest some time and look at the Boost libraries and try something with that.


I thought the same thing. I am considering coding it in Java first to see how it goes. I am going to try C++ first nonetheless just for the challenge. :D

Both are good practice... ;)


Top
  Profile  
 
 Post subject: Re: The string cheese challenge
PostPosted: Wed Aug 11, 2004 9:55 pm 
Bitchin' Fast 3D Z8000
Bitchin' Fast 3D Z8000
User avatar

Joined: Mon Jun 14, 2004 4:04 pm
Posts: 985
Location: Earth
This is long overdue, but I had some time to kill:

output:
sk kn ks kskrks knkc sik ksksesi
pac man roks
i love string keese!
please, I want need some keese
did iou know that Masi's is runing a keese sale?
ztemeks keedar keksks is for serious keese snakers

Heres's the code:

Code:
public class StringCheese
{
   private string op01_Replace_FirstX_with_Z(string args)
   {
      return Regex.Replace(args,"^x","z");
   }

   private string op02_Replace_X_with_KS(string args)
   {
      return Regex.Replace(args,"[x]","ks");
   }

   private string op03_Replace_All_Y_to_I(string args)
   {
      return Regex.Replace(args,"[y]","i");
   }

   private string op04_Change_C_to_S_if_followed_By_I_or_E(string args)
   {
      args = Regex.Replace(args,"ce","se");
      args = Regex.Replace(args,"ci","si");
      return args;
   }

   private string op05_Remove_C_If_Followed_By_K(string args)
   {
      int num = args.Length;
      for(int i = 0; i < num; i++)
      {
         args = Regex.Replace(args,"ck","k");
      }
      return args;

   }

   private string op06_Change_SCH_To_SK(string args)
   {
      return Regex.Replace(args,"^sch","sk");
   }

   private string op07_Change_CH_To_K_If_Followed_By_R(string args)
   {
      return Regex.Replace(args,"chr","kr");
   }
   private string op08_Change_All_C_To_K_Not_Followed_By_H(string args)
   {
      return Regex.Replace(args,"c[a-ij-z]","k");
   }

   private string op09_Replace_KN_With_N_At_Beginning(string args)
   {
      return Regex.Replace(args,"^kn","n");
   }

   private string op10_Remove_Redundant_Consonants(string args)
   {
      Regex r = new Regex("[b-df-hj-np-tv-z]");
      MatchCollection mc = r.Matches(args);
      string pattern;

      for(int i = 0; i < mc.Count; i++)
      {
         pattern = "[" + mc[i].Value + "]+";

         args = Regex.Replace(args, pattern, mc[i].Value);
      }

      return args;
   }

   public string runStringCheeseChallenge(string args)
   {
      string result =   this.op01_Replace_FirstX_with_Z(args);

      result = this.op02_Replace_X_with_KS(result);
      result = this.op03_Replace_All_Y_to_I(result);
      result = this.op04_Change_C_to_S_if_followed_By_I_or_E(result);
      result = this.op05_Remove_C_If_Followed_By_K(result);
      result = this.op06_Change_SCH_To_SK( result );
      result = this.op07_Change_CH_To_K_If_Followed_By_R( result );
      result = this.op08_Change_All_C_To_K_Not_Followed_By_H( result );
      result = this.op09_Replace_KN_With_N_At_Beginning( result );
      result = this.op10_Remove_Redundant_Consonants( result );

      return result;
   }

}


The code isn't the prettiest, but I was in a rush. Anyhow, I made darn sure that the function names are related to the action of the function itself. I didn't do much debugging, I started late at night, and I just want something to do before bed. :D

Anyhow, this is the C# solution. Where's the Java one?


Top
  Profile  
 
 Post subject: Re: The string cheese challenge
PostPosted: Fri Aug 13, 2004 7:36 am 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
Code:
input = open("text.txt", "r")       #opening file
T = input.read()                    #reading into var
x=0                                 #simple var counter
L = len(T)                          #length of file
print "Input file:"
print T
T= T.replace(" x"," z")             #rule 1
T= T.replace('"x','"z')             #rule 1
T= T.replace("x","ks")              #rule 2
T= T.replace("y","i")               #rule 3
T= T.replace("ce","se")             #rule 4
T= T.replace("ci","si")             #rule 4
T= T.replace("cc","c")              #rule 5
T= T.replace("ck","k")              #rule 5 
T= T.replace("ck","k")              #rule 5
T= T.replace('"sch','"sk')          #rule 6
T= T.replace(" sch"," sk")          #rule 6
T= T.replace("chr","kr")            #rule 7
T= T.replace("ch","CH")             #rule 8
T= T.replace("c","k")               #rule 8
T= T.replace("CH","ch")             #rule 8
T= T.replace(" kn"," n")            #rule 9
T= T.replace('"kn',"n")             #rule 9
try:                                #rule 10 (BELOW)
    while x < L and T[x]:
        if T[x] == T[x+1] not in ['a','e','i','o','u',' ']:
            T= T[:x] + T[x+1:]
            x = x + 1
        x=x+1
except:
    print "Output:"
    print T

Quote:
Input file:
"sch kn x xschrx cknnchc cyck xxceci"
" pac man roccccccks "
"i love string cheese!"
"please, I want need some cheese"
"did you know that Macy's is running a cheese sale?"
"xtemex cheedar chexx is for serious cheese snackers"
Output:
"sk n z zskrks nchk sik zksesi"
" pak man roks "
"i love string cheese!"
"please, I want need some cheese"
"did iou now that Masi's is runing a cheese sale?"
"ztemeks cheedar cheksks is for serious cheese snakers"

I think it works

Manta


Top
  Profile  
 
 Post subject:
PostPosted: Fri Aug 13, 2004 12:48 pm 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
Quote:

Feedback....
Was that problem too easy? I wanted to make our first little contest problem / language comparison fairly easy, but I'm not too sure if it was too easy, or maybe, a bit too hard for some of the newer folks around here.


So, it took about 15minutes for the main part and about two hours killing a python bug and a Manta bug (Python doesn't like index variables in while loops that "look" like they can go out of range. Thus the exception handle).

If I knew python better I would have been done in a 20-30 minutes. I took a pretty brut force aproach. I didn't use any loops unless needed to save lines. I just used replace tricks. I could have used "text" instead of "T", but python convention fall between the two because of the way I was using indexing.

If the rules had allowed it, I could have saved space by running rule 10 first.

Also, I made assuptions that the input text would be exactly as you gave - strings in quotes with no caps. Quotes offer both problems and blessing in python. Dealing with Caps would have changed my approach.

Anyways - it looks just like the php program - but I swear I didn't copy.

Manta


Top
  Profile  
 
 Post subject:
PostPosted: Tue Aug 17, 2004 12:50 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Finally got off my duff and posted a Java solution. Code block followed by an output block. Next time, I'll post a ACM problem with input and output file test cases so that you can easily check them - plus it will be a bit harder and, hopefully, a fun challenge.

Code:
import java.util.regex.*;

public class StringCheese {
    public static String rewrite(String s) {
       
        //I like this method of removing the first word and last word special cases
        s = " " + s + " ";
       
        //rules 1 thru 7
        s = s.replaceAll(" x"," z");
        s = s.replaceAll("x","ks");
        s = s.replaceAll("y","i");
        s = s.replaceAll("ce","se");
        s = s.replaceAll("ci","si");
        s = s.replaceAll("c+k","k");
        s = s.replaceAll(" sch"," sk");
        s = s.replaceAll("chr","kr");
       
        //rule 8
        StringBuffer sb = new StringBuffer(s);
        for (int i = 0; i < sb.length(); i++)
            if (sb.charAt(i) == 'c' && (i + 1 >= sb.length() || sb.charAt(i+1) != 'h'))
                sb.replace(i,i+1,"k");
       
        //rule 9
        s = sb.toString().replaceAll(" kn"," n");
        sb = new StringBuffer(s);
       
        //rule 10
        for (int i = 0; i < sb.length() - 1; i++) {
            if (Pattern.matches("[aeiou ]",sb.substring(i,i+1)) == false && sb.charAt(i) == sb.charAt(i+1))
                sb.deleteCharAt(i--);                           //notice the -- not just i
        }
       
        //using substring to remove the extra spaces that were inserted at the beginning and end
        return sb.substring(1,sb.length()-1).toString();
    }
   
   
    public static void main(String args[]) {
       
        System.out.println(StringCheese.rewrite("sch kn x xschrx cknnchc cyck xxceci"));
        System.out.println(StringCheese.rewrite("  pac  man  roccccccks  "));
        System.out.println(StringCheese.rewrite("i love string cheese!"));
        System.out.println(StringCheese.rewrite("please, I want need some cheese"));
        System.out.println(StringCheese.rewrite("did you know that Macy's is running a cheese sale?"));
        System.out.println(StringCheese.rewrite("xtemex cheedar chexx is for serious cheese snackers"));
       
        System.exit(0);
    }
}


Code:
sk n z zskrks nchk sik zksesi
  pak  man  roks 
i love string cheese!
please, I want need some cheese
did iou now that Masi's is runing a cheese sale?
ztemeks cheedar cheksks is for serious cheese snakers


Top
  Profile  
 
 Post subject: Re: The string cheese challenge
PostPosted: Tue Aug 17, 2004 1:22 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
A couple of things caught my eye:

Does replace actually replace all occurances of the rule or just one? I noticed that you have 3 replaces for rule 5 when it looks like only the last one was needed.

Rule 8 is good! I like that kind of thinking. Sure is a hell of a lot faster to write then my looping structure.

Rule 10 is interesting. What does while T[x] mean? While index x in T exists continue, right? If so, it seems like the x < L is redundant. If not, you should have replaced L with len(T) instead. ;)

Not bad for a rookie. :)


Top
  Profile  
 
 Post subject: Re: The string cheese challenge
PostPosted: Tue Aug 17, 2004 7:38 am 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
Gadget wrote:
A couple of things caught my eye:

Does replace actually replace all occurances of the rule or just one? I noticed that you have 3 replaces for rule 5 when it looks like only the last one was needed.


It replaces all, but only does a single pass (I think). So "ccc" gets turned into "cc" (not "c"). So, ccccck turns into cck. Then you need 2 ck passes to change the ck to k. It works for the examples you gave, but I think it won't work for others - I have to check. Rule 10 at the begining would have help A LOT in this case.
Quote:
Rule 8 is good! I like that kind of thinking. Sure is a hell of a lot faster to write then my looping structure.


hehe - I thought it was a cheat

Quote:
Rule 10 is interesting. What does while T[x] mean? While index x in T exists continue, right? If so, it seems like the x < L is redundant. If not, you should have replaced L with len(T) instead. ;)


I had a time with that loop. The T[x] is a remnant and should have been taken out. Python is a little wierd about using indexing in loops. I think it has to do with Python "dynamic typing" rules. You don't declare variable types (unless you have to). So python assumes the worst BEFORE attempting the loop. Thus the exception handle (my last resort). I was gonna try declaring x, but I had already posted.

It was a good exercise

Manta


Top
  Profile  
 
 Post subject:
PostPosted: Tue Aug 17, 2004 11:55 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dude-X wrote:
I would try this in C++, but standard C++ has no real useful string manipulation libraries.
Maybe I should invest some time and look at the Boost libraries and try something with that.

I, for one, would be interested to see a C++ implementation using the Boost libs.


Top
  Profile  
 
 Post subject:
PostPosted: Tue Aug 17, 2004 1:53 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Counting what I would call 'functioning lines of code' I came up with the following results:

Code:
PHP        17 loc
Java & C#  18 loc
Python     25 loc
FoxPro     28 loc


I didn't count things like print, sout, method signatures or returns (if they could have been merged with a functional statement). Only the loc needed to directly solve the problem.

It looks like the php solution benefited quite a bit from the ability to specify a matching regex and a regex replacement, whereas all the other solutions used a string replacement. If I were able to do this with my own solution in Java, it would shrink by approximately 5 loc (and I am looking!).

Double check my counting to see if you agree.

I nominate Dude-X to list the awards (unless he decides to provide a C++ Boost solution).


Top
  Profile  
 
 Post subject:
PostPosted: Tue Aug 17, 2004 2:10 pm 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
[quote="Gadget"][/quote]

Looks right for python

I think I could do better now - but oh well :)


Top
  Profile  
 
 Post subject:
PostPosted: Tue Aug 17, 2004 3:07 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
MantaBase wrote:
Looks right for python

I think I could do better now - but oh well :)

Go ahead and put in an update - rookies get a second chance. :)

BTW, the ACM problem that I have in mind you're going to like a lot.... and hate!


Top
  Profile  
 
 Post subject:
PostPosted: Tue Aug 17, 2004 3:56 pm 
Bitchin' Fast 3D Z8000
Bitchin' Fast 3D Z8000
User avatar

Joined: Mon Jun 14, 2004 4:04 pm
Posts: 985
Location: Earth
Gadget wrote:
BTW, the ACM problem that I have in mind you're going to like a lot.... and hate!


So are you going to post it? C'mon man, don't be a sissy! POST IT!!! :twisted:


Top
  Profile  
 
 Post subject:
PostPosted: Tue Aug 17, 2004 4:39 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
DJSPIN80 wrote:
Gadget wrote:
BTW, the ACM problem that I have in mind you're going to like a lot.... and hate!


So are you going to post it? C'mon man, don't be a sissy! POST IT!!! :twisted:

I'll do it when I get home a little later. I have so much to do today, way more than normal.

Oh yeah, I have an interview with Boeing next Monday. :)


Top
  Profile  
 
 Post subject:
PostPosted: Wed Aug 18, 2004 11:05 am 
Bitchin' Fast 3D Z8000
Bitchin' Fast 3D Z8000
User avatar

Joined: Wed Jun 16, 2004 11:30 am
Posts: 368
Location: San Antonio, TX
Gadget wrote:
Counting what I would call 'functioning lines of code' I came up with the following results:

Code:
PHP        17 loc
Java & C#  18 loc
Python     25 loc
FoxPro     28 loc


I didn't count things like print, sout, method signatures or returns (if they could have been merged with a functional statement). Only the loc needed to directly solve the problem.

It looks like the php solution benefited quite a bit from the ability to specify a matching regex and a regex replacement, whereas all the other solutions used a string replacement. If I were able to do this with my own solution in Java, it would shrink by approximately 5 loc (and I am looking!).

Double check my counting to see if you agree.

I nominate Dude-X to list the awards (unless he decides to provide a C++ Boost solution).


I could shave some off of that PHP solution too...


Top
  Profile  
 
 Post subject:
PostPosted: Wed Aug 18, 2004 9:36 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
DaBrain wrote:
Gadget wrote:
Counting what I would call 'functioning lines of code' I came up with the following results:

Code:
PHP        17 loc
Java & C#  18 loc
Python     25 loc
FoxPro     28 loc


I didn't count things like print, sout, method signatures or returns (if they could have been merged with a functional statement). Only the loc needed to directly solve the problem.

It looks like the php solution benefited quite a bit from the ability to specify a matching regex and a regex replacement, whereas all the other solutions used a string replacement. If I were able to do this with my own solution in Java, it would shrink by approximately 5 loc (and I am looking!).

Double check my counting to see if you agree.

I nominate Dude-X to list the awards (unless he decides to provide a C++ Boost solution).


I could shave some off of that PHP solution too...

Oh, you and your php. We'll see how well that language scales when we leave the little league game and actually do something useful. :P


Top
  Profile  
 
 Post subject:
PostPosted: Wed Aug 18, 2004 9:39 pm 
Bitchin' Fast 3D Z8000
Bitchin' Fast 3D Z8000
User avatar

Joined: Mon Jun 14, 2004 4:04 pm
Posts: 985
Location: Earth
So when are we going to see the nominations? Best do it now, I'm not known for my patience. :P


Top
  Profile  
 
 Post subject:
PostPosted: Wed Aug 18, 2004 10:12 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
DJSPIN80 wrote:
So when are we going to see the nominations? Best do it now, I'm not known for my patience. :P


I went to the chatroom to see about having dudex do them.... he's not there. Maybe you should do them.... you could do a runner up and a winner for each category that seems appropriate.


Top
  Profile  
 
 Post subject:
PostPosted: Wed Aug 18, 2004 10:25 pm 
Bitchin' Fast 3D Z8000
Bitchin' Fast 3D Z8000
User avatar

Joined: Mon Jun 14, 2004 4:04 pm
Posts: 985
Location: Earth
Gadget wrote:
DJSPIN80 wrote:
So when are we going to see the nominations? Best do it now, I'm not known for my patience. :P


I went to the chatroom to see about having dudex do them.... he's not there. Maybe you should do them.... you could do a runner up and a winner for each category that seems appropriate.



:lol: But I'd win every category, even the bad ones!!! ;)

Sure, why not, give me a day or two to look at the code once more.

EDIT: I'd have to decline actually, I like to judge things fairly hence I might insert some of my own bias towards my code. I'll try the maxPC chat and see if I can find Dude-X.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 51 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group