This first assignment was to write a program to estimate the value of the percolation threshold via Monte Carlo simulation.
I thought that the solution I coded last weekend was fine because it was correctly computing the percolation thresholds for many different grid sizes.
However, when I tested it today using the provided PercolationVisualizer class, I realized that it was suffering from the "backwash" problem.
The problem was also detected by the automatic assessment tests:
Compilation: PASSED Style: PASSED Findbugs: No potential bugs found. API: PASSED Correctness: 16/20 tests passed Memory: 8/8 tests passed Timing: 9/9 tests passed Raw score: 87.00% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]There were four tests checking the backwash problem.
It took me a couple of hours but, in the end, I managed to fix it by using two WeightedQuickUnionUF objects instead of one.
This was the final result of the automatic assessment tests:
Assessment Summary Compilation: PASSED Style: PASSED Findbugs: No potential bugs found. API: PASSED Correctness: 20/20 tests passed Memory: 8/8 tests passed Timing: 9/9 tests passed Raw score: 100.00% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]
I'm enjoying this course very much!
Hi classmate,
ReplyDeleteI am also working on this problem.
Using two WeightedQuickUnionUF objects works for backwash, but the memory for Percolation exceeded the requirement for a little bit.
Mine: 20.00 N^2 + 20.00 N + 192.00 bytes
Max allowed: 17 N^2 + 128 N + 1024 bytes
Could you educate me how you fix that?
Thanks a lot!
This comment has been removed by the author.
DeleteHi
ReplyDeleteThis is the memory my program is using:
In Percolation class:
1. An array of size N^2 + 2 to store a boolean for each site to know if the site is open or not (N^2 real sites + two virtual ones).
2. A WeightedQuickUnionUF object with N^2 real sites + two virtual sites.
3. A WeightedQuickUnionUF object with N^2 real sites + one virtual site.
4. Three ints to store sizes and important indexes.
In PercolationStats:
1. An array of size T to store the result of each experiment
2. Four doubles to store the statistics results and two ints to store the grid size and number of experiments.
I hope this helps you.
Best regards,
M
How you use second union-find object to avoid backwash problem?
ReplyDeleteHi
ReplyDeleteThink about why the backwash problem happens and its connection with a site being full.
Best regards,
M
Hi,
ReplyDeleteI fixed the backwash by using two weighted union-find objects, but am now facing a memory problem, meaning all the 4 memory tests are now failing. Could you please give me a clue of what could be different in my case from your case? Thanks a lot, D.
Hi
ReplyDeleteI don't know what could be different in your case but I described my memory usage in a previous comment. Try to compare yours with it.
I hope that helps.
Best regards,
M
I was the cookies monster before :)
DeleteI made the same mistake because I use int instead of boolean to store the open status of the cells. When I switched to boolean, the problem was solved.
DeleteHope it helps