David Bilger

Greenhorn
+ Follow
since Feb 09, 2015
Merit badge: grant badges
For More
Cows and Likes
Cows
Total received
In last 30 days
0
Forums and Threads

Recent posts by David Bilger

Stefan Evans wrote:My initial reactions:

A couple of your comments look like they have been copied/pasted, and don't apply where they are.
Specifically the second "put the number into the correct pocket" comment.
Yes, comments ARE important.

Rather than doing a peek to print out the number, then a dequeue, I would just do a dequeue, and then print out the result.

Your method of printing destroys the queue in the process. Not sure if you can do anything about that really, but a non-destructive print method would be useful for debugging :-)

As I think has been pointed out before, in one place you have used '10' rather than the NUMDIGITS constant. That might create a problem if you change the constant :-)

The algorithm itself looks like it should work. What are your results?



Ah yes thank you for noticing the comments. Do you mean the NUMBASE constant?

My results are properly sorted!

Thank you to everyone who helped me, I really appreciate it.
9 years ago
Ok I made some changes and have come up with the following code.



How do you like the implementation?
9 years ago

Junilu Lacar wrote:

Piet Souris wrote:
OP repeatedly stated he understood the radix algorithm, and he only needed assistance when it comes to the implementing part. Now, I wonder, what in this topic made you to spell out the algorithm again?


I'm afraid I may have crossed the line between being helpful and being overbearing. I apologize to David if he feels that way. It's just that I've been watching this thread and got a sense that David is in this way over his head. Since he said a lot of the code was already given and that he only had to complete some parts, my reckoning was that this would be a two- to three-hour exercise. Instead, it seems it dragged on significantly longer and he is obviously struggling with some of the programming language constructs, for example, using square brackets instead of parentheses with a method call. What's more, one of sections to be filled by him has the comment "make a recursive call to radix" -- that's like kicking the guy in the head when he's already got the wind knocked out of him.

As I said, from my vantage point, it seems like he was just poking around and trying one thing or another without a concrete plan of attack. I was simply trying to get him back on the right track. But again, my enthusiasm to help may have gotten the best of me, so please accept my apologies if that is the case here.



No worries, you have been very helpful and patient with helping me. I will be tackling this more tonight.
9 years ago

Junilu Lacar wrote:And why are you enqueue'ing the variable i? You should only enqueue the numbers you are sorting. You are not sorting the values that the variable i takes. You need to use i in a different way.



Then I am pretty confused. What would you suggest?

In regards to looking at the different implementations of get, one is assigned to q, of type QueueReferencedBased.
9 years ago

Junilu Lacar wrote:So, the section of code below is given and you can't change it?



That is correct. I cannot change it.
9 years ago

Piet Souris wrote:Strange. The code in the 'radix' method has this piece:

So, pockets.get(i) should definitely work.

Can you show me the code you have for 'radix' so far?



9 years ago

Piet Souris wrote:Hmm... nice class, this QueueRefenrenceBased.

Wait, how would I move everything from the input Q to the new q (bucket) in the first place?



This is what you have in the 'radix' method:


We get an Integer from 'Q.dequeue()'. Problem is that we do not put this value
into a variable, so we cannot store it into one of the buckets. We also determine
the kth digit of this integer, but again, we do not store that value in a variable.
And all that is a pity, since we must store the integer into the bucket with index
this kth digit.

So, repair this situation: get this dequeue into a variable I, get this kth digit in a variable k,
and enque this I into Que[k]. You get this Que[k] by using pockets.get[k].
The code, therefore would be:

Implement this.

Then, enqueueing the original Que with the now filled buckets:

The routine that I gave in my previous post is still relevant. However,
this Que is not Iterable, so it seems. Therefore, we have little choice:




When coding the for loop
"get" cannot be resolved or is not a field.

9 years ago

Piet Souris wrote:Right. How do you add something to a Queue?

First of all, I do not know this particuar 'QueueReferenceBased' class.
If you look at the description that goes with this class, you will no doubt
find methods to add and retrieve an Integer from this class.
Suppose that your Que is just a plain LinkedList, as we know it from Java.
Then to add an Integer I, you would simply say: Que.addLast(I).
And to retrieve and remove an integer, simply use Que.removeFirst.

I suggest you have a look at the LinkedList API in the Oracle documentation.

(Note: I use addLast and removeFirst, since it is a bit tricky to use
the standard get(i) and remove(i) in combination with LinkedList<Integer>).

So, I assume you can use the same commands for your Queue as well, but again,
look at you documentation.

Next: how do we get the 'buckets'? How about:



So, now we have filled our original Que again, so the question is: are
we finished sorting?
One way to find out would be to check that only one bucket was filled, while
all others are empty. Why is that? And how to check for this?
Can you think of another way to see if we're finished with the sorting?

Lastly: if we are not finished sorting, what then? How do we enter the next step?



QueueReferencedBased allows me to use isEmpty, dequeueAll, enqueue, dequeue, and peek.

Wait, how would I move everything from the input Q to the new q (bucket) in the first place?
When I try to get the buckets, I get and error in the advanced for loop that q can only iterate over an array or an instance of java.lang.iterable.

We are not finished sorting, we have not even begun to. We must use the getKthNumber method at this point correct?
9 years ago

Piet Souris wrote:With 'get the numbers' I mean: in the end, in what order are the numbers sorted?

The question about using the input Que when putting th buckets back, or creating
a new Que for this, is a detail in the implementation. To decide on this, you have
to look at how you call the radix method, I see this in your code:


Well, given this, it is necessary to use the input Que. Think about it. It is part
of the impementation.

Okay, so: how do you put those buckets back into the input Que? Do you know
how to add to this Que?

Finally: how do you know when you are finished with the sorting?

Greetz,
Piet



In the end of the first pass, the numbers are sorted based on the first digit. Each number that has the same first digit goes into the same bucket.

I do not know how to add them back to the input Que, nor do I know how to pull the numbers out and sort them in the first place.
I am finished with the sorting when a pass does not need to switch any numbers around anymore.
9 years ago

Piet Souris wrote:Okay.

After that, I would go through, from right to left, putting those items starting with kth number 9 back into the original queue.


Agreed. In what order will you get the numbers, according to this strategy?
Is it necessary to use the input Que for this? Or could you create a new one, and use that in the recursion?
Lastly: if you have put all the 'buckets' back into the input Que, what then? (be as detailed as you can!).

Well, I hope I'm not resembling your teacher in any way...

Greetz,
Piet



What do you mean by 'get' the numbers? It is not necessary to use the input Que, but why not? After putting all of the buckets back into the input que, you advance to the next kth digit and repeat the same process, sorting by the next kth digit using the two queues.
Like I have previously mentioned, I have a decent grasp on radix sort conceptually, but I am lost on how to code for it.
Also, thank you so much for helping me! I really appreciate it.
9 years ago

Piet Souris wrote:No, don't worry, I see what is happening in the code, and I will use that.

So, looking at the radix method, an ArrayList<Que> is created, with
initial room for NUMBASE Que's (I abbreviate the QueueReferenceBased<Integer>
to Que, for shortness' sake). NUMBASE is 10, currently.

For each Integer I in the inputQue, the kth digit is determined. What should be done now,
is to place that Integer I into one of the Que's of your ArrayList. So, in effect,
these Que's of the ArrayList are the buckets.

Which Que to put this Integer in? The array has 10 Que's.
So, suppose the kth digit = 7. In what Que would you place that number?

You can take k = 1 to start with, if you think it gets complicated.

Now, suppose you have put all the Integers of the inputQue into
the Que's of the ArrayList. Now what? Can you describe what to do next?

Greetings,
Piet



I would put it in the Que for 7. Since there are 10 spots, 0-9.
After that, I would go through, from right to left, putting those items starting with kth number 9 back into the original queue.
9 years ago

Piet Souris wrote:hi David,

I hadn't understood that part, I'm sorry.
From what I remember of your code, and what Junilu already remarked,
is that you do nothing with the k th digit. What I meant was to store
that number in the hashmap, with key being this k th digit.

Of course I want to help, but I need to give your code another, more thorough
read. Meanwhile, If anyone around already knows how to help, please step in!

Greetz,
Piet

PS: and I'm doubting about a hashmap or a treemap... well, I'll be in touch.



I am a beginner still and do not know what a hashmap or treemap is, so I don't think I should use those to complete it.
9 years ago

Piet Souris wrote:

Piet Souris wrote:(...)
The first Integer being the radix.


I meant to say: the first integer being the k-th digit of each number, k being the second
parameter of your radix function.

Sigh... harder to describe than to implement, I'm afraid...

People of name and fame, on this very site, often write that one has to describe
a problem in such small steps, that one can explain it to a 10 year old kid.
Now, either they are implying that a 10 year old kid can do their job,
or if not, then why bother...



Except for the parts marked TO COMPLETE, the code was given to me, so I cannot use the way you described. I have to work within the tools given. My problem is that I am struggling to code for the snippet that I mentioned earlier. Can you help me with that?

Thanks
9 years ago

Junilu Lacar wrote:Well, if you were to use pockets, what would that look like?

And the getKthNumber() method returns an int, but when you call it, you don't assign the result of the call to anything. In essence, you're ignoring what that method is giving back and it just disappears into the ether. What is the Kth number supposed to represent anyway? Is that a pocket number? If it is, then you need to keep it around long enough to use it.



This is what I have been working on:



in the empty space I want to be able to compare tmp to other values after using getKthNumber, but I do not know how to iterate through and compare.
9 years ago

Junilu Lacar wrote:You probably should take a cue from some other code in that class. A few lines below, I see:

What do you think is happening on line 21 there?



I ended up getting rid of that code because I didn't think it worked since it didn't use pockets. Can it be fixed to work?
9 years ago