Cracking Competitive Programming With Go

Introduction

The code challenging platforms like HackerRank or CodeEval test the logical ability and programming ability of a coder. Dynamic languages give us the edge in developing programs faster. The algorithms which require huge computation may lead to timeouts with interpreters. Go is a compiled and disciplined language which can do very well in the competitive programming world. Beginners always feel challenged when they start using Go because it is so strict. At the same time, it is so sweet with type inferences and out-of-box, built-in library.

These are essential things you need to know before jumpstart coding in Golang.

Input and Output

Even though many tutorials describe many ways to read input and print output, beginners of Golang usually find it hard to start. So I will cover the basic input/output pattern in Golang.

Taking a Line of Input and Displaying It

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	inputreader := bufio.NewReader(os.Stdin)
	input, _ := inputreader.ReadString('\n')
	fmt.Print(input)
}

Input ends with return key

$ go run input.go
Gopher
Hello Gopher

The above code just creates a Reader, which is attached to STDIN. In order to accept the input, the ReadString method is used. A new line (\n) is used here to identify the end of the input.

Now let us see the variations in printing to STDOUT:

fmt.Println("Something......") // prints a new line after output

fmt.Printf("%d + %d = %d", x, y, z) // formats the output string as per adjustments

str := fmt.Sprintf("%d + %d = %d", x, y, z) // used for interpolating values into a string

Type Conversions

In any programming language type conversion is the most common thing. Let us see how we do type conversions in Go:

package main

import "strconv"
import "fmt"

func main() {
	str := "34"
	floatStr := "12.34"
	truth := "false"
	// string to int conversion
	intNum, _ := strconv.Atoi(str)
	// Use ParseFloat and ParseBool for other data types
	floatNum, _ := strconv.ParseFloat(floatStr, 64)
	boolVal, _ := strconv.ParseBool(truth)
	fmt.Println(intNum, floatNum, boolVal)
}

We can also convert an Integer, Float value to a string using Iota method of strconv:

i := 10
strVal, _ = strconv.Iota(i)

If we observe carefully, strconv is returning two values, not one. The first value is the actual result, while "_" contains the error message if the operation fails. If we plan to handle the error wisely then we can use it. If the operation is successful, it stores nil into err.

i := 10
// Now you can use err if something goes wrong
strVal, err = strconv.Iota(i)

Make Array Slices Your Great Friend

In other programming languages, Arrays and Lists are the main storing data structures. But in Go, you must use slices. Here, the frequent usage of slices is essential in competitive programming.

package main

import "fmt"

func main() {
	s := []string{"Naren", "Saikiran"}
	// appending an element at the end of slice
	s = append(s, "Manoj", "Harish")
	fmt.Println(s)
	// removing element at the end
	s = s[:len(s)-1]
	fmt.Println(s)
	index := 1
	// removing element at the nth index
	s = append(s[:index], s[index+1:]...)
	fmt.Println(s)
}

$ go run slices_test.go
[Naren Saikiran manoj Harish]
[Naren Saikiran manoj]
[Naren manoj]

Practice playing with slices more and more to get familiar with them. One word of caution: the indexing of a slice is immutable. You need to reassign a new slice to an existing one after an operation.

String Processing and Cleaning

In any coding competition, we need to process strings a lot. String processing includes:

• Trimming the spaces
• Splitting using separators

Now we are going to see the most straightforward way of doing that. In coding challenges we usually input the number of test cases and values for each test case.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func cleanString(stream string, seperator string) []int {
	// Trims the stream and then splits
	trimmed_stream := strings.TrimSpace(stream)
	split_arr := strings.Split(trimmed_stream, seperator)
	// convert strings to integers and store them in a slice
	clean_arr := make([]int, len(split_arr))
	for index, val := range split_arr {
		clean_arr[index], _ = strconv.Atoi(val)
	}
	return clean_arr
}
func main() {
	inputreader := bufio.NewReader(os.Stdin)
	input, _ := inputreader.ReadString('\n')
	noOfTestCases, _ := strconv.Atoi(strings.TrimSpace(input))
	for i := 0; i < noOfTestCases; i++ {
		lineInput, _ := inputreader.ReadString('\n')
		fmt.Println(cleanString(lineInput, " "))
	}
}

So we have two methods for splitting and stripping of strings: strings.TrimSpace(string) and strings.Split(trimmed_stream, seperator).

These are equivalent to Python's trim() and split() built-in methods

Other Tricks

Using Math library

While using Golang's math library, you should be careful about the types of arguments passed and the type of the operation result. For example, for finding the absolute value of a number, you need to pass a float64 number to the math.Abs function.

import "math"

num := -10

absNum := math.Abs(num) // Throws error since Abs function only accept float64
absNum := math.Abs(float64(num)) // fine!

So you should always refer to the language manual to see type castings.

Using Wild Card Format Option in Printf

We all know that by using format options we can customize the width and precision of output while using Printf.

n := 10.666
fmt.Printf("%12.4f", n)

This actually tells Go to print a float value 12 spaces wide and round it to 4 floating points. But what if that width should be supplied programatically? Here is a wildcard trick for that.

n,s := 10.666, 12
fmt.Printf("%*.4f",s, n)

This produces the same output as the above, but has the advantage of changing width dynamically. Here is an example called "printing staircase" where this trick will be useful.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	inputreader := bufio.NewReader(os.Stdin)
	N, _ := inputreader.ReadString('\n')
	number, _ := strconv.Atoi(strings.TrimSpace(N))
	temp := number
	for i := temp; i > 0; i-- {
		result := fmt.Sprintf("%*s", temp, "#")
		for j := temp; j < number; j++ {
			result += "#"
		}
		fmt.Println(result)
		temp--
	}
}

The output is a beautiful staircase:

$ go run staircase.go
5
    #
   ##
  ###
 ####
#####

This article is an output of effort I went through while solving HackerRank. Send your comments to narenarya@live . If you really like this article, please share it and spread the word.

Thank You! :)