MM89 考えたこと
マラソン参加3回目、がっつり参加したのは初めてだけれど楽しかったです。
暫定 72.34点 15位 Python
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&pm=10967
全部Sにしたら100%になるよねーと思って上からSE以外をSにする。
38点
初期解(ランダム解)でなぜ迷路がほとんどできないのか考えてみる。
境界からスタートしてランダムに動いてもその場からあまり動かない。迷路の中心に向かう力がない。大きな迷路ができにくい。
ビジュアライザを無効なパスを表示するように変えてみる。
Uに突っ込んでる。Uを変えればよい。
くるっと回転して自分のパスに突っ込んでる。回転しなければよい。直進すればよい?やっぱりSが強い?
直進すれば迷路の中心に向かって迷路が大きくなり、回転して死ぬこともなくなる?
紙にいろいろ書いて思いつく。
LとRが交互に並ぶようなライン(間にSやEはあってもよい)はどこから進入しても下から入れば上へ、上から入れば下へ抜ける。蛇行しながら直進する。
このラインを下端から上端まで積めば下端から上端、上端から下端へ抜ける迷路がたくさんできる。
このLとRが交互になるような修正をX座標が小さい順にF個とる。
64点
ここでかなり迷走したので数多のソースが生まれそして死んでいった。
複数の迷路が密に重なっているのがよくないのではと思った。
複数の迷路で修正を共有しているのはメリットだけれど、マスを共有しているのはデメリットなのでトータル損してそう。もっと高効率な迷路をばらけさせたい。
LとRが交互になるような修正を全体にしたうえで有効な迷路を列挙する。
厳密に列挙すると指数時間になってしまうので、上左右の移動だけ、下左右の移動だけでできる迷路を列挙する。列挙漏れはEがからむときだけなので見なかったことにする。この制限でメモ化ができるようになってるはずなんだけど今自分の実装見るとしてない。あれ?
で、列挙した迷路をFを超えない範囲で近似スコアが最大になるように選択する組み合わせ問題になった。
最初DPしようとしたけどマスが共有されているのでできなんだ。
迷路ごとのマス数/修正数が大きい順にFを超えない範囲で選んでいく(貪欲)。
71点
選択した迷路をひとつのぞいて別の迷路を選択して近似スコアが上がれば採用(山登り)。
72点
焼きなまそうと思ったけどよくわからず。
おわり
その他
方針さえあってれば Python でも探索時間減るだけやし上位狙わなければへーきへーきと思ったけど全然きつい。終わる前提の処理が終わらない終わらない。配列使いまわしたり、boolの2次元配列を整数の1次元配列に圧縮したり、なくなく迷路集合カットするなどした。
LとRを交互にするというアイデアに固執しすぎた感。マラソン終わるまで現解法の発展が上位の解法だと信じて疑わなかった。反省。
EとEを優先的につなぐように修正してみたけど微増だったのでやめた。テストケースごとのスコアは大きく上下するのがたまにある感じでWHFに特徴がみられなかった。今思うとEの割合とかもっとよく見ればよかった。平均じゃなくてFが多いとか少ないとか個々のテストケース見るの大事。
結局乱数使わなかったんだけどこれでいいのか。
Python 240 行
from copy import deepcopy from itertools import compress, count, product, starmap from time import time class MazeFixing: def improve(self, maze, F): reverse = len(maze[0]) < len(maze) if reverse: maze = transpose(maze) else: maze = list(map(list, maze)) fixes = createFixes(maze) paths = createPaths(maze, F, fixes) pair = climb(maze, F, paths, *greed(maze, F, paths)) pair.fixed.i = -1 fixes = [(y, x, fixes[y][x]) for y in range(len(maze)) for x in range(len(maze[0])) if maze[y][x] is not '.' and pair.fixed.get()] if reverse: fixes = ((y, x, dest) for x, y, dest in fixes) return list(starmap('{} {} {}'.format, fixes)) def transpose(maze): return list(map(list, zip(*maze))) def createFixes(maze): fixes = [[''] * len(maze[0]) for _ in range(len(maze))] ux = -1 for y, line in enumerate(maze): for x, cell in enumerate(line): if cell in '.LRE': if ux >= 0: if left is cell is 'L': line[ux] = 'R' fixes[y][ux] = 'R' elif left is cell is 'R': line[ux] = 'L' fixes[y][ux] = 'L' else: line[ux] = 'S' fixes[y][ux] = 'S' ux = -1 left = cell elif cell is 'U': if ux >= 0: line[ux] = 'S' fixes[y][ux] = 'S' ux = x xs = [] for y, line in enumerate(maze): for x, cell in enumerate(line): if cell in '.E' or cell in 'LR' and xs and cell is not line[xs[0]]: for i in xs[1:-1:2]: line[i] = 'R' if line[i] is 'L' else 'L' fixes[y][i] = line[i] if xs and not len(xs) % 2: line[xs[-1]] = 'S' fixes[y][xs[-1]] = 'S' xs = [] if cell in 'LR': xs.append(x) return fixes def createPaths(maze, F, fixes): width = len(maze[0]) height = len(maze) paths = [] visited = [[False] * width for _ in range(height)] fixed = deepcopy(visited) for y, x, d in product(range(height), range(width), (1, 3)): if maze[y][x] is not '.' and maze[y + dy[d]][x + dx[d]] is '.': search(maze, fixes, visited, fixed, x, y, (d + 2) % 4, d) path = BoolsPair((width - 2) * (height - 2)) for i, j in product(range(height), range(width)): if maze[i][j] is not '.': path.append(visited[i][j], fixed[i][j]) visited[i][j] = False fixed[i][j] = False if any(path.fixed.a): paths.append(path) return paths def search(maze, fixes, visited, fixed, x, y, d, b): if maze[y][x] is '.': return d is (b + 2) % 4 for i in range(4) if maze[y][x] is 'E' else [ (d + 'SRUL'.index(maze[y][x])) % 4]: if not (i is b or i is (d + 2) % 4): visited[y][x] = search(maze, fixes, visited, fixed, x + dx[i], y + dy[i], i, b) or visited[y][x] if visited[y][x]: fixed[y][x] = bool(fixes[y][x]) return visited[y][x] def greed(maze, F, paths): src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2)) dest = deepcopy(src) mx = deepcopy(src) compressed = [True] * len(paths) while any(compressed): mx.visited.count = 0 mx.fixed.count = 1 for i, path in compress(enumerate(paths), compressed): dest.merge(src, path) if src.visited.count == dest.visited.count or dest.fixed.count > F: compressed[i] = None elif (mx.visited.count / mx.fixed.count < dest.visited.count / dest.fixed.count): mxI = i mx, dest = dest, mx if any(compressed): compressed[mxI] = False src, mx = mx, src return src, [c is False for c in compressed] def climb(maze, F, paths, mx, mxAdded): timer.limit = 8 while True: updated = False added = mxAdded[:] for i in compress(range(len(added)), added): if timer.elapses(): return mx added[i] = False src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2)) dest = deepcopy(src) for path in compress(paths, added): src.merge(src, path) for j, path in enumerate(paths): if not (i == j or added[j]): dest.merge(src, path) if (dest.fixed.count <= F and mx.visited.count < dest.visited.count): updated = True mx, dest = dest, mx mxAdded[i] = False mxAdded[j] = True added[i] = True if not updated: break return mx class BoolsPair: def __init__(self, n): self.visited = Bools(n) self.fixed = Bools(n) def append(self, visited, fixed): self.visited.append(visited) self.fixed.append(fixed) def merge(self, a, b): self.visited.merge(a.visited, b.visited) self.fixed.merge(a.fixed, b.fixed) def copy(self, a): self.visited.copy(a.visited) self.fixed.copy(a.fixed) class Bools: def __init__(self, n): self.a = [0] * ((n + 62) // 63) self.i = 0 self.count = 0 def append(self, v): self.a[self.i // 63] = self.a[self.i // 63] | v << self.i % 63 self.i += 1 def merge(self, a, b): self.count = 0 for i, a, b in zip(count(), a.a, b.a): self.a[i] = a | b self.count += bin(self.a[i]).count('1') def copy(self, a): self.count = a.count for i, a in enumerate(a.a): self.a[i] = a def get(self): self.i += 1 return self.a[self.i // 63] >> self.i % 63 & 1 class Timer: def __init__(self): self.start = time() def elapses(self): return time() - self.start > self.limit dx = 1, 0, -1, 0 dy = 0, 1, 0, -1 timer = Timer() # maze = [raw_input() for _ in range(int(raw_input()))] # F = int(raw_input()) # ret = MazeFixing().improve(maze, F) # print(len(ret)) # print('\n'.join(ret))
Laravel 5 のデバッグ出力
Laravel 5 でデバッグ出力する3つのやり方についてまとめる。
ログファイルに書きだす
2通りの書き方がある。
ヘルパー関数 logger(), info()
<?php Route::get('/', function() { $message = ['a' => 1, 'b' => 2, 'c' => 3]; logger($message); info($message); // logger()->notice($message, $context); // logger()->warning($message, $context); // logger()->error($message, $context); // logger()->critical($message, $context); // logger()->alert($message, $context); // logger()->emergency($message, $context); return 'OK'; });
storage/logs/laravel.log に書き出される。
[2015-07-31 13:40:35] local.DEBUG: array ( 'a' => 1, 'b' => 2, 'c' => 3, ) [2015-07-31 13:40:35] local.INFO: array ( 'a' => 1, 'b' => 2, 'c' => 3, )
配列ライクは var_export() で、 Jsonable なクラスインスタンスは JSON 文字列に内部で見やすく整形してくれる。なので、何も考えずに引数に渡してよい。
Log ファサード
<?php namespace App\Http\Controllers; use Log; // ... class MyController extends Controller { public function index() { $message = ['a' => 1, 'b' => 2, 'c' => 3]; Log::debug($message); Log::info($message); // Log::notice($message, $context); // Log::warning($message, $context); // Log::error($message, $context); // Log::critical($message, $context); // Log::alert($message, $context); // Log::emergency($message, $context); return 'OK'; } }
ヘルパー関数と Log ファサードのやってることはまったく同じ。ただ、 Log ファサードはファイルの先頭で use Log; しないといけなかったり、 use Log; できない php ファイルがある?のでヘルパー関数の logger() のほうが便利。グローバル関数は最強だな。
ブラウザに表示する var_export()
<?php Route::get('/', function() { $message = ['a' => 1, 'b' => 2, 'c' => 3]; echo '<pre>' . var_export($message, true) . '</pre>'; return 'OK'; });
Laravel と関係ない PHP おなじみのやり方。一応説明すると var_export() で見やすく整形して pre タグで改行を可視化している。
ブラウザにリッチに表示する dd()
<?php Route::get('/', function() { $message = view(); dd($message); return 'OK'; });
dump and die の略。上述の2つと違ってクラスインスタンスとか複雑なものも表示できる。 die と名のつく通りアプリケーションの実行を停止する( OK が表示されてないよね)。なんかすごい。
まとめ
logger($message, $context);
ログファイルに書きだすので残る。
echo '<pre>' . var_export($message, true) . '</pre>';
ブラウザに表示する。
dd($message);
ブラウザにリッチに表示する。クラスインスタンスとか複雑なものも表示できる。アプリケーションの実行を停止する。
以上です。それでは Laravel のよきデバッグライフを。
CoffeeScript と Phaser でゲームつくったよ!
ゲーム インビジゴースト - 見えざる敵の居所を探り、迎え撃て!
ソース hakomo/InvisibleGhost · GitHub
遊んでみてね。
ゲームフレームワーク Phaser を使っていて思ったことを書きたい。
Atom を設定した
Atom の正式版公開当初にさわって以来ごぶさただったのですが、最近話題をちらちら見るのでさわってみたらよかったので設定した。
Atom は主に CoffeeScript, Stylus, Slim, Markdown, メモを書くのに使うと思う。たまに Python, Ruby も。 Sublime からの乗り換え。
エディタはできるだけカスタマイズしないでデフォルトで使いたい人。
Settings
Settings で一般設定を、Packages でパッケージごとの設定が GUI でできる。
んで下記が GUI が出力したテキスト形式の設定。 CSON って言うらしい。 JSON の CoffeeScript 版だそうな、はじめて知った。まあ JSON から徹底的にタイプ量減らしましたみたいな。
GUI じゃないと無理って人も、テキストベースで管理したいって人も配慮しているこのかんじ好きよ。
それで私の Setting がこちら。
"*": welcome: showOnStartup: false editor: tabLength: 4 fontSize: 18 lineHeight: 1.25 scrollPastEnd: true fontFamily: "'Consolas' 'Meiryo'" invisibles: {} softWrap: true whitespace: ignoreWhitespaceOnCurrentLine: false "bracket-matcher": autocompleteBrackets: false "autocomplete-plus": {} core: {}
順番に見ていく。
tabLength: 4
どんな言語でもインデントはスペース4つ。らくちん。
fontSize: 18
lineHeight: 1.25
テキトーに自分の Sublime の設定に似せた。
scrollPastEnd: true
最下行以降もスクロールできるので最下行付近も画面中央で見れる。
fontFamily: "'Consolas' 'Meiryo'"
Windows だとおされな Atom の中で MS ゴシック さんがぶいぶいしちゃうのでなんとかする。
CSS の font-family プロパティに英字フォント、日本語フォントの順に指定すると英字は英字フォント、日本語は日本語フォントで表示されるというテクがある。そこで好みの等幅英字フォント、好みの日本語フォントの順にクォーテーションで囲んで指定する。この場合、( CSS font-family なら)囲まなくても動くと思うんだけど囲まないとなぜか動かない。
エディタのカスタマイズってエディタ固有の知識が多すぎて闇が深いなあと思っていたので、ブラウザベースの Atom なら闇を晴らしてくれるかと少し期待してみたけどだめだったよ。。。
softWrap: true
折り返す。
whitespace: ignoreWhitespaceOnCurrentLine: false
デフォルトでは保存時に行末のスペースを削除してくれるんだけどカーソル行のスペースは削除しない。おそらく、保存してから入力しようと思ったらスペースが削除されてスペースを打ち直すっていうのをなくす配慮だろうけど、行末にスペースを残しかねないので無効。
"bracket-matcher": autocompleteBrackets: false
( を入力したら ) を補完する。あらゆるエディタ・ IDE についてるけど邪魔だと思ったことこそあれ、便利だと思ったことはない。無効。
Your Keymap
ショートカットキーを変えられます。デフォルトが使いやすいのであまり変えていません。
'.platform-win32 atom-text-editor, .platform-linux atom-text-editor': 'f4': 'find-and-replace:replace-next' 'shift-f4': 'find-and-replace:replace-all'
置換を F4 に割り当てています。これは置換する、これはしない、これはする・・・とスッスッスーとやりたい。 F3 のスキップとあわせてできるようになります。 ctrl-enter で replace-all できるのですが、エディタ外の特殊なキーバインドのせいで ctrl-enter が押せないので割り当てています。
Your Stylesheet
Atom はブラウザベースなので外観を Stylesheet で記述する。ようするに、タグやクラス名とセレクターで要素を限定し、 CSS プロパティで色などを指定する。んで Atom は CSS の代替 LESS で記述する。いやあ Stylus 使いにはつらいぜ。
それで私の Stylesheet がこちら。
.tree-view { font-family: Meiryo; } atom-text-editor.is-focused::shadow .cursors .cursor { opacity: 1; } atom-text-editor::shadow .lines .line.cursor-line { background-color: transparent; }
順番に見ていく。
上述の記述だけでは MS ゴシック を根絶やすには不完全だったようで Tree View からこんにちは。
Tree View は等幅でなくてよいので Meiryo のみ指定。
.tree-view { font-family: Meiryo; }
それでもまだ Markdown Preview でこんにちはするし、他にもこんにちはするかもしれない。あとで直そう。。。
atom-text-editor.is-focused::shadow .cursors .cursor { opacity: 1; }
カーソルの点滅をなくす。
Blinking Cursor - Atom Discussion
URL 先を参考に改変。
atom-text-editor::shadow .lines .line.cursor-line { background-color: transparent; }
カーソル行のハイライトをなくす。
Where is the active line background color? - Atom Discussion
URL 先をコピペ。
カーソルの点滅とかカーソル行のハイライトって、カーソルを見失ったときに探しやすくするためですよね。カーソルが見つかっているのであれば、入力行に色がついて見づらいだけやし、周辺視野でチッカチッカする害悪だと思うんですよ。なので消します。
見失ったときは上キー押して下キー押せばカーソルが動いてすぐ見つかるので十分です。
Packages
あとから入れたパッケージ。設定も一通り見たがすべてデフォルト。
autocomplete-plus
デフォルトだと ctrl-space しないと補完候補がポップアップしないが、キー入力と同時にポップアップする。
autocomplete-snippets
補完候補にスニペットを含める。
japanese-wrap
日本語の折り返しを修正する。 Core Settings の Soft Wrap を有効にする必要がある。
language-slim
HTML の代替 Slim のシンタックスハイライトなど。
これとほぼ同じダウンロード数のパッケージに ruby-slim があったが ruby まわりでエラーを吐いた。 Slim のコンパイルは Node.js + gulp.js でやっていて Atom ではやらないので language-slim を採用した。
sort-lines
CSS のプロパティのような順番が(ほぼ)何でもよいときに、わかりやすい順番を考える時間が無駄なので無思考にソートする用。
Stylus
CSS の代替 Stylus のシンタックスハイライトなど。セレクター行で改行してもインデントしないのが Sublime に比べて使いづらい。
カスタマイズする上で役に立ちそうなもの
ctrl-,
Settings をすばやく開く。
alt-ctrl-i
Google Chrome でおなじみ Developer Tools を開く。
ctrl-shift-p
Command Palette を開く。すべてのコマンドを検索・実行できる。
ctrl-.
Keybinding Resolver を開く。開いた状態でキーを押すと、実行されたコマンドとコンテキストが表示される。
Command Palette と Keybinding Resolver を使うとショートカットキーの設定がはかどるかもしれない。
Menu -> Packages -> Timecop -> Show
起動にかかった時間が表示される。重いパッケージを無効化するときなどに。
Packages の各言語には Setting ボタンがないがクリックすると設定できる。戻る欲しい。
以上です。おつかれさまでした。
npm メモ
npm のコマンドを目的別にまとめています。 npm は gulp にしか使っていません。
コマンドにはエイリアスがたくさんあるので使いやすいものを選びましょう。
npm のコマンドについて調べる
npm-index
パッケージを探す
npm
install
プロジェクトにパッケージをインストール
$ npm install --save-dev package-name
パッケージをインストールし、 package.json
に書き出します。 package.json
を使うことで同じ環境構築が次から楽になります。
--save-dev
を指定すると開発するときに依存するパッケージとして書き出します。替わりに --save
を指定すると公開するときに依存するパッケージとして書き出します。例えばソースの圧縮のような開発するときにしか使わないものには --save-dev
、サーバサイドで使うものには --save
を指定します。
複数の package-name
をスペース区切りで指定してインストールすることもできます。
グローパルにパッケージをインストール
$ npm install -g package-name
-g
を指定するとグローバル、何も指定しないとプロジェクトという意味になります。使い分けは、端末から直接コマンドを叩くときはグローバル、プロジェクト内の js
から使うときはプロジェクトです。
プロジェクトが依存するパッケージをインストール
$ npm install
package.json
内のパッケージをすべてインストールします。 git clone
の直後などに実行します。
ls
プロジェクトにインストールされている一覧
$ npm ls --depth=0
直接インストールした一覧が表示されます。--depth=0
を指定しないと、直接インストールしたパッケージが依存する大量のパッケージが表示されてしまいます。
グローバルにインストールされている一覧
$ npm ls --depth=0 -g
uninstall
プロジェクトからパッケージをアンインストール
$ npm uninstall --save-dev package-name
グローバルからパッケージをアンインストール
$ npm uninstall -g package-name
update
プロジェクトのパッケージをアップデート
$ npm install -g npm-check-updates
パッケージをアップデートしても package.json
はアップデートされないようです。そのためコマンドをインストールします。
$ npm update
$ npm-check-updates -u
上記の2行のコマンドを実行すればパッケージと package.json
がアップデートされます。一行目はいらないかもしれません。
グローバルのパッケージをアップデート
$ npm update -g
completion, config
$ npm completion
補完が効くようです。 Windows では動かないので試していません。
$ npm config ...
npm の設定が変更できます。デフォルトで使っています。
Fit Win の新しいバージョンを公開しました!
ここでは技術的なことを書きます。 Fit Win の詳細は下記 URL をご覧ください。
Fit Win - ウィンドウを移動・サイズ変更するフリーソフト
開発言語は C#/Slim(HTML5)/Stylus(CSS3)/CoffeeScript(JavaScript) です。ただ本ソフトは Web アプリではありませんし通信もしません。デスクトップアプリなのです。C# のフォーム上に WebBrowser をのっけてその上で HTML5 アプリを動作させています。なぜそんなまわりくどいことをしたのかというと本ソフトがドラッグ&ドロップを多用したり、複雑な描画を行うリッチ GUI アプリだからです。実際 C# のみで書いた過去のバージョンに比べて、本バージョンのコード行数は3分の2に減っています!適切な言語選択の重要性を痛感しましたね。( XAML 使えよってツッコミが入りそうですが使ったことないんですよね。 CSS 並の表現力と jQuery 並の DOM 操作力はあるんでしょうか?)
IE12 で HTML5 たくさん実装されないかなー、でもって Windows 7 にもインストールできないかなー。技術的なことって何書いたらいいのかわからないのでコメントいただければ書くやもです。
最後に本ソフトの開発環境である HTML5/CSS3/JavaScript on C# WebBrowser のメリット・デメリットです。
メリット
- デスクトップアプリなのに HTML5/CSS3/JavaScript を使ったリッチ GUI アプリを作れる
- JavaScript でセキュリティ上不可能なことができる
デメリット
- 一般的ではなく、情報が少ない
- C# から JavaScript の関数を呼んだり、 JavaScript から C# のメソッドを呼んだりと見通しが悪い
- WebBrowser のデフォルトの挙動(ショートカットやコンテキストメニュー)の部分的な無効化がバッドノウハウのかたまりになってしまった