-
-
Save kaipakartik/8120855 to your computer and use it in GitHub Desktop.
package main | |
import ( | |
"code.google.com/p/go-tour/tree" | |
"fmt" | |
) | |
// Walk walks the tree t sending all values | |
// from the tree to the channel ch. | |
func Walk(t *tree.Tree, ch chan int) { | |
WalkRecursive(t, ch) | |
close(ch) | |
} | |
func WalkRecursive(t *tree.Tree, ch chan int) { | |
if t != nil { | |
WalkRecursive(t.Left, ch) | |
ch <- t.Value | |
WalkRecursive(t.Right, ch) | |
} | |
} | |
// Same determines whether the trees | |
// t1 and t2 contain the same values. | |
func Same(t1, t2 *tree.Tree) bool { | |
ch1, ch2 := make(chan int), make(chan int) | |
go Walk(t1, ch1) | |
go Walk(t2, ch2) | |
for { | |
n1, ok1 := <- ch1 | |
n2, ok2 := <- ch2 | |
if ok1 != ok2 || n1 != n2 { | |
return false | |
} | |
if !ok1 { | |
break; | |
} | |
} | |
return true | |
} | |
func main() { | |
ch := make(chan int) | |
go Walk(tree.New(1), ch) | |
fmt.Println(Same(tree.New(1), tree.New(2))) | |
fmt.Println(Same(tree.New(1), tree.New(1))) | |
fmt.Println(Same(tree.New(2), tree.New(1))) | |
} |
The same function must check whether t1 and t2 have the same values in any order. The implementation returns instead, whether the order is of the elements the same in both parameters.
Always try to strive for clean and readable code
package main
import "golang.org/x/tour/tree"
import "fmt"
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
recursiveWalk(t, ch)
close(ch)
}
func recursiveWalk(t *tree.Tree, ch chan int) {
if t == nil { return }
recursiveWalk(t.Left, ch)
ch <- t.Value
recursiveWalk(t.Right, ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for {
v1, ok1 := <- ch1
v2, ok2 := <- ch2
noMoreValuesInEitherTree := !(ok1 && ok2)
if noMoreValuesInEitherTree {
return true
}
isMoreNodesInOneTree := !(ok1 || ok2)
if isMoreNodesInOneTree {
return false
}
if v1 != v2 {
return false
}
// v1 and v2 exist and are equal to each other, so continue
}
}
func main() {
fmt.Println("Test 1 (expected true):", Same(tree.New(1), tree.New(1)))
fmt.Println("Test 2 (expected false):", Same(tree.New(1), tree.New(2)))
}
package main
import (
"golang.org/x/tour/tree"
"fmt"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if (t == nil) { return }
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for i := 0; i < cap(ch1); i++ {
if (<-ch1 != <-ch2) { return false }
}
return true
}
func testWalk() {
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := 1; i < 11; i++ {
if (i != <-ch) {
fmt.Println("Walk doesn't work")
break
}
}
fmt.Println("Walk does work")
}
func testSame() {
if Same(tree.New(1), tree.New(1)) && Same(tree.New(1), tree.New(2)) {
fmt.Println("Same does work")
} else {
fmt.Println("Same doesn't work")
}
}
func main() {
testWalk()
testSame()
}
The same function must check whether t1 and t2 have the same values in any order. The implementation returns instead, whether the order is of the elements the same in both parameters.
The requirement specifically states:
constructs a randomly-structured (but always sorted) binary tree
So, the solutions provided are all correct; they rely on the tree always being sorted. Not much use for a binary tree if it wouldn't be, anyhow
package main
import (
"golang.org/x/tour/tree"
"fmt"
"reflect"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t.Left != nil {
Walk(t.Left, ch)
}
ch <- t.Value
if t.Right != nil {
Walk(t.Right, ch)
}
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
var tree1, tree2 []int
go Walk(t1, ch1)
go Walk(t2, ch2)
tr1, tr2 := 0, 0
for i := 0; i < 20; i++ {
select {
case tr1 = <- ch1:
tree1 = append(tree1, tr1)
case tr2 = <- ch2:
tree2 = append(tree2, tr2)
}
}
return reflect.DeepEqual(tree1, tree2)
}
func main() {
fmt.Println("Same(tree.New(1), tree.New(1))", Same(tree.New(1), tree.New(1)))
fmt.Println("Same(tree.New(1), tree.New(2))", Same(tree.New(1), tree.New(2)))
}
package main
import (
"golang.org/x/tour/tree"
"fmt"
)
func WalkInternal(t *tree.Tree, ch chan int) {
if t== nil {
return
}
WalkInternal(t.Left, ch)
ch <- t.Value
//fmt.Println(t.Value)
WalkInternal(t.Right, ch)
}
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
WalkInternal(t,ch)
close(ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
tc1 := make(chan int, 10)
tc2 := make(chan int, 10)
go Walk(t1, tc1)
go Walk(t2, tc2)
for{
select{
case te1, ok1 := <-tc1:
te2, ok2 := <-tc2
if ok1 == ok2 {
//all done - chan closed
if ok1 == false {
fmt.Println("same")
return true
}
//value not same, no need to sort as we read from a sorted tree
if te1 !=te2 {
fmt.Println("not same")
return false
}
//fmt.Println("same:", te1, te2)
continue
}else{
fmt.Println("not same") //not same length
return false
}
}
}
//return same
}
func main() {
Same(tree.New(1), tree.New(1))
Same(tree.New(1), tree.New(2))
Same(tree.New(2), tree.New(2))
}
@Sebastian-Nielsen Great solution but I believe you meant:
noMoreValuesInEitherTree := !(ok1 || ok2) // !ok1 && !ok2
isMoreNodesInOneTree := !(ok1 && ok2) // !ok1 || !ok2
here:
noMoreValuesInEitherTree := !(ok1 && ok2) if noMoreValuesInEitherTree { return true } isMoreNodesInOneTree := !(ok1 || ok2) if isMoreNodesInOneTree { return false }
I tested with trees of uenequal lengths (or one nil
):
func TestSame(t *testing.T) {
tree1 := tree.New(1)
tree2 := tree.New(2)
treeSingle := &tree.Tree{Left: nil, Value: 42, Right: nil}
cases := []struct {
t1, t2 *tree.Tree
expected bool
}{
{tree1, tree1, true},
{tree1, tree2, false},
{nil, tree1, false},
{tree2, nil, false},
{tree2, treeSingle, false},
}
for _, c := range cases {
got := Same(c.t1, c.t2)
if got != c.expected {
t.Errorf("\nt1=%v\nt2=%v\n...returned %v, expected %v", c.t1, c.t2, got, c.expected)
}
}
}
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
var _Walk func(t *tree.Tree, ch chan int)
_Walk = func(t *tree.Tree, ch chan int) {
if t != nil {
_Walk(t.Left, ch)
ch <- t.Value
_Walk(t.Right, ch)
}
}
_Walk(t, ch)
close(ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
if (ok1 || ok2) == false {
return true
} else if (ok1 && ok2) == false || v1 != v2 {
return false
}
}
}
func main() {
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := range ch {
fmt.Print(i, " ")
}
fmt.Println()
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}
1 2 3 4 5 6 7 8 9 10
true
false
package main
import "golang.org/x/tour/tree"
import "fmt"
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int){
_Walk(t, ch)
close(ch)
}
func _Walk(t *tree.Tree, ch chan int){
if t.Left != nil {
_Walk(t.Left, ch)
}
ch <- t.Value
if t.Right != nil {
_Walk(t.Right, ch)
}
}
func Same(t1, t2 *tree.Tree) bool{
ch1 := make(chan int, 10)
ch2 := make(chan int, 10)
go Walk(t1, ch1)
go Walk(t2, ch2)
for v := range ch1 {
v2, ok := <-ch2
if v != v2 || ! ok{
return false
}
}
if _, ok := <-ch2; ok {
return false
}
return true
}
func main() {
t := tree.New(1)
ch := make(chan int, 1000)
go Walk(t, ch)
for r := range ch {
fmt.Println(r)
}
fmt.Println(Same(tree.New(1), tree.New(1)))
}
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
result := true
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
if (ok1 || ok2) == false {
break
} else if (ok1 && ok2) == false || v1 != v2 {
result = false
break
}
}
return result
}
func main() {
fmt.Println(Same(tree.New(1), tree.New(2)))
}
package main
import (
"golang.org/x/tour/tree"
"fmt"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
WalkRecursive(t, ch)
close(ch)
}
func WalkRecursive(t *tree.Tree, ch chan int) {
if (t == nil) {
return
}
if (t.Left != nil) {
WalkRecursive(t.Left, ch)
}
ch <- t.Value
if (t.Right != nil) {
WalkRecursive(t.Right, ch)
}
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
t1Values := make(map[int]int)
myChanForT1 := make(chan int)
go Walk(t1, myChanForT1)
for i := range myChanForT1{
t1Values[i] = 1
}
myChanForT2 := make(chan int)
go Walk(t2, myChanForT2)
for j := range myChanForT2{
if _, ok := t1Values[j] ; ok == false {
return false
}
}
return true
}
func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
}
package main
import (
"golang.org/x/tour/tree"
"fmt"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
walkR(t, ch)
close(ch)
}
func walkR(t *tree.Tree, ch chan int) {
if t == nil {
return
}
walkR(t.Left, ch)
ch <- t.Value
walkR(t.Right, ch)
}
func readChan(ch chan int) string {
l := []int{}
for v := range ch {
l = append(l, v)
}
return fmt.Sprint(l)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
s1, s2 := readChan(ch1), readChan(ch2)
return s1 == s2
}
func main() {
ch := make(chan int)
go Walk(tree.New(1), ch)
fmt.Println(readChan(ch))
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
close(ch)
return
}
stack, cur := []*tree.Tree{}, t
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
ch <- cur.Value
cur = cur.Right
}
close(ch)
}
type counts struct {
v1 int
v2 int
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int, 10), make(chan int, 10)
go Walk(t1, ch1)
go Walk(t2, ch2)
values := map[int]counts{}
for n := 2; n > 0; {
select {
case v, ok := <-ch1:
if !ok {
n, ch1 = n-1, nil
}
c, ok := values[v]
if !ok {
values[v] = counts{1, 0}
} else {
c.v1++
values[v] = c
}
case v, ok := <-ch2:
if !ok {
n, ch2 = n-1, nil
}
c, ok := values[v]
if !ok {
values[v] = counts{0, 1}
} else {
c.v2++
values[v] = c
}
}
}
for _, c := range values {
if c.v1 != c.v2 {
return false
}
}
return true
}
func main() {
ch := make(chan int, 10)
go Walk(tree.New(1), ch)
for v := range ch {
fmt.Println(v)
}
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}
package main
import (
"golang.org/x/tour/tree"
"fmt"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t.Left != nil {
Walk(t.Left, ch)
}
if t.Right != nil {
Walk(t.Right, ch)
}
ch <- t.Value
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch := make(chan int, 20)
go Walk(t1, ch)
go Walk(t2, ch)
res := 0
for i := 0; i < 20; i++ {
val := <-ch
res ^= val
}
return res == 0
}
func main() {
t1, t2 := tree.New(1), tree.New(1)
fmt.Printf("%v\n%v\n%v\n*****\n", t1, t2, Same(t1, t2))
t1, t2 = tree.New(2), tree.New(3)
fmt.Printf("%v\n%v\n%v\n*****\n", t1, t2, Same(t1, t2))
}
amazing! this help me!