April 25, 2016 · golang tech interviews

Solving ring-shaped problems with Go's container/ring

This post was featured in Golang Weekly Issue 107.


Certain problems are solved best with certain data-structures. Golang's container/ring is well suited to problems with fixed data-sets that need circular traversal, and FIFO-like queue operations. Take the following problem:

Given a set of players sitting in a circle that are numbered from 1 up, eliminate them 1-by-1 by first eliminating #1, then #3, and then #6 such that the amount of players that "survive" between each elimination increases by one. Continue around the circle until a final survivor remains.

Here we have fixed amount of elements, that we need to reduce to 1 by traversing through them and evicting every i+1 items.

Break it down

Let's start with a circular buffer filled with values 1..10:

items := ring.New(10)  
for i := 1; i <= items.Len(); i++ {  
    items = items.Next()
    items.Value = i
}

Now, let's reduce the buffer to 1 using the logic described in our problem:

skip := 1  
for items.Len() > 1 {  
    items.Unlink(1)
    items = items.Move(skip)
    skip++
}

The final items.Value remaining in our buffer should be 7.

http://play.golang.org/p/qh0tFq1FWZ

Put it through the rounds

Let's make our solution reuseable, and adopt the domain-language used in the problem statement:

package main

import (  
    "container/ring"
    "fmt"
)

func main() {  
    games := []int{100, 5, 6, 7, 10, 500}

    for _, playerAmount := range games {
        survivor := findSurvivor(playerAmount)
        fmt.Println("Given", playerAmount, "players, the surviving player was", survivor)
    }
}

func findSurvivor(playerAmount int) int {  
    players := ring.New(playerAmount)
    for i := 1; i <= players.Len(); i++ {
        players = players.Next()
        players.Value = i
    }

    skip := 1
    for players.Len() > 1 {
        players.Unlink(1)
        players = players.Move(skip)
        skip++
    }
    return players.Value.(int)
}

Running the program gives us the following:

Given 100 players, the surviving player was 31  
Given 5 players, the surviving player was 4  
Given 6 players, the surviving player was 5  
Given 7 players, the surviving player was 4  
Given 10 players, the surviving player was 7  
Given 500 players, the surviving player was 360  

http://play.golang.org/p/LajL_4Zpz3

Cheers.