31

Given a 1-deep n by m rectangular pit, what is the smallest 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?

3 Answers 3

49

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

__________
|Wo      |
|oW      |
|        |
|        |
|        |

W = water source placed by you
o = water source generated by the water mechanics

Now, simply scoop up any source block (it will refill), and dump it diagonally from the outermost block.

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

Repeat until you hit an edge. Which source block you take doesn't matter, they are all infinite (as in, will refill instantly) at this point.

__________
|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, dump a bucket every other row on one side. The very edge block always has to be filled.

__________
|Wooooooo|
|oWoooooo|
|ooWooooo|
|oooWoooo|
|ooooWWoW|

So to fill an n×m block rectangle, you need n + ceil((m - n) / 2) water sources, with m being the longer side. 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 square:

(Note that he always refills from the still source blocks for some reason, but as noted above, any source block will do.)

5
  • 7
    This is a fantastic, comprehensive answer!
    – dlras2
    Commented Sep 27, 2011 at 7:33
  • 2
    Now do the same with Lava! ;-) Commented Sep 27, 2011 at 8:18
  • 3
    You can actually improve on this. In your last row: ooooWWWW can be ooooWoWW (you only need a water source every other block, since the gaps will be filled in).
    – fredley
    Commented Sep 27, 2011 at 12:23
  • If you need to do this away from a large source of water, then carry two buckets of water and do the above with a 2x2 square. This will then provide infinite water blocks for you to use to fill your lakes. If you put dirt blocks 1 level deep but underneath is a void, destroying the dirt after creating the lake gives you deep water. Commented Sep 30, 2011 at 15:10
  • @lunboks - of course! Commented Oct 7, 2011 at 15:40
6

This might be slightly easier: You can also fill two adjacent sides with source blocks:

+-------+
|WWWWWWW|
|Woooooo|
|Woooooo|
|Woooooo|
|Woooooo|
|Woooooo|
+-------+

...without having to enter the pool and tread water. You can do it by traversing just two sides. It can be as efficient as @lunboks's excellent answer:

+-------+
|1 2 3 4|
|       |
|5      |
|       |
|6      |
|7      |
+-------+

...and has the additional benefit that if you place the corner block (1) last, you can watch the whole thing turn in one smooth motion! :)

3

The answer by user @a cat gives a construction for why the bound of n+ceil((m-n)/2) = ceil((m+n)/2) is achievable for any m x n pool of water, but I wanted to demonstrate that this is the best possible bound.

Let s be the number of initially placed source blocks. Each newly generated source block is generated from at least two adjacent source blocks. We look at our pool as a matrix:

+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

and we label the internal "walls" (denoted by |, - in the drawing and not on the outside) through which the "creation" of new source blocks took place in some way. Notice that you only label each internal wall at most once (as you can't have two source blocks that are adjacent both generate each other) and that you must label at least 2mn - 2s internal walls (as mn - s source blocks need to be newly generated, and each generation step labels two internal walls).

However, you can count that there are exactly 2mn - m - n internal walls in the matrix at all! Therefore, we obtain 2mn - 2s <= 2mn - m - n as the number of labeled walls is at most the number of total internal walls, which rearranges to s >= (m+n)/2 and the smallest integer that satisfies that is exactly the one in the construction above.

1
  • Can you link to what the "construction above" answer is? Referencing other answers by saying "above" isn't always accurate since if a user sorts the answers some criteria, it would move the answer around, potentially making the reference to an "above" answer confusing.
    – Timmy Jim
    Commented Dec 7, 2023 at 17:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .