Money Forward Developers Blog

I Tried Kotlin for Competitive Programming

Introduction

Hi! I’m Wibi, a software engineer at Cloud Payroll Group of Money Forward’s HR Solution Department. A part of my work is developing Cloud Payroll’s backend using Kotlin.

Up until a few months ago, I had no experience in writing Kotlin. To get used to it, I tried using Kotlin in what I usually do, which is competitive programming. In short, competitive programming is a mind sport where contestants write correct and efficient enough programs to solve simple problems. Recently, I have been doing it in AtCoder by participating in contests as Wie.

What makes this idea interesting to me is that Kotlin/JetBrains themselves promote usage of Kotlin in competitive programming. They sponsor the most prestigious university-level programming competition, hold competitive programming events and contests, and include competitive programming in their documentation. I thought that this is a good opportunity to see what the hype is all about.

In this blog, I would like to share what I attempted and my thoughts during these few months of trying out Kotlin for competitive programming.

Getting Ready

I started with setting up the tools. I picked stuff that I felt familiar with: Sublime Text 4, Kotlin command-line compiler, and JVM. I believe this combination is as effective as using IDEA or an online IDE, so there is no need to overthink the choices.

Next, I did some pre-reading to get some general ideas and early advices. I searched “Kotlin for competitive programming” in Google search and read some of the top results:

I also examined some problem solutions written in Kotlin. To do this, I visited Codeforces, opened some problems I had already solved in C++, filtered for Kotlin submissions, and skimmed through the results. I checked boilerplates others use, picked up some tricks and styles, and reverse-engineered thought process out of code. I also found and bookmarked the profile for arvindf232, a Codeforces Legendary Grandmaster who primarily uses Kotlin, for future reference.

After the above preps, I felt like it was a good point to start solving problems with Kotlin myself.

Attempting Problems

I arbitrarily picked problems to solve from LeetCode and Codeforces. For each problem, after briefly thinking about the main idea, I slowly wrote down the Kotlin solution while frequently consulting documentation and ChatGPT. In the process, to build a good habit, I tried to apply Kotlin’s idioms and coding conventions whenever possible.

After a few weeks or months of this, I started to gain some momentum. Ideally, my Kotlin implementation speed would be as good as my C++’s, but it proved challenging to surpass 7 years of C++ experience. I still occasionally submit solutions in Kotlin with the hope of gradually closing that gap.

As I gained momentum, my thoughts about using Kotlin for competitive programming started to consolidate. Here are a few main points I can share.

Code Length Varies

Code length is one thing I was looking forward to observe. Compared to my usual C++ code, would it be shorter, longer, or the same? Shorter code in Kotlin would be a plus, but it turned out that the result varied.

When the Kotlin code is shorter, it is often because I can transform C++ calculations involving mutable variables into one-line declarations in Kotlin. Here are some examples.

// storing n integers from stdin 
vector<int> a(n); for (int i=0; i<n; i++) cin >> a[i];
// storing n integers from stdin 
val a = readln().split(" ").map { it.toInt() }
// collecting integers that meets a certain condition
vector<int> cs;
for (int i=1; i<n; i++) {
  if (f(1, i) == f(n-i+1, n)) {
    cs.push_back(i);
  }
}
// collecting integers that meets a certain condition
val cs = (1..<n).filter { f(1, it) == f(n-it+1, n) }

When the Kotlin code is longer, it is usually because there are C++ “shortcuts” that I can’t convert well to Kotlin. An easy example would be for loops. You can throw in any condition and expression inside a C++ for loop, so it is more versatile and offers many opportunities for “shortcuts”. Kotlin’s for loops, on the other hand, only accepts iterable objects and so is less versatile. Here are some examples of C++ for loops that I frequently implement and my best attempt at writing them in Kotlin.

// iterating binary submasks of an integer
for (int mask=x; mask; mask=(mask-1)&x) {
  // mask is a submask of x
}
// iterating binary submasks of an integer
var mask = x
while (mask != 0) {
  // mask is a submask of x
  mask = (mask - 1) and x
}
// computing b-th power of a under modulo constant m
int modpow(int a, int b) {
  int ret = 1;
  for (; b; b>>=1) {
    if (b&1) ret = 1LL * ret * a % m;
    a = 1LL * a * a % m;
  }
  return ret;
}
// computing b-th power of a under modulo constant m
fun modpow(a: Int, b: Int): Int {
  var x = a; var e = b; var ret = 1
  while (e > 0) {
    if (e and 1 == 1) ret = (ret.toLong() * x % m).toInt()
    x = (x.toLong() * x % m).toInt()
    e = e shr 1
  }
  return ret
}

For some classic algorithms, the code does not differ much between C++ and Kotlin, and so the length remains roughly the same. As an example, here is my implementation of Dijkstra’s shortest path algorithm in both languages.

vector<int> dijkstra(vector<vector<pair<int, int>>> &adjl, int source) {
  int n = adjl.size();
  vector<bool> vis(n, false);
  vector<int> dist(n, 1e9+3);
  priority_queue<pair<int, int>> pq;

  dist[source] = 0;
  pq.emplace(-dist[source], source);
  while (!pq.empty()) {
    int u = pq.top().second; pq.pop();
    if (vis[u]) continue;
    for (auto &[v, w] : adjl[u]) {
      if (dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        pq.emplace(-dist[v], v);
      }
    }
  }

  return dist;
}
fun dijkstra(adjl: List<List<Pair<Int, Int>>>, source: Int): List<Int> {
  val n = adjl.size
  val vis = MutableList(n) { false }
  val dist = MutableList(n) { (1e9+3).toInt() }
  val pq = PriorityQueue { a: Pair<Int, Int>, b: Pair<Int, Int> -> if (a.first > b.first) 1 else -1}

  dist[source] = 0
  pq.add(Pair(dist[source], source))
  while (!pq.isEmpty()) {
    val u = pq.poll().second
    if (vis[u]) continue
    for ((v, w) in adjl[u]) {
      if (dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w
        pq.add(Pair(dist[v], v))
      }
    }
  }

  return dist
}

A deeper analysis with bigger sample size might yield more decisive conclusion regarding the code length comparison, but so far Kotlin feels fine. It has no major issue and offers many opportunity for improvements.

Extensions are Fun to Use

One thing that I can do in Kotlin but not in C++ is defining custom methods/operators for primitive types and standard libraries. As an example, here is how I implement modular arithmetic operations in C++ and Kotlin.

// assuming only one modulus is needed
const int mod = 998244353;

class Mint {
public:
  int v;

  Mint& operator+=(const Mint &a) {
    v += a.v;
    if (v >= mod) v -= mod;
    return *this;
  }
  friend Mint operator+(Mint a, const Mint &b) { return a += b; }
  
  // ... other operators
}
// assuming only one modulus is needed
const val mod = 998244353

// can't override plus operator in Kotlin, so I'm naming it modAdd
infix fun Int.modAdd(b: Int): Int { 
  val ans = this + b
  return if (ans >= mod) ans - mod else ans 
}

// ... other operators

In the Kotlin version, I don’t need to create a new class to implement my method/operator. This is really helpful since I don’t have to mind the different types/classes and the conversion between them. The code also looks neat and short. Certainly a plus for Kotlin.

Resource Usage is OK

A common folklore in competitive programming is that a valid solution in C++ might not pass the time/memory limit of the problem if reimplemented in another language. This causes some interesting effects in the community:

  • uneven time/memory limit distribution between languages in some problems,
  • language-specific speedup tricks attached in problem descriptions, and
  • contests announcing that solutions not implemented in C++ are not guaranteed to pass the time/memory limit.

Knowing the folklore, I expected to see some “false” time/memory limit exceeded verdicts in my Kotlin submissions. However, I’ve only had one such instance so far (which I’ll discuss in the next section).

The time/memory usage shown in my Kotlin submissions are also generally OK. It might be because I’m not doing much problems requiring constant or log factor optimizations yet, but I’m fine with how Kotlin performs for now.

Writing My Favorite Classic Algorithm

Other than doing problems arbitrarily, I also wrote a classic algorithm and looked for a specific problem where I can submit it. The algorithm that I picked is one of my favorites: Polynomial (Rolling) Hash.

I tried to write the algorithm as a class that I could easily copy and paste for future use. The plan is to also do this for other classic algorithms and form something similar to KACTL, a popular ICPC team reference document written mainly for C++. I already prepared a personal repository, in hope that I can steadily fill it until it is as comprehensive as KACTL, starting with the Polynomial Hash.

Here is how my Kotlin implementation of Polynomial Hash looks like, along with my usual C++ implementation (which I usually write from scratch and not really copy-pasteable).

class StringPolynomialSingleHash(val s: String) {
  companion object {
    private const val maxn = 1000003
    private const val mod = 1000000007
    infix fun Int.modMul(b: Int): Int { return ((this.toLong() * b) % mod).toInt() }
    infix fun Int.modAdd(b: Int): Int { val ans = this + b; return if (ans >= mod) ans - mod else ans }
    infix fun Int.modSub(b: Int): Int { val ans = this - b; return if (ans < 0) ans + mod else ans }
    fun Int.modInv(): Int = this.modPow(mod-2)
    infix fun Int.modPow(e: Int): Int {
      var x = this; var e = e ; var ret = 1
      while (e > 0) {
        if(e and 1 == 1) ret = ret modMul x
        x = x modMul x
        e = e shr 1
      }
      return ret
    }
 
    private val base = 98237
    private val ibase = base.modInv()
    val pw = generateSequence(1) { it modMul base }.take(maxn).toList()
    val ipw = generateSequence(1) { it modMul ibase }.take(maxn).toList()
  }
 
  private val n = s.length
  private val p = pw.take(n).zip(s.toList()) { p, c -> p modMul c.code }.runningFold(0) { sum, cur -> sum modAdd cur }
  
  // Returns hash of s[l..r], where l and r are one-index-based, O(1)
  fun get(l: Int, r: Int): Int {
    return (p[r] modSub p[l-1]) modMul ipw[l]
  }
}
const int maxn = 1e6+3;
const int base = 98237;
const int mod = 1e9+7;

int pw[maxn], ipw[maxn];
int modpow(int a, int b) {
  int ret = 1;
  for (; b; b>>=1) {
    if (b&1) ret = 1LL * ret * a % mod;
    a = 1LL * a * a % mod;
  }
  return ret;
}
int modinv(int a) { return modpow(a, mod-2); }
void init() {
  pw[0] = 1;
  for (int i=1; i<maxn; i++) pw[i] = 1LL * pw[i-1] * base % mod;
  ipw[maxn-1] = modinv(pw[maxn-1]);
  for (int i=maxn-1; i>0; i--) ipw[i-1] = 1LL * ipw[i] * base % mod;
}

int main() {
  init();

  ...

  int n = s.size();
  vector<int> p(n+1, 0);
  for (int i=1; i<=n; i++) p[i] = (p[i-1] + 1LL * pw[i] * (s[i-1] - 'a' + 1)) % mod;
  auto get = [&](int l, int r) -> int {
    return 1LL * (p[r] - p[l-1] + mod) * ipw[l] % mod;
  };
}

The problem I chose to test my Kotlin implementation was Codeforces 126B. I felt it was a good test case because the solution does not require much else besides Polynomial Hash. Any issue that arises will most likely come from the Polynomial Hash implementation.

So, what was the verdict? Time limit exceeded. I tried tweaking the solution a few times but it did not get any better.

Just to make sure that the solution idea is not at fault, I tried reimplementing the solution in C++. It passed with a comfortable margin in time and memory usage.

It seems I likely made some mistakes in my Kotlin implementation of the algorithm. Optimizing this implementation would be a valuable learning experience, providing insights into Kotlin: inner workings of Kotlin features, their complexity and performance, and alternative implementations. However, that will have to wait for another time.

My submissions for the test problem can be found here: Kotlin, C++.

Conclusion

I have been enjoying practicing Kotlin via competitive programming. I have learnt a lot from it and still have much ahead to work on. I’m eager to continue competing using Kotlin!

Published-date