Competitive programming in Nim

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.

"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.

Basic features: parametric polymorphism. Advanced features: macros (including term-rewriting macros), compile-time function execution, effect system, concepts

An idea popped into my mind: why not solve some coding challenges in Nim?

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Maximum Number of Events That Can Be Attended II
import algorithm

func 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 a.nim to generate a_comb.c:

-d:useMalloc avoids Nim's own memory manager and can greatly decrease the C code size. There are several choices for --gc, but --gc:arc can genreated the smallest C code. Unfortunately --gc:none does not work.

The CIL generated file looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Generated by CIL v. 1.8.1 */
/* print_CIL_Input is true */

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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).

If CIL fails to handle some syntax, use another deduplicator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/env python
from collections import Counter
import re
import sys
l = list(i.rstrip() for i in sys.stdin.readlines())
seen = Counter()
include = set()
i = 0
output = []
intbits = -1

while i < len(l):
if l[i] == '#define NIM_INTBITS 64' and intbits == -1:
intbits = i

if l[i] == '#include "nimbase.h"':
i += 1
continue

m = re.match(r'#include <(.*)>', l[i])
if m:
include.add(m.group(1))
i += 1
continue

if l[i].startswith('N_LIB_PRIVATE '):
l[i] = l[i][14:]

m = re.match(r'struct (\w+) \{$', l[i])
if m: seen[m.group(1)] += 1
if m and seen[m.group(1)] > 1:
c = 0
changed = False
while True:
c += l[i].count('{') - l[i].count('}')
changed = changed or c > 0
i += 1
if c == 0 and changed: break
continue

m = re.match(r'static N_INLINE\(.*, (\w+)\)\(.*\) \{$', l[i])
if m: seen[m.group(1)] += 1
if m and seen[m.group(1)] > 1 or l[i].startswith('int main('):
c = 0
changed = False
while True:
c += l[i].count('{') - l[i].count('}')
changed = changed or c > 0
i += 1
if c == 0 and changed: break
continue

output.append(l[i])
i += 1

with open('/home/maskray/Util/Nim/nimbase.min.h') as f:
nimbase = list(i.rstrip() for i in f.readlines())

output = output[:intbits] + nimbase + output[intbits:]
for i in include:
print(f'#include <{i}>')
for line in output:
print(line)
1
cat ~/.cache/nim/a_r/*.c | ./dedup.py > for-submit.c