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.