19092011 sake
いけたにさんから。
末廣は福島のお酒。かなり美味い。それから神渡は経営が変わる前の神渡。H7BYくらいだったかな。優しい味わいですね。
相模灘は酒のいわせで購入。ここのお酒はしっかり系ですね。グビグビ飲んだらすぐに空いたような？
今飲んでるのが先週末にコメヤスさんで購入した久礼の山間米。これもしっかり系で味わい深い。個人的にはさらっとしているのよりはじっくり旨い日本酒がすきなので、こういうタイプは好きですね。
19092011 javascript HTML5
HTML5 CANVAS chapter 2
Shapeの扱い方全般。グラデーションのかけかたや、影の落とし方を覚えた。それからsaveとリストアが何をしているのかとか。
HTML5 Canvas: Native Interactivity and Animation for the WebSteve Fulton
Oreilly & Associates Inc / 2922円 ( 2011-05-13 )
Express+jade+coffeeで書いたのはGitHubにあげている。
18092011 javascript HTML5
HTML5 CANVAS chapter 1
文字当てクイズをCanvasで。コードはGitHubにおいた。
HTML5 Canvas: Native Interactivity and Animation for the WebSteve Fulton
Oreilly & Associates Inc / 2922円 ( 2011-05-13 )
17092011 javascript
javascript読書会終了、来月からはHTML5読書会
JGPの最終話はJSLintの話
JavaScript: The Good Parts ―「良いパーツ」によるベストプラクティスPythonにはPEP8、PerlにはPBPそしてjavascriptにはJSLint
綺麗なコードは好きですか？YES
そんな感じで。
時間が余ったので、LTっぽい話も。みんなネタ持ってんので、時間が余ってもそれはそれで有意義。
Project Euler @ksmakoto
もうすぐ100問超えなのか、すごいな。
CoffeeScript @kzfm
CoffeeScriptを使うことでJGPで指摘されているようなルールは結構解決すると思う。関数の最初で全ての変数宣言してくれるし、同値演算子もわかりやすいし。
ただ、デバッグはしにくいよね。
Windows8 @ishisaka
Windows8の起動はやい。うちのWinはXPで止まっているが「いいじゃん」って思った。あとjavascriptでデスクトップアプリの開発ができるらしい。
Soundation @yoshinabu
Chuckに続き、またも音ネタ。
さらにかぶせた。
次回からはHTML5の読書会になり、初回は10/29@三島の予定ですが、ラッキーなことに当日は三島バルが開催されるので、読書後、飲み歩きという楽しみが待っていますね。
HTML5＆CSS3実践入門 最新Web標準を使いこなす (The Pragmatic Programmers)ブライアンP.ホーガン
インプレスジャパン / 2940円 ( 2011-07-08 )
16092011 javascript coffeescript
HTML5 Canvasを読み始めた
600ページ超の熱い本だが、一通りきちんとコードを追いかけようと。
HTML5 Canvas: Native Interactivity and Animation for the WebSteve Fulton
Oreilly & Associates Inc / 2922円 ( 2011-05-13 )
ただ写経するだけではつまらないので、coffeescriptで書いていくことにする。
class Debugger log: (message) -> try console.log(message) catch exception return canvasSupport = -> Modernizr.canvas canvasApp = -> return if !canvasSupport() theCanvas = document.getElementById("canvasOne") context = theCanvas.getContext("2d") d.log("Drawing Canvas") drawScreen = -> context.fillStyle = "#ffffaa" context.fillRect(0, 0, 500, 300) context.fillStyle = "#000000" context.font = "20px _sans" context.textBaseline = "top" context.fillText("Hello World!", 195, 80) context.strokeStyle = "#000000" context.strokeRect(5, 5, 490, 290) drawScreen() d = new Debugger canvasApp()
Express+jade+CoffeeScriptという構成で書いてみている。 コードはGitHubに置いてある。
16092011 Scala
部分関数でFizzBuzz
部分関数って離散数学とかの集合論をやると理解しやすいよなぁと。
離散数学への招待〈上〉ScalaのPartialFunctionを使って。
object FizzBuzz { val PFizz:PartialFunction[Int,String] = { case n if n%3==0 => "Fizz" } val PBuzz:PartialFunction[Int,String] = { case n if n%5==0 => "Buzz" } val PFizzBuzz:PartialFunction[Int,String] = { case n if n%15==0 => "FizzBuzz" } val PInt:PartialFunction[Int,String] = {case n => n.toString} val FizzBuzz = PFizzBuzz orElse PBuzz orElse PFizz orElse PInt def main(arg:Array[String]) = { println((1 to 30).toList.map(FizzBuzz(_))) } }
Scalaはコップ本よりもこっちのほうが好みかな
Scalaプログラミング入門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)))
これでそこそこ便利になったが、もうちょっとカイゼンする余地はあるんだろうなぁ。
Emacsテクニックバイブル ～作業効率をカイゼンする200の技～おまけ
静岡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って面白いデータ構造だ。
プログラミングコンテストチャレンジブックこのデータ構造を使ってバブルソートの交換回数を数えるんだけど、理屈がいまいちわからん。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])