着手できる場所のチェックと石を取る処理を追加
ちゃんとテストしていない。
# -*- coding: utf-8 -*- import sys import codecs sys.stdout = codecs.getwriter('utf-8')(sys.stdout) class Untouchable(Exception): pass class Goban(object): invalid = 99 empty = 0 black = 1 white = -1 around_moves = ((1, 0), (-1, 0), (0, 1), (0, -1)) def __init__(self, size): self.size = size self.data = [ [ 0 for i in range(size) ] for j in range(size) ] def render(self, output=sys.stdout): for i, line in enumerate(self.data): for j, point in enumerate(line): if point == self.empty: output.write(self._empty_str(i, j)) elif point == self.black: output.write(u'●') else: output.write(u'○') output.write('\n') def get_opponent_color(self, color): return color * -1 def touch(self, x, y, color): if not self.touchable(x, y, color): raise Untouchable() self.data[y][x] = color gottens = set() opponent = self.get_opponent_color(color) for move_x, move_y in self.around_moves: next_x = x + move_x next_y = y + move_y if self.get_state(next_x, next_y) is not opponent: continue if not self.check_alive(next_x, next_y, opponent): self._get_stones(next_x, next_y, gottens) for gotten_x, gotten_y in gottens: self.data[gotten_y][gotten_x] = self.empty return len(gottens) def _get_stones(self, x, y, gottens): color = self.get_state(x, y) targets = [(x, y)] gottens.add((x, y)) target = targets.pop() while target is not None: x, y = target for move_x, move_y in self.around_moves: next_x = x + move_x next_y = y + move_y if self.get_state(next_x, next_y) is not color: continue if (next_x, next_y) not in gottens: targets.append((next_x, next_y)) gottens.add((next_x, next_y)) target = targets.pop() if targets else None def touchable(self, x, y, color): if self.get_state(x, y) is not self.empty: return False else: if not self.check_alive(x, y, color): return False return True def get_state(self, x, y): if x < 0 or self.size <= x or y < 0 or self.size <= y: return self.invalid return self.data[y][x] def check_alive(self, x, y, color): targets = [(x, y)] target = targets.pop() while target is not None: for move_x, move_y in self.around_moves: next_x = x + move_x next_y = y + move_y state = self.get_state(next_x, next_y) if state is self.empty: return True elif state is color: targets.append((next_y, next_y)) target = targets.pop() if targets else None return False def _empty_str(self, x, y): if x == 0: if y == 0: return u'┏' elif y == self.size - 1: return u'┓' else: return u'┯' elif x == self.size - 1: if y == 0: return u'┗' elif y == self.size - 1: return u'┛' else: return u'┷' else: if y == 0: return u'┠' elif y == self.size - 1: return u'┨' else: return u'┼' def test(): goban_size = 19 goban = Goban(goban_size) goban.touch(3, 3, Goban.black) goban.touch(15, 15, Goban.white) goban.touch(0, 1, Goban.black) goban.render() goban.touch(0, 0, Goban.white) goban.render() gotten = goban.touch(1, 0, Goban.black) goban.render() print gotten, 'got.' if __name__ == '__main__': test()
実行。
┏┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┓ ●┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼●┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼○┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┗┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┛ ○┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┓ ●┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼●┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼○┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┗┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┛ ┏●┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┯┓ ●┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼●┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼○┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┠┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┼┨ ┗┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┷┛ 1 got.
Pythonで碁盤を表す文字列を生成
なんでこんなものを書いてるか、の説明はあとで。
# -*- coding: utf-8 -*- import sys import codecs sys.stdout = codecs.getwriter('utf-8')(sys.stdout) class Goban(object): empty = 0 black = 1 white = 2 def __init__(self, size): self.size = size self.data = [ [ 0 for i in range(size) ] for j in range(size) ] def render(self, output=sys.stdout): for i, line in enumerate(self.data): for j, point in enumerate(line): if point == self.empty: output.write(self._empty_str(i, j)) elif point == self.black: output.write(u'●') else: output.write(u'○') output.write('\n') def touch(self, x, y, color): self.data[y][x] = color def _empty_str(self, x, y): if x == 0: if y == 0: return u'┏' elif y == self.size - 1: return u'┓' else: return u'┯' elif x == self.size - 1: if y == 0: return u'┗' elif y == self.size - 1: return u'┛' else: return u'┷' else: if y == 0: return u'┠' elif y == self.size - 1: return u'┨' else: return u'┼' def test(): goban_size = 19 goban = Goban(goban_size) goban.touch(4, 4, Goban.black) goban.touch(15, 15, Goban.white) goban.touch(0, 1, Goban.black) goban.render() if __name__ == '__main__': test()
TopCoder SRM 498
6回目のSRM参戦。
Div2 Easy: AdditionGame（Java）
はいはい。スピード勝負。
public class AdditionGame { public int getMaximumPoints(int A, int B, int C, int N) { int res = 0; for (int i = 0; i < N; i++) { int max = Math.max(Math.max(A, B), C); if (max >= 1) { res += max; if (max == A) A--; else if (max == B) B--; else if (max == C) C--; } } return res; } }
switch/case文を使おうとしたら定数じゃないとダメって怒られた。ふだん使わないから知らんかった。（Pythonにはswitch/case文がない）
Div2 Medium: FoxSequence（Java）
最初C#で書きかけてJavaで書き直すというアホなことをしてしまった。。。
比較的素直に書いていけばよさそうな問題ですが・・・
public class FoxSequence { public String isValid(int[] seq) { int diff = seq[1] - seq[0]; if (diff <= 0) return "NO"; int status = 1; for (int i = 2; i < seq.length; i++) { int newdiff = seq[i] - seq[i-1]; if (status == 1 || status == 4) { if (newdiff <= 0) { status++; } else if (newdiff != diff) { return "NO"; } } else if (status == 2 || status == 5) { if (newdiff >= 0) { status++; if (status == 3 && newdiff != 0) { status++; } } else if (newdiff != diff) { return "NO"; } } else if (status == 3) { if (newdiff != 0) { status++; } } diff = newdiff; } if (status != 5) return "NO"; return "YES"; } }
おそるおそる提出したところ、不安が的中してChallenge Phaseで被撃墜。
int seq = {1, 2, 2, 2, 3, 2};
のようなケースで落ちます。
条件式のミス。
追記: 他にも {1} や {1, 2, 3, 4, 5, 4, 3, 3, 3, 2, 1} の時がだめです。一行修正・二行追加。
Div2 Hard: NinePuzzle（Java）
めずらしく時間が余ったのでだめもとでHard問題にもチャレンジ。
んー、これって入れ替えとか考える必要あるのかなー？
こんな簡単なわけないから間違ってるだろうけど、一応出してみるか・・・。
public class NinePuzzle { public int getMinimumCost(String init, String goal) { int res = 0; char[] colors = {'R', 'G', 'B', 'Y'}; for (char color : colors) { int initnum = 0; int goalnum = 0; for (int i = 0; i < init.length(); i++) { if (init.charAt(i) == color) initnum++; if (goal.charAt(i) == color) goalnum++; } res += Math.abs(initnum - goalnum); } return res / 2; } }
なんと正解。746.08ptゲット！
結果
977.65ptで179位。
レーティングは859から947に回復し、緑色コーダーに復帰。
TopCoder SRM 496をC#で練習
参加できてなかったので本番のつもりで練習。
Div2 Medium: ColoredStrokes
using System; class ColoredStrokes { public int getLeast(string[] picture) { int res = 0; int width = picture[0].Length; int height = picture.Length; for (int i = 0; i < height; i++) { bool onHStroke = false; for (int j = 0; j < width; j++) { if (picture[i][j] == 'R' || picture[i][j] == 'G') { if (!onHStroke) { res++; onHStroke = true; } } else { onHStroke = false; } } } for (int i = 0; i < width; i++) { bool onVStroke = false; for (int j = 0; j < height; j++) { if (picture[j][i] == 'B' || picture[j][i] == 'G') { if (!onVStroke) { res++; onVStroke = true; } } else { onVStroke = false; } } } return res; } }
縦と横でそれぞれストローク数をカウントするだけ。
二重ループ一個で書けるかな・・・。
271.27ptでsubmitしてシステムテストもクリア。
SRM 497の回答をC#で書き直してみた
id:chokudai先生の真似してC#で参戦できないかなーと思案中。
Parallels上のWindows 7にVisual C# Expressを入れてみました。プロジェクト名がnamespaceになったり余計なusingが入るのって制御できないのかなー。
Div2 Easy: Filtering
using System; class Filtering { public int[] designFilter(int[] sizes, string outcome) { int max = int.MinValue; int min = int.MaxValue; for (int i = 0; i < sizes.Length; i++) { if (outcome[i] == 'A') { max = Math.Max(max, sizes[i]); min = Math.Min(min, sizes[i]); } } for (int i = 0; i < sizes.Length; i++) { if (outcome[i] == 'R' && min <= sizes[i] && sizes[i] <= max) { return new int[0]; } } int[] res = { min, max }; return res; } }
Div2 Medium: PermutationSignature
using System; class PermutationSignature { public int[] reconstruct(string signature) { int[] res = new int[signature.Length + 1]; int[] stack = new int[signature.Length + 1]; int stackpos = 0; int pos = 0; int cur = 1; stack[stackpos++] = cur++; for (int i = 0; i < signature.Length; i++) { if (signature[i] == 'I') { while (stackpos != 0) res[pos++] = stack[--stackpos]; } stack[stackpos++] = cur++; } while (stackpos != 0) res[pos++] = stack[--stackpos]; return res; } }
うむ
自分としてはきれいに書けて満足。クラスライブラリを全然知らないからスタックも配列で実装しました。
Hard問題にもそろそろ挑戦しようかな。
TopCoder SRM 497
コード貼るならはてなでしょってことで、ひさびさにこちらに書きます。
5回目のTopCoder挑戦です。これまでの記録はこちら。 http://www.topcoder.com/tc?module=MemberProfile&cr=22907785&tab=alg
Div2 Easy: Filtering
public class Filtering { public int[] designFilter(int[] sizes, String outcome) { int minA = Integer.MAX_VALUE; int maxA = -1; int minR = Integer.MAX_VALUE; int maxR = -1; char[] chars = outcome.toCharArray(); for (int i = 0; i < chars.length; i++) { char c = chars[i]; if (c == 'A') { minA = Math.min(minA, sizes[i]); maxA = Math.max(maxA, sizes[i]); } else { minR = Math.min(minR, sizes[i]); maxR = Math.max(maxA, sizes[i]); } } int[] ret = {minA, maxA}; if (minR != Integer.MAX_VALUE && minA < minR) { ret = new int[0]; } else if (maxR != -1 && maxR < maxA && minR < maxR ) { ret = new int[0]; } return ret; } }
Easyのわりに問題文長い。。理解に時間がかかった。
maxRの更新箇所でコピペの修正ミスがあり、Easyでは初のFailed。
そもそもRは最小値と最大値を取る必要なかった。
Div2 Medium: PermutationSignature
いい加減に解きたいMedium問題。
import java.util.Arrays; import java.util.List; import java.util.ArrayList; import java.util.Stack; public class PermutationSignature { public int[] reconstruct(String signature) { int[] ret = new int[signature.length()+1]; for (int i = 0; i < ret.length; i++) { ret[i] = i+1; } char[] chars = signature.toCharArray(); List<Integer> res = new ArrayList<Integer>(); Stack<Integer> stack = new Stack<Integer>(); stack.push(1); for (int i = 0; i < chars.length; i++) { if (chars[i] == 'I') { while (stack.size() != 0) { res.add(stack.pop()); } } stack.push(ret[i+1]); } while (stack.size() != 0) res.add(stack.pop()); for (int i = 0; i < ret.length; i++) { ret[i] = res.get(i).intValue(); } return ret; } }
境界条件ではまって提出が間に合わなかった。10分ほどオーバーして書き上げたのがこれ。
合ってると思うのですがいかに。
というわけで
初のEasy失敗でスコア0・・・。最悪の結果に終わり、レーティングは854まで落ちてしまいました。
次回から挽回です！
名前解決がパフォーマンスに与える影響
http://blog.miraclelinux.com/asianpen/2008/05/python-code-rea.html#more
でも実験されていますが、もう少し細かいケースで試してみました。
scope_test.py
def with_local(num): l = [] l_value = True for i in xrange(num): l.append(l_value) def with_nested(num): l = [] n_value = True def nested(num): for i in xrange(num): l.append(n_value) nested(num) m_value = True def with_module(num): l = [] for i in xrange(num): l.append(m_value) def with_builtin(num): l = [] for i in xrange(num): l.append(True) if __name__ == "__main__": import sys from timeit import Timer t = sys.argv[1] num = sys.argv[2] if t == "local": def_name = "with_local" elif t == "nested": def_name = "with_nested" elif t == "module": def_name = "with_module" elif t == "builtin": def_name = "with_builtin" t = Timer("%s(%s)" % (def_name, num), "from __main__ import %s" % def_name) print def_name, t.timeit(1)
手元のcoLinux(on ThinkPadX61 Core2 Duo 2GHz)で実行。まずは100万回。
[michisu@colinux] $ python scope_test.py local 1000000 [~/python-code-reading] with_local 0.941817998886 [michisu@colinux] $ python scope_test.py nested 1000000 [~/python-code-reading] with_nested 1.04100513458 [michisu@colinux] $ python scope_test.py module 1000000 [~/python-code-reading] with_module 1.03532505035 [michisu@colinux] $ python scope_test.py builtin 1000000 [~/python-code-reading] with_builtin 1.08331394196
1000万回。
[michisu@colinux] $ python scope_test.py local 10000000 [~/python-code-reading] with_local 9.48914504051 [michisu@colinux] $ python scope_test.py nested 10000000 [~/python-code-reading] with_nested 10.4752728939 [michisu@colinux] $ python scope_test.py module 10000000 [~/python-code-reading] with_module 10.4114220142 [michisu@colinux] $ python scope_test.py builtin 10000000 [~/python-code-reading] with_builtin 10.6834070683
ビルトイン型をそのまま使うとやはり少し遅い。
1000万回回しても1秒程度しか差が出ないので、Setのような汎用コレクションクラスのコードでもない限り、普段は気にしなくても良さそうだけど。（これをつねにやるぐらいならCを使えって話になる）
ある名前がコードブロック内で使われると、その名前を最も近傍から囲うようなスコープ (最内スコープ: nearest enclosing scope) を使って束縛の解決を行います。
http://www.python.jp/doc/2.4/ref/naming.html
ということで、最内スコープによる名前の解決がもっとも高速になり、順次外のスコープが使われるのでルックアップが遅くなると思われます。
上のケースではnestedがmoduleより常に少しだけ遅いのが面白いですが、この理由はよく分かりません。
追記。タイトル変更しました。「スコープの変数解決が」→「名前解決が」
追記2。地の文で回数の桁が間違ってたので直しました。
