唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

AtCoderのショートコード数で1位になってみた(コードゴルフ)

競技プログラミング atcoder

Competitive Programming （その2） Advent Calendar 2015の4日目の記事です

注意、ショートコーディング(コードゴルフ)のテクニックっぽい話はほとんど載っていません

ちょっと2ヶ月ぐらいAtCoderでショートコーディングをがんばってみました。楽しかったので頭の体操としておすすめです


7月に宇宙ツイッタラーXさんのAtCoder ProblemsにAtCoderの問題ごとの最短コードの獲得数のランキングが追加されました

kenkoooo.hatenablog.com

ショートコードを意識して書いているのは10人もいないっぽいので「結構簡単に上位には入れそう」と思って7月から9月の2ヶ月間ぐらいがんばってみました
最初は自分のショートコード数は1問しかなかったけど1位の人でも100問ぐらいしかなくて、1日がんばるだけで1桁順位になれました

AtCoderは他人の提出が見られるので、今の最短の他人のコードをなんとかして1バイト縮めることができれば最短になれます(マナー的にはよくないかも知れませんが(？)
他人のコードを見るのはかなり勉強になるので、最初は「自分でショートコーディングする」「最短あたりの人のコードを見る」「自分のコードを直す」って感じで進めてました
他人のコードを見ると知らないコマンドや関数、文法がたくさん見つかって面白かったです
テクニックをいろいろメモしていたら150行ぐらいになりました
はまってくると数バイト縮めるアイディアを思いつくだけで脳汁が出ます

Beginner ContestのA,B問題などは簡単なので電車通勤の合間にスマホで解くとかできて時間のない社会人にも優しいです(？)

一時はショートコード数140問まで行きました

最近はやってないのとPerlゴルフガチ勢の%20(x20)さんの参戦などで109問に減っています

f:id:sucrose:20151204000655j:plain

というわけでAtCoderで上位に入れない自分でも、ショートコーディングでは簡単に上位に入れたりして楽しかった、という話でした
本気でやれば1桁順位ぐらいはすぐにいけると思うのでぜひ試してみてください

ランキングができてかなりやる気が出たので宇宙ツイッタラーXさんに感謝！
AtCoder Problemsは他にもいろいろ機能がついていて便利です

おもしろいこととか微妙なハマりどころとか

どの言語がよいか

AtCoderではいろんな言語が使えますが、競技プログラミングなので高速な言語でないと解けない問題があり基本C++で解かれているのが多いです。難しい問題だと最短コードの提出でも最初に大量にマクロが定義されていたり短く書こうとしていないのがほとんどなので、改行を消したりするだけで最短が取れると思います
ショートコーディングをちゃんとしているのだとRuby、Perl、Pythonなどやシェルスクリプト(Bash)が強い感じ
自分は普段はPythonをメインで使っているのですが、ショートコーディングの為にRubyを勉強しました
Perlはかなり短くかけて強いのですが、慣れてないのでまだ他人のコードが読めません＞＜

AtCoder Problemsに載ってた最短コードを適当にクロールして言語別にカウントしました

f:id:sucrose:20151204233736p:plain

言語 ショートコード数
C++ 281
Ruby 236
C++11 149
Python 82
Perl 82
Bash 73
C 29
Text 21
Python3 15
Haskell 13
Java 6
Scala 2
C++14 2
PHP 1

クロールに使ったソースコード(pyqueryを入れないと動かない)

# -*- coding: utf-8 -*-

import pyquery
import time
import collections

if __name__ == '__main__':
    link_list = pyquery.PyQuery(url='http://kenkoooo.com/atcoder/')
    for elm in link_list.find('tr td:nth-child(7) a'):
        a = pyquery.PyQuery(elm)
        href = a.attr('href')
        
        if 'http' not in href:
            continue

        solution = pyquery.PyQuery(url=href)
        lang = solution.find('table:eq(0) tr:nth-child(4) td:nth-child(2)')
        print lang.text()
        
        time.sleep(1.5)

1行毎に言語が出力されるのでuniq -cでカウントして一部手で修正

sort temp.txt | awk '$0=$1' | sed '/^$/d' | uniq -c | sort -nr | awk '$0=$2" "$1'

ついでにpyqueryの使い方の記事を昔書いたので貼っておくsucrose.hatenablog.com

見ていて一番おもしろかったコード

AtCoder Regular ContestのD問題を3バイトで通すSubmissionです
Submission #476526 - AtCoder Regular Contest 026 | AtCoder

インタプリタやコンパイラのバージョンが古い問題と新しい問題で違う

例えば古い問題だとRuby 1.9、新しい問題だとRuby 2.1なのでたまにコードの動作が違って動かないことがあります

改行が2バイトになるか1バイトになるか


普通にブラウザから提出すると改行が2バイトになる(環境による？)ので手元で改行が1バイトのファイルを作って下記のツールで提出しましたshindolog.hatenablog.com

変な入力

古い問題だと入力の改行などがおかしい場合がある

簡単な問題は正解のチェックがゆるい

A問題などは、題意を満たさないコードでもACになることがあるので、これを利用すると短く書けたりします