Challenge from CodingBat that's got me beat!

Ho there Xpertz :

I've been trying to meet this challenge :

http://codingbat.com/prob/p198664

 . . . but failed. Does anyone have a *complete* solution, and can say why it works? Thanks.
LVL 17
krakatoaAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

CPColinSenior Java ArchitectCommented:
What does your version look like? I tried it and had a few tests fail when the last character was a g, because I was doing my math wrong.
0
dpearsonCommented:
Here's one approach krakatoa, I'm sure there any many other solutions.
For problems like this I like to make sure the decision step is as clear as possible, so it mimics the original problem statement:

public boolean gHappy(String str) {
  for (int i = 0 ; i < str.length() ; i++) {
     char left = (i > 0) ? str.charAt(i-1) : ' ';
     char right = (i < str.length()-1) ? str.charAt(i+1) : ' ' ;
     
     if (str.charAt(i) == 'g' && left != 'g' && right != 'g')
        return false ;
  }
  return true ;
}

Open in new window


As for why it works - hopefully that's pretty clear.  'left' and 'right' hold the character to the left and right of the current character or a space if we're at the end of the line.  Once you have left and right, the final test is pretty simple.

Hope that helps,

Doug
0
krakatoaAuthor Commented:
OK, so I did / do have a solution (not as neat or concise as Doug's) but there is the fact that on task gHappy(""), I need to artificially return an erroneous 'true' result. So either there is something I do not understand, or the challenge is faulty.

Here is my code

public boolean gHappy(String str) {



char p;
boolean happy = false;

if(str.length()==0){return true;}  //deliberately wrong to force a correct result
if(str.length()==1){return false;}


for(int y=0;y<str.length();y++){

	if(y==str.length()-2){if((!(str.charAt(str.length()-2)=='g'))&&str.charAt(str.length()-1)=='g'){return false;}}

	p = str.charAt(y);

	if(!(p=='g')){continue;}



	if(y>0){
       		if(str.charAt(y-1)=='g'||str.charAt(y+1)=='g'){
       		happy = true;
       		}
       		else{happy = false;}
	}
}

return happy;

}

Open in new window

0
Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

CPColinSenior Java ArchitectCommented:
I think the key is that you should be returning true, unless something in the string indicates you should return false. That way, the empty string case works out okay. Doug's code does that by returning true if the code gets all the way through the for loop without returning false.

His code is almost identical to mine:

public boolean gHappy(String str) {
  for (int index = 0; index < str.length(); index++) {
    if (str.charAt(index) == 'g') {
      char previous = index > 0 ? str.charAt(index - 1) : ' ';
      char next = index < str.length() - 1 ? str.charAt(index + 1) : ' ';
      
      if (previous != 'g' && next != 'g') {
        return false;
      }
    }
  }
  
  return true;
}

Open in new window


(I wanted you to post what you'd done before anybody just gave it away, like with a homework question, but it didn't work out that way.)
0
awking00Commented:
public boolean gHappy(String str) {
  boolean pairG = str.matches(".*(?=gg).*");
  boolean oneG = str.matches(".*[^g]g[^g].*");
  if (pairG and !oneG) {
   return true;
  }
return false;  ==> will also include no g
}
0
krakatoaAuthor Commented:
@CPColin -

Not sure what there was to give away ;) . Anyway, the idea that gHappy("") returns true is, to me, a complete nonsense in light of the challenge's wording. You can't return true for happiness if there are no tokens at all which qualify.

@awking  your code doesn't complete the tests (even after it's made compilable).
0
CPColinSenior Java ArchitectCommented:
Return true if all the g's in the given string are happy.

If there are no g's in the string, then "all the g's" are happy.
0
dpearsonCommented:
Yes I agree with CPColin - an empty string contains no g's - so all of the g's are happy (because there are none).

Perhaps it's easier to think of the inverse of the expression:
"Return false if any of the g's are unhappy"

It's logically equivalent and may make it more obvious that "" should return true.

Doug
0
krakatoaAuthor Commented:
Sorry - I can't agree with that reasoning at all. You can't have happy gs if there are no gees. Jeez. Get a grip.

If there are no g's in the string, then "all the g's" are happy.

I'd go for that. Except for one thing : all the gs outside of gHappy("") . . . where are they? In the alphabet, that's where they are. But  . . .  they are not happy, or rather, it is not happy :(( why . . . he's a single g(uy).
0
mccarlIT Business Systems Analyst / Software DeveloperCommented:
What this challenge (and the comments here) show is that a software system can't be properly specified in a few lines of words. Personally, I don't think anyone commenting here is wrong OR right, what it shows is the FACT that the words used to describe this challenge have been interpreted in (at least) 2 different ways. What the challenge should really do is list those test cases and their expected results, up front along with the words, because it is the combination of those that specify more precisely what the method should do. You shouldn't have to run the code once just to get the rest of the specification. With the words as well as those expected results you have less ambiguity as to what the code should do.

Anyway, with that little rant over, this is how I would tackle the particular problem...

public boolean gHappy(String str) {
  int gCount = 0;
  for (int i = 0; i < str.length(); i++) {
    if (str.charAt(i) == 'g') {
      gCount++;
    } else {
      if (gCount == 1)
        return false;
      gCount = 0;
    }
  }
  return gCount != 1;
}

Open in new window

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
krakatoaAuthor Commented:
Thanks for your code all.

Complete conjecture, but something on these lines then : .....

Let's say that a scientist has come up with the hypothesis that a certain DNA coding sequence leads to a certain biological condition for which a cure needs to be found. He needs more statistical analysis of the incidence of this variation, which exemplifies itself by a sequence such as CGTA, where there is a non-contiguity of the appearance of the "G" nucleobase. (So ANY other combination of CGTA, where there is *more than one contiguous occurrence* of the G element, would be considered normal, and return a "true" or "OK" result). Otherwise, any DNA sequence with even a single, non-contiguous appearance of G, would return false, indicating a possible problem state.

If there were no tissue sample in some of the examined material, for reasons of normal sampling and practical aberrations - the last thing the scientist tells us should be expected would be a "normal" (true) result, as his statisticians tell him that would put the whole research in jeopardy.

What would you say to him about the results of a gHappy("") algorithm?


------------------

Or, somewhat less pretentiously, a cabin attendant has to go through the aircraft and note down if in either of the rows of three seats on both sides of the aisle, there is only one person (one 'g') sitting, or two people, but with an empty seat between them. What should she note down when she (or he), comes across an empty row?
0
awking00Commented:
Didn't test for one "g" at the beginning or end and didn't expect the empty string to return true -
public boolean gHappy(String str) {
      boolean gPair = str.matches(".*(?=gg).*")||str.isEmpty();
      boolean loneG = str.matches(".*[^g]g[^g].*")
            || str.matches("^g[^g].*")
            || str.matches(".*[^g]g$");

      if (gPair && !loneG) {
      return true;
      }
      return false;
}
The test doesn't seem to address something like "xxx", so I'm not sure what that should return. Given that the empty string has no g's, "xxx" might return true. If that's the case, just replace str.isEmpty() with !str.contains("g"), otherwise, above should work for all cases.
0
CPColinSenior Java ArchitectCommented:
Or, somewhat less pretentiously, a cabin attendant has to go through the aircraft and note down if in either of the rows of three seats on both sides of the aisle, there is only one person (one 'g') sitting, or two people, but with an empty seat between them. What should she note down when she (or he), comes across an empty row?

The instructions aren't saying to note empty rows, so the flight attendant should not note them.
0
krakatoaAuthor Commented:
The instructions aren't saying to note empty rows, so the flight attendant should not note them.

Oooow . . . this IS the same as equating true with an empty row, just as the gHappy("") test is 'supposed' to return true.

awking00
Didn't test for one "g" at the beginning or end and didn't expect the empty string to return true -
public boolean gHappy(String str) {

agree with that, but don't agree with your last paragraph. "xxx" should return true if any two adjacent places hold 'g's.
0
CPColinSenior Java ArchitectCommented:
Oooow . . . this IS the same as equating true with an empty row, just as the gHappy("") test is 'supposed' to return true.

Not quite. They're two different problems with two different sets of requirements.

"Return true if all the g's in the given string are happy." is logically equivalent to "Return false if the given string contains no g's that are unhappy." Any string that contains no g's fits that description, including empty strings.
0
awking00Commented:
>> "xxx" should return true if any two adjacent places hold 'g's. <<
Not sure what you mean here. The string "xxx" (i.e. three x's and nothing else) contains no 'g's so there is no instance of two adjacent places holding 'g's. The unknown is does a non-empty string without any 'g's return true like the empty string (which, of course, contains no 'g's) or does it return false because it contains characters, none of which are two adjacent 'g's?
0
krakatoaAuthor Commented:
Awking i assumed you were using x as a placeholder for g. But still agree that an empty string should not return true, and cannot agree with CPColin's logic at all. The happiness of g's depends on gs being present to assess - but in CPColin's logic, "xyz" should return true, since there are exactly as many gs in that as there are in "".
And this co-incides with what you ended your last comment with, which would be the logical conclusion.
0
CPColinSenior Java ArchitectCommented:
You can disagree with my logic all you want, but it'll still get you code that passes all the tests!
0
krakatoaAuthor Commented:
Yes, but the underlying logic of the test is wrong - that's the more important issue. For what it's worth I'd venture to say that the task's author based his question logic on the outcome of the code rather than base his code on a priori logic. So he has ended up painting himself into a corner, not having seen that an empty string edge case blows all his otherwise good code out if the water.
This problem is a meta "anding" problem, but it doesnt provide a viable solution when there is nothing to be anded.
0
CPColinSenior Java ArchitectCommented:
You are interpreting the instructions incorrectly.
0
krakatoaAuthor Commented:
No way on this Earth.
0
CPColinSenior Java ArchitectCommented:
Your interpretation is leading you to write code that fails some of the tests. Several people who have participated in this question have interpreted the instructions in a way that led to code that passes all the tests.
0
krakatoaAuthor Commented:
Yes. I know and understand that. I've written my own code that passes too. But that doesn't mean the test is correct and that is the case here.
0
krakatoaAuthor Commented:
I don't recall any othet Codingbat test that included an empty string being true or returning some other required type, in complete disregard of all other cases.
The present challenge effectively equates "" with "gg". Which is tripe.
0
CPColinSenior Java ArchitectCommented:
You should take it up with the author of the challenge, probably.
0
awking00Commented:
The problem is that the questions didn't include instructions for all cases. If it rains, they won't play baseball today. If they played baseball today, one can conclude that it didn't rain but, if they didn't play baseball to day, one can't conclude for certain that it rained, or it was a scheduled off-day, or for a variety of other reasons. The ambiguity in this case occurs because we don't know for certain that the empty string should return true because it's empty or because there are no g's in the string.
0
krakatoaAuthor Commented:
@CPColin - yes, probably.

@awking00, well maybe you might want to take it up with him too. But for me, there is no ambiguity at all.

happy can only be true in ONE case . . . and that is when there are 2 or more contiguous gs. If there is only one g, happy is false. How would the calling code differentiate between a 'true' being returned when there WERE 2 contiguous gs, and when there were NONE AT ALL? It couldn't.
0
awking00Commented:
Well, according to the results on codingbat, there is another case when the string does not contain two consecutive g's and no single g that returns true, and that's when the string is empty. I personally agree that it doesn't make sense but somehow codingbat has made that the case, which raises the question that none of us can answer for sure, which is, "Is it because the string is empty, or because the string doesn't contain any g's?"
0
dpearsonCommented:
krakatoa - I think you're asking the question of what "all" means.  Is it 0 or more or 1 or more?

You're right that in English this can be ambiguous, but in logic (as in propositional logic - the stuff underlying computer languages) it's not ambiguous, it means "0 or more".  When you say
"For all x, some condition holds", if x never happens the statement is still deemed to be true.  We probably have the Greeks to blame for this - i.e. it's been settled for a very long time.

This is why to several of us (including CPColin, the CodingBat writer and me) the answer seems clear, while to you it is maybe less so - you're considering it as an English expression and there "all" is potentially ambiguous - does there need to be at least one 'g' for the "all" to exist?  Maybe yes - maybe no.

So nobody is really right or wrong here.  But if you wish to interpret this statement as a logical proposition, then there is a definite answer and it's the one we've been suggesting (0 g's returns true).  If you prefer to interpret it as an English statement, then it's ambiguous and you can pick the interpretation you like - which is why English isn't a great choice for specifications and logical statements are better.

Doug
1
krakatoaAuthor Commented:
Well Doug, again, thanks for your troubles on this.

Unfortunately for the retinue of great ancient Greek philosophers as well as those programmers here and elsewhere who might believe this proposition holds, I am not swayed by any of these arguments in favour of "" returning a true value for this challenge. There can be no real-world situation in which this semantic Aegean definition can be applicable - and so, I'll place this piece of new "knowledge" that's come my way into my brain's outhouse, along with the Y2K bug and other novelties, where I'll go visit it every now and again like an exiled felon, to see if it has learned its lesson or not and wants to plead for forgiveness.

Meanwhile, I think I'll continue to write my bits of code in line with reality, and see if anybody can spot the difference.
0
krakatoaAuthor Commented:
I've said in answers to other questions that the Codingbat site tests are meaningless, and this just confirms it. When it "tests", it does so incompletely, not covering, inter alia, the complete range of ints that could be given in an answer, thus making it highly likely that bad practice, bad habits, and incomplete analysis of the problems are carried over by students of the language into real applications. It's a game, nothing more.
0
dpearsonCommented:
When it "tests", it does so incompletely
This is touching on some pretty profound computer science theory that can show that for any (moderately complex) piece of software the tests must be incomplete.  A complete suite of tests would be one of those uncountable infinite sets - not a good thing to try to write out by hand (or by machine).

So we'll have to live with Coding Bat (and all other tests) being incomplete and do our best anyway :)

Doug
0
krakatoaAuthor Commented:
Doug, I understand - and I am pleased you qualified it that way - that any *moderately* complex programme can never be proven to be completely tested and robust a priori. I know that is a fundamental principle in CS.

But we are not talking about flying the Space Shuttle with this range of codingbat material - we are talking about some fundamental Java / programming notions that are staple diet. They are not even moderately complex - testing ints for integrity - excuse the pun - should be within the grasp of a schoolboy, not just a CS guru.

But codingbat firstly makes the mistake of hiding, under "other tests", a range of undisclosed trials of the code, which the coder can never verify . . . and what IS the point of doing that, when we all know that the bounds of the int type are public knowledge - it's not like they should be kept secret or something. This is bad PR in my view, and sucks away any confidence one might have in their system - why hide what the other tests were? There are several of the recent challenges that I have chipped in on which handle int parameters, yet  let models pass all the tests which would fail if subjected to other test data. That's ludicrous, imho.

The code you posted does not handle, with any specificity, the particular case of being passed an empty String. And because of that, the case is never dealt with. Instead, it "falls through" the logic cascade, (a bit like not putting 'break' into a switch statement construction), and so gets shoved-in with the true positives, when in fact it is neither true nor false - like an empty Brazil nut shell that turns up occasionally in the batch you buy for Christmas : you can't say that that nut tasted better or worse than the last one you cracked, because there WAS no nut in the shell. There can be no way on Earth that testing data objects for what they may or may not contain when they contain SOMETHING, can be carried out in the same way for cases where there IS no data.
0
CPColinSenior Java ArchitectCommented:
But codingbat firstly makes the mistake of hiding, under "other tests", a range of undisclosed trials of the code, which the coder can never verify . . . and what IS the point of doing that, when we all know that the bounds of the int type are public knowledge - it's not like they should be kept secret or something.

They probably want you to work through the logic until it's right, as opposed to hacking your code until it passes a battery of public tests. My professors, back in college, would do the same thing. Some of them wouldn't publicize any of the tests. They'd just say, "Sorry, you didn't pass. Think about the requirements and any edge cases you missed."
0
krakatoaAuthor Commented:
Think about the requirements and any edge cases you missed."

Yep . . . and that is exactly what doesn't get done in most of the code posts above. As I said, the gHappy("") edge case "falls through", giving a false positive result.

Even if it is not possible to test for all eventualities / permutations on a theme, it is possible to exclude those that do not qualify themselves materially into the model set in the first place.

Maybe the Greeks and one or two others should have thought of this.
0
krakatoaAuthor Commented:
Headmaster Solomon Wyse is proud of the achievements of his Special Needs school.

He is in the process of assessing the performance of his new reception class teacher, Agnes Memnon, who seems to have been making good progress. One of the assessment tests is based on some new-fangled IT-based metrics, in which the children are observed for a happiness quotient, as general good humoured disposition and sociability skills amongst the children appears essential to their ability to learn. Solomon believes that all children must have voluntarily pulled their table and chair up to sit down next to at least one other child. One of the main tenets of this metric is that the entire class fails, should just one of the children be sitting alone. The number of seats and desks in this classroom is at least equal to the number of children.

"I've tasked Archie Meades, the Head of IT, to write a programme for you Agnes, to help assess the kids' happiness. All you have to do is report back to me when Archie's programme tells you that all happiness tests have passed. OK?"

Off goes Agnes with her laptop into the classroom. She reads Archie's instructions and gets the happiness or unhappiness state of the class back. But whatever she tries, there is always one case that throws an error, and she can't see why. Rather than pester the Head, she goes back into the class the next day, but still no 100% result. She returns again and again, each time failing the same one test result. One day, dazed by the pressure of the incompleteable task, she mistakenly stumbles into the class at lunchtime when there are no kids in. She fires up the laptop and, abracadabra, passes the chronically-failing test, but fails all the others. Seeing is believing, and she is a great believer in IT, so she records the remaining missing pass for this condition, and trundles back to the staff room for a nap.

Solomon's deadline for appraisal is running out, and he wonders where Agnes' results are, and so requests her attendance in his office over the tannoy. "What's taken you so long with this?" he enquires when she arrives. "Well, the kids are always happy, would you believe it, even when they are not in the classroom.They could be anywhere I guess - at home, at lunch, on holiday, dead - but they really are nevertheless so so happy. You should have no worries - they're  happy all the time, according to Archie's parameters."

"Did you say 'even when they are not in the classroom' by any chance? Are you telling me you measured the childrens' state when they not in the classroom?!" "Yup", says Agnes, "that's just what I did".

"Get Archie for me my dear, will you?"

"Archie, hi. Sit down. Look, I've got this spare motherboard here in my drawer that's been looking for a home for months now. Do you possibly have any ideas about where I should put it at all?"

"Look, let me explain . . . give me a chance . . . I know I should never have got involved with Sophie Cleese, and let her delude me with her ancient Greek metaphysics . . . but . . . "

"Archie, let's take a last walk around the flowerbeds at the back of the schoolyard, shall we . . .?"
0
krakatoaAuthor Commented:
Some of them wouldn't publicize [SIC] any of the tests.

Not sure then how you ever found out about them at all. ;)

Anyway, I don't think it is so much a question of 'hiding' the tests, (as I coloured my comment with earlier), but of arranging challenges that test the full range of the type - like int for example. Therefore in that sense, there can be no "other tests", as the CB results table displays, because if there were, then these would be tests for non-type determinants, which would be nonsensical again. How difficult can it be to include a negative int or two in a couple of the tests? The more I think about the nature of these challenges, the more irresponsible they appear, and yet the fig-leaf of the labour-intensity of exhaustive tests remains firmly stuck. These, IMHO, are not tests of algorithms, they are tests of type probation, because it is possible to submit the most hare-brained solutions that "work", as long as they return correct type in the end.
0
krakatoaAuthor Commented:
I think this is probably the most painless way of ending this question - and I mean no disrespect to any of the other experts who have taken the trouble of commenting. But on this occasion, although he doesn't perhaps say it entirely, mccarl's leaning toward the ambiguity of the challenge and its explanation comes closest, for me, to where I am with it. There may be esoteric cases founded in ancient and still-provable set logic that things "work" otherwise, but as wrong as it might be for me to say it, I can see no case whatsoever for obtaining a true result on a test of Nothing, unless that test were for Nothing itself. So, for now I will go back into my little box, and thanks for your inputs and code.
0
dpearsonCommented:
Fair enough Krakatoa :)
1
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.