16092011 javascript Emacs

Emacsのcoffee-modeに" -> "を挿入するショートカットキーを設定した

CoffeeScriptはfunctionが->になっただけでしょっちゅう->を打たなければならない。

これは面倒なのでショートカットキーを割り当てた。

(require 'coffee-mode)

(add-to-list 'auto-mode-alist '("\\.coffee$" . coffee-mode))
(add-to-list 'auto-mode-alist '("Cakefile" . coffee-mode))

(add-hook 'coffee-mode-hook '(lambda ()
                             (local-set-key "\C-j" (lambda ()
                             (interactive)(insert " -> ")))
                 ))

;; CoffeeScript uses two spaces.
(defun coffee-custom ()
  "coffee-mode-hook"
 (set (make-local-variable 'tab-width) 2))

(add-hook 'coffee-mode-hook
  '(lambda() (coffee-custom)))

これでそこそこ便利になったが、もうちょっとカイゼンする余地はあるんだろうなぁ。

ProductName Emacsテクニックバイブル　～作業効率をカイゼンする200の技～
るびきち
技術評論社 / 2919円 ( 2010-08-03 )


おまけ

静岡javascript勉強会が10/1にあります。node.jsやjQueryMobileのトークも入ってて盛りだくさんなのでおもしろそうですね。枠が埋まっているけど、キャンセル待ちに入れておくといいと思います。

残念なことに僕がキャンセル第一号ですけどねー

15092011 Java

SRM518 DIV2 500

辞書順で一番大きい部分文字列を探す。

java慣れしないとなぁ。

import java.util.*;
public class LargestSubsequence {
    public String getLargest(String s) {
        int pos  = 0;
        char best;
        String ret = "";
        while (pos < s.length()) {
        best = s.charAt(pos);
        if(pos == s.length()-1) {
            ret += s.charAt(pos);
            break;
        }
        for(int i = pos+1; i < s.length();i++){
            if(s.charAt(i) > best) {
            best = s.charAt(i);
            pos  = i;
            }
        }
        ret += best;
        pos++;
        }
        return ret;     
    }
}

14092011 Python

PythonでBinary Indexed Tree

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

Binary Indexed Treeって面白いデータ構造だ。

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


このデータ構造を使ってバブルソートの交換回数を数えるんだけど、理屈がいまいちわからん。BITの示しているのが交換しなくていい組の数なのはわかるんだけど、なぜ左から順繰りにアペンドしていくのかがしっくりこない。

class Bit(object):
    def __init__(self,l):
        self.size = l
        self.bit = [0] * (self.size+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

    def __str__(self):
        return str(self.bit)

if __name__ == '__main__':

    a = [3,1,4,2]
    ans = 0
    bit = Bit(len(a))
    for i,v in enumerate(a):
        ans += i - bit.sum(v)
        bit.add(v,1)
        print "%d: ans=%d v=%d %s" % (i, ans, v, bit)

    print ans

実行するとこんな感じ

0: ans=0 v=3 [0, 0, 0, 1, 1]
1: ans=1 v=1 [0, 1, 1, 1, 2]
2: ans=1 v=4 [0, 1, 1, 1, 3]
3: ans=3 v=2 [0, 1, 2, 1, 4]
3

わかりやすい説明ないかなぁ。

13092011 Python

devquizのスライドパズル

Pythonで。

copyモジュールを使うと遅いのでコピーしないようにした。アルゴリズムは、壁を考慮したマンハッタン距離をつかったBFS枝刈り。狩りかたは探索時のベストスコアを覚えていてそれより閾値以下の経路をバシバシ切る。

キツすぎて経路が見つからない場合は閾値を一つ上げて再探索。一問当たりの制限時間を決めておいて時間の掛かり過ぎる問題はカット。

それからmultiprocessingモジュールのpmapをはじめてつかったけど、これは超便利ですね。なにも考えなくてもコアの数だけ速くなるし

これで、2.4Gのcore2 duoのmacbookで3600問解けた。

ファイルが2つにわかれているのは片方をCythonで高速化しようと奮闘した結果、速く出来なかったという。最初からクラスにしないで解くべきだったなぁと。

あと、debquizで触れたGoにすっかり魅了されましたね。静的型付けでコンパイルできる言語もそこそこできるようになっておきたいなぁ。

slidepuzzle.py

import time
from os import environ
DEBUG = environ.get('debug', False)

class SlidePuzzle(object):
    """slidepuzzle"""

    def __init__(self, width, height, initdata):
        self.width = width
        self.height = height
        self.data = [c for c in initdata]
        self.pos0 = self.find_pos0()
        self.valid = {}
        for vi,vc in enumerate('123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[:width*height-1]):
            self.valid[vc] = vi
        self.maze_score_table = self.maze_score_init()
        self.score = self.calc_score()

    def display(self):
        l = len(self.data)
        w = self.width
        d = self.data
        return "".join(["".join(d[i:(i+w if i+w < l else l) ])+'\n' for i in range(0,l,w)])[:-1]

    def calc_score(self):
        return self.maze_score()

    def can_move(self,direction,last_moved):
        if direction == 'U':
            if last_moved == 'D': return False
            return False if (self.pos0) / self.width == 0 or self.data[self.pos0-self.width] == '=' else True
        elif direction == 'D':
            if last_moved == 'U': return False
            return False if (self.pos0) / self.width == self.height-1 or self.data[self.pos0+self.width] == '=' else True
        elif direction == 'L':
            if last_moved == 'R': return False
            return False if self.pos0 % self.width == 0 or self.data[self.pos0-1] == '=' else True
        elif direction == 'R':
            if last_moved == 'L': return False
            return False if self.pos0 % self.width == self.width-1 or self.data[self.pos0+1] == '=' else True
        else:
            return False

    def next_pattern(self,last_moved):
        c = 0
        if last_moved != 'D':
            if (self.pos0) / self.width != 0 or self.data[self.pos0-self.width] != '=':
                c += 1
        if last_moved == 'U':
            if (self.pos0) / self.width != self.height-1 or self.data[self.pos0+self.width] != '=':
                c += 1
        if last_moved == 'R':
            if self.pos0 % self.width != 0 or self.data[self.pos0-1] != '=':
                c += 1
        if last_moved == 'L':
            if self.pos0 % self.width != self.width-1 or self.data[self.pos0+1] != '=':
                c += 1
        return c

    def move(self, direction):
        if direction == 'U':
            self.swap(self.pos0,self.pos0-self.width)
            self.pos0 = self.pos0 - self.width
        elif direction == 'D':
            self.swap(self.pos0,self.pos0+self.width)
            self.pos0 = self.pos0 + self.width
        elif direction == 'L':
            self.swap(self.pos0,self.pos0-1)
            self.pos0 = self.pos0 - 1
        elif direction == 'R':
            self.swap(self.pos0,self.pos0+1)
            self.pos0 = self.pos0 + 1

    def move_string(self, mstr):
        for m in mstr: self.move(m)

    def reverse_move(self, direction):
        if direction   == 'U': self.move('D')
        elif direction == 'D': self.move('U')
        elif direction == 'L': self.move('R')
        elif direction == 'R': self.move('L')

    def reverse_move_string(self, mstr):
        for m in mstr[::-1]: self.reverse_move(m)

    def find_pos0(self):
        return self.data.index('0')

    def swap(self, i, j):
         self.data[i], self.data[j] = self.data[j], self.data[i]

    def maze_score(self):
        """calculates sum of modified Manhattan distances"""
        cdef int manhattan_score = 0
        cdef int i, manhattan_dist

        for i,c in enumerate(self.data):
            if c != '=' and c != '0':
                dest = self.valid[c]
                if dest<i:
                    manhattan_dist = self.maze_score_table[dest][i]
                else:
                    manhattan_dist = self.maze_score_table[i][dest]
                manhattan_score += manhattan_dist
        return manhattan_score

    def maze_score_init(self):
        table = [[1000]*(self.width * self.height) for l in [1000]*(self.width * self.height)]
        for i,c in enumerate(self.data):
            if c != '=':
                if i%self.width-1 >= 0 and self.data[i-1] != '=':
                    table[i][i-1] = 1;table[i-1][i] = 1;
                if i%self.width+1 < self.width and self.data[i+1] != '=':
                    table[i][i+1] = 1; table[i+1][i] = 1
                if i-self.width-1 > 0 and self.data[i-self.width] != '=':
                    table[i][i-self.width] = 1; table[i-self.width][i] = 1
                if i+self.width < len(self.data) and self.data[i+self.width] != '=':
                    table[i][i+self.width] = 1; table[i+self.width][i] = 1
        search_path = []

        for i in range(len(self.data)):
            table[i][i] = 0

        for i in range(len(self.data)-1):
            for j in range(i+1,len(self.data)):
                if self.data[i] != '=' and self.data[j] != '=':
                    search_path.append((i,j))

        while len(search_path) > 0:
            s,g = search_path.pop(0)
            minimum_path = table[s][g]

            if not minimum_path < 1000:
                for m in range(len(self.data)):
                    mp = table[s][m] + table[m][g]
                    if mp < minimum_path:
                        table[s][g] = mp
                        table[g][s] = mp
                        minimum_path = mp
                    if not minimum_path < 1000:
                        search_path.append((s,g))
                        #print "%d,%d not found" % (s,g)
        return table

class SlidePuzzleSolver(object):
    """slidepuzzle solver"""

    def __init__(self,width,height,data,threashold=10,maxtime=10):
        self.puzzle = SlidePuzzle(width,height,data)
        self.candidates = ['']
        self.stats = {''.join(self.puzzle.data):1}
        self.backward_candidates = ['']
        self.backward_stats = {'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[:width*height-1]+'0':''}
        self.threashold = threashold
        self.maxtime = maxtime

    def solve(self):
        best = 100
        start = time.time()

        for rval in range(100):
            # start forward search 
            for cand in self.candidates:
                if time.time() - start > self.maxtime:
                    return ''
                self.puzzle.move_string(cand)
                last_moved = cand[-1] if len(cand) > 0 else ''
                for direction in ['U','D','L','R']:
                    if self.puzzle.can_move(direction,last_moved):
                        new_cand = cand + direction
                        self.puzzle.move(direction)
                        score = self.puzzle.calc_score()
                        stat = ''.join(self.puzzle.data)
                        if DEBUG: print self.puzzle.display(),'\n'
                        if score == 0: 
                            return new_cand
                        else:
                            if self.stats.get(stat,0) == 0:
                                self.stats[stat] = 1
                                if score < best: best = score
                                if self.puzzle.next_pattern(direction) == 1:
                                    self.candidates.insert(0,new_cand)
                                elif score < best + self.threashold + rval:
                                    self.candidates.append(new_cand)
                        self.puzzle.reverse_move(direction)
                self.puzzle.reverse_move_string(cand)
            # end forward search
        return ''

solve.py

import sys
from slidepuzzle import SlidePuzzleSolver
from multiprocessing import Pool

def answer (problem_t):
    problem_num, problem = problem_t
    prefix = "problem %d: (%s) " % (problem_num+1,problem)
    mylist = problem.split(',')
    width = int(mylist[0])
    height = int(mylist[1])
    data = mylist[2]

    solver = SlidePuzzleSolver(width, height, data,5,120)
    result = solver.solve()
    if len(result) == 0:
        sys.stderr.write(prefix + 'not found\n')
    else:
        sys.stderr.write(prefix + '!!! solved !!!\n')
    return result

class Calculate(object):
    def run(self, problems):
        p = Pool(2)
        return p.map(answer, enumerate(problems))

if __name__ == '__main__':
    with open("slidepuzzle.txt") as f:
        lim = [int(i) for i in f.readline()[:-1].split()]
        Llim,Rlim,Ulim,Dlim = lim[0], lim[1], lim[2], lim[3]
        Total_boards = int(f.readline()[:-1])
        problems = [l.rstrip() for l in f.readlines()]

    cl = Calculate()
    results = cl.run(problems)
    print 'solved: ', len([p for p in results if len(p) > 0])

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

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])
}