異なるデータ構造を使用して再帰的にマップをループする方法

Question

私は、移動の[string]intマップを再帰的に通過する最良の方法を理解しようとしています。私は、複数の国が関わっているゲームを構築しており、最終的に2つのチームでグループに分かれています。

目標は最低の「スコア」を持つ2つの国を2つのグループに一致させ、コレクションに戻して新しいマップにそれらの国のスコアの合計値を与えることです。

その後、すべてのグループに対して再帰的に行い、最後に1つのグループと1つの合計値になります。例えば

、あなたが持っていた場合：今5の「スコア」で最初のコレクションに戻されることになる5

グループ1の合計で

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

GROUP1 = {[US:2] [Germany:3]}をそれがかかるため2つの最も低い得点。私たちは、今持っているでしょう：

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

これは今コレクションの中で最も低いスコアだった場合、次の反復は、次のようになりますように

グループ2 = {[Korea:4] [group1:5]}

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

そして、あなたがしているまで私は基本的な構造がこのようなものでなければならないと思う。しかし、データ構造が今度は[string]intマップとこの新しいマップを包含しているので、これを行う適切な方法がわかりません。

これは一般的な質問ではありませんが、このためにインターフェイスを使用できますか？私は非常に新しいので、アドバイスが役立つだろう。ここで

はさらに私が何を意味するか説明する例です。 https://play.golang.org/p/cnkTc0HBY4

Answer 1

あなたの問題は、「簡単」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) 
    } 
} 

runnable codeは、Go Playgroundで見つけることができます。 。

Answer 2

package main 

import (
    "container/heap" 
    "fmt" 
) 

//Recursive data structure may looks something like 
type Group struct { 
    Score int 
    Left *Group 
    Right *Group 
    Country string 
} 

//You can use slice to hold them organized in tree 
type GrHeap []Group 

//To implement your logic you can use stdlib/container/heap Heap interface 
//you must implement Heap interface for your slice 
func (h GrHeap) Len() int   { return len(h) } 
func (h GrHeap) Less(i, j int) bool { return h[i].Score < h[j].Score } 
func (h GrHeap) Swap(i, j int)  { h[i], h[j] = h[j], h[i] } 

func (h *GrHeap) Push(x interface{}) { 
    // Push and Pop use pointer receivers because they modify the slice's length, 
    // not just its contents. 
    *h = append(*h, x.(Group)) 
} 

func (h *GrHeap) Pop() interface{} { 
    old := *h 
    n := len(old) 
    x := old[n-1] 
    *h = old[0 : n-1] 
    return x 
} 

func main() { 
    //you most likely already have a map 
    //anyway it will be handy to keep it for convenient access to individual country 
    score := map[string]int{ 
     "Canada": 7, 
     "US":  2, 
     "Germany": 3, 
     "Korea": 4, 
    } 
    //here we allocate heap 
    gr := make(GrHeap, 0) 
    //populate it from map 
    for k, v := range score { 
     g := Group{v, nil, nil, k} 
     gr = append(gr, g) 
    } 
    //and initialize 
    heap.Init(&gr) 
    //and here we use heap magic to implement your logic 
    for len(gr) > 2 { 
     l := heap.Pop(&gr).(Group) 
     r := heap.Pop(&gr).(Group) 
     ng := Group{l.Score + r.Score, &l, &r, ""} 
     heap.Push(&gr, ng) 
    } 
    fmt.Println(gr) 
    fmt.Println(gr[1].Left) 
    fmt.Println(gr[1].Right.Left) 
//and you can see it works https://play.golang.org/p/gugJxJb7rr 
} 

Answer 3

あなたはType assertionでmap[string]interface{}を試すことができ ここではデモ

package main 

import "fmt" 

const total = "total" 


func GetValue(i interface{}) int { 
    value, ok := i.(int) 
    if ok { 
     return value 
    } 
    return i.(map[string]interface{})[total].(int) 
} 

func main() { 
    score := map[string]interface{}{ 
     "Canada": 7, 
     "US":  2, 
     "Germany": 3, 
     "Korea": 4, 
    } 
    groupCount := 0 

    for len(score) > 2 { 
     var (
      firstMin = math.MaxInt32 
      secondMin = math.MaxInt32 
      firstKey = "" 
      secondKey = "" 
     ) 
     for k, v := range score { 
      iv := GetValue(v) 
      if iv < firstMin { 
       secondMin = firstMin 
       secondKey = firstKey 
       firstMin = iv 
       firstKey = k 
       continue 
      } 
      if iv < secondMin { 
       secondMin = iv 
       secondKey = k 
       continue 
      } 

     } 
     groupCount++ 

     score[fmt.Sprintf("Group%d", groupCount)] = map[string]interface{}{ 
      firstKey: score[firstKey], 
      secondKey: score[secondKey], 
      total:  GetValue(score[firstKey])+ GetValue(score[secondKey]), 
     } 
     delete(score, firstKey) 
     delete(score, secondKey) 
    } 
    fmt.Println(score) 
} 

です。ここスライスではありませんリンクhttps://play.golang.org/p/qq5qwAsh1m