13092011 Go

Goでheapの実装

IntVectorってのはsortのInterfaceを実装しているのでsortはなにも定義しなくても普通にOK

package main

import  (
    "container/vector"
    "sort"
    "fmt"
)

func main() {
    v := new(vector.IntVector)
    v.Push(3)
    v.Push(2)
    v.Push(4)
    v.Push(1)

    sort.Sort(v)
    fmt.Println(v)
}

続いて、heapの実装。godoc container/heapすると

type Interface interface {
    sort.Interface
    Push(x interface{})
    Pop() interface{}
}

となっていて、sortのインターフェースとPush,Popが実装されていればイイ。IntVectorにはPushとPopも実装されているのでOKかなと思ったがこれはだめ。

package main

import  (
    "container/vector"
    "container/heap"
    "fmt"
)

func main() {
    v := new(vector.IntVector)
    heap.Push(v,3)
    heap.Push(v,2)
    heap.Push(v,4)
    heap.Push(v,1)
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
}

これをコンパイルしようとすると

$ 6g myheap.go
myheap.go:11: cannot use v (type *vector.IntVector) as type heap.Interface in function argument:
    *vector.IntVector does not implement heap.Interface (wrong type for Pop method)
        have Pop() int
        want Pop() interface { }

といって怒られる。じゃぁメソッドってオーバーライドできるのかなと。

package main

import  (
    "container/vector"
    "container/heap"
    "fmt"
)

func (v *vector.IntVector) Push (i interface{}) { v.Push(i.(int)) }
func (v *vector.IntVector) Pop ()  interface{}  { return v.Pop() }

func main() {
    v := new(vector.IntVector)
    heap.Push(v,3)
    heap.Push(v,2)
    heap.Push(v,4)
    heap.Push(v,1)
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
    fmt.Println(heap.Push(v))
}

これをコンパイルしようとすると

$ 6g myheap.go
myheap.go:9: method redeclared: vector.IntVector.Push
    method(p *vector.IntVector)func(x int)
    method(v *vector.IntVector)func(i interface { })

結局構造体を作ってこんな感じにした。

package main

import  (
       "container/vector"
       "container/heap"
       "fmt"
)

type heapq struct {
       hq vector.IntVector
}

func (h *heapq) Len() int          { return h.hq.Len() }
func (h *heapq) Less(i,j int) bool { return  h.hq.Less(i,j) }
func (h *heapq) Swap(i,j int)      { h.hq.Swap(i,j) }
func (h *heapq) Push(i interface{}){ h.hq.Push(i.(int)) }
func (h *heapq) Pop() interface{}  { return h.hq.Pop() }

func main() {
       hq := new(heapq)
       heap.Push(hq,3)
       heap.Push(hq,2)
       heap.Push(hq,4)
       heap.Push(hq,1)
       fmt.Println(heap.Pop(hq))
       fmt.Println(heap.Pop(hq))
       fmt.Println(heap.Pop(hq))
       fmt.Println(heap.Pop(hq))
}

結構面倒くさい。単に面倒くさい方法を選択しているだけなのだろうか？よくわからんです。

12092011 Go

godoc便利だ

interfaceの情報出てくる

$ godoc container/Heap

TYPES

type Interface interface {
    sort.Interface
    Push(x interface{})
    Pop() interface{}
}
Any type that implements heap.Interface may be used as a
min-heap with the following invariants (established after
Init has been called):

    !h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()

Heapを使いたい時にはsortのインターフェースにあわせてPushとPopを実装するべしということですね。

11092011 Go

Goで個数制限付き部分和問題

プログラミングコンテストチャレンジブック(2-3)

数字の種類と個数が幾つか与えられたときに足し算で任意の数が作れるかという問題。DPで解く

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


配列を0以外の数で初期化する方法が分からなかったので、初期化してから全ての要素に-1を放り込むためにループを回したけど、ここはどうするのがいいんだろう。あと本のコード間違ってるよね。dp[0]には0じゃなくてmiを入れないと。

package main

import "fmt"

const MAX_N = 100

func main() {
    n := 3
    a := []int{3,5,8}
    m := []int{3,2,2}
    K := 17
    dp := [MAX_N]int{}
    for i,_ := range(dp) {
        dp[i] = -1
    }

    for i := 0; i<n; i++ {
        dp[0] = m[i]
        for j := 0;j<=K;j++ {
            if dp[j] >= 0 {
                dp[j] = m[i]
            } else if j < a[i] || dp[j - a[i]] <= 0 {
                dp[j] = -1
            } else {
                dp[j] = dp[j - a[i]] - 1
            }
        }
    }
    if dp[K] >= 0 {
        fmt.Println("yes")
    } else {
        fmt.Println("no")
    }
}

11092011 Go

Goでナップサック問題

プログラミングコンテストチャレンジブック(2-3)

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


Dynamic Programmingで解く

package main

import "fmt"

const MAX_N int = 100
const MAX_W int = 10000

type knapsack struct {
    weight int
    value int
}

func max(i,j int) int{
    if i > j {
        return i
    }
    return j
}

func main() {
    W := 5
    N := 4
    knap := []knapsack{{2,3},{1,2},{3,4},{2,2}}
    dp := [MAX_N][MAX_W]int{}
    for i := 0; i<N; i++ {
        for j :=0; j<=W; j++ {
            if j < knap[i].weight {
                dp[i+1][j] = dp[i][j]
            } else {
                dp[i+1][j] = max(dp[i][j], dp[i][j - knap[i].weight] + knap[i].value)
            }
        }
    }
    fmt.Println(dp[N][W])
}

11092011 Go

Best Cow Line (Go)

プログラミングコンテストチャレンジブック(2-2)

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


Goにはwhileがないけどforで同じことができる。文字列はbyteの配列のように振る舞うので出力するときにstringで変換しないと数字が出力される。それから配列の参照時に、インクリメント、デクリメントステートメントは使えない、つまりS[a++]という書き方はできない。

package main

import "fmt"

const MAX_N int = 2000

func main() {
    N := 6
    S := "ACDBCB"
    a := 0
    b := N-1

    for a <= b {
        left := false
        for i := 0; a+i < b; i++ {
            if S[a+i] < S[b-i] {
                left = true
                break
            } else if S[a+i] > S[b-i] {
                left = false
                break
            }
        }

        if left {
            fmt.Printf("%s",string(S[a]))
            a++
        } else {
            fmt.Printf("%s",string(S[b]))
            b--
        }
    }
    fmt.Printf("\n")
}

10092011 Go

Goで区間スケジューリング問題

プログラミングコンテストチャレンジブック(2-2)

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


本ではpairを使ってソートして解いているのだが、Goにはpair型がないっぽいので、擬似的に2要素の配列とそのスライスに名前をつけてsort出来るようにした。

package main

import (
    "fmt"
    "sort"
)

type pair [2]int
type Pi []pair

func (p Pi) Len() int          { return len(p) }
func (p Pi) Less(i,j int) bool { return  p[i][1] < p[j][1] }
func (p Pi) Swap(i,j int)      { p[i],p[j] = p[j],p[i] }

func main() { 
    s := [5]int{1, 2, 4, 6, 8}
    t := [5]int{3, 5, 7, 9, 10}
    itv := make(Pi, 5)
    for i := 0; i<len(s); i++ {
        itv[i] = pair{s[i],t[i]}
    }
    sort.Sort(itv)
    ans := 0
    time := 0
    tasks := []int{}
    for j := 0; j<len(s); j++ {
        if time < itv[j][0] {
            ans++
            time = itv[j][1]
            tasks = append(tasks, j)
        }
    }
    fmt.Printf("%d tasks %v\n", ans,tasks)
}

書いてて、あれ、配列のスライスは辞書順でソートしてくれるかな?と思い、

itv := make([][2]int,5)

に変更してコンパイルしてみたらやはり通らなかった。

schedule.go:22: cannot use itv (type [][2]int) as type sort.Interface in function argument:
    [][2]int does not implement sort.Interface (missing Len method)

ちょっと、スライスの使い方がわかってきたような気がする。

09092011 Go

GoでGreedy algorithm

プログラミングコンテストチャレンジブック(2-2)

「できるだけ少ない数の硬貨で支払うには？」というよくある問題。minとかmaxが見当たらなかったので自分で定義した。

package main

import "fmt"

func min(i,j int) int {
       if i < j {
               return i
       }
       return j
}

func main() {
       ans := ""
       A := 620
       coins := [6]int{500,100,50,10,5,1}
       num := [6]int{2,0,3,1,2,3}
       for k, coin := range(coins){
               t := min(A/coin,num[k])
               A -= t * coin
               ans += fmt.Sprintf("%d: %d ",coin,t)
       }
       fmt.Printf("%s\n",ans)
}

まだまだ初級編

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


08092011 Go

GoでDFS

プログラミングコンテストチャレンジブック2-1のLake Counting

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


次のような水たまり(Wで八方向に繋がっている)の数を数える

W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

コード

package main

import "fmt"

const MAX_N = 100
const MAX_M = 100
var N,M int

func makeTable(lake []byte, field *[MAX_N][MAX_M]byte, width,height int) {

    for y := 0; y < height; y++ {
        for x := 0; x < width; x++ {
            field[y][x] = lake[y*width+x]
        }
    }
}

func dfs (field *[MAX_N][MAX_M]byte, x, y int) {
    var nx,ny int
    field[x][y] = '.'
    for dx := -1; dx <= 1; dx++ {
        for dy := -1; dy <= 1; dy++ {
            nx = x + dx
            ny = y + dy
            if 0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W' {
                dfs(field, nx, ny)
            }
        }
    }
}

func main() {
    N = 10
    M = 12
    res := 0
    field := new([MAX_N][MAX_M]byte)

    lake := []byte("W........WW..WWW.....WWW....WW...WW\
    ..........WW..........W....W......W...W.W.....WW.W.\
    W.W.....W..W.W......W...W.......W.")

    makeTable(lake,field,M,N)

    for i := 0; i<N; i ++ {
        for j :=0; j<M; j++ {
            if field[i][j] == 'W' {
                dfs(field, i, j)
                res++
            }
        }
    }
    fmt.Printf("result: %d\n", res)
}

Goにはpermutationとかあんのかなぁとふと思った。

08092011 Go

stackoverflowで参考になった質問(Go)

新しい言語を学ぶときにsofを取りあえずなめとくのはもはや定番だと思うが、goのタグ付いてるのが400問ちょいだったので、全部眺めてみて役だったものをリストアップしてみた。

入門ドキュメント

answerに載ってたドキュメントが面白そう。

文字列関連

文字列の操作は結構はまった。というかいまでもよくわからん部分が多い。取りあえず配列とスライスの違いは理解したが。

プロファイラ

google-perftoolsってのを使えばいいらしい。

配列のコピー

コピーはちょっとめんどくさそう

インターフェース

ダックタイピングみたいなもん。結構わかりやすい説明だった。

channelをhaskellでエミュレートするには？

面白そうなんだけどまだちゃんと読んでないというか、channelをきちんと理解してないから後で読む。

07092011 Python Go

Goでフィボナッチのメモ化

Goでつくる簡易Wikiのサンプルは楽しいですね。標準ライブライブラリにhttpやHTML5用のパーサが入っているのはポイント高いですな。あとGAEにも対応したしね。

なかなか楽しいので少し覚えるためにプログラミングコンテストチャレンジブックをGoで書いていくことにしようかなと。

ProductName プログラミングコンテストチャレンジブック
秋葉 拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )


定番のフィボナッチ（メモ化）

package main

import "fmt"

var memo [100]int

func fib(n int) int {
   if n <= 1 {
       return n
   }
   if memo[n] != 0 {
       return memo[n]
   }
   memo[n] = fib(n-1) + fib(n-2)
   return memo[n]
}

func main() {
   fmt.Println(fib(10))
}

こっちはPythonで

memo = [0]*100

def fib(n):
    if n <= 1:
        return n
    if memo[n] != 0:
        return memo[n]
    else:
        memo[n] = fib(n-1) + fib(n-2)
        return memo[n]

if __name__ == '__main__':
    print fib(10)