Create Sorting Algorithm to place plants in ideal spot based on compatibility

[Katie-N]

For the purpose of thinking about this: break up each row as its own array. Also, keep the dimensions fixed while we think about this.

Say we have a 3x3 plot of ground. We want to plant 1 tomato, 1 onion, and 1 pea. Tomatoes and onions are friends. Peas and onions are enemies. Tomatoes and Peas are neutral.

For n types of plants there is C number of unique relationship pairings where C = n!/[(n-2)!2!] For n=3 we expect C = 3. Check: 6/2 = 3 Yep.

For n = 4, what is C? (4321)/(2121) = 6

If we also wanted to plant potatoes Tomatoes and onions are friends. Peas and onions are enemies. Tomatoes and Peas are neutral. Tomatoes and potatoes are enemies Onion and potatoes are friends Peas and potatoes are neutral Yep there are 6 unique relationships to keep track of when planting 4 types of plants.

So the number of relationships to track grows very very quickly. (Factorials grow even quicker than exponents!)

[Katie-N]

For 1 type of plant: Easy peasy, don't even need to consider relationships.

For 2 types of plants: We only need to check if one plant is friends with the other because there are no cases where plant A is friends with plant B but B is enemies with A. if (plant A.friendlist.includes(plant B)): // Friends plant A and B near eachother else if (plant A.enemylist.includes (plant B)): // Enemies plant A and B far from each other. else: // Neutral plant order doesn't matter, just plant as given

For 3 types of plants: Consider recursion. Could call the same logic from planting 2 plants.

Also, if there is an enemy plant, we want to see if any of the other enemy plants are friends with the first enemy plants. Then they could have their own symbiotic relationship patch away from their enemies.

[Katie-N]

Let's simplify even further by saying all the plants are in one row. We want to sort them so that each plant is close to a friend/neutral and separated from an enemy.

For our example of Tomato, Onion, and Pea

let plants = [T,O,P]
sort(plants);

function sort(arrayOfPlants) {
  let sortedPlants = [];
  sortedPlants.append(arrayOfPlants[0]); // Start list off with whatever plant happened to be added first.
  for (i=0; i < arrayOfPlants.length(); i++) {
    if (!arrayOfPlants[i].enemylist.includes(arrayOfPlants[i+1].name){
      // i and i + 1 plant are friends or neutral
      sortedPlants.append(arrayOfPlants[i+1]); // Add next plant to the sortedPlants.
    } else {
      // They're enemies so we should separate them.
      // Move to the beginning of the sorted list.
      // Check the plant at the start of the sorted list is enemies with the plant you're trying to plot
      // If not, insert at the beginning of the list.
      // If they are enemies, go to the next 
      if (
    }
  }
}

Here's how I would manually sort tomatoes, onions, and peas. First I would say, tomatoes and onions are friends tomatoes and peas are neutral. onions and peas are enemies.

So separate onions and peas |onions| |peas|

Then see the free spot. IF we planted tomatoes in the free spot, its left neighbor would be a friend, awesome! IF we planted tomatoes in the free spot, its right neighbor would be neutral, that's ok too! So our final garden would be | onions | tomatoes | peas |

[Katie-N]

If I wanted to plant tomatoes, onions, peas, and potatoes manually. I would first say Tomatoes and onions are friends. Peas and onions are enemies. Tomatoes and Peas are neutral. Tomatoes and potatoes are enemies Onion and potatoes are friends Peas and potatoes are neutral

First find the enemies: Peas and onions are enemies. Tomatoes and potatoes are enemies. Could we just alternate? | pea | tomato | onion | potato | Now there are no enemies directly next to each other. But we didn't check for friendship and I'm not sure how I'd detect possibly alternating in the code.

Could also separate the first pair of enemies and then go from there | pea |_| onion || remaining plants: tomato, potato Tomato: IF we put tomato in the first empty slot, its left neighbor would be pea and they are neutral. Its right neighbor would be onion and they are friends. IF we put tomato in the second empty slot, its left neighbor would be onion and they are friends. It would have no right neighbor.

Potato IF we put potato in the first empty slot, its left neighbor would be pea and they are neutral. Its right neighbor would be onion and they are friends. IF we put potato in the second empty slot, its left neighbor would be onion and they are friends. It would have no right neighbor.

There is no advantage to planting them one way or the other. The alternating plan ended up being the best decision in this case after all.

[Katie-N]

If we planted cabbage and cucumber Cabbage and cucumber are enemies -> insert a space between them | cabbage | ____ | cucumber|

If we planted cabbage, cucumber, and strawberries Cabbage and cucumber are enemies Cabbage and strawberries are enemies Strawberries and cucumber are neutral

First separate cabbage and cucumbers | cabbage | ____ | cucumber |

Next check if the current plant (strawberry) has any enemies that neighbor the empty spot. cabbage is the left neighbor and it is an enemy so we can't plant in the empty spot. Check if the next empty spot (the end) has enemies that neighbor it. cucumber is the only neighbor (its on the left) and cucumbers are neutral with strawberries. So we plant after cucumber | cabbage | ____ | cucumber | strawberries |

[Katie-N]

So basically, I think the logic should look like this.

1. Put the first plant in the unsorted array as the first plant in the sorted array. Start Loop:
2. Check relationship: find first instance of an empty space (may be end of list)
   • if the plant left OR right of the empty space is an enemy of the current plant: skip to the next empty space.
   • else: plant in the empty space

There should also be a way to insert empty spaces.

Maybe instead of optimizing the layout, we should just let the user pick where to plant and then give a warning when they put enemies next to each other.

Could also consider a drag and drop system.

[Katie-N]

Look at this for making the garden drag and drop