• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Need some pointers for run-length encoding, I am a deer in the headlights

 
Thomas Dallaire
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I've been staring at the last part of an assignement I have to do for about 2 hours now with little success...it goes something like this:

Part 8. Create a new implementation of the List interface, called an Part8List. An Part8List (a run-length encoded list) stores its elements as a List (using ArrayList or LinkedList, as you wish). However, when the same element occurs several times in succession, the element is stored only once, and a counter is used to keep track of how many times it actually occurs. (Treat two elements a and b as "the same" if a.equals(b) is true.)

For example, a list containing

"apple", "banana", "banana", "kd", "orange", "apple", "apple"


gets represented internally as

("apple",1), ("banana",2), ("kd",1), ("orange",1), ("apple",2)

Now, I AM NOT LOOKING TO HAVE THIS SOLVED FOR ME as im sure there will be complaints. But I really have no idea how to approach this.

Could I get some pointers on what I should be doing? Is it better to append a number to an entry on the list and then extract it later when I print it? Should I create a list within the list to hold counters? A seperate list with counters? Something I haven't thought of yet??

Please help!
 
Campbell Ritchie
Sheriff
Pie
Posts: 49367
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

You need to forget all this high-tech new-fangled electronic stuff, and use paper pencil and eraser. The latter is the most important.
Write down exactly what you want to do, and go through it and make it simpler. You are aiming for words of one syllable.
Hint: Make a class which has two fields, one for "fruit" and the other for "count". That is one syllable per word.
 
Mos Jeff
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Try using a Map. What I mean is have the element be a key and the count be the value you update. If you haven't learned java.util.Map yet you could create a value object that holds a key and count, then create a list of these objects

Good Luck.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49367
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The original poster was told to use a List. I think a List is easier for run-length recording than a Map.
 
Mos Jeff
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:The original poster was told to use a List. I think a List is easier for run-length recording than a Map.

ahhh.. yes, I missed that in the question. I agree, use a List.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12143
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
start off simpler. can you create a list that stores all the elements, one at a time?
 
Thomas Dallaire
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can create a list and read a test file one line at a time and save each line as an entry in the list. My problem is how I attach a counter to those entries and create method's that behave naturaly ( as if it was a full list not a compressed one)
 
Campbell Ritchie
Sheriff
Pie
Posts: 49367
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How would you do it by hand? That is what you need to work out.
 
Nick Bowen
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lol you go to carleton don't you

Would be so much easier if you could use a map :P.

I've started by making an ArrayList to hold the elements, but not having each of the ones that are consecutive stored, but i'm also having trouble with trying to keep the count for when some of the numbers are consecutive :P
 
Campbell Ritchie
Sheriff
Pie
Posts: 49367
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

It might be easier to use a Map, but that will give a simple count, not run-length counting. You will need to use a List, as it says in the instructions you were given.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12143
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can create a list and read a test file one line at a time and save each line as an entry in the list.

Ok...next I would say you need to save something else. you need to save a line AND a count - even if that count is only the number '1' each time. Can you do that?
 
Thomas Dallaire
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Nick,

Yup, guess you're in the same situation eh haha

@Fred,

That's the part I can't figure out how to do...i'm not sure how to create a list class that takes both elements and the only other way I can see to do it is to append the number to the entry on the string. Im guessing that's not what you're thinking of though?

And I appreciate the help eh! Sorry if I seem slow on this
 
Campbell Ritchie
Sheriff
Pie
Posts: 49367
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yesterday, I wrote: . . . Hint: Make a class which has two fields, one for "fruit" and the other for "count". . .
Hemmmm, hemmmm!
 
Anand Hariharan
Rancher
Posts: 272
C++ Debian VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
It might be easier to use a Map, but that will give a simple count, not run-length counting. You will need to use a List, as it says in the instructions you were given.


Looking at what is expected of "apple" in OP's example, I think it pretty much rules out the use of a Map; certainly, it is easier to solve the problem as specified, by the use of a List than a Map.
 
Nick Bowen
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thomas Dallaire wrote:@Nick,

Yup, guess you're in the same situation eh haha

@Fred,

That's the part I can't figure out how to do...i'm not sure how to create a list class that takes both elements and the only other way I can see to do it is to append the number to the entry on the string. Im guessing that's not what you're thinking of though?

And I appreciate the help eh! Sorry if I seem slow on this


Yeah the problem (or at least the problem I can't really get around) with appending a number to a string is that we need to make it generic
 
Campbell Ritchie
Sheriff
Pie
Posts: 49367
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wrote: . . . Hint: Make a class which has two fields, one for "fruit" and the other for "count". . .
If you miss hints like that, you deserve all you get
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic