Element of 2D sort
I don't have a fully cooked idea today, so let's discuss half-baked.
In The Farmer Was Replaced game there is a subgame where you plant cacti. Quite a complex description of game rules boils down to quite a simple idea: in order to make cacti harvest efficient, you are to sort 2D matrix of cacti heights. I.e. cacti become bigger when you move upward or to the right.
And, of course, there are limitations. You can move agent (drone) and it can swap a cactus under it with neighboring cacti. This prevents long-distance swaps, typical for traditional sorting algorithms like quicksort or merge sort and gives time complexity of O(n³) for n, the side length of the square field.
There is a global leaderboard in the game and the first place is 17 seconds for 8x8 field. My best attempt so far is 24.3 s. It's a 2D modification of insertion sort, I posted in here some time ago.
And today I'm going to try the approach in the picture. C - is the current drone position. Other letters - are the neighbors. Idea I want to test:
- write a tiny optimal procedure which sorts the cross in the order
- scan the field, apply the algorithm to each cell
- run insertion sort
My intuition is that this "cross local optimization" can cheaply move cacti far both in horizontal and vertical direction and it should take part of the load off insertion sort.