Hey Sandeep Panda, thanks for this awesome question!

Code at github.com/sidhantpanda/FoxGooseCorn.

We can assume a state of the the game represented as a string of 0s and 1s. 0 means the character is on the right side and 1 means the character/item is on left side.

1. The 0th index represents the Farmer.
2. The 1st index represents the Fox.
3. The 2nd index represents the Goose.
4. The 3rd index represents the Corn.

For eg, the string "1011" represents:

1. Farmer is present on left side.
2. Fox is present on right side.
3. Goose is present on left side.
4. Corn is present on left side.

Now each index has 2 possible values -> 0 or 1. Hence the total number of states the game can possible go into is 2^4 = 16.

We have a forest of all the states possible:

[0000] [0001] [0011] [0111] [1000] .... [1100] ... [11110] ....

Now as per the question, there are some illegal states which will lead to the game stopping. We'll mark these states as invalid.

Now we check each state and find the possible next state from it (provided its not invalid) and add a directed edge between them with a weight of 1.

Now we have a directed graph and we can easily use Dijkstra's algo to find the shortest path and steps required.

The time complexity for setting up the forest is O(n). Thus our whole solution is limited by the time complexity of Dijkstra where we are using a MinHeap as a priority queue.

Would recommend everyone to give this question a try! It touches a lot of concepts:

1. Graphs
2. MinHeaps (used for maintaining priority queue during the last phase)
3. Dijkstra Algo (to find the least number of steps and the shortest path)

The solution (1 of 2) so people can use it to code it:

1. farmer takes the goose, leaving fox and beans on river bank 1
2. farmer comes back
3. farmer takes the beans & brings the goose back, leaving the beans on river bank 2
4. farmer takes the fox, leaving the goose on river bank 1
5. farmer comes back
6. farmer takes the goose, now everything is on river bank 2

In code: There are the 2 conditions of things eat things. But there is also the 3rd condition that under the farmer things do not eat things.

Expectations Crusher

I am diverting a little bit from the way I usually answer questions; this time, I will not write the code immediately since I want to go into the theory more as a lot of good concepts are revealed! I am so sorry Sandeep Panda for not answering the question directly! I will, in the near future!

Prologue

This is a really interesting problem which everyone should try as it can be implemented in a couple of ways. I will try explaining two simple methods here:

Recursion

With a simple if-else-if ladder, you can keep on checking if two entities collide. The logic for this can be as simple as saying that -1 means one side and 1 means the other side. You can, then, define a HashMap to match the possible collisions as the product of these two weights. Then, keep on recursing till you reach a pre-mapped disposition (where every weight is -1 or 1) .

Binary Classification

We humans are really good at making simple - yes/no - decisions.

• Is Hashnode the best? Yes.
• Does Shreyansh Pandey type way too much? Yes.
• Should I use ASP.NET for my next API? GOD NO!

You get the picture. Now, we know which two entities have a problem with each other. Based on this, you can create a simple mapped model and then use recursion to solve it. This isn't a method as much as it is an extension or an approach.

Discrete Mathematics

This is where it gets super interesting.

If you define each of the entities as a tree node and the edges (what connects two nodes) as a trip (or a mutation), you can build a very simple abstract (or even cyclic) tree. Now that you have the final state represented, you can solve this problem in one of two ways:

Graphical Disposition

You can use the shortest path algorithm (Dijkstra's, for example) and find the required mutations. Pretty simple stuff, so we will leave this as an exercise for the reader.

Linear Algebra

Extending from the above, there is another way to look at this problem. Imagine, in the standard 2D plane, we have two vectors: a and b.

We can see that we can define a as a scalar product of b. Why? Because it's made by adding b three times and multiplication is nothing but fancy addition. So, more formally, we can define this as:

Hmm. Notice something? a and b are related. Now, the biggest problem becomes that we are restricted to the line y = x. We can do whatever we want with a and b, but they are useless because they stay on the same line and go no where. This is called a dependent vector and it's useless for us right now. Let's find some independent ones!

Awesome! Now we have two independent vectors. I can hear you asking - Okay, this is good. But for what joy?! Let me explain. With two independent vectors, we can reach any point in space.

Let's take an example: suppose we want to reach the point P(2, 4). We can do this by:

Perfect.

Now let me introduce what solves the question.

If we know the end state as a graph, we can represent it as a point. Then, we can have 4 dimensions (one for each entity) and as long as we have the same number of independent vectors, we can reach that end-position!

More specifically, we want to solve the following system:

With that said, you can now find a static mutation and list the steps you need to make this happen. The initial vectors are all (0, 0, 0, 0). Based on the system you are using, you can define the final vector according to your needs.

---

Programming

After some good Math, this part looks a little boring. However, the explanations are in no way complete and I will update them with more descriptive mathematical content in a day.

I am starting a GitHub repository where I will solve the question using recursion, then with graphs and then, finally (if I have some intellect left) with linear algebra.

---

Spoiler

Don't give up! However, for everyone practicing TDD, here is the answer:

1. take the goose and come back;
2. take the fox and bring the goose back;
3. take the corn and leave the goose;
4. come back to get the goose and done.