# 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.