Drkcore

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を実装するべしということですね。

12092011 Python

devquizの一人ゲーム

5で割り切れて2で割り切れない場合に分岐させつつBFS

import sys

def halve(numbers):
   return [int(n / 2) for n in numbers]

def sweep(numbers):
   return [n for n in numbers if n % 5 != 0]

def get_data(f):
   N = int(f.readline())
   numbers = [int(n) for n in f.readline().split()]
   return (N, numbers)

def is_sweep_ok(numbers):
   for n in numbers:
       if n % 5 != 0:
           return False
   return True

def calc_cycle(numbers_set, count):
   #print numbers_set
   new_numbers_set = []
   for numbers in numbers_set:
       if is_sweep_ok(numbers):
           return count
       else:
           new_numbers_set.append(halve(numbers))
           for number in numbers:
               if (number % 5 == 0 and number % 2 != 0):
                   new_numbers_set.append(sweep(numbers))
                   break
   return calc_cycle(new_numbers_set, count + 1)

if __name__ == '__main__':
   with open(sys.argv[1]) as f:
       T = int(f.readline())
       total_count = 0
       while(total_count < T):
           N, numbers = get_data(f)
           if len(numbers) != N:
               print "error invalid numbers"
           print calc_cycle([numbers], 1)
           total_count += 1

12092011 Python

分割数の漸化式

プログラミングコンテストチャレンジブック(2-3)の漸化式の説明が分からなかったのでググりをかましたら、わかりやすいのを見つけた。

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

特にGoで書く必要もなかったのでPythonでDP

n=4
m=3
M=10000
dp = [[0]*(n+1) for i in range(m+1)]

dp[0][0] = 1

for i in range(1,m+1):
    for j in range(n+1):
        if j-i >= 0:
            dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % M
        else:
            dp[i][j] = dp[i-1][j]
        print i,j,dp

print dp[m][n]

dpを表示させてナニが起きてるのか確認。

1 0 [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 1 [[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 2 [[1, 0, 0, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
2 0 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
2 1 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
2 2 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 0, 0], [0, 0, 0, 0, 0]]
2 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 0], [0, 0, 0, 0, 0]]
2 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [0, 0, 0, 0, 0]]
3 0 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 0, 0, 0, 0]]
3 1 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 0, 0, 0]]
3 2 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 0, 0]]
3 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 3, 0]]
3 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 3, 4]]
4

O(n*m)の計算量ですな。

11092011 Go

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

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

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

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 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)

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 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)

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 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 javascript

9/17は第6回JavaScript読書会

来週末は最後のJavascript読書会です。

ついでに次回以降の読書会のネタぎめもやると思います。

日　時　： 2011年9月17日（土） 13：00～17：30
場　所　： b-nest 静岡市産学交流センター演習室3
URL　　： http://www.b-nest.jp/
地　図　： http://www.b-nest.jp/map.html
定　員　： 20名
費　用　： 1,000円 (学生・未成年無料)
持ち物　：パソコン、課題図書
課題図書： JavaScript: The Good Parts （ISBN-10: 4873113911）※各自事前購入
環境　　： JavaScriptのコーディング用エディタ及び動作確認用webブラウザ
範　囲　：付録C　JSLint
担　当　：きしもとさん

JavaScript: The Good Parts ―「良いパーツ」によるベストプラクティス
Douglas Crockford
オライリージャパン / 1890円 ( 2008-12-22 )

個人的にはこの本を読んでよかったと思っている。Node.jsのコードリーディングも楽になったし。

来週に向けてJSLintをコマンドラインから動かせるようにしておく

npm intstall jslint -g

これでjslintというコマンドラインで動くコマンドが手に入るのでちょっと使ってみる。

$ jslint echo.js

echo.js
/*jslint node: true, es5: true */
  1 8,13: Move 'var' declarations to the top of the function.
    for (var i=0;i < sockets.length; i++) {
  2 8,13: Stopping.  (42% scanned).

varは関数のトップで宣言しろとお叱りをうけた。

どっちかというとpep8に近い。

10092011 Go

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

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

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 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)
}

まだまだ初級編

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

もう5年目(wishlistありマス♡)
最近はPythonとDeepLearning
日本酒自粛中
ドラムンベースからミニマルまで
ポケモンGOゆるめ