tour.golang exercise solutions

exercise.tour.go

/* Exercise: Loops and Functions #43 */
package main

import (
	"fmt"
	"math"
)

func Sqrt(x float64) float64 {
	z := float64(2.)
	s := float64(0)
	for {
		z = z - (z*z - x)/(2*z)
		if math.Abs(s-z) < 1e-15 {
			break
		}
		s = z
	}
	return s
}

func main() {
	fmt.Println(Sqrt(2))
	fmt.Println(math.Sqrt(2))
}

/******************************************************************************************************/

/* Exercise: Maps #44 */
package main

import (
	"tour/wc"
	"strings"
)

func WordCount(s string) map[string]int {
	ss := strings.Fields(s)
	num := len(ss)
	ret := make(map[string]int)
	for i := 0; i < num; i++ {
		(ret[ss[i]])++
	}
	return ret
}

func main() {
	wc.Test(WordCount)
}

/******************************************************************************************************/

/* Exercise: Slices #45 */
package main

import "tour/pic"

func Pic(dx, dy int) [][]uint8 {
	ret := make([][]uint8, dy)
	for i := 0; i < dy; i++ {
		ret[i] = make([]uint8, dx)
		for j := 0; j < dx; j++ {
			ret[i][j] = uint8(i^j+(i+j)/2)
		}
	}
	return ret
}

func main() {
	pic.Show(Pic)
}

/******************************************************************************************************/

/* Exercise: Fibonacci closure #46 */
package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
	var x, y = 0, 1
	return func() (z int) {
		z, x, y = x, y, x+y
		return
	}
}

func main() {
	f := fibonacci()
	for i := 0; i < 10; i++ {
		fmt.Println(f())
	}
}

/******************************************************************************************************/

/* Advanced Exercise: Complex cube roots #47 */
package main

import (
	"fmt"
	"math/cmplx"
)

func Cbrt(x complex128) complex128 {
	z := complex128(2)
	s := complex128(0)
	for {
		z = z - (cmplx.Pow(z,3) - x)/(3 * (z * z))
		if cmplx.Abs(s-z) < 1e-17 {
			break
		}
		s = z
	}
	return z
}

func main() {
	fmt.Println(Cbrt(2))
}

/******************************************************************************************************/

/* Exercise: Errors #57 */
package main

import (
	"fmt"
)

type ErrNegativeSqrt float64

func (e ErrNegativeSqrt) Error() string {
	return fmt.Sprintf("cannot Sqrt negativ number: %g", float64(e))
}

func Sqrt(f float64) (float64, error) {
	if f < 0 {
		return 0, ErrNegativeSqrt(f)
	}
	return 0, nil
}

func main() {
	fmt.Println(Sqrt(2))
	fmt.Println(Sqrt(-2))
}

/******************************************************************************************************/

/* Exercise: Images #58 */
package main

import (
	"image"
	"tour/pic"
	"image/color"
)

type Image struct{
	Width, Height int
	colr uint8	
}

func (r *Image) Bounds() image.Rectangle {
	return image.Rect(0, 0, r.Width, r.Height)
}

func (r *Image) ColorModel() color.Model {
	return color.RGBAModel
}

func (r *Image) At(x, y int) color.Color {
	return color.RGBA{r.colr+uint8(x), r.colr+uint8(y), 255, 255}
}

func main() {
	m := Image{100, 100, 128}
	pic.ShowImage(&m)
}

/******************************************************************************************************/
/* Exercise: Rot13 Reader #59: 'You cracked the code!' */
package main

import (
	"io"
	"os"
	"strings"
)

type rot13Reader struct {
	r io.Reader
}

func (rot *rot13Reader) Read(p []byte) (n int, err error) {
	n,err = rot.r.Read(p)
	for i := 0; i < len(p); i++ {
		if (p[i] >= 'A' && p[i] < 'N') || (p[i] >='a' && p[i] < 'n') {
			p[i] += 13
		} else if (p[i] > 'M' && p[i] <= 'Z') || (p[i] > 'm' && p[i] <= 'z'){
			p[i] -= 13
		}
	}
	return
}

func main() {
	s := strings.NewReader(
		"Lbh penpxrq gur pbqr!")
	r := rot13Reader{s}
	io.Copy(os.Stdout, &r)
}

/******************************************************************************************************/

/* Exercise: Equivalent Binary Trees #67 */
package main

import (
	"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) {
	_walk(t, ch)
	close(ch)
	
}

func _walk(t *tree.Tree, ch chan int) {
	if t != nil {
		_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 := range ch1 {
		if i != <- ch2 {
			return false
		}
	}
	return true	
}

func main() {
	//tree.New(2)
	ch := make(chan int)
	go Walk(tree.New(1), ch)
	for v := range ch {
		fmt.Print(v)
	}
	fmt.Println(Same(tree.New(1), tree.New(1)))
	fmt.Println(Same(tree.New(1), tree.New(2)))
}

/******************************************************************************************************/

/* Exercise: Web Crawler #69 */
package main

import (
    "fmt"
)

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)
}

var store map[string]bool

func Krawl(url string, fetcher Fetcher, Urls chan []string) {
    body, urls, err := fetcher.Fetch(url)
    if err != nil {
        fmt.Println(err)
    } else {
        fmt.Printf("found: %s %q\n", url, body)
    }
    Urls <- urls
}

func Crawl(url string, depth int, fetcher Fetcher) {
    Urls := make(chan []string)
    go Krawl(url, fetcher, Urls)
    band := 1
    store[url] = true // init for level 0 done
    for i := 0; i < depth; i++ {
        for band > 0 {
            band--
            next := <- Urls
            for _, url := range next {
                if _, done := store[url] ; !done {
                    store[url] = true
                    band++
                    go Krawl(url, fetcher, Urls)
                }
            }
        }
    }
    return
}

func main() {
    store = make(map[string]bool)
    Crawl("http://golang.org/", 4, fetcher)
}


// 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/",
        },
    },
}

My solution for Web Crawler, heavily inspired by the official solution:

package main

import (
	"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)
}

type URLCache struct {
	mu      sync.Mutex
	fetched map[string]struct{}
}

func (c *URLCache) Add(url string) {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.fetched[url] = struct{}{}
}

func (c *URLCache) Has(url string) bool {
	c.mu.Lock()
	defer c.mu.Unlock()
	_, ok := c.fetched[url]
	return ok
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func crawl(url string, depth int, fetcher Fetcher, urlCache *URLCache) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
	if depth <= 0 {
		fmt.Printf("<- Done with %v, maximum depth reached\n", url)
		return
	}

	if urlCache.Has(url) {
		fmt.Printf("<- Done with %v, already fetched\n", url)
		return
	}

	body, urls, err := fetcher.Fetch(url)

	urlCache.Add(url)

	if err != nil {
		fmt.Printf("<- Error on %v: %v\n", url, err)
		return
	}

	fmt.Printf("Found: %s %q\n", url, body)

	var wg sync.WaitGroup
	wg.Add(len(urls))
	for i, u := range urls {
		fmt.Printf("-> Crawling child %v/%v of %v : %v.\n", i, len(urls), url, u)
		go func(url string) {
			defer wg.Done()
			crawl(url, depth-1, fetcher, urlCache)
		}(u)
	}
	wg.Wait()
	fmt.Printf("<- Done with %v\n", url)
}

func Crawl(url string, depth int, fetcher Fetcher) {
	urlCache := URLCache{fetched: make(map[string]struct{})}
	crawl(url, depth, fetcher, &urlCache)
}

func main() {
	Crawl("https://golang.org/", 4, fetcher)
}

// 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{
	"https://golang.org/": &fakeResult{
		"The Go Programming Language",
		[]string{
			"https://golang.org/pkg/",
			"https://golang.org/cmd/",
		},
	},
	"https://golang.org/pkg/": &fakeResult{
		"Packages",
		[]string{
			"https://golang.org/",
			"https://golang.org/cmd/",
			"https://golang.org/pkg/fmt/",
			"https://golang.org/pkg/os/",
		},
	},
	"https://golang.org/pkg/fmt/": &fakeResult{
		"Package fmt",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
	"https://golang.org/pkg/os/": &fakeResult{
		"Package os",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
}

To avoid creating a global variable, I used an unexported function that takes in a concurrent-safe cache and initialize it in Crawl.

@apo1967

@Aternus

Reader Solution:

package tour

import (
	"fmt"
)

type MyReader struct{}

func (r MyReader) Read(b []byte) (int, error) {
	bufferLength := len(b)
	if bufferLength <= 0 {
		return 0, fmt.Errorf("buffer length must be greater than 0")
	}
	buffer := make([]byte, bufferLength)
	for k := range buffer {
		buffer[k] = uint8('A')
	}
	n := copy(b, buffer)
	return n, nil
}

Is there a reason why you just don't set the 'A' directly in b? Why creating an internal slice and then copying to b? Just curious...

Just did the same as you...

func (r MyReader) Read(b []byte) (int, error) {
	l := len(b)
	for i := range l {
		b[i] = byte('A')
	}
	return l, nil
}

Can't find a specific reason, other than explicit exercise constraints which are not included in this case, since b will already be a copy of whatever variable the Validate function will use as an argument.

My solution for rot13:

package main

import (
	"io"
	"os"
	"strings"
)

type rot13Reader struct {
	r io.Reader
}

func (reader *rot13Reader) Read(b []byte) (int, error) {
	n, err := reader.r.Read(b)
	for i := range n {
		if (b[i] >= 65 && b[i] <= 77 || b[i] >= 97 && b[i] <= 109) {
			b[i] += 13
		} else if (b[i] >= 78 && b[i] <= 90 || b[i] >= 110 && b[i] <= 122) {
			b[i] -= 13
		}
	}
	return n, err
}

func main() {
	s := strings.NewReader("Lbh penpxrq gur pbqr!")
	r := rot13Reader{s}
	io.Copy(os.Stdout, &r)
}

I've not seen this solution already, which I propose as an efficient/smart alternative: instead of relying on explicit characters, ASCII characters can be just handled by their int value (through the standard Ascii Table here )

My solution for Crawler.
Honestly this seemed the hardest so far: why doesn't the TourGo website instructs the user about the WaitGroup before this exercise? Without it this exercise was almost impossible without changing most of the function definitions.

package main

import (
	"fmt"
	"sync"
)


type Fetcher interface {
	Fetch(url string) (string, []string, error)
}

type FetchResult struct { 
	body string
	urls []string
	err error 
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher) {
	defer wg.Done() // gets executed at the end of Crawl
	
	if depth <= 0 {
		return
	}
	if cache.Check(url) {
		fmt.Printf("Hit! %s\n", url)
		return
	}
	
	body, urls, err := fetcher.Fetch(url)
	cache.Set(url)
	
	if err != nil {
		fmt.Println(err)
		return
	}
	
	fmt.Printf("found: %s %q\n", url, body)
	for _, u := range urls {
		wg.Add(1)
		go Crawl(u, depth-1, fetcher)
	}
	return
}


type Cache struct {
	v map[string]bool // Url -> Body
	m sync.Mutex
}

func (c *Cache) Check(key string) bool {
	c.m.Lock()
	defer c.m.Unlock()
	return c.v[key]  
}

func (c *Cache) Set(key string) {
	c.m.Lock()
	c.v[key] = true
	c.m.Unlock()
}

// 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{
	"https://golang.org/": &fakeResult{
		"The Go Programming Language",
		[]string{
			"https://golang.org/pkg/",
			"https://golang.org/cmd/",
		},
	},
	"https://golang.org/pkg/": &fakeResult{
		"Packages",
		[]string{
			"https://golang.org/",
			"https://golang.org/cmd/",
			"https://golang.org/pkg/fmt/",
			"https://golang.org/pkg/os/",
		},
	},
	"https://golang.org/pkg/fmt/": &fakeResult{
		"Package fmt",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
	"https://golang.org/pkg/os/": &fakeResult{
		"Package os",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
}

var cache Cache = Cache{ v: make(map[string]bool) }
var wg sync.WaitGroup     // required to let all launched goroutines finish before main() exits

func main() {
	wg.Add(1)
	go Crawl("https://golang.org/", 4, fetcher)
	wg.Wait()
}