golang-tour: Solutions to the exercises.
R=adg
CC=golang-dev
https://golang.org/cl/6585074
diff --git a/gotour/solutions/README b/gotour/solutions/README
new file mode 100644
index 0000000..4915dc7
--- /dev/null
+++ b/gotour/solutions/README
@@ -0,0 +1,8 @@
+This directory contains the solutions to the exercises presented in the Go tour.
+
+IMPORTANT: The main point of the Go tour is to challenge you, so please try to
+solve all problems by yourself before reading these solutions!!!
+
+In any case, these are not the only valid solutions. But they have been reviewed
+by the Go team. Therefore you can use them as a guide on how to solve the
+most basic problems in Go.
diff --git a/gotour/solutions/binarytrees.go b/gotour/solutions/binarytrees.go
new file mode 100644
index 0000000..bcd454e
--- /dev/null
+++ b/gotour/solutions/binarytrees.go
@@ -0,0 +1,61 @@
+package main
+
+import (
+ "fmt"
+ "tour/tree"
+)
+
+func walkImpl(t *tree.Tree, ch chan int) {
+ if t.Left != nil {
+ walkImpl(t.Left, ch)
+ }
+ ch <- t.Value
+ if t.Right != nil {
+ walkImpl(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) {
+ walkImpl(t, ch)
+ // Need to close the channel here
+ close(ch)
+}
+
+// Same determines whether the trees
+// t1 and t2 contain the same values.
+func Same(t1, t2 *tree.Tree) bool {
+ w1, w2 := make(chan int), make(chan int)
+
+ go Walk(t1, w1)
+ go Walk(t2, w2)
+
+ for {
+ v1, ok1 := <-w1
+ v2, ok2 := <-w2
+ if v1 != v2 || ok1 != ok2 {
+ return false
+ }
+ if !ok1 {
+ break
+ }
+ }
+ return true
+}
+
+func main() {
+ fmt.Print("tree.New(1) == tree.New(1): ")
+ if Same(tree.New(1), tree.New(1)) {
+ fmt.Println("PASSED")
+ } else {
+ fmt.Println("FAILED")
+ }
+
+ fmt.Print("tree.New(1) != tree.New(2): ")
+ if !Same(tree.New(1), tree.New(2)) {
+ fmt.Println("PASSED")
+ } else {
+ fmt.Println("FAILED")
+ }
+}
diff --git a/gotour/solutions/complexcube.go b/gotour/solutions/complexcube.go
new file mode 100644
index 0000000..d4dc0e2
--- /dev/null
+++ b/gotour/solutions/complexcube.go
@@ -0,0 +1,26 @@
+package main
+
+import (
+ "fmt"
+ "math/cmplx"
+)
+
+const delta = 1e-10
+
+func Cbrt(x complex128) complex128 {
+ z := x
+ for {
+ n := z - (z*z*z-x)/(3*z*z)
+ if cmplx.Abs(n-z) < delta {
+ break
+ }
+ z = n
+ }
+ return z
+}
+
+func main() {
+ const x = 2
+ mine, theirs := Cbrt(x), cmplx.Pow(x, 1./3.)
+ fmt.Println(mine, theirs, mine-theirs)
+}
diff --git a/gotour/solutions/errors.go b/gotour/solutions/errors.go
new file mode 100644
index 0000000..2b625b4
--- /dev/null
+++ b/gotour/solutions/errors.go
@@ -0,0 +1,34 @@
+package main
+
+import (
+ "fmt"
+ "math"
+)
+
+type ErrNegativeSqrt float64
+
+func (e ErrNegativeSqrt) Error() string {
+ return fmt.Sprintf("Sqrt: negative number %g", e)
+}
+
+const delta = 1e-10
+
+func Sqrt(f float64) (float64, error) {
+ if f < 0 {
+ return 0, ErrNegativeSqrt(f)
+ }
+ z := f
+ for {
+ n := z - (z*z-f)/(2*z)
+ if math.Abs(n-z) < delta {
+ break
+ }
+ z = n
+ }
+ return z, nil
+}
+
+func main() {
+ fmt.Println(Sqrt(2))
+ fmt.Println(Sqrt(-2))
+}
diff --git a/gotour/solutions/fib.go b/gotour/solutions/fib.go
new file mode 100644
index 0000000..efdc639
--- /dev/null
+++ b/gotour/solutions/fib.go
@@ -0,0 +1,20 @@
+package main
+
+import "fmt"
+
+// fibonacci is a function that returns
+// a function that returns an int.
+func fibonacci() func() int {
+ f, g := 0, 1
+ return func() int {
+ f, g = g, f+g
+ return f
+ }
+}
+
+func main() {
+ f := fibonacci()
+ for i := 0; i < 10; i++ {
+ fmt.Println(f())
+ }
+}
diff --git a/gotour/solutions/image.go b/gotour/solutions/image.go
new file mode 100644
index 0000000..6bfec92
--- /dev/null
+++ b/gotour/solutions/image.go
@@ -0,0 +1,43 @@
+package main
+
+import (
+ "image"
+ "image/color"
+ "tour/pic"
+)
+
+type Image [][]uint8
+
+func (m Image) ColorModel() color.Model {
+ return color.RGBAModel
+}
+
+func (m Image) Bounds() image.Rectangle {
+ dx, dy := len(m), 0
+ if dx > 0 {
+ dy = len(m[0])
+ }
+
+ return image.Rect(0, 0, dx, dy)
+}
+
+func (m Image) At(x, y int) color.Color {
+ v := m[x][y]
+ return color.RGBA{v, v, 255, 255}
+}
+
+func NewImage(x, y int, f func(int, int) uint8) Image {
+ m := make([][]uint8, x)
+ for i := range m {
+ m[i] = make([]uint8, y)
+ for j := range m[i] {
+ m[i][j] = f(i, j)
+ }
+ }
+ return m
+}
+
+func main() {
+ m := NewImage(255, 255, func(a, b int) uint8 { return uint8(a * b) })
+ pic.ShowImage(m)
+}
diff --git a/gotour/solutions/loops.go b/gotour/solutions/loops.go
new file mode 100644
index 0000000..810f861
--- /dev/null
+++ b/gotour/solutions/loops.go
@@ -0,0 +1,26 @@
+package main
+
+import (
+ "fmt"
+ "math"
+)
+
+const delta = 1e-10
+
+func Sqrt(x float64) float64 {
+ z := x
+ for {
+ n := z - (z*z-x)/(2*z)
+ if math.Abs(n-z) < delta {
+ break
+ }
+ z = n
+ }
+ return z
+}
+
+func main() {
+ const x = 2
+ mine, theirs := Sqrt(x), math.Sqrt(x)
+ fmt.Println(mine, theirs, mine-theirs)
+}
diff --git a/gotour/solutions/maps.go b/gotour/solutions/maps.go
new file mode 100644
index 0000000..a158289
--- /dev/null
+++ b/gotour/solutions/maps.go
@@ -0,0 +1,18 @@
+package main
+
+import (
+ "strings"
+ "tour/wc"
+)
+
+func WordCount(s string) map[string]int {
+ m := make(map[string]int)
+ for _, f := range strings.Fields(s) {
+ m[f]++
+ }
+ return m
+}
+
+func main() {
+ wc.Test(WordCount)
+}
diff --git a/gotour/solutions/rot13.go b/gotour/solutions/rot13.go
new file mode 100644
index 0000000..5533359
--- /dev/null
+++ b/gotour/solutions/rot13.go
@@ -0,0 +1,39 @@
+package main
+
+import (
+ "io"
+ "os"
+ "strings"
+)
+
+func rot13(b byte) byte {
+ var a, z byte
+ switch {
+ case 'a' <= b && b <= 'z':
+ a, z = 'a', 'z'
+ case 'A' <= b && b <= 'Z':
+ a, z = 'A', 'Z'
+ default:
+ return b
+ }
+ return (b-a+13)%(z-a+1) + a
+}
+
+type rot13Reader struct {
+ r io.Reader
+}
+
+func (r rot13Reader) Read(p []byte) (n int, err error) {
+ n, err = r.r.Read(p)
+ for i := 0; i < n; i++ {
+ p[i] = rot13(p[i])
+ }
+ return
+}
+
+func main() {
+ s := strings.NewReader(
+ "Lbh penpxrq gur pbqr!")
+ r := rot13Reader{s}
+ io.Copy(os.Stdout, &r)
+}
diff --git a/gotour/solutions/slices.go b/gotour/solutions/slices.go
new file mode 100644
index 0000000..035f9ac
--- /dev/null
+++ b/gotour/solutions/slices.go
@@ -0,0 +1,22 @@
+package main
+
+import "tour/pic"
+
+func Pic(dx, dy int) [][]uint8 {
+ p := make([][]uint8, dy)
+ for i := range p {
+ p[i] = make([]uint8, dx)
+ }
+
+ for y := range p {
+ for x, row := range p[y] {
+ row[x] = uint8(x * y)
+ }
+ }
+
+ return p
+}
+
+func main() {
+ pic.Show(Pic)
+}
diff --git a/gotour/solutions/webcrawler.go b/gotour/solutions/webcrawler.go
new file mode 100644
index 0000000..3ec2444
--- /dev/null
+++ b/gotour/solutions/webcrawler.go
@@ -0,0 +1,131 @@
+package main
+
+import (
+ "errors"
+ "fmt"
+ "sync"
+)
+
+type Fetcher interface {
+ // Fetch returns the body of URL and
+ // a slice of URLs found on that page.
+ Fetch(url string) (body string, urls []string, err error)
+}
+
+// fetched tracks URLs that have been (or are being) fetched.
+// The lock must be held while reading from or writing to the map.
+// See http://golang.org/ref/spec#Struct_types section on embedded types.
+var fetched = struct {
+ m map[string]error
+ sync.Mutex
+}{m: make(map[string]error)}
+
+var loading = errors.New("url load in progress") // sentinel value
+
+// Crawl uses fetcher to recursively crawl
+// pages starting with url, to a maximum of depth.
+func Crawl(url string, depth int, fetcher Fetcher) {
+ if depth <= 0 {
+ fmt.Printf("<- Done with %v, depth 0.\n", url)
+ return
+ }
+
+ fetched.Lock()
+ if _, ok := fetched.m[url]; ok {
+ fetched.Unlock()
+ fmt.Printf("<- Done with %v, already fetched.\n", url)
+ return
+ }
+ // We mark the url to be loading to avoid others reloading it at the same time.
+ fetched.m[url] = loading
+ fetched.Unlock()
+
+ // We load it concurrently.
+ body, urls, err := fetcher.Fetch(url)
+
+ // And update the status in a synced zone.
+ fetched.Lock()
+ fetched.m[url] = err
+ fetched.Unlock()
+
+ if err != nil {
+ fmt.Printf("<- Error on %v: %v\n", url, err)
+ return
+ }
+ fmt.Printf("Found: %s %q\n", url, body)
+ done := make(chan bool)
+ for i, u := range urls {
+ fmt.Printf("-> Crawling child %v/%v of %v : %v.\n", i, len(urls), url, u)
+ go func(url string) {
+ Crawl(url, depth, fetcher)
+ done <- true
+ }(u)
+ }
+ for i := range urls {
+ fmt.Printf("<- [%v] %v/%v Waiting for child %v.\n", url, i, len(urls))
+ <-done
+ }
+ fmt.Printf("<- Done with %v\n", url)
+}
+
+func main() {
+ Crawl("http://golang.org/", 4, fetcher)
+
+ fmt.Println("Fetching stats\n--------------")
+ for url, err := range fetched.m {
+ if err != nil {
+ fmt.Printf("%v failed: %v\n", url, err)
+ } else {
+ fmt.Printf("%v was fetched\n", url)
+ }
+ }
+}
+
+// fakeFetcher is Fetcher that returns canned results.
+type fakeFetcher map[string]*fakeResult
+
+type fakeResult struct {
+ body string
+ urls []string
+}
+
+func (f *fakeFetcher) Fetch(url string) (string, []string, error) {
+ if res, ok := (*f)[url]; ok {
+ return res.body, res.urls, nil
+ }
+ return "", nil, fmt.Errorf("not found: %s", url)
+}
+
+// fetcher is a populated fakeFetcher.
+var fetcher = &fakeFetcher{
+ "http://golang.org/": &fakeResult{
+ "The Go Programming Language",
+ []string{
+ "http://golang.org/pkg/",
+ "http://golang.org/cmd/",
+ },
+ },
+ "http://golang.org/pkg/": &fakeResult{
+ "Packages",
+ []string{
+ "http://golang.org/",
+ "http://golang.org/cmd/",
+ "http://golang.org/pkg/fmt/",
+ "http://golang.org/pkg/os/",
+ },
+ },
+ "http://golang.org/pkg/fmt/": &fakeResult{
+ "Package fmt",
+ []string{
+ "http://golang.org/",
+ "http://golang.org/pkg/",
+ },
+ },
+ "http://golang.org/pkg/os/": &fakeResult{
+ "Package os",
+ []string{
+ "http://golang.org/",
+ "http://golang.org/pkg/",
+ },
+ },
+}
