Go
golang

A Tour of Goの練習問題をちゃんと解いた解答

はじめに

A Tour of GoはGoの入門にはいい教材だと思いますが、練習問題の中には初見だと難しいと感じたものがありました。調べてもそのまま動く解答がなかなか見つからない問題もあったため、解答を残しておきたいと思います。

  • そのままコピーして正しく動く
  • 必要ないパッケージを使わない
  • なるべくシンプルに書く

を解答の方針とします。

見つけた他の解答
https://qiita.com/kroton/items/8622d5e9e38ff822070c
https://gist.github.com/zyxar/2317744
https://github.com/golang/tour/tree/master/solutions
http://takatoshiono.hatenablog.com/entry/2016/09/08/001823
http://blog.yuuk.io/entry/2014/02/16/183206

Exercise: Loops and Functions

関数とループを使った簡単な練習として、 ニュートン法 を使った平方根の計算を実装してみましょう。...
問題 https://go-tour-jp.appspot.com/flowcontrol/8

10回だけ繰り返す

最初は、その計算式を10回だけ繰り返し、 x を(1, 2, 3, ...)と様々な値に対する結果がどれだけ正解値に近づくかを確認してみてください。

exercise-loops-and-functions.go
package main

import (
    "fmt"
)

func Sqrt(x float64) float64 {
    z := 1.0
    for i := 0; i < 10; i++ {
        z -= (z*z - x) / (2 * z)
    }
    return z
}

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

直前との差が小さくなったら停止

次に、ループを回すときの直前に求めたzの値がこれ以上変化しなくなったとき (または、差がとても小さくなったとき)に停止するようにループを変更してみてください。

exercise-loops-and-functions.go
package main

import (
    "fmt"
)

func Sqrt(x float64) float64 {
    z := 1.0
    for d := 1.0; d*d > 1e-10; z -= d {
        d = (z*z - x) / (2 * z)
    }
    return z
}

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

Exercise: Slices

Pic 関数を実装してみましょう。 このプログラムを実行すると、生成した画像が下に表示されるはずです。 この関数は、長さ dy のsliceに、各要素が8bitのunsigned int型で長さ dx のsliceを割り当てたものを返すように実装する必要があります。 画像は、整数値をグレースケール(実際はブルースケール)として解釈したものです。...
問題 https://go-tour-jp.appspot.com/moretypes/18

exercise-slices.go
package main

import "golang.org/x/tour/pic"

func Pic(dx, dy int) [][]uint8 {
    pic := make([][]uint8, dy)
    for y := range pic {
        pic[y] = make([]uint8, dx)
        for x := range pic[y] {
            pic[y][x] = uint8((x + y) / 2)
        }
    }
    return pic
}

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

Exercise: Maps

WordCount 関数を実装してみましょう。string s で渡される文章の、各単語の出現回数のmapを返す必要があります。 wc.Test 関数は、引数に渡した関数に対しテストスイートを実行し、成功か失敗かを結果に表示します。...
問題 https://go-tour-jp.appspot.com/moretypes/23

exercise-maps.go
package main

import (
    "golang.org/x/tour/wc"
    "strings"
)

func WordCount(s string) map[string]int {
    m := make(map[string]int)
    for _, w := range strings.Fields(s) {
        m[w]++
    }
    return m
}

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

Exercise: Fibonacci closure

fibonacci (フィボナッチ)関数を実装しましょう。この関数は、連続するフィボナッチ数(0, 1, 1, 2, 3, 5, ...)を返す関数(クロージャ)を返します。
問題 https://go-tour-jp.appspot.com/moretypes/26

exercise-fibonacci-closure.go
package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    a, b := -1, 1
    return func() int {
        a, b = b, a+b
        return b
    }
}

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

Exercise: Stringers

IPAddr 型を実装してみましょう IPアドレスをドットで4つに区切った( dotted quad )表現で出力するため、 fmt.Stringer インタフェースを実装してください。...
問題 https://go-tour-jp.appspot.com/methods/18

exercise-stringer.go
package main

import "fmt"

type IPAddr [4]byte

func (ip IPAddr) String() string {
    return fmt.Sprintf("%d.%d.%d.%d", ip[0], ip[1], ip[2], ip[3])
}

func main() {
    hosts := map[string]IPAddr{
        "loopback":  {127, 0, 0, 1},
        "googleDNS": {8, 8, 8, 8},
    }
    for name, ip := range hosts {
        fmt.Printf("%v: %v\n", name, ip)
    }
}

Exercise: Errors

Sqrt 関数を 以前の演習 からコピーし、 error の値を返すように修正してみてください。...
問題 https://go-tour-jp.appspot.com/methods/20

exercise-errors.go
package main

import (
    "fmt"
)

type ErrNegativeSqrt float64

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

func Sqrt(x float64) (float64, error) {
    if x < 0 {
        return 0, ErrNegativeSqrt(x)
    }
    z := 1.0
    for i := 0; i < 10; i++ {
        z -= (z*z - x) / (2 * z)
    }
    return z, nil
}

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

Exercise: Readers

ASCII文字 'A' の無限ストリームを出力する Reader 型を実装してください。
問題 https://go-tour-jp.appspot.com/methods/22

exercise-reader.go
package main

import "golang.org/x/tour/reader"

type MyReader struct{}

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

func main() {
    reader.Validate(MyReader{})
}

Exercise: rot13Reader

io.Reader を実装し、 io.Reader でROT13 換字式暗号( substitution cipher )をすべてのアルファベットの文字に適用して読み出すように rot13Reader を実装してみてください。
問題 https://go-tour-jp.appspot.com/methods/23

exercise-rot-reader.go
package main

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

type rot13Reader struct {
    r io.Reader
}

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

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

Exercise: Images

前に解いた、画像ジェネレーターを覚えていますか? 今回は、データのスライスの代わりに image.Image インタフェースの実装を返すようにしてみましょう。...
問題 https://go-tour-jp.appspot.com/methods/25

exercise-images.go
package main

import (
    "golang.org/x/tour/pic"
    "image"
    "image/color"
)

type Image struct{}

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

func (i Image) Bounds() image.Rectangle {
    return image.Rect(0, 0, 256, 256)
}

func (i Image) At(x, y int) color.Color {
    return color.RGBA{uint8(x), uint8(y), 255, 255}
}

func main() {
    m := Image{}
    pic.ShowImage(m)
}

Exercise: Equivalent Binary Trees

2つの二分木が同じ順序を保持しているかどうかを確認する機能は、多くの言語においてかなり複雑です。 シンプルな解決方法を記述するために、Goの並行性( concurrency )とチャネルを利用してみます。...
問題 https://go-tour-jp.appspot.com/concurrency/7
問題続き https://go-tour-jp.appspot.com/concurrency/8

exercise-equivalent-binary-trees.go
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(*tree.Tree, chan int)
    walk = func(t *tree.Tree, ch chan int) {
        if t == nil {
            return
        }
        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 := 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() {
    ch := make(chan int)
    go Walk(tree.New(1), ch)
    for i := range ch {
        fmt.Println(i)
    }
    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(1), tree.New(2)))
}

Exercise: Web Crawler

この演習では、ウェブクローラ( web crawler )を並列化するため、Goの並行性の特徴を使います。...
問題 https://go-tour-jp.appspot.com/concurrency/10

sync.WaitGroupは本文中に出てこないですが、以下の理由のため使用しています。

  • Mutexを使うのでどうせsyncパッケージはインポートすることになる
  • channelを使って頑張るよりもシンプルで分かりやすく書ける
  • WaitGroupのドキュメントのExampleがこの問題と同じような設定

あと、一瞬で終わってしまうため並行で実行できているかが確認しづらいので、timeパッケージをインポートして、メソッドFetchの1行目にtime.Sleep(1 * time.Second)を入れて1秒待つようにすると分かりやすくなると思います。正しければ3秒で終わるはずです。

exercise-web-crawler.go
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)
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher) {
    cache := struct {
        visited map[string]bool
        sync.Mutex
    }{
        visited: make(map[string]bool),
    }
    var wg sync.WaitGroup
    var crawl func(string, int)
    crawl = func(url string, depth int) {
        defer wg.Done()
        if depth <= 0 {
            return
        }
        cache.Lock()
        if cache.visited[url] {
            cache.Unlock()
            return
        }
        cache.visited[url] = true
        cache.Unlock()
        body, urls, err := fetcher.Fetch(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)
        }
    }
    wg.Add(1)
    go crawl(url, depth)
    wg.Wait()
}

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