A question on my Midterm

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

lordhidetora
Posts: 20
Joined: Wed Jul 18, 2007 10:12 pm UTC
Location: In the minds of the innocent
Contact:

A question on my Midterm

Postby lordhidetora » Thu Dec 18, 2008 8:52 pm UTC

I was looking over my midterm, and I tried to write this method, but I'm so stuck, no clue where to start.

Implement the method public static String unique(String s) which, given a string s, returns the string consisting of a single copy of each character in s. For example unique("abracadabra") is "abrcd".

I'm guessing, there will be nested loops, a for loop that for the s.length(); and a while loop, which I'm stuck on.

Thanks a lot for the help.
Image
Image

User avatar
Why Two Kay
Posts: 266
Joined: Sun Mar 23, 2008 6:25 pm UTC
Location: Plano, TX
Contact:

Re: A question on my Midterm

Postby Why Two Kay » Thu Dec 18, 2008 9:38 pm UTC

Pseudocode:

Code: Select all

character array letters;
character array given = toCharacterArray(inputString);

for each character in given
{
   if(character NOT in letters)
      add character to letters
}

return characterArrayToString(letters);
tl;dr - I said nothing important.

joeframbach
Posts: 1478
Joined: Sun Nov 05, 2006 12:49 am UTC

Re: A question on my Midterm

Postby joeframbach » Thu Dec 18, 2008 9:40 pm UTC

Why Two Kay wrote:if(character NOT in letters)
I was going to say that you could do much better than O(n) here, but hell, this method is provided in Java. Nevermind.

lordhidetora
Posts: 20
Joined: Wed Jul 18, 2007 10:12 pm UTC
Location: In the minds of the innocent
Contact:

Re: A question on my Midterm

Postby lordhidetora » Thu Dec 18, 2008 10:04 pm UTC

Why Two Kay wrote:Pseudocode:

Code: Select all

character array given = toCharacterArray(inputString);



What do you mean by that? : x

Edit: Oh, nevermid, sorry. lol.
Image

Image

User avatar
Why Two Kay
Posts: 266
Joined: Sun Mar 23, 2008 6:25 pm UTC
Location: Plano, TX
Contact:

Re: A question on my Midterm

Postby Why Two Kay » Thu Dec 18, 2008 10:40 pm UTC

lordhidetora wrote:
Why Two Kay wrote:Pseudocode:

Code: Select all

character array given = toCharacterArray(inputString);



What do you mean by that? : x

Edit: Oh, nevermid, sorry. ¡This cheese is burning me!.


There is a built in method of the String class in java that handles that, I assume you found it.
tl;dr - I said nothing important.

lordhidetora
Posts: 20
Joined: Wed Jul 18, 2007 10:12 pm UTC
Location: In the minds of the innocent
Contact:

Re: A question on my Midterm

Postby lordhidetora » Thu Dec 18, 2008 11:55 pm UTC

Why Two Kay wrote:for each character in given
{
if(character NOT in letters)
add character to letters
}

[/code]


Yeah, I got it.

Ah I'm stuck on the main part. The if statement.
Image

Image

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: A question on my Midterm

Postby 0xBADFEED » Fri Dec 19, 2008 12:29 am UTC

Another way would be to take advantage of data structures like a Set that automatically give you uniqueness

Code: Select all

String lettersOf(String s)
{
   Set<char> letters = new HashSet<char>();
   for(char c : s.toCharArray()) {
      letters.add(c):
   }
   return new String(letters.toArray(new char[0]));
}


I haven't compiled this and haven't written Java in a while, but I believe it is correct in spirit if not in syntax.

Rysto
Posts: 1460
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: A question on my Midterm

Postby Rysto » Fri Dec 19, 2008 12:48 am UTC

You can't have a Set<char>. You have to use the Character wrapper class.

User avatar
Why Two Kay
Posts: 266
Joined: Sun Mar 23, 2008 6:25 pm UTC
Location: Plano, TX
Contact:

Re: A question on my Midterm

Postby Why Two Kay » Fri Dec 19, 2008 1:48 am UTC

And I would almost guarantee that the assignment would expect the use of an array, since Sets and Maps and such are not taught in a Computer Science class until assignments like these are well in the past. I remember doing a similar assignment in Comp Sci I last year, and we have yet to even get past basic singly linked lists in my Comp Sci II class so far this year.
tl;dr - I said nothing important.

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: A question on my Midterm

Postby 0xBADFEED » Fri Dec 19, 2008 2:35 am UTC

Rysto wrote:You can't have a Set<char>. You have to use the Character wrapper class.


Right.

Like I said, haven't done Java in a while. I forgot about boxing issues.

User avatar
Emu*
Posts: 689
Joined: Mon Apr 28, 2008 9:47 am UTC
Location: Cardiff, UK
Contact:

Re: A question on my Midterm

Postby Emu* » Fri Dec 19, 2008 12:59 pm UTC

Put the Set version in a comments block, to show that you know of better ways of doing things...
Cosmologicon wrote:Emu* implemented a naive east-first strategy and ran it for an hour, producing results that rivaled many sophisticated strategies, visiting 614 cells. For this, Emu* is awarded Best Deterministic Algorithm!

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: A question on my Midterm

Postby Berengal » Fri Dec 19, 2008 2:27 pm UTC

Another alternative to Set is to make your own set. Now, normally I wouldn't advocate rolling your own anything unless it's neccessary, but in this case it's simple, and all it uses is a simple boolean array, which is fine since there's just a finite (and "small") amount of characters out there anyway. What I'm talking about is this:

Code: Select all

  public static void uniqueCharacters(String in){

    boolean[] chars = new boolean[256];

    for(Character c : in.toCharArray()){
      chars[c] = true;
    }

    for(char c = 0; c < 256; c++){
      if (chars[c]) System.out.print(c);
    }
  }
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: A question on my Midterm

Postby mrkite » Fri Dec 26, 2008 5:35 am UTC

Berengal wrote:which is fine since there's just a finite (and "small") amount of characters out there anyway.


I thought java strings were unicode.. which means there are 64 thousand, not 256.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: A question on my Midterm

Postby Berengal » Fri Dec 26, 2008 9:16 am UTC

Possibly, but a char is still just a byte long.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: A question on my Midterm

Postby 0xBADFEED » Fri Dec 26, 2008 4:18 pm UTC

Berengal wrote:Possibly, but a char is still just a byte long.


No.

All characters in Java are UTF-16 encoded, and thus, 2 bytes long.

If you want a data type that is one byte long you must use the "byte" type.

It just so happens that UTF-16 codepoints 0-255 contain the latin-alphabet characters.

This makes your program appear "correct", even though technically it is not.

Or... it is correct as long as strings only contain characters from codepoints 0-255.
Last edited by 0xBADFEED on Fri Dec 26, 2008 10:25 pm UTC, edited 1 time in total.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: A question on my Midterm

Postby You, sir, name? » Fri Dec 26, 2008 4:42 pm UTC

If you have a versatile string class (i.e. you're not using C-style character arrays), you could do it like this:

Code: Select all

For every letter P in string
  For every letter Q after this letter in string:
    If P is the same as Q, remove Q from string.
  End loop
End loop


You can do it with character arrays as well, but that is a bit of a headache.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
Why Two Kay
Posts: 266
Joined: Sun Mar 23, 2008 6:25 pm UTC
Location: Plano, TX
Contact:

Re: A question on my Midterm

Postby Why Two Kay » Fri Dec 26, 2008 7:04 pm UTC

Berengal wrote:Possibly, but a char is still just a byte long.


They are also the only unsigned data type in Java.
tl;dr - I said nothing important.

Karrion
Posts: 92
Joined: Fri Jun 22, 2007 12:14 am UTC
Location: Melbourne, AU

Re: A question on my Midterm

Postby Karrion » Mon Dec 29, 2008 1:03 am UTC

Nitpick, but:
0xBADFEED wrote:It just so happens that UTF-16 codepoints 0-127 contain the latin-alphabet characters.


Specifically, unicode codepoints 0-127 are the same as ASCII, which is what makes UTF-8 such a nice encoding.

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: A question on my Midterm

Postby 0xBADFEED » Mon Dec 29, 2008 4:27 am UTC

Karrion wrote:Nitpick, but:
0xBADFEED wrote:It just so happens that UTF-16 codepoints 0-127 contain the latin-alphabet characters.


Specifically, unicode codepoints 0-127 are the same as ASCII, which is what makes UTF-8 such a nice encoding.


The way I worded that could be somewhat misleading.

I didn't mean to imply that codepoints 0-255 are a bound on the latin-alphabet characters or ASCII characters, merely that the characters contained in that range are latin alphabet characters and of course ASCII-supported punctuation.

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: A question on my Midterm

Postby Qoppa » Wed Dec 31, 2008 7:06 pm UTC

Off topic, but now I know why Berengal never shuts up about Haskell. :P
Spoiler:

Code: Select all

unique :: String -> String
unique = reverse . foldl (\acc x -> if notElem x acc then x:acc else acc) []

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: A question on my Midterm

Postby Berengal » Wed Dec 31, 2008 7:41 pm UTC

Spoiler:
Or just

Code: Select all

unique :: String -> String
unique = nub
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: A question on my Midterm

Postby Qoppa » Wed Dec 31, 2008 7:50 pm UTC

That's just called being a smart ass. Aliasing a built in function hardly counts as writing your implementation of it.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests