2019-04-24

Google Code Jam 2019のインタラクティブ問題を解くときのメモ

Google Code Jam でインタラクティブ問題が初登場したのはリニューアル後の2018年。2019年にも引き続きインタラクティブ問題が出題されたのだけれど、ローカルでのデバッグ用にGoogleが提供するデバッグツールの使い方が2018年から変わっていたので、その使い方を忘れないようにメモしておきます。

準備

まず、手元にPython環境を用意します。手元で動かす限りPython 2でもPython 3でもどちらでもよいようですが、今ならPython 3の一択でしょう。

次に、interactive_runner.pyとtesting_tool.py、2種類のデバッグツールを、問題文に付記されたリンクからダウンロードします。このうち、interactive_runner.py はインタラクティブ問題に共通するスクリプトで、testing_tool.pyはその問題に特有のスクリプトです。

注：Google Code Jam 2020では testing_tool.py から local_testing_tool.py という名前に変わりました。名前以外は今も変わっていないと思います。

実装

次に、問題を解くスクリプトを実装します。例えば、Google Code Jam 2019 Round 1Aで出題された Golf Gophers のSmallを解くC++のコードを gist に示します。

実装には以下のことに気をつける必要があります。

標準出力したあとは必ずflushする。
- これをしないとツールが待ち状態になってTLEしてしまいます。
- C++でのflushは、標準出力のあとに毎回必ず cout << flush; とすればよいです。
- Python 3でのflushは、print('answer', flush=True) などとflush=Trueをprintに加えればよいです。もしくは、以下のようなprint2関数を定義しておき、print2('answer')などとprintの代わりにprint2を使うようにする手もあります。

def print2(*args, **kwargs):
    print(*args, **kwargs)
    sys.stdout.flush()

デバッグプリントは標準エラー出力で行う。
問題文の指示に従った入出力を行う。
- 例えば、 Golf Gophers の場合、解答を出力したあとにその結果が正しいか否かをverdictで受け取り、これが-1だったらすみやかにプログラムを終了させねばなりません。そうしないとデバッグツールがずっと待ち状態になってしまいます。

C++のようなコンパイルを要する言語で実装した場合は実行ファイルを生成しておきます。ここでは実行ファイルをa.outとします。

ツールの実行

C/C++にて実行ファイルa.outを生成した場合、以下のようにツールを実行します。

$ python interactive_runner.py python testing_tool.py 0 -- ./a.out

Pythonにてsolve.pyという名前のスクリプトファイルを作成した場合、以下のようにツールを実行します。

$ python interactive_runner.py python testing_tool.py 0 -- python solve.py

(solve.pyに実行権限をつけている場合)
$ python interactive_runner.py python testing_tool.py 0 -- ./solve.py

ここで、第3引数にある'0'はSmall用のテストケースを、'1'はLarge用のテストケースを使うことを意味します。テストケースはtesting_tool.pyに埋め込まれているので自由に改変可能ですが、問題により埋め込み方は異なるので読み解きが必要です。たとえば

Google Code Jam 2019 Round 1Aの Golf Gophers であれば以下の部分を修正する必要がありました。

CASES = ([1, 2, 3],
         [1, 2, 3]) # fill in your own cases
QS = (365, 7)

Google Code Jam 2019 Qual DのDat Baeであれば以下の部分を修正する必要がありました。

def getTestCases(test_number):
  F = (10, 5)[test_number]
  # You can edit or add your own test cases here.
  cases = [Case([1, 2, 3], 4, F), Case([2, 3, 5], 6, F), Case([1000], 1024, F)]
  return cases

ツールの実行結果の見方

無事正答を出すプログラムで上記ツールを実行すると以下のように表示されるはずです。

Judge return code: 0
Judge standard error:
Solution return code: 0
Solution standard error:
(標準エラー出力の結果がここにまとめて表示される)

エラーがある場合は以下のようにどのテストケースで落ちたかが表示されます。

Judge return code: 1
Judge standard error: Case #1 (1) failed: Wrong guess: 3. Expected: 1.

Solution return code: 0
Solution standard error:
(標準エラー出力の結果がここにまとめて表示される)

参考URL

インタラクティブに関する公式FAQ
診断人さんの連ツイート
- GCJ インタラクティブ問題でどハマリしたので、まとめ。
  ● テスターツールは2つある。１つはGCJ共通用・１つは問題別。
  ● python interactive_runner.py python testing_tool.py 1 -- ./a.out のように使う。
  ● デバッグ出力はcerrのようにエラー出力で。
  — nico_shindannin（診断人） (@nico_shindannin) 2019年4月7日

2019-03-30

中綴じ小冊子の自作メモ

others

中綴じ小冊子を自作するために調べた簡単なメモです。

セブンイレブン

セブン‐イレブンのマルチコピー機で同人活動をもっと手軽に・もっと楽しく！にある「中とじ冊子」に従うと作成できます。

ホッチキスは自分で行う必要がある
用紙サイズの指定に注意。製本後A4になる本を作りたい場合、A3を選ぶ必要がある。
- 詳しくは 3ステップでカンタン！コピー本作り | セブン‐イレブンのマルチコピー機で同人活動をもっと手軽に・もっと楽しく！を参照

kinko's

以下の2種類の方法があるようです。

いちど印刷をして、印刷した紙をスキャンしながら中綴じ製本
- 同人誌（コピー本）の印刷・製本 | コピー・ポスター・名刺印刷・製本のキンコーズ・ジャパンにある動画に従う。結構ややこしい
- いちど紙を経由するので画質が劣化する
- 自動でホッチキスしてくれる
有料でPCを借り、PCから印刷
- こちらは紙を経由しないので画質は劣化しない。ただし試してません

2019-03-04

Pythonにてリストの最後の要素を消すにはdelかpop()を使う

python

Pythonにて長さ100000のリスト arr があるとします。このリストの末尾を削除するとき

arr = arr[:-1]

とする方法は非常に遅いので要注意です。arr[:-1]により新規にリストが作成されてしまうのが原因です。ついカジュアルにこのような書き方をしてしまいがちなので注意が必要です。

上記方法に比べ、

del arr[-1]

や

arr.pop(-1)

とする方法だと1000倍ほど高速です。

検証用コードを以下に示します。

import time


ARRAY_SIZE = 100000
REPEAT_NUM = 1000


def func1():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        arr = arr[:-1]
        arr.append(0)


def func2():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        del arr[-1]
        arr.append(0)


def func3():
    arr = [0] * ARRAY_SIZE
    for i in range(REPEAT_NUM):
        arr.pop(-1)  # pop()の戻り値(指定したindexの値)はここでは使っていない
        arr.append(0)


def main():
    s = time.time()
    func1()
    print("func1() time:", time.time() - s)

    s = time.time()
    func2()
    print("func2() time:", time.time() - s)

    s = time.time()
    func3()
    print("func3() time:", time.time() - s)


main()

実行例は以下です。

$ python3 tmp.py
func1() time: 1.9272332191467285
func2() time: 0.0010654926300048828
func3() time: 0.0011544227600097656

2019-02-01

Windows 10でディスクを入れるとVLCが起動するのを防ぐ

Windows

Windows 10でトレイにCDを入れるとVLCが自動起動して再生が始まってしまう現象に困っていました。

以下の手順により、自動起動を防ぐことができるようになりました。

Explorerを起動
光学ドライブを右クリックし、「自動再生を開く」を選択
「何もしない」を選択

2019-01-11

kaggle Traveling Santa 2018 参加記

kaggle

kaggleの最適化コンペ "Traveling Santa 2018" にソロで参加しました。結果は1874チーム中328位。着手したのが2018/12/22と遅く、冬休みはまるまる何もできず。かけた時間がいくら何でも少なすぎました。スコアが平凡であまり価値はありませんが、記録としてやったことをメモしておきます。

問題概要

2次元座標上に197769個の都市が与えられる。都市には0から197768までの番号が付いている。0から始まりすべての都市を１つずつ通る経路のうち、「経路の総距離」と「ペナルティ」の和からなるスコアが小さくなるような経路を見つける。

ここで、ペナルティは、経路を構成する都市のうち10個おきに発生しうる。もしその都市の番号が素数ならペナルティなし、素数でないなら、その都市と次の都市との間の距離に0.1をかけた値がペナルティとなる。正確な理解のためには https://www.kaggle.com/seshadrikolluri/understanding-the-problem-and-some-sample-paths を参照すること。

初期検討 - 自力実装

都市番号順に並べるだけの愚直解で 446884407.52。スコア計算が正しくできていることを確認。

初期解を求める方法を2つ実装。

1つ目はNearest Neighbor法。都市0から始めて、未使用の都市のうちもっとも近い都市を繋いでいく方法。これでスコアは1812602.18点。

2つ目は挿入法。都市0→都市1→都市0と戻る最小構成の経路を最初に作成。総距離の増加長をもっとも短くなる場所を選んで都市2, 都市3, ...を順に挿入していく。スコアを記録し忘れたがNN法よりはよかったはず。

当初は、これらで得られる経路を初期解として、後述する経路組み換えを行いスコア改善を狙った。焼きなましも実装した。しかしスコアの改善に行き詰まり、1652066.12点が限界。

Concordeの導入

カーネル https://www.kaggle.com/blacksix/concorde-for-5-min を実行。これは巡回セールスマン問題のソルバであるConcordeを実行するというもの。わずか5分で1518313.05点が出て衝撃を受ける。これで603位相当。

Concordeは商用利用不可とあったので使って良いのか不安だったが、https://www.kaggle.com/c/traveling-santa-2018-prime-paths/discussion/72767 を読むとConcordeを使ってよいことがわかる。そこで今後はConcordeの解を初期解として使っていくことにする。

経路組み換えの実装

Concordeで得られる経路を初期解とする。これに以下の経路組み換えを行い、スコアの低減を目指した。

2都市のスワップ
1都市を経路から削除し他の場所に挿入
経路の一部分をreverse

スコアを高速に計算できるように、「経路の総距離」と「ペナルティ」とを分けて持つ工夫をした。上記のどの経路組み換えを行っても「経路の総距離」は一瞬で計算できる。「ペナルティ」は残念ながら再計算が必要だが、それでも最悪で全都市の1/10について再計算すればよい。

また、例えば2都市を入れ替えるとき、遠くにある2都市を入れ替えても意味がない。そこで、各都市についてその近傍の都市をN個（N=10, のちに20) 持っておくようにした。これによりスコアが改善する可能性がある経路組み換えだけを実行できる。

Concordeの初期解に対して上記の経路組み換えを適用して山登りすることで、130ポイントほどスコアが向上することを確認できた。

本当は上記以外にもより複雑な経路組み換え法 (3-optなど) を実装したかったのだが、餅とおせちを食べるのに忙しくなり進捗がなくなる。その間に次々と激強カーネルが投稿された影響で順位が大幅に下がっていることに気付く。これらの激強カーネルの結果を初期解として、上記経路組み換えを行って少しだけスコア改善したものを投稿、というしょうもないことを片手間でしばらくやった。スコア改善に寄与したのは上記の方法のうち2と3だけだったように思う。スコア改善とはいっても改善幅はほんのわずかで、行き詰まりを感じる。

そこで焼きなましを導入してスコア改善を図ったが、スコアが低下したまま向上してくれず、全然うまくいかなかった。

セグメント単位の焼きなまし

終了日前日、経路を適当な長さ（100程度）のセグメントに分割し、セグメント単位で焼きなましを行うことを思いつく。ハイパーパラメータの調節をする暇は全然なかったし、一晩しか回せなかったので全セグメントを舐めきることもできなかったのだが、それでも効果はあった。終了直前に投稿されたカーネルのスコア1515564.01から、1515562.86まで改善。だがここで時間切れ。コンペ終了後も12時間ほど動かしたら1515561.30になったことからまだ少しはポテンシャルがあった。もっと早くこの方針に辿りつくべきだった。とはいえブロンズ圏内である1515493.13までたどり着くためにはこれだけでは足りなかったと思われる。

反省点

他人のカーネルを使わせてもらうばかりで中をほとんど読まなかった。PythonのNumbaを使って高速計算したり、C++のコードを文字列としてファイル保存・コンパイルすることでC++のコードを動かしたり、Concordeのソースを持ってきてビルドして実行したりといった技が詰まっていたので後でも勉強したい。
久しぶりにC++を書くと経路組み換え時のスコア計算がバグだらけでデバッグが大変だった。数十都市からなるミニデータでデバッグするのは有用だったのでもっと簡単にデータを切り替えられるようにしたい。
経路を長さ10程度のセグメントに区切って、全経路順を生成してスコア最小のパスを選ぶ実装は簡単なのでやっておくべきだった。

2018-12-29

"WslRegisterDistribution failed with error"への対応法（追記あり）

Windows

Windows 10にてwindows subsystem for linuxを利用したUbuntu 16.04を立ち上げると、以下のようなエラーが出て起動に失敗しました。（エラーコードの部分は0x800703faです）

Installing, this may take a few minutes...
WslRegisterDistribution failed with error: 0xXXXXXXXX
Error: 0xXXXXXXXX The parameter is incorrect.
Press any key to continue...

心当たりがあるとすれば、前回の起動時にsudo apt-get update && sudo apt-get upgradeしたときに、途中でエラーが出て失敗したのでCtrl - Cでkillしたことです。

How to resolve 'WslRegisterDistribution failed with error: - Microsoft Community にあるように以下のことをすると無事起動できるようになりました。

Windows Powershellを起動
bash と打ちEnter
sudo apt-get update と打ちEnter

元回答とは異なり、自分の場合はsudo apt-get updateまでで大丈夫でした。

(2018/12/30追記) 後日、Windowsの再起動後に、上記と同じ"WslRegisterDistribution failed with error"が出ました。上記の対応法に則り、bashと打ちEnterをおしたところ、以下のエラーメッセージとともに失敗しました。

> bash
Windows Subsystem for Linux には、ディストリビューションがインストールされていません。
ディストリビューションは Microsoft Store にアクセスしてインストールすることができます:
https://aka.ms/wslstore
続行するには何かキーを押してください...

今度は以下の対応法をとることで再度Ubuntuが復活しました。

「Windowsの機能の有効化または無効化」を開く
- Explorerに「コントロールパネル\プログラム\プログラムと機能」と入力して、左側のペインから選ぶと簡単
"Windows Subsystem for Linux" にチェックが付いているはずなので、チェックを外してWindowsを再起動
再度 "Windows Subsystem for Linux" にチェックを付けてWindowsを再起動

2018-12-22

Visual Studio Codeで等幅フォントを使う

vscode

Visual Studio Codeはデフォルトだと日本語が等幅で表示されません。

f:id:minus9d:20181222110013p:plain

そこで以下の手順により、日本語がある場合でも等幅で表示されるようにしました。

公式ページから Myrica.ttc をダウンロードし、インストール
- 半角文字と全角文字の横幅の比が 1:2 なことからこのフォントを選定。
- 他にも等幅フォント比較：プログラミング用 - Qiita で紹介されているフォントが使えそう
Visual Studio CodeでCtrl + ,して設定を呼び出し、"font family"の欄に'Myrica M'を追加

その結果、以下のようにいい感じに文字が表示されるようになりました。

f:id:minus9d:20181222110659p:plain

(2019/5/9追記) 最新のWindows 10にバンドルされているBIZ UDフォント（モリサワ、「BIZ UDフォント」の「Windows 10 October 2018 Update」採用を正式発表 - 窓の杜）を使うと、フォントのインストール不要で等幅フォントが使えます。"font family"の欄に'BIZ UDゴシック' と書けばOKです。

このフォントの表示例を以下に示します。

f:id:minus9d:20190509230144p:plain