Competitive programming in Nim

UNDER CONSTRUCTION

In the afternoon, I came cross the Nim programming language again on Lobsters. I first learned some basics of the language in 2015, but had not touched it since then. An idea popped into my mind: why not solve some coding challenges in Nim?

"Nim is a statically typed compiled systems programming language. It combines successful concepts from mature languages like Python, Ada and Modula.", according to its website.

As a niche language, it is not supported on many coding challenge websites. Fortunately, the Nim compiler generates C code. With a small amount of work, we can build a self-contained C source file suitable for submission.

Let's take a LeetCode challenge as an example. We write the main algorithm in Nim and use the emit pragma to write a C wrapper.


import algorithm

proc solution(events: ptr UncheckedArray[ptr UncheckedArray[cint]], eventSize: int, k: int): int {.exportc.} =
  type E = tuple[start,stop,value: int]
  var
    a = newSeq[E](eventSize)
    dp0: seq[int] = newSeq[int](eventSize+1)
    dp1: seq[int] = newSeq[int](eventSize+1)
  for i in 0..<eventSize:
    a[i] = (cast[int](events[i][0]), cast[int](events[i][1]), cast[int](events[i][2]))
  a.sort(proc (x, y: E): int = x.stop - y.stop)
  for _ in 0..<k:
    for i in 0..<eventSize:
      let j = a.lowerBound(a[i].start, proc (x: E, y: int): int = x.stop - y)
      dp1[i+1] = max(dp1[i], dp0[j]+a[i].value)
    swap(dp0, dp1)
  result = dp0[eventSize]

{.emit: """
int maxValue(int** events, int eventsSize, int* eventsColSize, int k) {
  return solution(events, eventsSize, k);
}
""".}

Then, create a self-contained C file with the approach described on https://zen.su/posts/amalgamating-nim-programs/.

Prepare nim.cfg and run nim c -d:danger --gc:arc -d:useMalloc --nimcache:. a.nim to generate a_comb.c: The CIL generated file looks like:




typedef long ptrdiff_t;
typedef unsigned long size_t;
...
struct _IO_FILE {
   ...
};
...
__inline extern  __attribute__((__nothrow__)) int ( __attribute__((__nonnull__(1),
__leaf__, __gnu_inline__)) atoi)(char const   *__nptr )  __attribute__((__pure__)) ;
__inline extern int ( __attribute__((__nonnull__(1), __leaf__, __gnu_inline__)) atoi)(char const   *__nptr ) 
{ 
  long tmp ;

  {
  tmp = strtol((char const   * __restrict  )__nptr, (char ** __restrict  )((char **)((void *)0)),
               10);
  return ((int )tmp);
}
}

The LeetCode environment includes some glibc headers like <stdio> which result in some conflicts due to duplicate definitions of struct _IO_FILE and some GNU extern inline functions. Let's write a Nim program to remove the duplicate definitions.

import strutils
var
  body: seq[string] = @[]
  i = 0
for line in lines "a_comb.c":
  body.add(line)

while i < body.len:
  if body[i].startsWith("struct _IO_FILE {"):
    while not body[i].startsWith "}":
      i += 1
    i += 1
    continue
  if body[i].startsWith("__inline extern") or body[i].startsWith("int main("):
    var c = 0
    var changed = false
    i += 1
    while true:
      c += body[i].count('{') - body[i].count('}')
      changed = changed or c > 0
      i += 1
      if c == 0 and changed: break
    continue

  echo body[i]
  i += 1

1	nim c --run --verbosity:0 x > for-submit.c

Finally, run { echo '/*'; cat a.nim; echo '*/'; cat for-submit.c; } | xclip -i -selection clipboard and paste the content into the LeetCode editor:) Well, the Nim source is not really needed but it is useful for archive purposes.

for-submitted.c is suitable for 64-bit Linux environment.

TODO Figure out how to support Codeforces (Windows with a 64KiB source code size limit).