Steam Community :: Guide :: The Gnome and The Cactus

Store Page

The Farmer Was Replaced

All Discussions Screenshots Artwork Broadcasts Videos News Guides Reviews

The Farmer Was Replaced > Guides > owenz's Guides

Not enough ratings

The Gnome and The Cactus

By owenz

So your cactus needs sorting?

Try letting our horde of gnomes handle that? They are very good at getting them prickly plants into a short to tall sequence.

Come on down to get your gnomish sorters today!

Award

Created by

owenz
Online

Category: Gameplay Basics, Walkthroughs

Languages: English

Posted

Updated

16 Jun, 2024 @ 10:35am

20 Jul, 2024 @ 7:03pm

782	Unique Visitors
2	Current Favorites

Guide Index

Overview

The Problem Space

PreSort

PreSort - Code

The Sort

The Sort - Code

Into 2-D Sort

Into 2-D Sort - Code

Put It All Together

Put It All Together - Code

Further Improvments!

Code Complete

Comments

The Problem Space

So you have unlocked the cacti and now in order to even harvest it the cacti must be sorted from shortest to tallest in a 2-Dimension space.

https://youtu.be/1LaOMhF5k_E

A cactus only drops cactus items when harvested if it's in sorted order. A cactus is considered to be in sorted order if there is a smaller or equal cactus to the South and to the West and a larger or equal cactus to the North and to the East. Essentially the cacti must be sorted in increasing x and y directions for them to drop anything.

With the above prompt we must essential sort the cacti for lest to greatest in 2-Dimensions. As 1-Dimensional array sorting is a very much solved thing, to the best of human ability, let us just look a sorting algorithm.

Sorting Algorithm Chocies

Merge Sort - Merging
Heap Sort - Selection
Tree Sort - Insertion
Block Sort - Insertion/Merging
Bubble Sort - Exchanging

Now look at that list of possible sorting methods, not all possible, each with it's own benefits

Now let's prune those choices down to get the one we need.

Qualifications

Must be stable
Drone must be able to complete the sort, as drone cannot pick up cacti

Oh no, look at that we have already narrowed down the space in which we can work to only exchange as the drone is limited in what it can do. The limitations of the drone means we can only do inplace exchanges so we must use an exchanging sort. There are only a limited number of such a sorting method.

Bubble Sort - Exchanging
Comb Sort - Exchanging
Cocktail Shaker Sort - Exchanging
Gnome Sort - Exchanging
Odd-Even Sort - Exchanging
Exchange Sort - Exchanging

Now that we have a few to choose from let's narrow down our choice. Firstly we want an easy to implement algorithm which is small in size and performs at about the same at the others. It must also be able to be easily modified to work in 2-D space so that we can sort the cacti to their specifications.

Ok, with those limitations we get the Cocktail Shaker, Gnome, and Bubble sorting. Looking further into it only the cocktail shaker and gnome sort fit into the simplicity of code that is needed to easily implement into 2-D space. Finally, gnome sort takes the position of the last sort and moves back to it vs the cocktail sort which slides back and fourth until each elements is sorted(harder to do in 2-D as we piviot on each slide making it take way longer) thus we are left with the gnome(I am not paid or sponsored by the gnome, I swear!!!)

PreSort

Now that the problem space has been defined and we selected an algorithm that should work for us let's start to implement that into a working format. This will be harder than we initially expected as taking something that is meant for 1-D spaces into the 2-D spaces can be cumbersome and difficult.

Implementing the Gnomes

Let us first start by sorting a single row of the cacti and then harvesting it as we are not yet prepared for 2-D as we have nothing to build on.

So, first things first. I create a new game for this and just modified the save to unlock all the resources and unlocks.

Thus, the main is empty.

Starting from scratch just off the top we need several things before we can even plant the cacti.

A movement function
A planting function

You might be wondering why we don't have the harvesting function yet, well we are going to put that logic in the cacti phase loop later so for now we only need to move around and plant.

Movement is easily accomplished and thus let's just make one here

def move_self(tx, ty): # Code is in Code Section ...

Now we have the ability to move around the map and it returns the (x, y) of it's last position, we can always change it to the same true/false of the built-in move function though.

Next we need the planting function for cacti.

def plant_crop(crop): # Code is in Code Section ... def plant_cacti(): # Code is in Code Section ...

OK, now we can plant a cacti at (x, y). So now we need to create a function to traverse the board in order to plant the entirety of it. As a note the board can be treated as a 1-D array as there is not need for it to be a 2-D one as each space is equivalent. Thus we will convert all positional data to 1-D, though not sorting data as the cacti data is not equivalent.

def one_d_two_d(pos): # Code is in Code Section ... def two_d_one_d(x, y): # Code is in Code Section ...

Now that we can convert the 2-D position to a 1-D position we can use a simple for loop that iterates over the whole board.

def plant_cacti_field(max_pos): # Code is in Code Section ...

Awsome, now we can just pass in a 1-D position of the board and the little drone will plant it.

So if we just want the first row down we just need to put in a 10

plant_cacti_field(10)

Finally, on the the sorting.

PreSort - Code

All Code for The Sort section.

The Sort

Everything we need to start writing the gnome sort is now complete, we can move and plant the board, awesome.

Gnomes!

Sorting is a complex and very needed to solve issue in all of computer science, and using an efficient algorithm that does things in O(1) time is the dream but alas we are stuck at doing it in O(n^2) time with our Gnomes. Do not fret though as it is still just as good as the other exchanging sorts.

Now let us implement the gnome sort

GNOME SORT PSUDECODE

Source:
en.wikipedia.org/wiki/Gnome_sort

procedure gnomeSort(a[]): pos := 0 while pos < length(a): if (pos == 0 or a[pos] >= a[pos-1]): pos := pos + 1 else: swap a[pos] and a[pos-1] pos := pos - 1

As can be quickly seen this is a very small and easy to grasp sorting algorithm, just perfect for us to tinker with.

Let's sort that first row that we planted. As the gnome sort always sorts to the left from the right then moves to the previous position we will do the same.

def gnome_basic(): move_self(0, 0) # Start at the root node

First step get to the root node.

pos = 0

Second, set the position to the root node

while pos < max_pos: ...

Now we need to loop through the board's positions till we hit our limit.

def plant_cacti_field(max_pos): board = [] for i in range(max_pos): x, y = one_d_two_d(i) if not plant_cacti(x, y): return False board.append(measure()) return board

We need to measure the cacti to ensure we are sorted!!!! Thus we need a thing to hold the information and we need to measure the data and change the planting function to do that as it should be done in there as the values is decided on planting.

... while pos < max_pos: x, y = one_d_two_d(pos) move_self(x, y) if pos == 0 or board[pos] >= board[pos - 1]: pos += 1

Next is to move around the board if the current position is greater than the previous position, and to change the positional data as we go.

else: board[pos], board[pos - 1] = board[pos - 1], board[pos] swap(West) pos -= 1

Finally we swap as if the previous if statement failed we know that we are less than and thus need to do a swap and in addition we need to update our position and move to the previous swaped position.

Now everything put together.

def gnome_basic(max_pos, cacti): move_self(0, 0) # Start at the root node pos = 0 board = cacti while pos < max_pos: x, y = one_d_two_d(pos) move_self(x, y) if pos == 0 or board[pos] >= board[pos - 1]: pos += 1 else: board[pos], board[pos - 1] = board[pos - 1], board[pos] swap(West) pos -= 1

Let see what that looks like now

The Sort - Code

Code for The Sort

def plant_cacti_field(max_pos): board = [] for i in range(max_pos): x, y = one_d_two_d(i) if not plant_cacti(x, y): return False board.append(measure()) return board def gnome_basic(max_pos, cacti): move_self(0, 0) # Start at the root node pos = 0 board = cacti while pos < max_pos: x, y = one_d_two_d(pos) move_self(x, y) if x == 0 or board[pos] >= board[pos - 1]: pos += 1 else: board[pos], board[pos - 1] = board[pos - 1], board[pos] swap(West) pos -= 1

Into 2-D Sort

Now all that is left is to finish planting the entire field and then sort it. Planting is not hard

clear() cacti_board = plant_cacti_field(100) gnome_basic(10, cacti_board)

Here is the field fully planted with the first row sorted.

Now the problem is that the gnome sort lacks the ability to sort in 2-D and as a result would totally mess this up and get stuck in an infinite loop as it. We can make it sort each row easiliy by doing the following.

if x == 0 or board[pos] >= board[pos - 1]: ... gnome_basic(100, cacti_board)

This will give us the following

As seen we have everything row sorted and planted. This does us no good as we need to be sorted as shown in the video at the head of this guide. Let us create an advanced gnome sort!

def advanced_gnome_sort(cacti): ws = get_world_size()

First thought is to just reuse the previous basic_gnome sort and add a pivoted sort of the basic. This should work, let's try it out.

while pos < ws**2: x, y = pos % ws, pos // ws move_self(x, y) if y > 0 and y != ws: pos_2 = two_d_one_d(x, y - 1) if board[pos_2] > board[pos]: swap(South) board[pos_2], board[pos] = board[pos], board[pos_2] pos = pos_2 continue y += 1 if y >= ws: y = 0 x += 1 if x >= ws: break pos = two_d_one_d(x, y)

This code block is a lot beefier but it is basically the same as the basic just pivoted. There is some nuance here though as we have to account for the fact we pivoted the board. Thus the extra little bit of checks and setting the pos.

while pos < ws**2: x, y = one_d_two_d(pos) move_self(x, y) ... y += 1 if y >= ws: y = 0 x += 1 if x >= ws: break pos = two_d_one_d(x, y)

The easy part is setting the drone location via the position. This is done through the 1-D -> 2-D functions and adding 1 to y then reverting it so that the move_self function can get us there, and handling the moving around the board

if y > 0 and y != ws: pos_2 = two_d_one_d(x, y - 1) if board[pos_2] > board[pos]: swap(South) board[pos_2], board[pos] = board[pos], board[pos_2] pos = pos_2 continue

Next is the meat and potatoes of the function which is to swap, and as such we need to check and swap. The magic is that part where we switch to pos_2 and then continue as this skips the rest of the code so we don't update the position normally.

And look at this,

Into 2-D Sort - Code

Code for the Into 2-D Sort

def advanced_gnome_sort(cacti): ws = get_world_size() gnome_basic(ws**2, cacti) move_self(0, 0) # Start at the root node pos = 0 board = cacti while pos < ws**2: x, y = one_d_two_d(pos) move_self(x, y) if y > 0 and y != ws: pos_2 = two_d_one_d(x, y - 1) if board[pos_2] > board[pos]: swap(South) board[pos_2], board[pos] = board[pos], board[pos_2] pos = pos_2 continue y += 1 if y >= ws: y = 0 x += 1 if x >= ws: break pos = two_d_one_d(x, y)

Put It All Together

Now that we have a working sorting function all we need to do is add that last little bit to harvest it.

pre_harvest = num_items(Items.Cactus) harvest() quick_print(num_items(Items.Cactus) - pre_harvest)

As we can see after this harvest, with max upgrades, we get 4,000 cacti. A decent harvest. Now let us time it.

start_time = get_time() clear() cacti_board = plant_cacti_field(100) advanced_gnome_sort(cacti_board) pre_harvest = num_items(Items.Cactus) harvest() quick_print(num_items(Items.Cactus) - pre_harvest) quick_print(get_time() - start_time)

Nice, 27.93 secs that is decent.

Let's clean up the code and such. We will not get too much of time savings by doing this and as such it is just to make it more concise. What we will do is combine the two separate sorting functions into one.

def final_gnome_sort(cacti): ...

That is a complete solution that still gets us in the ~30 sec range. I implore the reader to try one of the other sorting methods mentioned at the start and to see if they have any time savings over the Gnomes.

Also as a note, an optimization one can do is to only move to the (x, y) when you are doing a swap. If no swap is performed do not even bother, take into account that you have to move there before the swap though.

Put It All Together - Code

Code for Put It All Together

def final_gnome_sort(cacti): # Reset drone to 0,0 move_self(0, 0) ws = get_world_size() cacti_val = cacti # Sort all cacti using moddifed gnome sort pos = 0 while pos < ws**2: # Swap pos to south x, y = one_d_two_d(pos) if y > 0 and y != ws: pos_2 = two_d_one_d(x, y - 1) if cacti_val[pos_2] > cacti_val[pos]: move_self(x, y) swap(South) cacti_val[pos_2], cacti_val[pos] = cacti_val[pos], cacti_val[pos_2] pos = pos_2 continue # Swap pos to left if x == 0 or cacti_val[pos] >= cacti_val[pos - 1]: pos += 1 else: move_self(x, y) cacti_val[pos], cacti_val[pos - 1] = cacti_val[pos - 1], cacti_val[pos] swap(West) pos -= 1

Further Improvments!

Thanks to N0ma13 for the following idea.

Originally posted by Mairsil The Pretender:
Originally posted by N0ma13:
... the more I run the sunflowers the more I realize it needs refactored to use dictionaries.
Obv was made before that unlock.

...

The more I looked at sunflowers, the more I came to the realization that the obvious solution, figure out the maximum petals among your grid, is far less efficient than planting a grid full of MINIMUM petals and then just working a single cell with anything other than minimum. The minimum of seven came from trial and error because I couldn't find anything with the actual range of possible petals. With maximum drone speed, but no mazes yet (so base level sunflowers because I have no treasure) and a 10x10 farm, this cranks out 6,000 power per minute. Great if you have enough pumpkins for infinite fertilizer.
...

Instead of using this method for the sunflowers as there is cannot shine. I tested it with the cacti. And boy does it work. It is effectively reducing the problem space as instead of having to sort the entire space with any value between 1-9 it is now reduced to the following code

def plant_cactus(entity, ground, to_buy_at_once=10): if ground == Grounds.Turf: till() if num_items(Items.Cactus_Seed) > 1 or trade(Items.Cactus_Seed, to_buy_at_once): if plant(Entities.Cactus): val = measure() if val // 2 > get_pos_y() or val // 2 > get_pos_x(): till() return plant_cactus(get_entity_type(), get_ground_type()) return val return False

The magic line is if val // 2 > get_pos_y() or val // 2 > get_pos_x(): as it is effectively placing a limit on each square as it is planted. This change brings our times to a mean of 23.4 seconds after 23 harvests. For reference the standard used before was a mean of 27.5 seconds. This is a ~17% time improvement even though the seed cost will be slightly higher.

So that 17% savings translates into a jump from 109 cacti per sec to 127 cacti per sec.

I am still tweaking the values but this is definitely a good route to go down.

Stats

Pre/Post Change To Planting

Mean

Median

Min

Max

Pre

27.17

26.88

22.51

31.33

Post

23.49

23.98

18.55

27.28

Code Complete

Below is every code section in one place.

def one_d_two_d(pos): world_size = get_world_size() return pos % world_size, pos // world_size def two_d_one_d(x, y): world_size = get_world_size() return x + y * world_size def move_self(tx, ty): ws = get_world_size() dx, dy = get_pos_x() - tx, get_pos_y() - ty ns = (None, South, North) we = (None, West, East) def inner_move(delta, move_dir): if abs(delta) > ws // 2: delta -= (delta / abs(delta)) * ws for i in range(0, delta, delta / abs(delta)): move(move_dir[delta / abs(delta)]) inner_move(dx, we) inner_move(dy, ns) return get_pos_x(), get_pos_y() def plant_crop(crop): if get_ground_type() != Grounds.Soil: till() if get_entity_type() != crop: return plant(crop) return False def plant_cacti(x, y): move_self(x, y) return plant_crop(Entities.Cactus) def plant_cacti_field(max_pos): for i in range(max_pos): x, y = one_d_two_d(i) plant_cacti(x, y) def plant_cacti_field(max_pos): board = [] for i in range(max_pos): x, y = one_d_two_d(i) if not plant_cacti(x, y): return False board.append(measure()) return board def gnome_basic(max_pos, cacti): move_self(0, 0) # Start at the root node pos = 0 board = cacti while pos < max_pos: x, y = one_d_two_d(pos) move_self(x, y) if x == 0 or board[pos] >= board[pos - 1]: pos += 1 else: board[pos], board[pos - 1] = board[pos - 1], board[pos] swap(West) pos -= 1 def advanced_gnome_sort(cacti): ws = get_world_size() gnome_basic(ws**2, cacti) move_self(0, 0) # Start at the root node pos = 0 board = cacti while pos < ws**2: x, y = one_d_two_d(pos) move_self(x, y) if y > 0 and y != ws: pos_2 = two_d_one_d(x, y - 1) if board[pos_2] > board[pos]: swap(South) board[pos_2], board[pos] = board[pos], board[pos_2] pos = pos_2 continue y += 1 if y >= ws: y = 0 x += 1 if x >= ws: break pos = two_d_one_d(x, y) def final_gnome_sort(cacti): # Reset drone to 0,0 move_self(0, 0) ws = get_world_size() cacti_val = cacti # Sort all cacti using moddifed gnome sort pos = 0 while pos < ws**2: # Swap pos to south x, y = one_d_two_d(pos) if y > 0 and y != ws: pos_2 = two_d_one_d(x, y - 1) if cacti_val[pos_2] > cacti_val[pos]: move_self(x, y) swap(South) cacti_val[pos_2], cacti_val[pos] = cacti_val[pos], cacti_val[pos_2] pos = pos_2 continue # Swap pos to left if x == 0 or cacti_val[pos] >= cacti_val[pos - 1]: pos += 1 else: move_self(x, y) cacti_val[pos], cacti_val[pos - 1] = cacti_val[pos - 1], cacti_val[pos] swap(West) pos -= 1

15 Comments

< >

HarshTarsier290 13 Jan @ 2:10am

I get the error "attempted to divide by zero" here

def inner_move(delta, move_dir):
if abs(delta) > ws // 2:
> delta -= (delta / abs(delta)) * ws
for i in range(0, delta, delta / abs(delta)):
move(move_dir[delta / abs(delta)])

hooverad 23 Dec, 2024 @ 1:40pm

I just brute force the problem by not leaving a square until it contains a 9. Exploiting the "or equal" part of the check.

Basically, if it is not a 9, harvest it, if it is a 9, move on. Fill in the whole field that way, and then harvest.

Chews through carrots like MAD, but it works.

owenz [author] 31 Jul, 2024 @ 3:09pm

@Shoninya also look at the "Putting It All Together" section as the main loop code I used for testing is there and would have worked.

owenz [author] 31 Jul, 2024 @ 3:08pm

Simply just call the plant then sort.

So to do it one time ->

final_gnome_sort(plant_cacti_field(get_world_size()**2))

This follows what is going on as plant_cacti_field takes 1 argument which is the total number of positions you would like to plant and in a max sized field's case it would be 100 or world size squared.

Then we pass the board which is returned from plant_cacti_field to the gnome sorting function and it will do what needs to be done at that point.

Also, as I stated before I have no idea what or how another performs there code and this guide isn't a copy pasta it all solution though the code provided does work and is as effective as stated.
As long as a 1-D array with the cacti values is passed in the function will sort.

Shoninya 29 Jul, 2024 @ 10:56pm

then maybe thats the issue. cant you send the full code in one file?
or excluding to this, how should the main loop look like then?

owenz [author] 29 Jul, 2024 @ 10:48pm

You have to create a main loop to call the function, no idea what your code environment looks like so I did not provide a main loop.

Shoninya 20 Jul, 2024 @ 11:51pm

thanks, i just tried it. nothing happens. the "define" statement shortly glow and thats it. :(

naming of this code dosnt matter?

owenz [author] 20 Jul, 2024 @ 7:05pm

@Shoninya

I can, I will append a section for that.

Shoninya 18 Jul, 2024 @ 11:04pm

can you then maybe provide one code file? it dosnt has to be several,

cause its very confusing with these plenty code snippets here. thanks

owenz [author] 15 Jul, 2024 @ 8:52pm

@Shoninya Considering the fact that I created a new save just for this guide and the code is a direct reflection of this save's code I can only infer that your code has something going on. Also this is for the cactus sort and has nothing to do with the maze solutions.

I have directly copy pasta'd this code into the a new save as well and it runs as described,

In addition the fact that you are seeing it moving but not functioning properly leads me to believe that there is something going on in how you copied it over and have code in the background that is messing with the code I provided. I cannot do anything about that particular and this guide is just a run down on how to implement an exchange type sort which in this case is the gnome sort.

< >