Leaderを選ぶアルゴリズム

　CodilityのlessonにあるLeaderを選ぶアルゴリズムが面白い。

非負整数を要素に持つ長さnの配列a[]がある。
配列の中にn/2 回より多く出現する要素がある場合、その要素を配列のleaderと呼ぶ。

例えば、
[1,2,3,1,1,1]
という配列の場合、1がleader。

[1,1,1,2,3,4]
の場合は、leader不在となる。

配列a[]が与えられた時に、a[]のleaderを求めよ。

mapを使って要素毎の出現回数を数えるだけでしょ。
と思ったら、時間計算量の制限はO(n)らしい。

それなら、unodered_mapで数えればいいでしょ。
と思ったら、空間計算量（※）はO(1)らしい。
（※入力aを格納するのに必要なメモリは除く）

いや、分かりません。
ということでマテリアルを読むと、スタックを使ったクレバーな解が紹介されてました。
C++で書いてみました。

#include <iostream>
#include <vector>

using namespace std;

int leader(const vector<int> &a) {
  int n = a.size();
  int sz = 0;  // stack size
  int val;     // value in stack
  
  for (auto &x : a) {
    if (sz == 0) {
      ++sz;
      val = x;
    } else {
      if (val != x)
        --sz;
      else
        ++sz;
    }
  }

  if (sz && count(a.begin(), a.end(), val) > n / 2)
    return val;

  return -1;  // no leader
}

int main() {
  cout << leader({1,2,3,1,1,1}) << endl;
  cout << leader({1,1,1,2,3,4}) << endl;
  cout << leader({2,3,4,1,1,1}) << endl;

  return 0;
}

[TED] Tony Wyss-Coray: How young blood might help reverse aging. Yes, really

　脳の若返り治療に関する話。

二匹のマウスを手術で結合し、血液循環器を共有させる。

片方は若いマウス、他方は年老いたマウス。

すると、年老いたマウスに若返り現象が見られた。

若返り現象は、筋肉、肝臓、膵臓、心臓、そして、脳に見られた。

特に興味深いのは、脳が若返ったということだ。若い血に晒されることで、ニューロンが多く作られ、シナプスの活動が盛んになった。

”プラズマ”と呼ばれる血液成分がこの若返りに関与していると考察し、今度はマウスに若いマウスの”プラズマ”を注射して、脳の活動の変化を観察した。すると、手術で循環器を共有させたときと同様に脳の若返りが観測できた。

さらに一歩研究を進め、若い”人間”のプラズマをマウスに注射し、その効果を確認した。

Barnes Mazeテストと呼ばれる認知テストを行ったところ、”人間”のプラズマにもマウスの脳を若返らせる効果があることが分かった。

”プラズマ”によって脳が若返るのはマウスだけなのだろうか？

我々人間も若いプラズマによって脳を若返らせることができないだろうか？

現在スタンフォードで臨床試験が行われている。

アルツハイマー患者に20代の人間のプラズマを注入して、症状が改善するかどうかを確認中だ。

もしポジティブな結果がえられれば、脳を若返らせる要素を発見し、その要素を合成することでアルツハイマーやその他の認知症を治療することができるかもしれない。

モンテカルロ法でシャープレイ値を計算

　昨日動的計画法でシャープレイ値を計算してみたが、一般的な計算方法としてよく知られたものだったらしい。他にもモンテカルロ法を使った計算方法もあるとのことなので、モンテカルロ法で計算するプログラムも書いてみた。

問題は昨日のやつと同じく国連理事国のやつ。random_shuffle便利だよねーっていう。

#include <iostream>
#include <vector>

using namespace std;

const int N = 15;  // # of members
const int M = 9;   // required # of members to approve a decision
const int K = 5;   // # of permanent members
const int T = 1e6; // # of MC iteration

inline int payoff(int s) {
  int vetoMask = (1<<K) - 1;

  if ((s & vetoMask) < vetoMask)
    return 0;

  if (__builtin_popcount(s) < M)
    return 0;

  return 1;
}

double sharpleyValue(int p) {
  vector<int> v;
  for (int i = 0; i < N; i++)
    v.push_back(i);

  double ret = 0;
  for (int _ = 0; _ < T; _++) {
    random_shuffle(v.begin(), v.end());
    int s = 0;
    for (auto & x : v) {
      int t = s | 1 << x;
      if (x == p) {
        ret += payoff(t) - payoff(s);
        break;
      }
      s = t;
    }
  }
  
  return ret / T;
}

int main() {

  for (int i = 0; i < N; i++)
    cout << i << " :" << sharpleyValue(i) << endl;

  return 0;
}

国連理事国のシャープレイ値を計算

　最近シャープレイ値なるものを学んだ。協力ゲームにおいて、ゲームでえられた利得をグループ内のメンバーで公正に分配する方法の一つだ。直感的にはゲームにより貢献したプレイヤーほど多くのシャープレイ値が割り当てられる。

　このシャープレイ値の計算がなかなか面白い。ということでシャープレイ値を計算するプログラムを書いてみた。

[問題設定]

国連の理事国には、常任理事国と非常任理事国が存在する。

常任理事国は５カ国、非常任理事国は１０カ国である。

国連において何かを決める場合、常任理事国すべての賛成に加え、合計９カ国の賛成が必要である。

いま議論している内容が可決となる場合は利得1、否決となる場合は利得0とする。

常任理事国、非常任理事国のシャープレイ値を求めよ。

　以下C++で書いたコード。なんとなくTSPのビットDP解法に似ている気がする。

#include <iostream>

using namespace std;

const int N = 15;  // # of members
const int M = 9;   // required # of members to approve a decision
const int K = 5;   // # of permanent members
long long fac[N+1];

void init() {
  fac[0] = 1;
  for (int i = 1; i <= N; i++)
    fac[i] = i * fac[i-1];
}

inline int payoff(int s) {
  int vetoMask = (1<<K) - 1;

  if ((s & vetoMask) < vetoMask)
    return 0;

  if (__builtin_popcount(s) < M)
    return 0;

  return 1;
}

double sharpleyValue(int p) {

  double ret = 0;
  
  for (int i = 0; i < 1<<N; i++) {
    if (!(i & 1<<p))
      continue;
    
    double tmp = payoff(i) - payoff(i & ~(1<<p));
    int s = __builtin_popcount(i);
    ret += tmp * fac[s-1] * fac[N-s];
  }

  return ret / fac[N];
}

int main() {

  init();

  for (int i = 0; i < N; i++)
    cout << i << " :" << sharpleyValue(i) << endl;

  return 0;
}

結果は、
常任理事国 = 0.1963
非常任理事国　= 0.001865

ということで常任理事国の影響度が非常に高いことが分かる。

[TED] Jennifer Doudna: We can now edit our DNA. But let's do it wisely

　CRISPR-Cas9という遺伝子工学技術に関する話。

CRISPRテクノロジーは遺伝子工学領域の新しい技術で、遺伝子の編集を行うことができる。この技術は細菌がどのようにウイルス感染と戦うかを研究する過程で生まれた。

CRISPRは細菌がウイルスから身を守るための細胞のようなもので、複数世代に渡り細菌が感染したことのあるウイルス情報を蓄積している。細菌はCRISPRに蓄積された情報からウイルスのDNAをコピーしたRNAを作成する。このRNAとマッチするパターンがDNA内に見つかると、Cas9がそのDNA部分（=ウイルス）をカットする。

この仕組みを遺伝子工学に応用することで、驚くべき正確さで特定のDNAを削除することができる。例えば、HIVウイルスを感染者の細胞から除去することができる。
このCRISPRテクノロジーが従来の遺伝子工学技術と一線を画しているのは、プログラム可能であるということだ。つまり、カットしたいDNA情報をプログラムすることで、簡単に複数の分野に応用できる。10年後以内には、CRISPRテクノロジーの医療分野への応用が実現する見込みで、現在この技術領域のスタートアップが盛り上がりを見せVCの投資も増えている。

CRISPRテクノロジーは治療以外にも強化にも使える。例えば、骨格を強くしたり、身長を高くしたり、目の色を変えたり、視力を改善したり、IQを高くしたりなどだ。
現在は、どの遺伝情報がどのような特性と関連しているのかがよく知られていないが、この関連性が明らかになるとCRISPRテクノロジーを使い、上記のような人間をデザインするというようなことが可能になる。

このような技術には当然倫理的な問題が伴う。彼女と同僚はCRISPRテクノロジーを人間の胚に応用するとこを一時的に停止することを呼びかけた。世の中に大きなインパクトを与える技術には、十分な試験と検証が必要である。

[TED ] Federico Pistono: Robots Will Steal Your Job, but That's OK

　技術的特異点後の社会基盤の在り方についての話。

　このままのペースでオートメーションが進んでいくと、世の中の失業率は高くなっていく一方である。例えば、Googleが研究している自動運転車はタクシードライバーから職を奪ってしまう。

　しかし、彼はそれでもよいと言っている。それでもよいどころか素晴らしい世界が待っていると。ロボットに仕事を奪われた後の世界は、遊んで暮らせる完全失業の世界である。さすがにそれは極論すぎるが、我々の労働時間は減り、自由な時間が増えるのは確かだ。

　これを実現するためには、我々のマインドチェンジが必要だ。現代はリソースとテクノロジーは発達しているが、我々にはビジョンが不足している。テクノロジーの進歩により、我々はどこでもいつでも働けるようになった。しかし、これによりもたらされた結果は以前よりも長く働くようになったということだ。何のための人生かを考えなければならない。

　尽きることのない欲求を満たすためにテクノロジー、リソースを使うのではなく、新しい考え方が必要だ。オープンソースやDIYといった従来の大量生産主義、賃金労働性とは異なる仕組みに、新しい文明のヒントがあるかもしれない。

[TED] Elizabeth Gilbert: Success, Failure and the Drive to Keep Creating

自分のふるさと -- 自分よりも愛するもの -- を見つけなければならない。
いつか”ふるさと”から引き離されるときが来るだろう。それは大きな成功によってかもしれないし、大きな失敗によってかもしれない。
そのときが来たら、できるだけ迅速にそしてスムーズに、自分の”ふるさと”に戻らなければならない。

[NewLang] Learn Scala(3)

 Scalaの勉強３回目です。
前回チュートリアルサイトを読破しましたので、今回から以下の本を読んでいくことにしました。



最初の方は比較的易しいのでChapter2まで読みました。
練習問題の回答を載せようと思いましたが、それだと芸がないので自分で問題を作って解いてみました。

1. Int型の配列を受け取り配列内の要素の最大値を返す関数を定義せよ。関数のシグネチャはdef max(x : Array[Int]) : Intとする。
2. 関数fと非負整数nを受け取り、関数f^n（関数fをn回適用する）を返す関数を定義せよ。関数のシグネチャはdef apply[A](f: A => A, n: Int) : A => Aとする。

以下サンプル回答です。

package chapter2

object Problem1 {
  
  def max(x : Array[Int]) : Int = {
    
    @annotation.tailrec
    def go(i: Int, acc: Int) : Int = {
      if (i == x.length) acc
      else if (acc > x(i)) go(i+1, acc)
      else go(i+1, x(i))
    }
    
    go(1, x(0))
  }
  
  def main(args: Array[String]) : Unit = {
    println(max(Array(2, 3, 1))) 
    println(max(Array(100)))
  }  
}

package chapter2

object Problem2 {
  
  def apply[A](f: A => A, n: Int) : A => A = {
    @annotation.tailrec
    def go(acc: A => A, m: Int) : A => A = {
      if (m == 0) x => acc(x)
      else go(x => f(acc(x)), m-1)
    }
    go(x => x, n)
  }
  
  def main(args: Array[String]) : Unit = {
    val f = apply[Int](_ + 2, 5)
    val g = apply[Int](_ * 2, 10)
        
    println(f(1))
    println(g(10))
    
  }  
}

[Coursera] Game Theory Week 4: Extensive-Form Games

  Took the 4th week's lecture of "Game Theory." I am half way to the completion and the course is getting difficult now.

Results:

• Video Lectures: All seen and understood
• In-Video Quizz 5/5 (Passed)
• Problem Sets 6/6 (Passed)

What I Learned:

• normal form game vs extensive form game
• perfect information game vs imperfect information game
• pure strategy and Nash equilibrium in extensive form game
• induced normal form 
• sub-game perfect equilibrium
• back induction for finding sub-game perfect equilibrium
• mix strategy vs behavioral strategy

[NewLang] Learn Scala(2)

  Scalaの勉強２回目です。前回に引き続き、LEARN SCALAR PROGRAMMINGを読みました。

学んだこと

• クロージャが使える
• Javaで使えるすべてのクラスを利用できる
• StringはJavaのStringと同じ
• 配列はvar z = new Array[String](3)のように宣言
• 配列を初期化する場合は、var z = Array(“hoge”, “fuga”, “bar”)のように宣言
• 多次元配列は、var z = Array.ofDim[int](3,3)
• collectionsにはstrict/lazyがある
• collectionsにはmutable/immutableがある
• 継承できるクラスの個数は1個
• クラスはstaticメンバーを持てない
• シングルトンなクラスはobjectキーワードで作成
• traitはシグネチャを定義する（Javaのabstract classと同様）
• traitは継承と異なり多重ミックスイン可能
• パターンマッチングをサポート
• 正規表現をサポート
• 正規表現パターンはJavaのものを使用
• 例外処理はtry/catch/finallyで行い、例外の種類はパターンマッチで識別する
• extractorはunapplyというメソッドを持つ。
• extractorはオブジェクトから値を取り出すときに使われ、パターンマッチで使用できる。

[TED] Barry Schwartz: The way we think about work is broken

　TEDでリスニング３週目。今回は社会学・人類学系の話を聞いてみた。
英語は聞き取りやすいのだが、内容が難しく、彼の主張を正しく理解できたのかどうか自信はないが、要約を載せておく。

我々はなぜ働くのだろうか？お金のためだろうか？

なぜ、この惑星の大多数は、単調で無意味で活力を奪われるような労働を行っているのだろうか？なぜお金のためだけにそこまでするのだろうか？

我々が働く理由はテクノロジーである。ここで言うテクノロジーとは、いわゆる物のテクノロジーではなく、”Idea Technology”である。これは人間の物事の考え方、物事への反応を支配する社会的な仕組みのことである。

イケてない物のテクノロジーは自然に淘汰されるが、偽りのIdea Technologyは消えてなくならない。なぜなら、それが正しいものだと人々が思い込んでしまうと、それに従って世の中の仕組みが作られてしまうからだ。

産業革命によって、賃金の他には何も得られない工場制度が生まれた。アダム・スミスは人間は元来怠惰な生き物で、インセンティブを与えないと何もしないと考えたのだ。人々は次第にその制度に順応していき、仕事から当然えられるはずの喜びを奪われてしまった。工業化が進み豊かになったが、大切なものを失ってしまった。アダム・スミス自身もこの状況に気づき、工場労働者のことを「これ以上ないほど愚かになってしまった人間」と呼んだ。

しかし失望することはない。人間の性質というのは、我々によって考えられた人間を説明するための定理によって変えることができる。人間は"unfinished animal"である。人間の性質が社会の仕組みをつくり、我々はその中で生活をしている。その人間の性質とは、我々が仕事や生活の仕組みをデザインすることによって、形成されるものだ。

あなたは考えなければいけない。あなたの組織の中でどのような人間の性質をデザインしたいのかを。