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)の漸化式の説明が分からなかったのでググりをかましたら、わかりやすいのを見つけた。

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

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 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
  • 担　当　： きしもとさん

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

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をきちんと理解してないから後で読む。