Quantcast

Maximum PC
It is currently Sat May 25, 2013 6:36 pm

View unanswered posts | View active topics


Board index » OS/Software/Programming » Programmers' Paradise

All times are UTC - 8 hours




Post new topic Reply to topic  Page 1 of 1
  [ 6 posts ] 
  Print view Previous topic | Next topic 
Author Message
Gadget
 Post subject: Is TopCoder wrong?
PostPosted: Tue Jul 27, 2004 2:30 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
First, let me say that I think TopCoder is great and their problems are some of the best I have seen. BUT, I think they got this one wrong. The problem is 'Unlinker' - SRM 203 DIV2 Hard. I won't post the entire problem statement here - just the definitions (you can sign up for free btw - TC is a great site, even if just to do practice problems). You can find a general description and a much more intelligent solution than my own here.

Unlinker wrote:
For the purposes of this problem, a weblink is a string consisting of three parts. From left to right, these are the prefix,
domain, and suffix.

The prefix consists of one of the three following strings.
http://
http://www.
www.

The domain is a sequence of one or more characters, each of which is a letter (a character from 'a' to 'z' or from 'A' to 'Z'), a numeral ('0' to '9'), or a period (the character '.').

The suffix is one of the five following strings.
.com
.org
.edu
.info
.tv

There must be no space character within the weblink. The weblink may have any kind of character to the left and right of it. It may also occur at the beginning of the text, at the end of the text, or it may itself be the entire text.

My problem with this problem statement is that they say:
1) a web link is composed of 3 parts.
2) the domain is 1 or more characters long - no spaces.
3) notice that the prefix http://www. and .tv both have a . in them
4) you might not have caught it from the TC solution, but you're suppose to replace web links with OMIT then a numeral. The first replacement is OMIT1, the second OMIT2, etc.

I did this problem in a practice room, and by completely disregarding the obvious use of regex (idiot - that's what pressure will do to you), came up with a protracted solution that passed the six example test cases. So I submit and run the system test and boom.... it fails. WTF?! Here is system test if failed on....

Code:
arguement: luCJ7www. xgz.tvAd.tvJCyAwww..http://www.tvDgHvH
expected:  luCJ7www. Sxgz.tvAd.tvJCyAwww..OMIT1DgHvH
returned:  luCJ7www. xgz.tvAd.tvJCyAwww..http://www.tvDgHvH

So what do you guys think? Stop here - think about it for a minute. Grab a scratch paper and go use the can. :) My reading of the problem statement led me to believe that http://www..tv is not a weblink. It contains a prefix and suffix, but no domain. The regex in the example solution is interesting too....

Code:
public String clean(String text) {
  Pattern p = Pattern.compile(
    "((http://)?www[.]|http://)([a-zA-Z0-9.]+)[.](com|org|edu|info|tv)");
}

Think my interpretation is right? Well, techinically, it is wrong. That test is sort of sneaky and the http://www.tv is a weblink according to their definition.

prefix: http://
domain: www
suffix: .tv

Yeah, they made www the domain. But they're still wrong - IMO, it is wrong to do something that damn sneaky with the pressure on! Bastards!
Top
  Profile  
 
Jipstyle
 Post subject:
PostPosted: Tue Jul 27, 2004 3:11 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24153
Location: Granite Heaven
They are correct according to their rules. They are incorrect according to accepted syntax of URLs.

I think they did it that way to make it easier. Otherwise, you'd have to check for validity of the strings, AND of the way that the strings interrelate.

Fuck easy. You're right.
Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Tue Jul 27, 2004 3:51 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
Jipstyle wrote:
They are correct according to their rules. They are incorrect according to accepted syntax of URLs.

I think they did it that way to make it easier. Otherwise, you'd have to check for validity of the strings, AND of the way that the strings interrelate.

The way the hyperlinks interrelate was handled in the problem description. They state that you always take the largest matching part, ie. greedy in regex terms. So, "http://www.www.domain.com.edu" would be reduced to just "OMIT1". I'll have to redo my solution later to make sure I pass the other system tests.

Jipstyle wrote:
Fuck easy. You're right.

<inside joke>Hehe.... "fu bjarne! you want some of this!". :) </inside joke>
Top
  Profile  
 
Jipstyle
 Post subject:
PostPosted: Tue Jul 27, 2004 5:13 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24153
Location: Granite Heaven
Gadget wrote:
The way the hyperlinks interrelate was handled in the problem description. They state that you always take the largest matching part, ie. greedy in regex terms. So, "http://www.www.domain.com.edu" would be reduced to just "OMIT1". I'll have to redo my solution later to make sure I pass the other system tests.


Ah. I shoulda read that before posting. :P :)

Jipstyle wrote:
Fuck easy. You're right.

Gadget wrote:
<inside joke>Hehe.... "fu bjarne! you want some of this!". :) </inside joke>


Now I get it! :lol: :D


Last edited by Jipstyle on Tue Jul 27, 2004 7:34 pm, edited 3 times in total.

Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Tue Jul 27, 2004 7:27 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
Jipstyle wrote:
Gadget wrote:
The way the hyperlinks interrelate was handled in the problem description. They state that you always take the largest matching part, ie. greedy in regex terms. So, "http://www.www.domain.com.edu" would be reduced to just "OMIT1". I'll have to redo my solution later to make sure I pass the other system tests.


Ah. I shoulda read that before posting. :P :)

Jipstyle wrote:
Fuck easy. You're right.

Gadget wrote:
<inside joke>Hehe.... "fu bjarne! you want some of this!". :) </inside joke>


I feel left out. :( I dunno the joke.

LOL.... the inside joke was for you! :)

From the PP creation thread...
gadget wrote:
To get good - real good. I really think you have to do the equivalent of two or more TopCoder DIV 1 problems per day (DIV 2 hard and up). It is like any sport. You can beatup on the white and yellow belts all day, but you'll never get good until you're willing to look Stroustrup or Gosling in the eye and say, "You're mine bitch. I'm going to own you and your silly language." And then comes the ass beating, but that is how you learn. :)
Top
  Profile  
 
Jipstyle
 Post subject:
PostPosted: Tue Jul 27, 2004 7:32 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24153
Location: Granite Heaven
:lol:

I had missed that comment on my first read through the thread.

Thanks for the laugh ... sorry I idn't get it the first time. :)
Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 6 posts ] 

Board index » OS/Software/Programming » Programmers' Paradise

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 0 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