search

alexilyenko / Algorithms1

Programming assignments for Algorithms I Coursera e-learning course
20 stars 13 forks source link

About backwash in assignment 1, Percolation.java #2

Closed yzhang-gh closed 9 years ago

yzhang-gh commented 9 years ago

It seems that you didn't solve the "backwash" problem. I run the PercolationVisualizer with input20.txt, it's the result backwash

But maybe the correct one should be nobackwash

alexilyenko commented 9 years ago

It seems you're right. Do you have any ideas how can it be implemented in code?

yzhang-gh commented 9 years ago

I had looked for solutions for "backwash". A straight-forward method is to declare another WeightedQuickUnionUF wquf2 which don't connect to the virtual bottom site. Use wquf(1) in function percolates(), use wquf2 in function isFull(). Someone provided another elegant approach but I can't understand... This is the screenshot image

By the way, thank you for your codes. I'm learning Algorithms on Coursera recently. I often have a look at your codes after writing my own version. It's really helpful.

alexilyenko commented 9 years ago

I guess I'll leave solution the way it is. Don't have enough time to change it. You're welcome. Algorithms II will be here soon too :)

yzhang-gh commented 9 years ago

I think it's not important too. It's so trivial a problem.

firezdog commented 5 years ago

Implementing the solution provided does seem like it would be clever, but I think it's better to instantiate two UF's: the percolation client should not need to know details of how UF is implemented in order to determine whether a cell is full. (Some implementations of UF might not have a findRoot method.)

6i96rother commented 3 years ago

@yzhang-gh @firezdog @alexilyenko Hi guys! I thought you might be interested. I got another solution for backwash problem and all is needed is only single n*n+1 size array (I don't use OOTB union path structures). I use quick search + path compression algorithm. Though it's not as fast as weighted QU + path compression, it's logN, so it's fine. The main idea is to keep the greatest id as root and always set it as root on union operation. There's only 1 top abstract element. To check whether the grid percolates, we need to get top abstract element's root and check whether it's in the last row. Element with value -1 represents closed site. Please see the implementation here:

OmarShawky1 commented 2 years ago

@yzhang-gh @firezdog @alexilyenko Hi guys! I thought you might be interested. I got another solution for backwash problem and all is needed is only single n*n+1 size array (I don't use OOTB union path structures). I use quick search + path compression algorithm. Though it's not as fast as weighted QU + path compression, it's logN, so it's fine. The main idea is to keep the greatest id as root and always set it as root on union operation. There's only 1 top abstract element. To check whether the grid percolates, we need to get top abstract element's root and check whether it's in the last row. Element with value -1 represents closed site. Please see the implementation here:

This should not happen, he asked you to use Weighted Quick Union in specific. Also how did you pass the test? i see you use iterations O(N), If you want a solution you can jump to my Algo repo but i do not think so because it has been a year now 😀️.