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.