2011/09/13 20:47:07
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))
}
結構面倒くさい。単に面倒くさい方法を選択しているだけなのだろうか？よくわからんです。
2011/09/12 21:17:36
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を実装するべしということですね。
2011/09/11 15:39:27
プログラミングコンテストチャレンジブック(2-3)
数字の種類と個数が幾つか与えられたときに足し算で任意の数が作れるかという問題。DPで解く
配列を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")
}
}
2011/09/11 09:36:20
プログラミングコンテストチャレンジブック(2-3)
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])
}
2011/09/11 06:42:51
プログラミングコンテストチャレンジブック(2-2)
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")
}
2011/09/10 12:10:58
プログラミングコンテストチャレンジブック(2-2)
本では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)
}
書いてて、あれ、配列のスライスは辞書順でソートしてくれるかな?と思い、
に変更してコンパイルしてみたらやはり通らなかった。
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)
ちょっと、スライスの使い方がわかってきたような気がする。
2011/09/09 20:32:46
プログラミングコンテストチャレンジブック(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)
}
まだまだ初級編
2011/09/08 20:16:46
プログラミングコンテストチャレンジブック2-1のLake Counting
次のような水たまり(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とかあんのかなぁとふと思った。
2011/09/08 19:41:14
新しい言語を学ぶときにsofを取りあえずなめとくのはもはや定番だと思うが、goのタグ付いてるのが400問ちょいだったので、全部眺めてみて役だったものをリストアップしてみた。
入門ドキュメント
answerに載ってたドキュメントが面白そう。
文字列関連
文字列の操作は結構はまった。というかいまでもよくわからん部分が多い。取りあえず配列とスライスの違いは理解したが。
プロファイラ
google-perftoolsってのを使えばいいらしい。
配列のコピー
コピーはちょっとめんどくさそう
インターフェース
ダックタイピングみたいなもん。結構わかりやすい説明だった。
channelをhaskellでエミュレートするには？
面白そうなんだけどまだちゃんと読んでないというか、channelをきちんと理解してないから後で読む。
2011/09/07 19:31:22
Goでつくる簡易Wikiのサンプルは楽しいですね。標準ライブライブラリにhttpやHTML5用のパーサが入っているのはポイント高いですな。あとGAEにも対応したしね。
なかなか楽しいので少し覚えるためにプログラミングコンテストチャレンジブックをGoで書いていくことにしようかなと。
定番のフィボナッチ（メモ化）
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)
プログラミングコンテストチャレンジブック