The Farmer Was Replaced

The Farmer Was Replaced

Not enough ratings
Cactus - easy to understand for beginners
By Sajonji
Working code for sorting and harvesting cacti. Easy to understand even for coding beginners. Will of course contain spoilers.
   
Award
Favorite
Favorited
Unfavorite
Introduction
Here is a quick and working guide for sorting cacti and harvesting the whole field.
I'm a junior-dev IRL though not with Python. This game was a little and fun learning experience for me.
Meaning my code can surely be improved on and optimized. Though i don't care right now, it's working and doing it's thing.

This guide will provide code, therefore it contains obviously spoilers for the cactus puzzle. It should be obvious, but we live in difficult times regarding common sense and thinking capability ;)

Might also contain spelling errors, i wasn't to keen to double and triple check everything. If you find a spelling error: finders keepers :)
Overview
Important: i have the option in Options -> Errors -> Shadowing Errors disabled (as i'm a developer myself and know the basics about scopes). If you have that option enabled, you probably get errors. Either rename the loop variables inside the small helper functions to something unique (no variable used inside the main script) or also turn said option to disabled.

The basic idea is just like the hint of the cactus introduction tells you:
If we sort all columns and afterwards all rows (or vice-versa) in a grid, the whole grid will be sorted.

I have some useful functions (also useful for other puzzles), so here is what we're going over:
1. Initial tilling
2. trade to bound
3. go to position
4. cactus script
Initial Till
A small function to till the whole farm area:

def initial_till(): for i in range(get_world_size()): for i in range(get_world_size()): till() move(North) move(East)

Really nothing fancy, and also ends at the field you're starting in.
Trade to Bound
I don't like buying more seeds than i need, so sometimes this function is helpful if you know exactly how much seeds you need. Because cacti always do grow (unlike pumpkins), we do know how much seeds we need.
def tradeIfLower(item, number): nItem = num_items(item) if nItem < number: trade(item, number - nItem)

For example, if you have 4 cactus seed, and want to buy up to 10 seeds, this will buy 6 seeds.
Go to position
Often, you can traverse the whole field with just moving north and east until you're back at the starting position. Sometimes though, we want to move to specific tiles. This function does exactly that:

def goTo(xCoord, yCoord): if get_pos_x() > xCoord: goRight = xCoord + get_world_size() - get_pos_x() else: goRight = xCoord - get_pos_x() if get_pos_x() > xCoord: goLeft = get_pos_x() - xCoord else: goLeft = get_pos_x() + get_world_size() - xCoord if get_pos_y() > yCoord: goUp = yCoord + get_world_size() - get_pos_y() else: goUp = yCoord - get_pos_y() if get_pos_y() > yCoord: goDown = get_pos_y() - yCoord else: goDown = get_pos_y() + get_world_size() - yCoord # move left or right, whichever is faster if goLeft < goRight: for i in range(goLeft): move(West) else: for i in range(goRight): move(East) # move up or down, whichever is faster if goDown < goUp: for i in range(goDown): move(South) else: for i in range(goUp): move(North)

I don't want to go too much in depth, as this guide is about cacti, but here is the gist:
We are getting the x and y coordinate of our goal position. Then we calculate if it would be faster to go left or right and up or down. Then we move accordingly to the shortest path.
Cactus Script
Finally the main script for the cacti. You'll need the helper functions shown before, without them, you'll get errors.
First the script, explanation is below.

clear() cache = {} initial_till() while True: tradeIfLower(Items.Cactus_Seed, get_world_size()**2) for i in range(get_world_size()): for j in range(get_world_size()): plant(Entities.Cactus) cache[(i,j)] = measure() move(North) move(East) #sort columns for h in range(get_world_size()): count = 0 for i in range(get_world_size() - 1): #check if already sorted sorted = True for s in range(get_world_size() - 1): if cache[h,s] > cache[h,s + 1]: sorted = False break if sorted == True: break for j in range(get_world_size() - count - 1): if cache[h,j + 1] < cache[h,j]: swap(North) cache[(h,j)] = measure() cache[(h,j + 1)] = measure(North) move(North) goTo(h,0) count += 1 move(East) #sort rows for h in range(get_world_size()): count = 0 for i in range(get_world_size() - 1): #check if already sorted sorted = True for s in range(get_world_size() - 1): if cache[s,h] > cache[s + 1,h]: sorted = False break if sorted == True: break for j in range(get_world_size() - count - 1): if cache[j + 1,h] < cache[j,h]: swap(East) cache[(j,h)] = measure() cache[(j + 1,h)] = measure(East) move(East) goTo(0,h) count += 1 move(North) harvest()

If you just want to copy the code, stop looking here. Anything below is just explanation of the main script.
This is a little bigger, but let's break it down.

First of all, we're do clear(), to reset to default. This also puts the drone at our starting position of 0 , 0. Then we're defining an empty dictionary. We will use that to keep track of the cactus values.
Before entering the main loop, we also do an initial_till, because cacti need soil.

Starting in the main loop, we have this block first:

tradeIfLower(Items.Cactus_Seed, get_world_size()**2) for i in range(get_world_size()): for j in range(get_world_size()): plant(Entities.Cactus) cache[(i,j)] = measure() move(North) move(East)

Basically, we buy seeds, if we don't have enough for the whole field.
Then we traverse the whole field, plant a cactus on each field and save the size of the cactus in the dictionary with the current position as key.

Next, we sort the cacti column wise. Let's start explaining from the inside. The most important loop is the j-loop:

for j in range(get_world_size() - count - 1): if cache[h,j + 1] < cache[h,j]: swap(North) cache[(h,j)] = measure() cache[(h,j + 1)] = measure(North) move(North)

Ignore the count for a second.
This loop compares the cactus currently below the drone with the next one. If the next one is smaller, then we swap. Of course we then need to update our cache.
We do these comparisons for the whole column.
After this loop, the biggest number (or one of them if there are multiple identical numbers) is guaranteed to be at the far end.

Of course we need the whole column sorted, meaning we need to sort as many times as the column has elements minus one. Because if you have 3 elements, you can only do 2 comparisons ( 1 with 2 and 2 with 3).
Hence we wrap our loop with another loop:

for i in range(get_world_size() - 1): #check if already sorted sorted = True for s in range(get_world_size() - 1): if cache[h,s] > cache[h,s + 1]: sorted = False break if sorted == True: break for j in range(get_world_size() - count - 1): if cache[h,j + 1] < cache[h,j]: swap(North) cache[(h,j)] = measure() cache[(h,j + 1)] = measure(North) move(North) goTo(h,0) count += 1

The i-loop is exactly doing that, making sure the whole column gets sorted, not only 1 number.
Now we also see the count variable we use in the j-loop.
Every time the j-loop sorts the biggest number to the end, we can compare 1 less field, because we already know that the biggest number got sorted to the end.
You could run the code perfectly fine without the count, though it would be less optimized.

I've also built another optimization: before we start sorting the biggest number, we check if the whole column is already sorted. In that case we just break the i-loop, and move on to the next column.

Finally we wrap this in another loop to sort every column in the grid:

#sort columns for h in range(get_world_size()): count = 0 for i in range(get_world_size() - 1): #check if already sorted sorted = True for s in range(get_world_size() - 1): if cache[h,s] > cache[h,s + 1]: sorted = False break if sorted == True: break for j in range(get_world_size() - count - 1): if cache[h,j + 1] < cache[h,j]: swap(North) cache[(h,j)] = measure() cache[(h,j + 1)] = measure(North) move(North) goTo(h,0) count += 1 move(East)

After we have sorted every column, we now need to also sort all the rows.
Basically it's the same code as for the rows, but simply switched some indices and movement directions to transform sorting of columns into sorting of rows. I won't go into detail here, as it is so similar.

Finally, after all the rows have been sorted, we call harvest() and are happy about harvesting a full field of cacti.
Afterwords
Thanks for reading.

If you found this guid helpful, consider a thumbs up, to also help out others looking for help.

If you have any questions, feel free to ask inside the comments, i'll try to help as much as my free time allows it.
5 Comments
Ovalsquare 12 Jun @ 9:30am 
Sorry I hit the comment limit of 1,000 chars. Then after the sort, you just need to call harvest(). I think this version if O(n^3) and was the most efficient way I could think of after multiple refactors.
Ovalsquare 12 Jun @ 9:29am 
Hey, I recognize this thread was posted many months ago but it is still the first one regarding the Cactus puzzle that shows in the popular guides section so I thought I would post this here to maybe help some in the future / get your thoughts Sajonji. I implemented a version of insertion sort here that may be easier to understand, as you don't have to deal with a list or dictionary at all and I just use the built in move(direction) function rather than the go_to function (which I have a version of as well that is similar to yours).

def insertion_sort():
n = get_world_size()

# SORT THE ROWS
go_to(0,0)
for y in range(n):
for x in range(n):
go_to(x,y)
while get_pos_x() != 0 and measure() < measure(West):
swap(West)
move(West)

# SORT THE COLUMNS
go_to(0,0)
for x in range(n):
for y in range(n):
go_to(x,y)
while get_pos_y() != 0 and measure() < measure(South):
swap(South)
move(South)
alfred 21 Oct, 2024 @ 3:30am 
@Sajonji
I realised that my solution had a slight difference, which is why I needed to loop the sort, after changing that, it seems to work
Sajonji  [author] 4 Oct, 2024 @ 3:34am 
@alfred: You're wrong.
Supposing i have understood your example correct, it looks like this initially:
4 1
3 2

After sorting columns, you get:
4 2
3 1

After sorting rows we then have:
2 4
1 3

Which is the correct result.
If i interpreted your example wrong, please write the example down in a graphic way, like i did.

Lastly, this cactus problem is a rather standard problem in coding. Therefore i'd be very surprised if the widespread standard solution "sort both rows and columns" is wrong here ;)
alfred 29 Sep, 2024 @ 5:43am 
The way I understand it, isn't there a case where the columns aren't sorted anymore after the rows are. Consider ((4, 1), (3, 2)) (left to right, top to bottom) after sorting columns, when you sort the rows, you get ((1, 4), (2, 3)) now the columns aren't sorted
For anyone interested, my way around this is just to loop over the whole sorting process until both are sorted
Otherwise good guide though