2010年3月27日土曜日

おみくじ

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

Q:10種類のおみくじ(それぞれ無限大数入っている)で、10種類、全てを引くのに要する回数の期待値は?

 ガチャガチャでも、野球カードでも何でもいいです。10種類のcharacterがあって、全て揃うには、いくら注ぎ込まなければならないか?ということです。
 そして、N種類の場合は?

import sys
import random

def isCompleted(xs):
  b = True
  for x in xs:
    b = b and x
    if not b:
      return False
  return True

def experiment(N):
  count = 0
  xs = [False for x in range(N)]
  while not isCompleted(xs):
    xs[random.randint(0, N - 1)] = True
    count += 1
  return count

assert not isCompleted([False])
assert isCompleted([True, True])
assert not isCompleted([True, False])

N = 10
print experiment(N)

sum = 0.0
trial = int(sys.argv[1])
for i in range (trial):
  sum += experiment(N)
print sum / trial
実行結果
[nori@shinano]~/Desktop/study/python% python lotto.py 10000
46
29.1639
よさげ。ただ収束が非常に遅い。

2010年3月24日水曜日

封筒の話(さらに続き)

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

ここで、封筒に入れる金額は、ホストは以下のように決定します。ホストは、さいころを5か6が出るまで連続して振ります。この時、1〜4の目が出た数をn とします。

「この時、1〜4の目が出た回数をn とします」と読まないといけないのね。
しかしでかい方をあけた確率が0.6になってる。変すぎ。
[nori@shinano]~/Desktop/study/python/hack% python two2envelopes.py 100000
[1, 16685, 16685, 33370, 0] 2.0 0.0
[2, 27613, 55226, 60634, 16606] 1.09792489045 0.601383406367
[4, 18749, 74996, 82270, 11287] 1.09699183956 0.60200544029
[8, 12305, 98440, 107588, 7441] 1.09292970337 0.604713531085
[16, 8234, 131744, 144736, 4948] 1.09861549672 0.600923002186
[32, 5508, 176256, 194928, 3283] 1.10593681917 0.596042120552
[64, 3664, 234496, 263456, 2141] 1.1234989083 0.584334061135
[128, 2399, 307072, 337280, 1442] 1.09837432263 0.60108378491
[256, 1624, 415744, 453248, 985] 1.09020935961 0.606527093596
[512, 1074, 549888, 599808, 651] 1.09078212291 0.606145251397
[1024, 729, 746496, 821760, 437] 1.10082304527 0.599451303155
[2048, 469, 960512, 1048576, 284] 1.09168443497 0.605543710021
[4096, 296, 1212416, 1374208, 171] 1.13344594595 0.577702702703
[8192, 197, 1613824, 1667072, 127] 1.03299492386 0.644670050761
[16384, 162, 2654208, 3072000, 91] 1.15740740741 0.561728395062
[32768, 96, 3145728, 3342336, 60] 1.0625 0.625
[65536, 79, 5177344, 6324224, 41] 1.22151898734 0.518987341772
[131072, 39, 5111808, 5111808, 26] 1.0 0.666666666667
[262144, 27, 7077888, 7864320, 16] 1.11111111111 0.592592592593
[524288, 21, 11010048, 11796480, 13] 1.07142857143 0.619047619048
['sum', 99970, 40770819, 44700102]
修正後のコード
import sys
import random

class Die:
  def roll(self):
    r = random.randint(1, 6)
    assert r > 0
    assert r < 7
    return r
  def odd(self):
    return bool(random.randint(0, 1))

die = Die()

class Envelope:
  def __init__(self):
    r = die.roll()
    n = 0
    while r < 5:
      n += 1
      r = die.roll()
    self.values = (1 << n, 1 << (n + 1))
    self.first_opend = die.odd()

  def open(self):
    return self.values[self.first_opend]

  def swap(self):
    return self.values[not self.first_opend]
    

def experiment(t):
  result = {}
  for i in range(t):
    e = Envelope()
    v = e.open()
    s = e.swap()
    r = result.get(v, None)
    if r is None:
      r = [0, 0, 0, 0] #occurence, none-swap case, swap case, respectivly
    r[0] += 1
    r[1] += v
    r[2] += s
    r[3] += int(e.first_opend)
    result[v] = r
  return result

r = experiment(int(sys.argv[1]))

xs = [[i, r[i][0], r[i][1], r[i][2], r[i][3]] for i in r]
xs.sort(key=lambda x: x[0])

total = ['sum', 0, 0, 0]
for i in range(20):
  r=xs[i]
  total[1] += r[1]
  total[2] += r[2]
  total[3] += r[3]
  print r, 1.0*r[3]/r[2], 1.0*r[4]/r[1]
print total

封筒の話(続き)

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
r[3]/r[2]を計算するようにしてみた。あとそれからn=20までを対象にした。それ以上は外れ値として無視(頻度が低いため、十分な試行数がないから)
しかし2の時、交換すると減るという変な結果が出てるな。

[nori@shinano]~/Desktop/study/python/hack% python two2envelopes.py 100000
[1, 16715, 16715, 33430, 0] 2.0 0.0
[2, 19473, 38946, 27669, 16741] 0.710445231859 0.85970317876
[4, 5991, 23964, 31428, 2750] 1.3114672008 0.459021866133
[8, 7006, 56048, 73312, 3232] 1.30802169569 0.46131886954
[16, 8180, 130880, 172504, 3719] 1.31803178484 0.454645476773
[32, 6796, 217472, 222064, 4435] 1.02111536198 0.652589758682
[64, 4601, 294464, 364864, 2334] 1.2390784612 0.507281025864
[128, 4500, 576000, 697152, 2369] 1.21033333333 0.526444444444
[256, 4016, 1028096, 1234432, 2140] 1.20069721116 0.532868525896
[512, 3305, 1692160, 1935104, 1887] 1.14357034796 0.570953101362
[1024, 2764, 2830336, 3424256, 1456] 1.20984081042 0.526772793054
[2048, 2332, 4775936, 5721088, 1247] 1.19789879931 0.534734133791
[4096, 2095, 8581120, 10489856, 1086] 1.22243436754 0.518377088305
[8192, 1740, 14254080, 16429056, 983] 1.1525862069 0.564942528736
[16384, 1504, 24641536, 30138368, 779] 1.22307180851 0.51795212766
[32768, 1294, 42401792, 51724288, 673] 1.21986089645 0.520092735703
[65536, 1133, 74252288, 88834048, 607] 1.19638128861 0.53574580759
[131072, 984, 128974848, 148832256, 555] 1.15396341463 0.564024390244
[262144, 763, 200015872, 238026752, 412] 1.19003931848 0.53997378768
[524288, 682, 357564416, 438304768, 352] 1.22580645161 0.516129032258

どういう訳だか、2が出たときに、大きな数値が入っている封筒を高確率で先に開けてしまう。
import sys
import random

class Die:
  def roll(self):
    r = random.randint(1, 6)
    assert r > 0
    assert r < 7
    return r
  def odd(self):
    return bool(random.randint(0, 1))

die = Die()

class Envelope:
  def __init__(self):
    r = die.roll()
    n = 0
    while r < 5:
      n += r
      r = die.roll()
    self.values = (1 << n, 1 << (n + 1))

  def open(self):
    self.first_opend = die.odd()
    return self.values[self.first_opend]

  def swap(self):
    return self.values[not self.first_opend]
    

def experiment(t):
  result = {}
  for i in range(t):
    e = Envelope()
    v = e.open()
    s = e.swap()
    r = result.get(v, None)
    if r is None:
      r = [0, 0, 0, 0] #occurence, none-swap case, swap case, respectivly
    r[0] += 1
    r[1] += v
    r[2] += s
    if e.first_opend:
      r[3] += 1
    result[v] = r
  return result

r = experiment(int(sys.argv[1]))

xs = [[i, r[i][0], r[i][1], r[i][2], r[i][3]] for i in r]
xs.sort(key=lambda x: x[0])

total = ['sum', 0, 0, 0]
for i in range(20):
  r=xs[i]
  total[1] += r[1]
  total[2] += r[2]
  total[3] += r[3]
  print r, 1.0*r[3]/r[2], 1.0*r[4]/r[1]
print total

2つの封筒問題 - バリエーションB をシミュレートする

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
2つの封筒問題 - バリエーションB をシミュレートするプログラムを書いてみた。なーんか違う気がするんですけどね。

import sys
import random

class Die:
  def roll(self):
    return random.randint(1, 6)

die = Die()

class Envelope:
  def __init__(self):
    r = die.roll()
    n = 0
    while r < 5:
      n += r
      r = die.roll()
    self.values = (1 << n, 1 << (n + 1))

  def open(self):
    self.first_opend = die.roll() % 2
    return self.values[self.first_opend]

  def swap(self):
    return self.values[not self.first_opend]
    

def experiment(t):
  result = {}
  for i in range(t):
    e = Envelope()
    v = e.open()
    s = e.swap()
    r = result.get(v, None)
    if r is None:
      r = [0, 0, 0] #occurence, none-swap case, swap case, respectivly
    r[0] += 1
    r[1] += v
    r[2] += s
    result[v] = r
  return result

r = experiment(int(sys.argv[1]))

xs = [[i, r[i][0], r[i][1], r[i][2]] for i in r]
xs.sort(key=lambda x: x[0])

total = ['sum', 0, 0, 0]
for r in xs:
  total[1] += r[1]
  total[2] += r[2]
  total[3] += r[3]
  print r
print total
実行結果
[nori@shinano]~/Desktop/study/python/hack% python two2envelopes.py 1000  
[1, 193, 193, 386]
[2, 185, 370, 269]
[4, 56, 224, 304]
[8, 52, 416, 496]
[16, 84, 1344, 1824]
[32, 72, 2304, 2304]
[64, 50, 3200, 4192]
[128, 59, 7552, 8000]
[256, 37, 9472, 12416]
[512, 21, 10752, 10752]
[1024, 31, 31744, 45056]
[2048, 21, 43008, 46080]
[4096, 13, 53248, 51200]
[8192, 26, 212992, 241664]
[16384, 16, 262144, 303104]
[32768, 11, 360448, 573440]
[65536, 9, 589824, 589824]
[131072, 13, 1703936, 2228224]
[262144, 8, 2097152, 1835008]
[524288, 4, 2097152, 2621440]
[1048576, 2, 2097152, 4194304]
[2097152, 5, 10485760, 14680064]
[4194304, 2, 8388608, 10485760]
[8388608, 6, 50331648, 62914560]
[16777216, 4, 67108864, 83886080]
[33554432, 2, 67108864, 134217728]
[67108864, 4, 268435456, 234881024]
[134217728, 2, 268435456, 536870912]
[268435456, 1, 268435456, 134217728]
[1073741824, 2, 2147483648, 1073741824]
[2147483648, 1, 2147483648, 4294967296]
[4294967296, 2, 8589934592, 10737418240]
[17179869184, 1, 17179869184, 34359738368]
[68719476736, 1, 68719476736, 34359738368]
[1099511627776, 1, 1099511627776, 549755813888]
[281474976710656, 2, 562949953421312, 703687441776640]
[2251799813685248, 1, 2251799813685248, 1125899906842624]
['sum', 1000, 2815949081296883, 1830223154961391]

2010年3月21日日曜日

twitter searchからデータを拾ってほげほげする話(2)

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
http://viratter.jp/なるものを発見し、やる気喪失。
のこりの残骸を放置する。ahooonがアカウント削除したおかげで、あとからデータとるやり方では
どうしても追跡できない部分ができてしまう。viratterは定期的にデータをとっているので
そのようなことは起こらない。しかしどんだけのtweetをDLして持っているのだろう?

どうguessして埋めるかを考えるモノまた楽しみではあるが。

#!/usr/bin/python
# coding:utf8

import pickle
import re

#def make_strucure(

f = open('data.pkl')
try:
  all = pickle.load(f)
finally:
  f.close()


peopleTweet = {}
users = {}

for tweet in all.values():
  user_id = tweet['from_user_id']
  tweeted = peopleTweet.get(user_id, None)
  if not tweeted:
    tweeted = []
  tweeted.append(tweet['id'])
  peopleTweet[user_id] = tweeted

  user_name = tweet['from_user']
  possible = users.get(user_name, None)
  if not possible:
    possible = []
  if user_id not in possible:
    possible.append(user_id)
  users[user_name] = possible


USERNAME_PATTERN = r'(?P[_A-Za-z0-9]+)'
RETWEET_PATTERN = r'(RT )?@' + USERNAME_PATTERN + r':'

RETWEET_RE = re.compile(RETWEET_PATTERN)

def GuessParent(tweet):
  text = tweet['text']
  m = RETWEET_RE.match(text)
  if not m:
    return None
  n = (m.groupdict()['username']).encode('ascii')
  from_parent = text[len(n):]
  if n not in users:
    #this means that n is a special user ! 
    users[n] = [n,]
  candidates = users[n]
  if not len(candidates) == 1:
    print n, candidates
  c = candidates[0]

  try:
    ts = peopleTweet[c]
  except:
    return c #ugh!
    
  for t in ts:
    t = all[t]
    if t['text'].startswith(from_parent):
      return t['id']
  return None

RT = {}
for tweet in all.values():
  parent = GuessParent(tweet)
  if not parent:
    continue
  children = RT.get(parent, None)
  if not children:
    children = []
  children.append(tweet['id'])
  RT[parent] = children

print RT

twitter searchからデータを拾ってほげほげする話(1)

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
#!/usr/bin/python
# -*- coding: utf-8 -*-


import sys
import urllib
import simplejson

def printer(d, indent=''):
  if isinstance(d, dict):
    for k in d:
      print indent+k,
      printer(d[k], indent+' ')
  elif isinstance(d, list):
    print indent + 'item in list length =', len(d)
    for i in d:
      print indent+'-'*10
      printer(i, indent+ ' ')
  else:
    print (d, )
    #print indent, str(d).encode('utf-8')

def twittersearch(word, since_id=None, page=None):
  baseurl = "http://search.twitter.com/search.json"
  #param = urllib.urlencode({'q': u'堺市 中学'})
  if page is None:
    page = 1
  param = '?q=%E5%A0%BA%E5%B8%82%20%E4%B8%AD%E5%AD%A6' + '&per_page=20&page=%i'%(page,)
  #param = '?q=%E5%A0%BA%E5%B8%82%20%E4%B8%AD%E5%AD%A6' + '&since_id=%s'%(since_id,) #ugh!


  print >> sys.stderr, 'retreiving:', param
  h = urllib.urlopen(baseurl + param)
  return simplejson.load(h)


all = {}

since_id = None
page = 1
try:
  while True:
    result = twittersearch(None, since_id, page)
    if 'results' not in result or not len(result['results']):
      break
    #since_id = result['max_id']
    for item in result['results']:
      all[item['id']] = item
      if not since_id or int(item['id']) < int(since_id):
        since_id = item['id']
    printer(result)
    page += 1
finally:
  print len(all)
  print 'done'

since_idが使われていなかったり、()で囲ってprintしたりしているのはまあ、そういうモンだ