Ian P. Badtrousers

Using Go for competitive programming

Go is not much used for competitive programming, primarily because it doesn’t have a generic container library. It also gets too verbose at times, but are there any real applications of it? We already know that Go is pretty fast when it comes to speed and memory usage. We also know that it offers CSP out-of-the-box, so it’s much easier to build concurrent pipelines in it than in the other languages. But can we really benefit from it? Let’s take a look at major contest platforms and how they support Go.

The state of things as of now:

  • Hacker Rank — offers Go 1.6.2, limits run time to 4s/1024MB, as opposed to 2s/512MB for C++14 and lets you use as much as two cores simultaneously.
  • Codeforces — uses single-cored Go 1.5.2, doesn’t have time/memory limits for Go.
  • LeetCode — has support of Go 1.7.1 doesn’t have time/memory, but single core.
  • TopCoder — limits language list to C++, Java and C#, no love for Go yet.
  • Google Code Jam — doesn’t care, unless your program runs in under 4 minutes.
  • CodeChef — is stuck with Go1.4 and doesn’t compensate soutions in Go, single core.
  • Timus — is stuck with an even older version, Go 1.3.
  • You won’t use Go for ACM-ICPC either.

As you can see, we’re not gonna make a use out of concurrent primitives since most judges run Go code inside the single-core environment. That said, keep in mind that HackerRank lets you use twice the memory allowed for C++ and gives you 2x more time and 2 cores. In theory, it means that you can perform 4x more scalable transformations (e.g. MapReduce) than similar code in C++. It’s pretty unlikely, but just in case… you better know it.

Input/Output

Standard’s library fmt package doesn’t use buffering (= slow), so you should avoid its direct usage for performance reasons. Instead, nothing stops you from using bufio package and a couple handy wrapper functions:

package main

import (
	"bufio"
	"fmt"
)

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{}) { fmt.Fscanf(reader, f, a...) }

func main() {
	// STDOUT MUST BE FLUSHED MANUALLY!!!
	defer writer.Flush()

	var a, b int
	scanf("%d %d\n", &a, &b)
	printf("%d\n", a+b)
}

Add this to your template and you’ll be able to use powerful scanf/printf-style functions with buffered stream.

Strings, bytes, strconv, regexp

Remember that strings in Go are immutable so you should use []byte for all mutable transformations instead. Standard library features strings, bytes and regexp packages, full of specific commonly used functions (map, contains, prefix, suffix, repeat, split, trim, index, etc). There is a package strconv for all kinds of number parsing and formatting.

You also should know that index/suffixarray (substring search on []byte in logarithmic time using an in-memory suffix array) exists as well. It supports regular expressions as well.

This is how I solve 208A - Dupstep from Codeforces in Go (some of the template is intentionally omitted):

import (
	"regexp"
	"strings"
)

func main() {
	defer writer.Flush()

	var s string
	scanf("%s\n", &s)
	s = regexp.MustCompile("(WUB)+").ReplaceAllLiteralString(s, " ")
	s = strings.Trim(s, " ")
	printf("%s\n", s)
}

It finishes in under 60 ms on tests, while C++14 solutions tend to average in 30-60ms, while using less memory.

Package sort provides sorting methods for specific types. It features corresponding Sort() and Stable() methods for sorting and Search() for binary search. There also are a couple handy specifications, like Ints() , Float64s or SearchInts() for only a few common types (int, float64 and string). For other types you’ll have to use “generic” Sort() accepting a copy of sort.Interface. It’s a huge pain in the arse, but until Go1.8 with new sorting API releases and gets to major online judges, we’re stuck with it.

This is how you’d want to sort pairs of int and float64 in decreasing order:

type pair struct {
	x int
	y float64
}

type pairs []pair                  /**/
func (a pairs) Len() int           { return len(a) }
func (a pairs) Less(i, j int) bool { return a[i].x < a[j].x || a[i].y < a[j].y }
func (a pairs) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	defer writer.Flush()

	items := pairs{{4, 74.0}, {9, 34.56}, {9, 31.31}}
	sort.Sort(sort.Reverse(items))

	for _, item := range items {
		printf("(%d, %.2f)\n", item.x, item.y)
	}

	// (9, 34.56)
	// (9, 31.31)
	// (4, 74.00)
}

Sometimes I get really sad when I remember that Go haven’t got generics and compile-time parametric polymorphism… 😭😭😭 But it’s no crying matter… we just gotta live with it!

Math, big numbers, rand

Package math provides you with lots of nice mathematical functions and constants, including some crazy stuff like Expm1(x float64) float64 that calculates value of *e*x-1, is a more accurate alternative to Exp(x) - 1 for near-zero values. I’m certainly not going to go through all of them, since the package spans across 62 functions and 11 mathematical constants. If you feel like you need some of it, go on and check this out.

Package math/big represents a set of types and methods for arbitrary-precision arithmetic. From what I’ve heard, it’s blazingly fast, but I’ve never really had a chance to use it during the contest yet. That said, the package has an extensive overview of its types and I recommend you to go on and take a look at it just in case if you’ll need big numbers eventually.

Package math/rand implements pseudo-random number generators and offers a range of corresponding functions for seeding and generation. Make sure you seed RNG with rand.Seed() either with some time value or hash, depending on input data.

Conclusion

As you can see, there’s no much room for Go in competitive programming, since both C++ and Java do exceptionally well for existing problems and offer powerful generic template library, including hash sets, bit sets, priority queues, etc. Go can’t offer this to community, because it totally misses generics (sorry for bringing this up again). Currently I’d use it only for heavy string processing problems where C++ lacks functionality and Python would be too slow and for anything involving arbitrary-precision arithmetic.

But hey, let’s see where competitive programming community goes next. Hopefully we’ll see more problems that could be solved effectively with concurrency and parallelism—a field where noone beats Go yet.

Published: Sunday, 23 Oct 2016


(powered by Disqus)