Tuesday, September 27, 2011

What's the most efficient way to fill a rectangle with water?

Question

Given a 1-deep n by m rectangular pit, what are they fewest number of bucket loads that can be used to completely fill it with water source blocks? Given the way water propagates, what's the most efficient sequence to fill the rectangle with? Is this sequence different if trying to fill a square?

Answer

A water block becomes a source block when there's at least 2 other source blocks next to it. You start with the very edge and place two water blocks like so. This will give you a 2×2 square of water.

__________
|Wo      |
|oW      |
|        |         
|        |
|        |W = water source placed by you, o = water source generated by the water mechanics

Now, simply take the outermost water source with a bucket (it will refill), and dump it diagonally from it.

__________
|Woo     |
|oWo     |
|ooW     |         
|        |
|        |

Repeat until you hit an edge.

__________
|Woooo   |
|oWooo   |
|ooWoo   |         
|oooWo   |
|ooooW   |

As you can see, to fill an n-long square, you need n bucket loads (actually, only 2 since after that, you can refill from the pool).

To fill the entire rectangle, you just dump two more buckets anywhere in reach row, and there you go:

__________
|Wooooooo|
|oWoooooo|
|ooWooooo|         
|oooWoooo|
|ooooWWWW|

So to fill an n×m block rectangle, you need as many bucket loads as the longer side of the rectangle. Again, only 2 if you're talking resources, because after that, you're drawing from an infinite pool.

Here's a video of a guy using this technique on a perfect square:

No comments:

Post a Comment