The world’s leading publication for data science, AI, and ML professionals.

Smarter than me

Solving an algorithmic problem using machine learning

Photo by Franki Chamaki on Unsplash
Photo by Franki Chamaki on Unsplash

I must confess that I’m passionate about algorithmic problems. These are that type of challenges that you can find on codechef, codeforces, hackerrank etc. These challenges require very little specialized knowledge, but a lot of logical thinking is needed instead. Although I’m not very much into programming competitions, I like to train my mind with algorithmic problems from time to time…just to keep me in good shape.

Photo by Rob Schreckhise on Unsplash
Photo by Rob Schreckhise on Unsplash

Losing two hours

A few days ago, while I was searching new challenges, I came across a rather easy problem at first sight: Two Groups from CodeChef.

Here’s the problem:

A multiset S contains A copies of integer 1, B copies of integer 2 and C copies of integer 3. You must determine whether you can split S into two groups (multisets) such that the sum of the first group is equal to the sum of the second group.

For example: is S={1,1,1,2,2,2,3,3,3} then the answer is YES because you can split S into {1,1,2,2,3} and {1,2,3,3}

I spent two hours trying to find a solution 🤓

Here it is:

  • If the sum of S is an odd number then the answer is NO
  • If the sum of S is an even number then:
  • put A/2 copies of 1 in the first group and A/2 copies of 1 in the second group. If A is odd then put three copies of 1 in the first group and one copy of 3 in the second group.
  • put B/2 copies of 2 in the first group and B/2 copies of 2 in the second group. If B is odd then put two copies of 1 in the first group and one copy of 2 in the second group.
  • put C/2 copies of 3 in the first group and C/2 copies of 3 in the second group. If C is odd then put one copy of 1, one copy of 2 in the first group and one copy of 3 in the second group.

The CodeChef’s response to my solution:

Photo by NeONBRAND on Unsplash
Photo by NeONBRAND on Unsplash

Even after trying several variations of the above idea, I still failed to solve the problem 🙁 . The solution I thought about was still far from the official one. After some work on it, I’ve looked at the editorial 👀

The solution is pretty strange:

Something smarter than me

One morning, an idea came to me: how about trying to let the computer solve the problem on its own?

Photo by Frank Vessia on Unsplash
Photo by Frank Vessia on Unsplash

The idea was to implement a machine learning algorithm that would solve this problem. Like any other ML algorithm, this one needed also a set of data in order to learn from it. For this problem, the data was generated in the following way:

The algorithm that I ‘ve chosen was quite rudimentary: Knn (a nice explication here by Renu Khandelwal):

The accuracy of the model is 99%. Here is the confusion matrix:

Conclusions

What I couldn’t solve in few hours by designing an algorithm, an AI was able to solve in almost a second. It needed only a few examples and took care of the rest on its own. It was smarter than me.


Related Articles