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

07092011 life

METAMORPHOSE 2011

今年のメタモは荒天中止で残念だった。

友人たちが北海道と熊本から遠路はるばるやってきたけど、着陸後に公演中止を知ったので、週末はそのまま集合して残念会を開いていた。

残念会兼祝勝会って感じですね。よくつるんでいた最後の一人が結婚することになったのでそのお祝いも兼ねて宴会をしてた。

子供が寝てから夜中まで色々話すことが出来て楽しかったが、友人たちも楽しかったようで、「10年前に戻った感じで楽しかった」というメールがきて、ああ、十年も経つのねとちょっと感慨深くもなった。

あの頃は冬のシーズンは毎週ボードトリップしてて夏はキャンプ行ったりフェス行ったりと色々動き回っていたからなぁ。

そろそろボード再開しようかなと。ヤマボクも行きたいし、北海道にも遊びに来いって言われてるし。

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)

06092011 Emacs

Emacsでunindentationするには負の数を入れる

インデントするにはC-u C-x C-iとかC-u n(空白文字の数) C-x C-iなのはちょっと前に覚えたのだけど、逆に4文字字上げしたい場合には

C-u -4 C-x C-i

とやればよいということに気づいたが、ちょっとめんどくさい。数字打たなくてもいい方法ってあるのかな？

06092011 HTML5

入門HTML5

「HTML5が何を目指しているか」の入門書。初心者向けではないし、tips集とかコード例が載っている本ではない。文書の構造と意味付けに始まり、HTML5で登場した新しい機能をサクサクと説明してある。

特に10章はセマンティクスとか知らないと難しいかもしれないが、未来を感じさせられる内容だ。というかbioinformaticsなんかでは10年以上前からRDFとかセマンティックwebとかずっと言われ続けてきてると思うが、なかなか普及してないような気がする。けど本書を読んでpubmedとか出版社とか化合物のマイクロデータとか整備すればかなり面白いんじゃないかなぁとおもうんだけどねぇ。

9章のwebフォームも読んだら早速使いたくなる内容だった。一方8章のオフラインウェブアプリはちょっと身近な具体例が思い浮かばなかった。

ProductName 入門 HTML5
Mark Pilgrim
オライリージャパン / 2415円 ( 2011-04-23 )