Poor man's generics in Golang (Go) [or pick your poison]

Golang does not have generics. Period.

With that in mind, I just wish to share how I am thinking of implementing generic code. For this example, I am going to create a generic Stack datastructure.

type Stack struct {  
    T   reflect.Type
    arr []interface{}
}

Yes, it wraps around a slice of interface{} type. And yes, that means loosing static safety. I also do store the Type of values that are permitted to be added to the stack. Storing this Type is what would help us to prevent dirty data from entering our Stack and wreaking havoc later.

Next, is the constructor function for our Stack.

func New(T reflect.Type) *Stack {  
    return &Stack{T: T}
}

Also, lets define some errors that we shall use for indicating unacceptable conditions in our Stack implementation.

var TypeMismatchError = errors.New("new value does not match the type of the stack")  
var EmptyStackError = errors.New("unable to Peek/Pop and empty stack")  

While the API for our Stack may contain many functions, I am going to demonstrate the two that are the most useful, namely the Pop() and Push() functions.

func (s *Stack) Pop() interface{} {  
    var val interface{}
    val, s.arr = s.arr[len(s.arr)-1], s.arr[:len(s.arr)-1]
    return val
}

Nothing special there. It pops the last element from the arr slice and returns it as an interface{} type. This means, that we need to convert the popped value back to the original type, before we can use it in the client code.

func (s *Stack) Push(e interface{}) (*Stack, bool, error) {  
    if reflect.TypeOf(e) != s.T {
        return s, false, TypeMismatchError
    }
    s.arr = append(s.arr, e)
    return s, true, nil
}

The Push function is where I stop unsupported data type from entering our Stack and limit the side effects of using the interface{} type a bit. Rather than throwing a panic, we return the success/failure status as a bool and the error (TypeMismatchError in case, addition of unsupported type was attempted). By stopping dirty data from entering the Stack, we can be assured that our code wont break when converting the popped values back to their original types.

The following code demonstrates the usage of our generic Stack.

func main() {  
    // create a new Stack to hold the value of type MyStruct
    st := NewStack(reflect.TypeOf(MyStruct{}))

    // push some values onto the stack
    st.Push(MyStruct{"hello"})
    st.Push(MyStruct{"world"})
    st.Push(MyStruct{"again"})

    // pop values from stack
    v := st.Pop().(MyStruct)  // need to convert the interface{} to MyStruct
    fmt.Println(v.msg)  // "again"
    v = st.Pop().(MyStruct)
    fmt.Println(v.msg)  // "world"

    // try pushing some illegal value onto stack
    var success bool
    var err error
    st, success, err = st.Push(1)   
    fmt.Println("1 pushed to stack", success)   // "1 pushed to stack false"
    fmt.Println("error returned via pushing to stack:", err)        // "error returned via pushing to stack: new value does not match the type of the stack"
}

The above code is available for demo here

In conclusion:

  • Golang doesnt have generics and there is nothing you can do to get true generics in Go.
  • Writing generic code involves converting the data to and from interface{} values
  • This leads to decrease in performance. For example a stack of int type was 15 times faster in my personal benchmarks. And thats a lot !
  • Using interface{} everywhere leads to the loss of the safety provided by static typing.

In short, pick your poison - Generic (like) code vs Static Safety and speed !

Solution to Eight Queens problem in Golang

We shall use the recursive backtracking technique for getting all the solutions to the Eight Queens Problem.

We shall use two 8x8 arrays, one to store the position of the queens and the other to store the counts of the queens that are attacking a particular position.

var hasQueen [8][8]bool  
var inAttack [8][8]int  

Next is the helper function that we call to place a queen at a position (i, j).

func placeQueen(i, j int) {  
    hasQueen[i][j] = true
    // update attack counts
    // row
    for c := 0; c < 8; c++ {
        inAttack[i][c]++
    }
    // col
    for r := 0; r < 8; r++ {
        inAttack[r][j]++
    }
    inAttack[i][j] -= 2  // the (i,j) cell has been counted twice in the above iterations
    // diagonals
    for r := 0; r < 8; r++ {
        for c := 0; c < 8; c++ {
            if r == i && c == j {
                inAttack[r][c]++
                continue
            }
            if r-i == c-j || r-i == -(c-j) {
                inAttack[r][c]++
            }
        }
    }
}

Next, we write the function to remove a queen form a position (i, j). This shall be used when we are backtracking due to some reason and need to remove a queen.

func removeQueen(i, j int) {  
    hasQueen[i][j] = false
    // update attack counts
    // row
    for c := 0; c < 8; c++ {
        inAttack[i][c]--
    }
    // col
    for r := 0; r < 8; r++ {
        inAttack[r][j]--
    }
    inAttack[i][j] += 2
    // diagonals
    for r := 0; r < 8; r++ {
        for c := 0; c < 8; c++ {
            if r == i && c == j {
                inAttack[r][c]--
                continue
            }
            if r-i == c-j || r-i == -(c-j) {
                inAttack[r][c]--
            }
        }
    }
}

This function is just the inverse of the place_queen() function.

Next we use a global variable to hold he counts of the solutions discovered.

var solNo int  

Next is the actual function that does the recursive backtracking to solve the problem.

func solve(r int) {  
    if r == 7 {
        // can we place the queen somewhere
        for c, cnt := range inAttack[7] {
            if cnt == 0 {
                placeQueen(r, c)
                solNo++
                fmt.Println("Solution No.", solNo)
                pp2DBoolArr(hasQueen)
                removeQueen(r, c)
            }
        }

    } else {
        for c, cnt := range inAttack[r] {
            if cnt == 0 {
                placeQueen(r, c)
                solve(r + 1)  // solve the next row (recursive)
                removeQueen(r, c)  // remove this queen (backtrack)
            }
        }
    }
}

I also use a simple utility function to print the positions of the queens.

// `pp2DBoolArr` pretty prints a 2D int array
func pp2DBoolArr(data [8][8]bool) {  
    for i := 0; i < 8; i++ {
        row := make([]string, 8)
        for j := 0; j < 8; j++ {
            if data[i][j] {
                row[j] = "Q"
            } else {
                row[j] = "+"
            }
        }
        fmt.Println(strings.Join(row, " "))
    }
}

And the main function that is the entry point of the code.

func main() {  
    solve(0)
}

The complete code is available here. The generated output is available here.

Golang equivalent of Python's bisect_left() and bisect_right()

Today I needed to binary_search on a sorted list of items in Golang. In Python (which remains my favorite language, btw) it was a simple thing to use the bisect module. That got me looking for its equivalent in Golang std packages.

I found what I was looking for in the sort package. It has a function Search whose signature is like

func Search(n int, f func(int) bool) int  

As per the documentation,

Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) = true implies f(i+1) == true.

So I wrote some wrappers using this Search function to emulate the functionality of bisect_left and bisect_right python functions.

func BisectLeft(a []int, v int) int {  
    return bisectLeftRange(a, v, 0, len(a))
}

func bisectLeftRange(a []int, v int, lo, hi int) int {  
    s := a[lo:hi]
    return sort.Search(len(s), func(i int) bool {
        return s[i] >= v
    })
}

func BisectRight(a []int, v int) int {  
    return bisectRightRange(a, v, 0, len(a))
}

func bisectRightRange(a []int, v int, lo, hi int) int {  
    s := a[lo:hi]
    return sort.Search(len(s), func(i int) bool {
        return s[i] > v
    })
}

Using the above wrappers, the function for binary_search for a value is:

func BinarySearch(a []int, v int) int {  
    pos := BisectLeft(a, v)
    if pos == len(a) {
        // the value sought is higher than the 
        // max value in the slice
        return -1

    } else if a[pos] != v {
        // the value sought is not found
        // this is becuase the BisectLeft would return 
        // the insertion position for the value, 
        // irrespective of whether this value was found in the
        // slice or not
        return -1

    } else {
        // the value is 
        return pos
    }
}

Thats it!

Ofcourse this is limited to ints and is not generic. But then its not my fault that Golang does not have generics. Then again I could write a wrapper struct and use reflection to make it generic, but that is left as and exercise to the reader :D

Sample usage is available at the golang playground.

Input template (Go) for algorithmic competitions

Since I have been playing with Go recently, I decided to use it for the qualification round of Google Code Jam - 2016.

Here is the struct I wrote to wrap around a reader so as to handle input from either a file or os.STDIN (technicall any io.Reader).

type MyInput struct {  
    rdr         io.Reader
    lineChan    chan string
    initialized bool
}

func (mi *MyInput) start(done chan struct{}) {  
    r := bufio.NewReader(mi.rdr)
    defer func() { close(mi.lineChan) }()
    for {
        line, err := r.ReadString('\n')
        if !mi.initialized {
            mi.initialized = true
            done <- struct{}{}
        }
        mi.lineChan <- strings.TrimSpace(line)
        if err == io.EOF {
            break
        }
        if err != nil {
            panic(err)
        }
    }
}

Its just a simple wrapper around a reader with some state variables.
Next, I added the function readLine() which will be the base of all functions for reading from the input (file or stdin or whatever).

func (mi *MyInput) readLine() string {  
    // if this is the first call, initialize
    if !mi.initialized {
        mi.lineChan = make(chan string)
        done := make(chan struct{})
        go mi.start(done)
        <-done
    }

    res, ok := <-mi.lineChan
    if !ok {
        panic("trying to read from a closed channel")
    }
    return res
}

The first call to readLine() would initialize the MyInput instance, in addition to returning a line from the input.

Next I added some helper functions to cater to the most common use-cases for reading from an input, as far as algorithmic completions input is concerned.

// to read an int from a line that contains only one value and that is an int
func (mi *MyInput) readInt() int {  
    line := mi.readLine()
    i, err := strconv.Atoi(line)
    if err != nil {
        panic(err)
    }
    return i
}

// similar to `readInt` but returns an int64
func (mi *MyInput) readInt64() int64 {  
    line := mi.readLine()
    i, err := strconv.ParseInt(line, 10, 64)
    if err != nil {
        panic(err)
    }
    return i
}

// if a line has multiple ints seperated by a space, 
//use this to get the ints in a slice []int
// e.g. if line is "1 2 6 77"
// this would return []int{1,2,6,77}
func (mi *MyInput) readInts() []int {  
    line := mi.readLine()
    parts := strings.Split(line, " ")
    res := []int{}
    for _, s := range parts {
        tmp, err := strconv.Atoi(s)
        if err != nil {
            panic(err)
        }
        res = append(res, tmp)
    }
    return res
}

// similar to `readInts` but returns a slice of int64s
func (mi *MyInput) readInt64s() []int64 {  
    line := mi.readLine()
    parts := strings.Split(line, " ")
    res := []int64{}
    for _, s := range parts {
        tmp, err := strconv.ParseInt(s, 10, 64)
        if err != nil {
            panic(err)
        }
        res = append(res, tmp)
    }
    return res
}

// returns the words from the line that are seperated by a space
// e.g. if line is "who art thou",
// this would return []string{"who", "art", "thou"}
func (mi *MyInput) readWords() []string {  
    line := mi.readLine()
    return strings.Split(line, " ")
}

Using MyInput is as simple as shown below:

func main() {  
    f, _ := os.Open("input_file.in")
    mi := MyInput{rdr: f}
    // mi := MyInput{rdr: os.Stdin}

    t := mi.readInt()
    for caseNo := 1; caseNo <= t; caseNo++ {
        // TODO - solve the case !
    }
}

The complete code is available at as a Gitlab snippet here

go-hn: command line client for hacker news, written in golang

So, I was in need of a command line client for Hacker News and have been playing with Golang for some time.

This weekend, I finally got some spare time and I hacked together a command line client for HackerNews in Golang.

The project lives at gitlab.

Its a quick hack and is in no way polished. Currently supports logging in, upvoting, opening an item, navigating to next/prev page.

go-hn in action

Will work on it, as and when I get some spare time.