Hatena::ブログ(Diary)

エンジニアのソフトウェア的愛情 このページをアンテナに追加 RSSフィード Twitter

2014-04-13

会議の時間

第20回

先日、「オフラインリアルタイムどう書く」が開催されました。今回で20回目でした。コンスタントに優良なお題と、みんなで集まって解くという場を提供され続けていることに尊敬と感謝の念を抱くばかりです。

…。

とはいえ、いまだにオフラインリアルタイムで参加せずに、オンラインで非同期に問題を解くという開催の主旨に真っ向勝負なことをしているわけですが(苦笑)。


今回のお題。


オーソドックスな解き方としては、各人の毎分の状態を真偽値で持ち、その状態を重ね合わせて条件にあう状態が指定された期間連続する箇所を特定する、というのがあります。

そのアイディアで解いてみたものがこれ。


再挑戦

解いてはみたものの、なんとなく面白味に欠けるという理由で別解を探していたところ。

虎塚さんが書かれたブログのエントリの、

あらかじめ人数分の配列を作るのではなく、走査を1回だけにして、あるタイミング(分)ごとに、「お前今ヒマ?」と全員に確認するメソッド(おまひまメソッド)を作るとよいかもしれません。

という記述を見て、このアイディアで解けないか試みてみました。

その結果がこちら。


書きなぐったコードで半年もすると解読不能になりそうなので、主に未来の自分のために、書き直したコードと解説を書いておきます。


スケジュールの作り方

文字列から予定を読み出すところまでは基本的に同じです。

読み出した予定を記憶する部分で少し工夫しました。

予定の時刻というのは、予定が入っている人の状態を変えるタイミングになります。最初のアイディアでは1日分の状態をビット列に展開していましたが、これを状態が変わるタイミングだけを記憶するようにします。

次の図で言うと{ 1002 => 1, 1008 => 1 }だけを記憶しておきます。

初期状態を0として、カウントアップするごとにscheduleの値とxorをとります(scheduleに値が格納されていない場合は0とします)。xorをとったあとの値が、そのときの状態になります。

f:id:E_Mattsan:20140413121454p:image

人数が増えたばあいは人数分のビット列を用意して、演算を1ビットのxorから人数分ビットのビット列のxorに変えればよいので演算の回数は増えずにすみます。

f:id:E_Mattsan:20140413121541p:image

状態の変化で記憶しているので、開始時刻と終了時刻を区別する必要がないため、格納する情報を減らすことができます。

実装上の工夫として、予定を格納するときもxorを使って格納しています。こうすることで前の予定の終了時刻と次の予定の開始時刻が重なったばあいに対処しています(前の予定が終わる前に次の予定が始まるということが往々にしてありますが、そういう場合は考慮していないです)。

加えて、10時以前の予定はすべて10時によせるようにしています。これによって10時以降の状態だけを調べればよいことになります。開始終了とも10時以前のばあいにどちらも10時によせられてしまいますが、上記のようにxorをとって格納しているので、開始終了が同時刻のばあいには記録されないことになります。


会議時間を見つける

あとは初期状態を与えて、時間ごとに予定で更新し、「お前今ヒマ?」と全員に訊いて回り、連続して全員がヒマと答えた回数が指定した回数になったら、全員がヒマと答え始めた時刻(と指定回数に達した時刻)を出力すればよいことになります。

このとき、座間川さんだけ初期状態を反転しておくことで、ほかの人と同じように扱うことができるようになります。

全員がヒマかどうかを調べるには、全員の状態のビットが0のときを探せばよいことになります(座間川さんは初期状態を反転しているので、0のときが忙しいとき、つまりほかの人にとって都合のよいときになります)。

状態をビット列として整数値として扱えば、数値として0のときを判定すればよいことになります。

印旛沼さんと陣場山さんの状態はどちらかが0になっていればよいので、それぞれのビットをマスクした上でそれぞれ値を調べます。

f:id:E_Mattsan:20140413121812p:image


コードにしてみる

C++でコードにした結果です。


#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <map>

static const int A = 1 << 0;
static const int B = 1 << 1;
static const int I = 1 << 2;
static const int J = 1 << 3;
static const int Z = 1 << 4;

inline int charToPerson(char c)
{
    static const std::string  person("ABIJZ");
    return (1 << person.find(c));
}

inline int toMin(int hm)
{
    return (hm / 100) * 60 + (hm % 100);
}

inline int toHourMin(int min)
{   return (min / 60) * 100 + (min % 60);
}

std::map<int, int> read(const std::string& source)
{
    std::map<int, int> schedule;
    std::istringstream iss(source);
    while(iss.good())
    {
        char c;
        char separator;
        int  head;
        int  tail;
        iss >> c >> head >> separator >> tail;
        int person = charToPerson(c);
        schedule[toMin(std::max(head, 1000))] ^= person;
        schedule[toMin(std::max(tail, 1000))] ^= person;
        iss >> separator;
    }
    return schedule;
}

void write(int start_time, const std::string& expected)
{
    std::ostringstream oss;
    if(start_time)
    {
        oss << toHourMin(start_time) << "-" << toHourMin(start_time + 60);
    }
    else
    {
        oss << "-";
    }

    std::string actual = oss.str();
    std::string result = (expected == actual) ? "o" : "x";

    std::cout
        << "expected: " << expected
        << ", actual: " << actual
        << ", result: " << result
        << std::endl;
}

int search(std::map<int, int>& schedule)
{
    int count_i = 0;
    int count_j = 0;
    int status  = Z;
    for(int i = toMin(1000); i < toMin(1800); ++i)
    {
        status ^= schedule[i];
        count_i = ((status & ~J) == 0) ? (count_i + 1) : 0;
        count_j = ((status & ~I) == 0) ? (count_j + 1) : 0;

        if((count_i == 60) || (count_j == 60))
        {
            return i - 59;
        }
    }
    return 0;
}

void test(const std::string& source, const std::string& expected)
{
    std::map<int, int> schedule = read(source);

    int start_time = search(schedule);

    write(start_time, expected);
}

int main(int argc, char* argv[])
{
    /*0*/ test( "A1050-1130,B1400-1415,I1000-1400,I1600-1800,J1100-1745,Z1400-1421,Z1425-1800", "1425-1525" );
    // 以下テストパタン、略

    return 0;
}

いつか読むはずっと読まない:人生はサーフィンのように

竹内義晴さんのITmedia エンタープライズの連載「人生はサーフィンのように」を元にした電子書籍です(くわしくはこちらへ)。

実は思い入れのある連載です。

ちょうどこれらの記事が連載されていた時期に、荒波にもまれていたところでした。これらの記事でずいぶん勇気づけられたのを覚えています。その後竹内さんとはセミナーで機会があって知り合いになることができました。

結局この年の秋には荒波に抗えず難破状態になりましたが、このとき復帰に向けて手を貸して頂いたのも竹内さんでした。


それから1年半ほどがたった今。

今も荒波の渦中にあります。ただ当時のようにもまれるのでなく、ヘタながらも波に乗れる(少なくとも乗る努力ができる)ようになったような気がします。


やる気が出ない本当の理由

やる気が出ない本当の理由

2014-03-21

プログラミングで稼いでみたい

Twitterで、そのアカウントでの最初のtweetを検索するサービスが話題に出ていますが。

わたしも検索してみました。


感慨深い。



当時の自分に言ってやりたい。

プログラミングで稼ぐのは楽じゃないぞ。

でも、楽しいぞ、と。

2014-03-04

Steinhaus–Johnson–Trotter algorithm の実装


Permutation.h

#ifndef PERMUTATION_H
#define PERMUTATION_H

#include <vector>

class Permutation
{
public:
    Permutation(int* begin, int* end);
    bool isIdentity() const;
    Permutation& operator ++ ();
    Permutation operator ++ (int);
    const int* begin() const;
    const int* end() const;
    int operator [] (int i) const;

private:
    void init();

    std::vector<int> source_;
    std::vector<int> current_;
    std::vector<int> c_;
    std::vector<bool> d_;
    int x_;
    int i_;
    bool identity_;
};

#endif//PERMUTATION_H

Permutation.cpp

#include "Permutation.h"

#include <algorithm>

Permutation::Permutation(int* begin, int* end) :
    source_(begin, end),
    current_(begin, end),
    c_(std::distance(begin,end)),
    d_(std::distance(begin,end), true),
    x_(0),
    i_(std::distance(begin,end) - 1),
    identity_(true)
{
}

void Permutation::init()
{
    std::copy(source_.begin(), source_.end(), current_.begin());
    std::fill(c_.begin(), c_.end(), 0);
    std::fill(d_.begin(), d_.end(), false);
    x_ = 0;
    i_ = current_.size() - 1;
    identity_ = true;

}

bool Permutation::isIdentity() const
{
    return identity_;
}

Permutation& Permutation::operator ++ ()
{
    identity_ = false;
    do
    {
        if(c_[i_] < i_)
        {
            int index = d_[i_] ? (i_ - c_[i_] + x_) : (c_[i_] + x_ + 1);
            std::swap(current_[index - 1], current_[index]);
            ++c_[i_];
            i_ = current_.size() - 1;
            x_ = 0;
            return *this;
        }
        else
        {
            if(d_[i_])
            {
                ++x_;
            }
            d_[i_] = ! d_[i_];
            c_[i_] = 0;
            --i_;
        }
    } while(i_ > 0);
    init();
    return *this;
}

Permutation Permutation::operator ++ (int)
{
    Permutation result(*this);
    ++(*this);
    return result;
}

const int* Permutation::begin() const
{
    return &(*current_.begin());
}

const int* Permutation::end() const
{
    return &*current_.end();
}

int Permutation::operator [] (int i) const
{
    return current_[i];
}

PermutatinTest.cpp

#include "Permutation.h"

#include <iostream>

std::ostream& operator << (std::ostream& out, const Permutation& perm)
{
    std::copy(perm.begin(), perm.end(), std::ostream_iterator<int>(out, " "));
    return out;
}

int main(int, char* [])
{
    int a[] = { 2, 4, 6, 8 };
    Permutation perm(a, a + 4);

    do
    {
        std::cout << perm++ << std::endl;
    } while( ! perm.isIdentity());

    return 0;
}

ビルド&実行。

$ g++ -o PermutationTest Permutation.cpp PermutationTest.cpp 
$ ./PermutationTest 
2 4 6 8 
2 4 8 6 
2 8 4 6 
8 2 4 6 
8 2 6 4 
2 8 6 4 
2 6 8 4 
2 6 4 8 
6 2 4 8 
6 2 8 4 
6 8 2 4 
8 6 2 4 
8 6 4 2 
6 8 4 2 
6 4 8 2 
6 4 2 8 
4 6 2 8 
4 6 8 2 
4 8 6 2 
8 4 6 2 
8 4 2 6 
4 8 2 6 
4 2 8 6 
4 2 6 8 

問題は。「CiNii 論文 -  7. 順列の生成法 (<大特集>アルゴリズムの最近の動向) 」の中の「2.2 繰り返し的方法*1」をC++のコードにしてみただけで、中身をキチンと理解してないところ。リクツはわかるのだけれども。

*1:ページの右にあるプレビューを開いてください。プレビューにはリンクできないようです。

2014-02-27

それはおかしいと思います。

public class Shift {
    public static void main(String[] args) {
        for(int i = 0; i < Integer.SIZE + 2; ++i) {
            System.out.printf("%08x%n", 1 << i);
        }
    }
}

実行。

$ javac Shift.java 
$ java Shift
00000001
00000002
(中略)
40000000
80000000
00000001
00000002

えーっ!

型のビットサイズを超えてシフトしたら、ビットを押し出してくれることを期待したのに、まったくの予想外の挙動。

この挙動はシフトではありません。ローテイトです。

…。

そうか、<< 演算子はローテイト演算子なんだ…。

…で済めばよかったんですが(いや、それで済んでもあんまりよくないですけど)。


public class Shift {
    public static void main(String[] args) {
        for(int i = 0; i < Integer.SIZE + 2; ++i) {
            System.out.printf("%08x%n", 3 << i);
        }
    }
}

実行。

$ javac Shift.java 
$ java Shift
00000003
00000006
(中略)
c0000000
80000000
00000003
00000006

…。

いや、それ、絶対おかしい。

2014-01-26

グラフの木分解〜グラフ理論とわたし

グラフを木分解します。

…。

木分解。わたしもひと月前まで聞いたこともありませんでした。

木分解とは。おおざっぱに言うと、グラフからルールに従って部分グラフの集合を取り出し、その部分グラフを木構造ノードとする木を作ること。

くわしいことはこことかを参照してみてください。

なぜこのようなことをやっているかというと。仕事でアルゴリズムの実装というのを引き受けまして。これがグラフ理論論文でして。このひと月ほど集中的にグラフ理論の勉強をしているとこでして。

そのアルゴリズムの実装に木分解が必要になり、木分解のアルゴリズムのひとつである最小次数法というのを実装してみた次第。

Graphクラスを定義した graph.rb を用意します。

require 'Set'

class Graph
  attr_reader :edges, :vertices

  def initialize
    @edges = {}
    @vertices = Set.new
  end

  def add_vertex(v)
    @vertices.add(v)
  end

  def delete_vertex(v)
    @edges.each do |vertex, edge|
      edge.delete(v)
    end
    @edges.reject! do |vertex, edge|
      edge.empty?
    end
    @edges.delete(v)
    @vertices.delete(v)
  end

  def delete_edge(v1, v2)
    @edges[v1].delete(v2)
    @edges[v2].delete(v1)
  end

  def add_edge(v1, v2)
    @edges[v1] ||= Set.new
    @edges[v1].add(v2)
    @edges[v2] ||= Set.new
    @edges[v2].add(v1)
    vertices.add(v1).add(v2)
  end
end

木分解をする tree-decomposition.rb を用意。

require './graph'

# 木分解するグラフの準備
g = Graph.new
g.add_edge(1, 2)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.add_edge(4, 7)
g.add_edge(5, 6)
g.add_edge(5, 8)
g.add_edge(5, 9)
g.add_edge(6, 9)
g.add_edge(7, 8)
g.add_edge(7, 10)
g.add_edge(8, 9)

# 木分解の結果を格納する木
tree = Graph.new

# 最小次数法を使って木分解する

adj_v = nil
nodes = []
n0 = g.vertices
tree.add_vertex(:n0)

while adj_v != g.vertices do
  # 次数が最小の頂点を選ぶ
  vi = g.vertices.min { |v1, v2| g.edges[v1].size <=> g.edges[v2].size }
  # 該当する頂点に隣接する頂点の集合
  adj_v = g.edges[vi]
  # 該当する頂点と隣接する頂点からなる集合を木分解のノードにする
  ni = adj_v.dup.add(vi)
  tree.add_edge(:n0, ni)
  # 該当する頂点をグラフから取り除く
  g.delete_vertex(vi)

  # 該当する頂点の集合に対して完全グラフを作る
  adj_v.each do |source|
    adj_v.each do |target|
      if source != target
        g.add_edge(source, target)
      end
    end
  end

  # 既にあるノードが今回分解したノード ni によって最初のノード n0 と
  # 分離したら、ブランチを ni とのあいだに付け替える
  nodes.each do |n|
    if (! ((ni & n) - n0).empty?) && (tree.edges[n].include?(:n0))
      tree.delete_edge(n, :n0)
      tree.add_edge(n, ni)
    end
  end

  # 分解済みのノードの一覧に追加
  nodes << ni
end

# これ以上分解する要素がなくなったノード n0 を取り除く
tree.delete_vertex(:n0)

# 結果の出力
puts "# vertices"
tree.vertices.each do |v|
  puts "- [ #{v.to_a.join(', ')} ]"
end

puts "---"

puts "# edges"
tree.edges.each do |v, e|
  puts "- #{v.to_a}: #{e.map(&:to_a)}"
end

ここで用意しているグラフは上で参照してくださいと言った資料の中にある次のようなグラフです。

f:id:E_Mattsan:20140126181654j:image:w360


実行。

$ ruby tree-decomposition.rb 
# vertices
- [ 7, 10 ]
- [ 2, 4, 1 ]
- [ 2, 4, 3 ]
- [ 4, 5, 2 ]
- [ 5, 7, 4 ]
- [ 8, 5, 7 ]
- [ 5, 9, 6 ]
- [ 8, 9, 5 ]
---
# edges
- [7, 10]: [[8, 5, 7]]
- [2, 4, 1]: [[4, 5, 2]]
- [2, 4, 3]: [[4, 5, 2]]
- [4, 5, 2]: [[2, 4, 1], [2, 4, 3], [5, 7, 4]]
- [5, 7, 4]: [[4, 5, 2], [8, 5, 7]]
- [8, 5, 7]: [[7, 10], [5, 7, 4], [8, 9, 5]]
- [5, 9, 6]: [[8, 9, 5]]
- [8, 9, 5]: [[8, 5, 7], [5, 9, 6]]

vertices 以下の8つの集合が木のノードです(ひとつのノードがグラフの複数の頂点を含んでいます)。

edges 以下がそれぞれのノードをつなぐブランチです。


わかりにくいと思うので。結果を図示。こんな感じ。木のノードが元のグラフの部分グラフになっています。

f:id:E_Mattsan:20140126181737j:image:w360


グラフ理論とわたし

趣味と言えるほどではないものの。ときどき数学の読み物を読んだりします。グラフ理論は本格的に学んだ覚えがないのですが、グラフ理論に触れるようなネタはプログラミングしたことがあります。

たとえば、これ。


…。本当に「ネタ」じゃないか orz


いつか読むはずっと読まない:グラフ理論の本

自分で買ったグラフ理論関係の唯一の本。

現代数学小事典」のようにグラフ理論も載っている本というのは他にもあるんですが、グラフ理論の本としては、わたしが持ってるのはたぶんこれだけ。

…。持ってるだけでこれも積ん読山脈に埋もれているのですが…。

最短経路の本 レナのふしぎな数学の旅

最短経路の本 レナのふしぎな数学の旅