PythonでStackOverflowのAPIを叩く

表題の件ですが、大した事は無いのですがバージョンが変わってちょっと調べるのに手間がかかったので書いておきます。正確にはStackOverflow単独のAPIは無くてStackExchangeのAPIです。ちなみに先ほどの記事はStackOverflowのAPIを弄っていて見つけました。

Continue reading “PythonでStackOverflowのAPIを叩く”

TOC13の1Bの2問目(EllysFigurines)

久々にTopCoderのアルゴリズムに参加したんですが、3問中でEasyのみしか解けなくて生きるのが辛いです。終わってからもMediumの問題が中々理解出来なかったので書いて覚えるメソッドです。問題の原文はこれです。

要はランダムで駒が置かれてる15×15以内のサイズのオセロ版みたいなのが与えられて、一回の操作でR行分かC列分の駒を消せる時、全部の駒を消すのに必要な操作回数を回答するというもの。

解いている時は2^15が途方も無い数だと言う気がしていて、全件走査はキツいから、DPで解くはずと思い込んでしまって全く手が動きませんでした。その後正解の方々のコードをチラチラ見ながら書いたのが以下のコードです。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <limits>
#include <algorithm>

using namespace std;

class EllysFigurines {
public:
    int getMoves(vector <string> board, int R, int C) {
        int ans = numeric_limits<int>::max();

        int H = board.size();
        int W = board[0].length();

        int rows[16] = {};
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                if (board[r][c] != '.') {
                    rows[r] |= (1 << c);
                }
            }
        }

		// ここから全件走査
        int max = 1 << W;
        for (int mask = 0; mask < max; mask++) {
            int cnt = 0;
            for (int i = 0; i < W; i++) {
                if ((1<<i) & mask) {
                    cnt++;
                    i += C - 1;
                }
            }
            for (int i = 0; i < H; i++) {
                if (rows[i] & ~mask) {
                    cnt++;
                    i += R - 1;
                }
            }
            ans = min(ans, cnt);
        }

        return ans;
    }
};

最初何をしてるのか分からなかったのですが、ビットマスク作って全件走査しています。個々のビットマスクがスウィープする行の組合せを表現していて、行の組合せが決まると列の組合せが一意に決まるんですね。
行の組合せをビットマスクで表現するというのが競技プログラミング特有な感じがしますね。

今週の水曜日にSRMがあるようなので、次はもうちょっと頑張りたいです。

PyPIモジュールのPython3対応状況を調べた

昨日Python3について少し調べたと書きましたが、ぶっちゃけ文法とかビルトインのライブラリ差異は大した事無くて、PyPIモジュールがどれだけ3に対応しているかどうかが、Python3使うかどうかの判断で一番重要だと考えられます。

それで実際のところどうなの?というのでPyPI RankingにPython3の対応状況を表示するようにしました。まぁ一度ざっくり眺めておいても損は無いと思いますが、それだけだと寂しいので少し集計した結果を載せておきます。

Continue reading “PyPIモジュールのPython3対応状況を調べた”

いまさらPython 3

今まで全然追いかけてなかったのですが、僕が過去に書いたPythonモジュールを、Python3に対応させろやというコメントが複数件来まして、それでも放置してたらpull requestまで送りつけられたので、重い腰を上げて調べました。

3.0〜3.3までのWhat’s Newのページを眺めてみて、目に留まった項目をチョロチョロ書いてみます。というか3.0ってもう4年以上前にリリースされてるんですね。全然普及してる感じがしないですけど。

2008.12.03 What’s New in Python 3.0
2009.06.27 What’s New in Python 3.1
2011.02.20 What’s New in Python 3.2
2012.09.29 What’s New in Python 3.3

Continue reading “いまさらPython 3”