読者です 読者をやめる 読者になる 読者になる

ICFPC 2016にチーム「試運転」で参加しました

JavaScript

ICFP Programming Contest 2016: Official Site: Task Description

ICFPC初参加です。

チームメンバー

チーム名「試運転」でNAISTの学生とNAISTの学生予備軍で参加しました。

やったこと

問題文を訳した

Google ドライブに問題文を貼り付けて並列に翻訳しました。

f:id:kujira16:20160808235557p:plain

自動提出ツールを書いた

Pythonで書きました。subprocess.check_output でソルバーと通信して,解答を requests.post で送信するだけです。

ビジュアライザを書いた

https://arosh.github.io/icfpc2016/web/index.html

入力を可視化するためのビジュアライザを作りました。

TypeScriptとD3.jsで書いています。

以下の入力を貼り付けてみてください。

1
4
0,0
1,0
1/2,1/2
0,1/2
5
0,0 1,0
1,0 1/2,1/2
1/2,1/2 0,1/2
0,1/2 0,0
0,0 1/2,1/2

提出状況確認ページを書いた

https://arosh.github.io/icfpc2016/web/result.html

今のソルバーで解けていない問題を確認したりするためのページを作りました。

TypeScript, D3.js, React, react-routerで書きました。

ソルバーを書いた?

幾何パートが難しくて,折り方を探索するパートまで進めませんでした。進捗ダメです。

結果

ソルバーの進捗ダメです。

反省

ぼく一人はソルバー開発にはほとんど貢献せずに,JavaScriptでビジュアライザを作って遊んでいるだけだった気がする。

npmで検索してみると,以下のようにJavaScriptで多倍長の分数を扱うライブラリもあるようだったので,問題を人力で解くのを補助するツールをJavaScriptで開発していたほうがチームに貢献できていたかも。

実装上の知見

データベース

TinyDBというライブラリを使って1つのJSONファイルにデータをすべて格納しようとしてみました。簡単に使えるのでデータ量が小さいうちは便利ですが,JSONファイルが数MBになってきたあたりでJSONファイルを開くだけで重くなってきてしまって残念です。数MBを超えるくらいの容量になることが予想できるならSQLiteかMongoDBを使うほうが良いでしょう。

Welcome to TinyDB! — TinyDB 3.2.1 documentation

JavaScript

Webサーバを用意するのを忘れていたので,提出状況確認ページはReact, react-routerを使ってSPAにしてみました。react-routerがバージョンによってAPIが変わりすぎなこと以外は良かったです。

https://github.com/reactjs/react-router/tree/master/upgrade-guides

ToDo

  • 非凸の多角形と非凸の多角形の包含関係
  • 非凸の多角形の三角形分割
  • 双対グラフ

他のメンバーの参加記

pakapa104.hatenablog.com