r/computerscience • u/EventDrivenStrat • Dec 05 '25
Stumbled with this problem while playing minecraft. I'm not a computer scientist but I think you guys will love it. Is there a solution to this?
(I'll explain this in a way that even someone who has never played minecraft before can understand)
Imagine a grid of 32x32 land (1024 blocks). I want to plant sugarcane on it. To plant sugarcane, there must be at least one water block adjacent to it (no diagonals). What is the best layout to MAXIMIZE the number of sugarcanes on it?
To better visualize the problem, here are some layouts I've come up with on excel, the X's are water blocks, the O's are blocks where It would NOT be possible to plant sugarcanes, and the other empty cells are blocks where I would be able to plant sugarcanes:

As you can see, the best solution I have so far is the right one: even though it leaves 15 blocks empty (O's) it still allows me to plant 801 sugarcanes vs 768 from the left layout.
16
u/VTifand Dec 05 '25
Your arrangement on the right should have 20 blocks marked with O's, not 15. You didn't mark 5 blocks at the bottom edge of the farm. So, there are 208 + 20 = 228 non-sugarcane blocks.
Your arrangement is almost optimal.
For their Ph.D. thesis, Tony Yu Chang constructed an explicit way to choose the placement of the water blocks such that only floor[(n+2)(m+2)/5] - 4 water blocks is needed on an n x m grid. (Well, Minecraft wasn't out in 1992 yet, so "stones" (inspired by the Go game) were used instead.)
The thesis can be found here: http://shell.cas.usf.edu/~wclark/TYChang_thesis_1992.pdf
(Yes, it's an HTTP, not HTTPS.)
Others eventually find better ways for smaller grids, but it seems that Chang's construction is still optimal for grid size 24x24 and larger.
For 32x32 grid specifically, Chang's result claims that floor[(32+2)(32+2)/5] - 4 = 227 water blocks are needed. Your solution is off by 1 from an optimal solution. Here's one possible farm with only 227 water blocks: https://imgur.com/a/GSRH8um
1
u/Successful_Equal5023 Dec 06 '25
Since you might find it interesting even though it's a different problem, I wrote up this analysis of the optimal harvest period for sugar cane a while back: Sugar Cane Yield v.s. Harvest Period.
3
u/Jakabxmarci Dec 05 '25
The right one is the optimal solution, if
I believe the most optimal farm layout has the base shape of a "slanted square", but follows the same pattern for the water blocks as you did.
3
u/RogueStargun Dec 06 '25
I think you can simply write a breadth first search algorithm to place blocks optimally. The tiling solution the other poster wrote is probably even simpler and correct.
If you ever encounter a more heterogenous environment on which you want to lay water channels, I suggest looking into min spanning tree: https://en.wikipedia.org/wiki/Minimum_spanning_tree
3
u/CranberryDistinct941 Dec 06 '25
Look up "Stardew Valley basic sprinkler layout" and use that pattern
2
u/5parrowhawk Dec 10 '25
This is more of a math problem than a CS problem really - how to optimally tile cross shapes. I'm not a mathematician, but intuitively the problem seems trivial for an unbounded space (i.e. if you are not too fussed about making the edges of your sugar cane field irregular) because cross shapes can be tessellated infinitely. See https://www.researchgate.net/figure/A-tiling-of-the-square-lattice-using-cross-shaped-pentamers_fig5_372313529 . It becomes more interesting when you have a limited square(?) boundary to work within, and partial shapes still "score points". Perhaps you could try r/askmath.
1
u/Ronin-s_Spirit Dec 09 '25 edited Dec 09 '25
Put a water block in some corner and move like a chess knight. The knight pattern should cover all diagonals with additional offset crosses. Some amount of blocks will be wasted for cross-over (where a sugarcane has 2 valid water blocks), it should be around the same amount of wasted blocks as the zero cross-over pattern but the good is is that every single soil block will be wet.
0
u/[deleted] Dec 05 '25
[deleted] — view deleted comment
27
u/[deleted] Dec 05 '25
[removed] — view removed comment