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

How I Completely Destroyed This Challenge Using “One Line of Code”

Think Twice, Code Once – Solving "Game of Maximization" Problem like a Pro

PROGRAMMING

Source: Image by the author (quote from Linus Torvalds)
Source: Image by the author (quote from Linus Torvalds)

Recently I participated in a competition, held by HackerRank (HackerFest 2020), where I encountered a problem called "Game of Maximization". And I solved it with only one line of code!

How? Let me show you …

I’m using this problem as an example to depict "how you should think while solving a competitive coding challenge"; how to write better Algorithms, faster.

For me, competitive coding is a form of art (just like obfuscated programming) where a person tries to solve a given problem most efficiently with a minimal amount of code.

Usually, Lesser Code = More Efficiency

Keeping that in mind, I’ll start with the piece of code that a beginner can understand, and then improve it further, step by step, to the pro level. Each time explaining my approach to you.

So let’s get started!


The Problem

Have a look at the problem statement first: –

Source: Image by the author (screenshot of the problem)
Source: Image by the author (screenshot of the problem)

As you can see, you need to pick the same number of stones from the odd-positioned piles as from the even-positioned piles; while picking no more than the number of stones available in the corresponding pile.

Pause and have a second to wrap your head around it.

We’re gonna build a function called maximumStones which will accept an integer array arr, representing the number of stones in each pile. And return a single integer representing the maximum total number of stones you can pick.

I’ll be using Python for the sake of simplicity and faster development.

How many lines of code do you think you’ll need to solve it?


First Iteration— The Novice method

Don’t try to identify the problem for its genre. It may be a greedy problem or a problem from dynamic programming, we don’t care. Let it come to you naturally.

If we do exactly what was written in the problem statement, we’ll end up with the code like this:

Don’t get intimidated by it. It’s actually straightforward.

Code Explanation

Here, we have calculated the sum of the number of stones in the odd-positioned pile and in even-positioned piles in variables a and b respectively, beforehand. Then, we’re looping until the difference between both (a and b), in variable c, becomes zero, that is, until a == b.

In each iteration, we see which piles need modification. If the odd-positioned piles(a) have a greater number of stones (c > 0), then we’ll subtract stones from those piles, otherwise, from the even-positioned piles.

How many stones do we need to subtract? c number of stones

While subtracting each time, we need to confirm whether we can subtract the whole pile (if picks[k]-c > 0) or not; and whether the c==0 or not.

Pretty simple. right?

Result: 13 out of 14 test cases passed (One Wrong Answer)

So how can we identify the error?


Second Iteration— Reducing the Code

Identify the code redundancy and unused loops, and get rid of them.

Lesser Code = Lesser Errors

See for yourself: –

Code Explanation

In our case, while-loop was not serving any purpose, that was basically running for one time only. Once we have determined the value of c, we just need to subtract the stones from those corresponding piles only (either odd-positioned pile or even-positioned piles).

And as you can see in our previous code, we were writing the same thing twice, in both the for-loops. So we can remove that too with a single condition for determining element choice –

idx = range(1,n,2) if c<0 else range(0,n,2)

Result: No improvement (Since we had removed the unnecessary code only)


Third Iteration – Redefining the Problem

Now, since you have come this far, you’ve grasped the logic of what we are doing. But the question is, Do we really need to do all of this to get what we want?

If you’ll think about this critically, you’ll find, we don’t need to subtract stones from each specific set of pile one at a time. Actually, we do not need to do that at all. Because every time we are subtracting those stones, we’re basically subtracting from the whole array of stone piles.

Mathematically speaking, both are equivalent.

So if we have already calculated the difference (abs(c)), then we can directly subtract it from the sum of the whole array, arr.

And we can further simplify it like this…

def maximumStones(arr):
    return sum(arr) - abs(sum(arr[::2]) - sum(arr[1::2]))

So here we are, the single line of code as our final answer is –

sum(arr) – abs( sum(arr[::2]) – sum(arr[1::2]) )

Result: 14 out of 14 test cases passed (Success!)

Source: Image by the author (screenshot of the submission)
Source: Image by the author (screenshot of the submission)

Takeaways –

Don’t jump to solve the problem as soon as you get a glimpse of it. Think about it for a couple of minutes, because, not every problem requires you to think straightly.

Some problems want you to think out of the box. A fresh perspective; a crucial piece of knowledge can save you a huge huge amount of time in Coding and debugging.

There are a couple of rules of thumb that you need to keep in mind –

  • Try to reduce the code as much as possible to increase its efficiency and to narrow down the bugs. Use built-in libraries, remove redundancies, and reduce the number of loops as much as possible.
  • When you can no longer do it, and the problem still remains, change the approach. Do not get attached to the program that you’ve coded till now. Redefine the problem – think abstractly and mathematically.

Obviously, there is more to Competitive Programming than I can cover in this article. All the tips and tricks will come to you as you’ll get more experience. But that’s all for now. I hope you enjoyed the article.

Happy Programming!


Other Awesome Article that you might enjoy –

How to Play Music Using Mathematics in Python

10 Game-changing AI Breakthroughs Worth Knowing About

Why it’s Super Hard to be an ML Researcher or Developer?

How I Won a National Level ML Competition with my Unique "Informal Approach"


Related Articles