如何使用不同的数据结构递归遍历地图

Question

I'm trying to figure out the best way to recursively go through a [string]int map in Go. I'm building a game in which multiple countries are involved, and grouped together by teams of two in the end.

The goal is to match the first two countries with the lowest 'score' into its own group of two, and add it back to the collection giving the new map a total value of the scores of those countries.

Then recursively doing that to all the groups, ending up with one group and one total value in the end.

For example, if you had:

score := map[string]int{
        "Canada": 7,
        "US": 2,
        "Germany": 3,
        "Korea": 4,
}

group1 = {[US:2] [Germany:3]} with a total of 5

group1 would now be put back into the initial collection with a 'score' of 5 since it takes the two lowest scores. We would now have:

score := map[string]int{
        "Canada": 7,
        "Korea": 4,
        group1: `US:2 Germany:3` with a total of 5
}

If this was now the lowest score in the collection, the next iteration would be:

group2 = {[Korea:4] [group1:5]}

 score := map[string]int{
            "Canada": 7,
            group2: `Korea:4 group1:5` with a total of 9
  }

And so on until you're left with one.. I think the basic structure should be something like this. However, I'm unsure of the proper way to do this since the data structure is now encompassing a [string]int map, as well as this new map.

I realize this is not such a generic question, but could an interface be used for this? I'm very new to Go, so advice would be helpful.

Here is an example to further illustrate what I mean: https://play.golang.org/p/cnkTc0HBY4

Answer 1

Your problem can "easy" be solved using a heap data structure.

package main

import (
    "container/heap"
    "fmt"
)



// Something that has a score
type Scoreable interface {
    fmt.Stringer
    Score() int
}



// A country has a name and a score
type Country struct {
    name  string
    score int
}

// Country implements Scoreable
func (c Country) Score() int {
    return c.score
}

// ... and fmt.Stringer
func (c Country) String() string {
    return fmt.Sprintf("%s [%d]", c.name, c.score)
}



// A team consists of two Scoreable's and has itself a score
type Team struct {
    team1, team2 Scoreable
    score        int
}

// Team implements Scoreable
func (t Team) Score() int {
    return t.score
}

// ... and fmt.Stringer
func (t Team) String() string {
    return fmt.Sprintf("(%s + %s)", t.team1.String(), t.team2.String())
}



// The heap will be implemented using a slice of Scoreables
type TeamHeap []Scoreable

// TeamHeap implements heap.Interface
func (th TeamHeap) Len() int {
    return len(th)
}

func (th TeamHeap) Less(i, j int) bool {
    return th[i].Score() < th[j].Score()
}

func (th TeamHeap) Swap(i, j int) {
    th[i], th[j] = th[j], th[i]
}

func (th *TeamHeap) Push(t interface{}) {
    *th = append(*th, t.(Scoreable))
}

func (th *TeamHeap) Pop() interface{} {
    old := *th
    n := len(old)
    t := old[n-1]
    *th = old[0 : n-1]
    return t
}


// The main function
func main() {

    // Create a heap and initialize it
    teams := &TeamHeap{}
    heap.Init(teams)

    // Push the countries (NB: heap.Push(), not teams.Push())
    heap.Push(teams, Country{"Canada", 7})
    heap.Push(teams, Country{"US", 2})
    heap.Push(teams, Country{"Germany", 3})
    heap.Push(teams, Country{"Korea", 4})

    // Take the two teams with lowest score and make a new team of them
    // Repeat this until there's only one team left
    for teams.Len() > 1 {
        t1 := heap.Pop(teams).(Scoreable)
        t2 := heap.Pop(teams).(Scoreable)
        heap.Push(teams, Team{t1, t2, t1.Score() + t2.Score()})
    }

    // Print the teams that we now have in the heap
    for teams.Len() > 0 {
        t := heap.Pop(teams).(Team)
        fmt.Println(t)
    }
}

You can find runnable code on the Go Playground.