2014年度ミニコンに向けて1

予定は未定です

2014年こそ、ミニコンに出る予定である。 とはいえ、ただ普通に作っただけではおもしろくない。 ちなみに一昨年は、Juliusを使って音声認識でロボットを操縦しようとした。

使いたい技術

フルのLinuxが走るボードを使用する。Haskellを走らせるためである。 古くからこの分野にはFunctional Reactive Programmingと呼ばれる分野が存在する。 これは関数型プログラミングの上にReactiveなパラダイムを構築しようというものである。 詳しくは以下を参照されたし。

• Functional reactive programming - Wikipedia, the free encyclopedia
• やさしいFunctional reactive programming（概要編） - maoeのブログ

なお、現在までに同様の試みはいくつか存在する。 例えば以下である。

• Haskell-controlled Segway robot | Enough Blogging!

しかしながら小型のロボットに搭載した例はあまりないようだ。 RasberryPiをはじめとした小型Linuxボードの登場によって、小さいロボットの作成が可能だろうと思われる。

そもそも

そもそもなぜ、FRPをロボットに使用しようと考えたか。 ある日、ロボットがモナドではないかと考えたからである。

追伸メモ

センサー類はi2cをつかうと良いようだ。もしかしたら加速度センサーのみあれば、積分によって座標が求まるのではと考えていたが、ノイズ等の誤差が蓄積するため難しいようだ。

• 加速度の積分 | Uchiyama Lab.

修行用xmodmap

修行中なので。

clear Lock
clear Control

keycode 66 = Control_L
keycode 135 = Super_R
! Return
keycode 36 = Control_R
add Control = Control_L
add Control = Control_R


! for strict.
! up left,right
keycode 111 = 
keycode 113 = 
keycode 114 = 
keycode 116 = 
keycode 166 = 
keycode 167 = 

! backspace
keycode 22 = 

! tab
!keycode 23 = Escape
keycode 23 =

Firefoxのvimperatorから英語でグーグル検索する

色々とやってられなかったので。

• まず、ここから Google (No country redirect) とかかれたところをクリックして、なんかインストールする。
• 一時的にNavigation Toolbarをオンにして、検索窓の左のとこからManage Search Engineする。
• いらないのを消したりして、google USのkeywordをeとかにしておく。

あとは:open eとかすればOK.

.vimperatorrc に以下のように書くと便利である。

nnoremap e o e
nnoremap E t e

雷ちゃんはかわいい

かわいいのでどこでも声を聞きたいので適当にでっちあげた。
あまりやりすぎないようにね。 swftoolsバグってるっぽくて透明なのがとりだせない……。

#!/bin/sh
VOICE_URL="http://203.104.105.167"
NUMBER_OF_VOICE=53
VOICE_DIR=voice
PIC_DIR=pic
WAIT_TIME=1

# make directory.
init ()
{
    mkdir -p $VOICE_DIR
    mkdir -p $PIC_DIR
}

# wget --referer="http://203.104.105.167/" http://203.104.105.167/kcs/sound/kc236/3.mp3
voice_download ()
{
    KN="$1"
    DOWNLOAD_DIR=$VOICE_DIR/$KN
    mkdir -p $DOWNLOAD_DIR
    echo "voice: $1 download start to $DOWNLOAD_DIR"
    for vi in `seq 1 $NUMBER_OF_VOICE`
    do
        wget --referer="$VOICE_URL/" $VOICE_URL/kcs/sound/kc$KN/$vi.mp3 -P $DOWNLOAD_DIR > /dev/null 2>&1
        sleep $WAIT_TIME
    done
}

pic_download ()
{
    KN="$1"
    DOWNLOAD_DIR=$PIC_DIR/$KN
    mkdir -p $DOWNLOAD_DIR
    echo "$pic: 1 download start to $DOWNLOAD_DIR"
    wget http://125.6.184.15/kcs/ships/$KN.swf -P $DOWNLOAD_DIR > /dev/null 2>&1

    for i in `swfextract $DOWNLOAD_DIR/$KN.swf | grep JPEGs | sed "s/.*ID(s)//" | sed "s/,//g"`
    do
        swfextract $DOWNLOAD_DIR/$KN.swf -j $i -o $DOWNLOAD_DIR/$i.jpeg
    done
}

init
voice_download 236
pic_download 236

POJ 1637 Sightseeing tour

オイラー閉路にtwo-wayなエッジを追加した問題. 最大流で解けます。考え方は以下の通り

• まずtwo-wayなエッジであろうと入力そのまま有向なエッジとしてグラフに追加していく。
• 出るエッジについて-1,入るエッジについて+1を各ノードで計算しておく。通常のオイラー閉路ならば、各ノードで0ならOK?
• 今回はtwo-wayなものをそのままグラフに追加したので、0にはならないが、必ず2の倍数になる。なぜなら、正解のグラフの向きにしたときには各ノードで0であり、正解と逆向きにすると入るところが+2,出るところが-2となるからである。
• inoutをすべて/2する。これは流量を丁度1とするためである。(実際には2を流したいが、1だけ流してしまうのを防ぐ)
• 流れないならば、決め打ちしたエッジはそのままで良く、流れるのならば、丁度-1+2=1となって逆向きのエッジを張ることに相当する
• 最初にtwo-wayなエッジで決め打ちしたのと逆方向に流量1のエッジをつける
• inoutがプラスとなっているところにsuper sourceからプラス分流し、マイナスとなっているところにsuper sinkからマイナス分流す
• プラスの総量分がsuper sourceからsuper sinkから流れたらOK.

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

// ----- lib start
struct Edge{
    int to,cap,rev;
    Edge(int _to,int _cap,int _rev) : to(_to),cap(_cap),rev(_rev) {};
};

void add_edge(vector<vector<Edge> >& E,int from,int to,int cap){
    E[from].push_back(Edge(to,cap,E[to].size()));
    E[to].push_back(Edge(from,0,E[from].size()-1));
}

vector<int> levels(vector<vector<Edge> > &E,int s){
    vector<int> level(E.size(),-1);
    level[s] = 0;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int v = Q.front();
        Q.pop();
        for(size_t i=0;i<E[v].size();i++){
            Edge &e = E[v][i];
            if(e.cap > 0 and level[e.to] == -1){
                level[e.to] = level[v]+1;
                Q.push(e.to);
            }
        }
    }
    return level;
}

int good_path(vector<vector<Edge> > &E,
        vector<int> &iter,
        vector<int> &level,
        int v,int t,int f){
    if(v == t) return f;
    for(int &i=iter[v];i<(int)E[v].size();i++){
        Edge &e = E[v][i];
        if(e.cap > 0 and level[v] < level[e.to]){
            int d = good_path(E,iter,level,e.to,t,min(f,e.cap));
            if(d > 0){
                e.cap -= d;
                E[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(vector<vector<Edge> > E,int s,int t){
    int flow = 0;
    const int INF = 1 << 30;
    while(true){
        vector<int> level = levels(E,s);
        if(level[t] < 0) return flow;
        vector<int> iter(E.size());
        int f;
        while((f=good_path(E,iter,level,s,t,INF)) > 0){
            flow += f;
        }
    }
}
// ----- lib end.

struct Street {
    int x,y,di;
    Street() {}
    Street(int _x,int _y,int _di) : x(_x),y(_y),di(_di) {}
};


bool solve(const vector<Street> &s,int m){
    vector<int> inout(m);
    // m is super source.
    // m+1 is super sink
    int source = m;
    int sink = m+1;
    vector<vector<Edge> > E(m+2);
    for(size_t i=0;i<s.size();i++){
        inout[s[i].x]--;
        inout[s[i].y]++;
        // two-way
        if(s[i].di == 0){
            add_edge(E,s[i].y,s[i].x,1);
        }
    }
    for(int i=0;i<m;i++){
        if(inout[i] % 2 == 1) return false;
        inout[i] /= 2;
    }
    int send=0;
    for(int i=0;i<m;i++){
        if(0 < inout[i]){
            add_edge(E,source,i,inout[i]);
            send += inout[i];
        }else if(inout[i] < 0){
            add_edge(E,i,sink,-inout[i]);
        }
    }
    return max_flow(E,source,sink) == send;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for(int test=0;test<n;test++){
        int m,s;
        cin >> m >> s;
        vector<Street> st(s);
        for(int i=0;i<s;i++){
            cin >> st[i].x >> st[i].y >> st[i].di;
            st[i].x--;
            st[i].y--;
        }
        if(solve(st,m)){
            cout << "possible" << endl;
        }else{
            cout << "impossible" << endl;
        }
    }
    return 0;
}

EmacsでシンタックスハイライトしたテキストをHTML化する方法

Emacs24以上で。

• package.elとかでhtmlizeをインストールする。
• disable-themeでテーマを一時的に無効化(黒背景とかだとヤバい？)
• M-x htmlize-file でファイルを指定する。
• HTMLができる

参考

• http://yohshiy.blog.fc2.com/blog-entry-8.html
• http://www.emacswiki.org/emacs/Htmlize
• http://batsov.com/articles/2012/02/19/color-theming-in-emacs-reloaded/

StateMonadをOCamlで書いた。

というお話。コンパイラを書く時に必要になるっぽいので。

(*simple monad*)
module type MONAD =
  sig
    (* Type for state.It's Covariant*)
    type +'a t
    (* lift up normal value to monaded value.*)
    val return : 'a -> 'a t
    (* bind is the function to apply function
         that take normal value and return monaded value to monaded value*)
    val bind : 'a t -> ('a -> 'b t) -> 'b t
  end

(*extended monad.*)
module type EMONAD =
  sig
    include MONAD
    (* let (>>=) = bind *)
    val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
    (*lift up function to monad.
        let lift f t = bind t (fun x -> return @@ f x)
     *)
    val lift : ('a -> 'b) -> 'a t -> 'b t
  end

(*for STATE_MONAD*)
module type STATE =
  sig
    type t
  end

module type STATE_MONAD =
  functor(State : STATE) ->
         sig
           include EMONAD
           (* receive monad and initial state*)
           val run : 'a t -> State.t -> ('a * State.t)
           (* set state to arg*)
           val put : State.t -> unit t
           (* get state.*)
           val get : State.t t
         end

module StateMonad : STATE_MONAD =
  functor(State : STATE) ->
         struct
             type state = State.t
             (* monad type*)
             type 'a t = state -> ('a * state)
             (* make pair of value and state*)
             let return a = fun s -> (a,s)
             (* return state -> ('a * state)
                at first,apply m(1st arg) to s ,
                apply f to returned value*)
             let bind m f =
               (* get new state and value ,*)
               fun s ->
               match m s with
               | (x,s') -> f x s'
             let (>>=) = bind
             let lift f t = bind t (fun x -> return @@ f x)
             let run m a = m a
             let put s =
               fun _ -> ((),s)
             let get =
               fun s -> (s,s)
           end

(* sample usage *)
module IntStateMonad = StateMonad(
                           struct
                             type t = int
                           end
                         )

type 'a cons_list = Nil | Cons of 'a * 'a cons_list

let cons a lst =
  IntStateMonad.(get >>=
                   fun i ->
                   put (succ i)
                 >>= (fun x
                      -> return (Cons (a ,lst))))
(* it is equal to cons*)
(* let cons0 a lst = *)
(*   IntStateMonad.(bind (bind get (fun x -> put @@ succ x)) (fun x -> return (Cons (a,lst)))) *)


(* (\* リストに一個追加したら、カウンターが1になる *\) *)
(* assert (Cons ("a", Nils), 1) = *)
(*     (IntStateMonad.(run (cons "a" Nils >>= fun s -> return s) 0)) *)

(* (\* リストに2個追加したら、カウンターが2になる *\) *)
(* assert (Cons ("b", Cons ("a", Nil)), 2) = *)
(*     (IntStateMonad.(run (cons "a" Nil >>= cons "b" >>= fun s -> return s) 0)) *)

参考

• http://www.haskell.org/haskellwiki/State_Monad
• http://d.hatena.ne.jp/naokirin/20120713/1342210328
• http://d.hatena.ne.jp/kazu-yamamoto/20080604/1212573964
• http://blogs.perl.org/users/cyocum/2012/11/writing-state-monads-in-ocaml.html