Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

ArrayLists and Beginner Troubles  RSS feed

 
B Madigan
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello all,

I am trying to write a method that creates and ArrayList with random numbers from 0-364 with size of what the user passes to it. It then looks if there are any duplicate numbers in the ArrayList. It runs the number of times (count) that the user wants and reports the percentage of runs that have a duplicate. Any help would be greatly appreciated.

 
Stefan Evans
Bartender
Posts: 1836
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, so what is the problem?

The code looks like it might work at first glance, though I can see a couple of things.
Ask yourself: What is meant to happen on the second iteration of the 'k' loop.

My feedback would be mainly on the code style
- You could probably use some more descriptive variable names.
- Why do you use a do-while loop with 'i' instead of a for loop?
- consider using a 'break' statement instead of j= size; for exiting a loop early.

In terms of data structure: using a Set instead of a list would give you no duplicates for 'free'
This kinda looks like a homework assignment - are you sure you are meant to use an ArrayList and not an Array?

 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is a simulation of the Birthday Problem so a Set would not be appropriate because you want to have duplicates.

OTOH, the point about array vs ArrayList is a good one. Keeping track of the number of times a number in the range comes up is the goal, not keeping track of individual instances of the numbers. I would use a fixed array to store counts and just increment the appropriate element for each random number generated.
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And Welcome to the Ranch!
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
B Mad wrote:I am trying to write a method that creates and ArrayList with random numbers from 0-364 with size of what the user passes to it. It then looks if there are any duplicate numbers in the ArrayList. It runs the number of times (count) that the user wants and reports the percentage of runs that have a duplicate. Any help would be greatly appreciated.

OK, let's start at the beginning: "I am trying to write a method".
    Why "a" method? Why not several?

You may want to make only one of them public - ie, for other people to use - but your own description suggests that there are several steps to this problem, and when that's the case, it's usually a good idea to break it down into tasks, each of which has its own method.

So let's break down your description:
1. [Create] an ArrayList with random numbers from 0-364 with size of what the user passes to it.
2. [Look to see] if there are any duplicate numbers in the ArrayList.
3. [Run 1 & 2] the number of times (count) that the user wants.
4. [Report] the percentage of runs that have a duplicate.

Which suggests three methods to me (at least), not one. Specifically:
  public double calculate(int size, int count) { ...
(as you already have) to do steps 3 and 4.
  private List<Integer> createList(int size) { ...
to do step 1, and
  private boolean hasDuplicates(List<Integer> list) { ...
to do step 2.

Then your calculate() logic becomes something like:Now obviously, you'll have to transfer some of your other logic to those new methods, but do you see how much simpler it makes everything?
That's because each method is now only responsible for doing one thing.

It also means that if you decide to take Junilu and Stefan's advice, and use an array (or List) of counts, it should be much more obvious how to do it and what needs to change.

So, a few tips for you:
1. Resist the urge to start coding immediately.
2. Not all methods have to be public.
3. Before you write one line of code, break you problem down into tasks, and write a method signature for each one.

Eventually, you'll want to start creating objects to work for you, rather than just code; but perhaps it's a little early to start worrying too much about that right now. Learning how to write methods that do one thing - and one thing ONLY - will help you with that too when the time comes.

However, it's very good to see that your method isn't static, so well done for that.

HIH

Winston

PS: If you want a loop to run N times, remember this construct:
  for(int i = 0; i < N; i++) { ...
It's especially useful because Java indexes normally start at 0, so you'll find you use it a LOT.
 
B Madigan
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First, thank you everyone for all the help. So I went with the suggestion above to create multiple methods and I am still having some trouble getting it to run. My code is below.


The problem is check able by a unit test (it is a free Android beginner MOOC) and it is not working. Specifically, the unit tests won't run, which means there must be an error someone I guess. This was the only method that had to be modified.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just because the unit test doesn't run doesn't mean your code is bad. That said, even if the unit test comes back okay, it doesn't mean your code will work.

When you say the unit test "doesn't run", are you getting an error? Can you post it?
 
B Madigan
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The test just goes and goes. It never gives a result. With the initial code, it ran and failed, but every time I modified it to make it so that the results were correct, the tests would not even run.
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I added a simple main() method and class to your methods and the program exited properly. (I don't think the result was correct, but that's another problem.) I think the unit test isn't setup properly. Have you tried JUnit?
 
B Madigan
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, so I was able to get the test to eventually run and it said that the result was wrong (it said the methods returned a result of 0 when it should have been 2.xx). Any ideas on what I am missing. I have tried rewriting this so many times lol
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


This code does not do what you think it does. It generates the same series of pseudo-random numbers every time you call it because you're always seeding the generator with 1. It doesn't matter that you're incrementing seed on line 24. Since seed is a local variable, line 24 is actually quite useless. You can delete line 17 and eliminate the seed variable to fix this issue.
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can actually check your answers yourself based on the information here: https://en.wikipedia.org/wiki/Birthday_problem

For 2.x%, size = 5

If you try size = 23, you should get close to 50% as an average.

Note that the more runs you specify, i.e., the larger the value of count, the closer you'll get to the percentages given on the Wikipedia table. About 15K runs seems to get close most of the time for me.
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, since you're only interested on whether or not there is a duplicate and not which day has the duplicate, you only need an array of boolean. Boolean arrays will have all their elements set to false by default. As you iterate through the random number generation, you set an element to true if it's currently false, otherwise, you return true right away. If you iterate through count random numbers without finding a duplicate, then you return false. Essentially, you try to generate X random numbers and return true as soon as you find a duplicate or return false if you generate all X numbers without a single duplicate.
 
Stefan Evans
Bartender
Posts: 1836
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
> This is a simulation of the Birthday Problem so a Set would not be appropriate because you want to have duplicates.

Actually I think it would be very appropriate.
Add X random numbers to a set
Number of duplicates generated can be determined by X - set.size()

If all you are concerned about is determining if a duplicate was encountered or not that would let the Set do the duplication detection for you.


> OTOH, the point about array vs ArrayList is a good one. Keeping track of the number of times a number in the range comes up is the goal, not keeping track of individual instances of the numbers. I would use a fixed array to store counts and just increment the appropriate element for each random number generated.

Actually my point about ArrayList vs array was more aimed at the fact that courses normally ignore the Collections API in favour of doing things 'manually' with arrays.
I just wanted to check that the OP wasn't setting themself up for a 0 because they didn't follow the base instructions :-)
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You may be right about Set, although it would not even be necessary to do the math: you just return true right away when the set already contains the number you're adding otherwise return false if you add all numbers without getting a duplicate. The boolean array version seems to execute more than twice faster though. I tried four different sizes with 75K runs each and it still runs in about 0.06s on my Mac. The Set version runs in about 0.15s. Avoiding object creation and just calling clear() between tries doesn't help much, running in about 0.14s. Probably has something to with boxing int to Integer, too.

 
B Madigan
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First, thank you everyone for all the suggestions. This was my first time posting here and everyone was extremely helpful.

It turns out that the UnitTests were just very slow, so I was assuming that it was incorrect when it took a while and kept making possibly unnecessary changes. Thank you!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!