麻雀の待ちリストアップ 「あなたのスキルで飯は食えるか？」より

同期に触発されて、麻雀の待ちを列挙するプログラムを書いてみた。
（ただし、字牌無し、マンズのみ、七対子非対応版）

また、元ネタ（※）を読んでいなかったので、出力形式がかなり要求仕様と異なる。
（※ http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html）

実行例

C:\etc\src\python>python majung_simple.py 1112345678999
set([1, 2, 3, 4, 5, 6, 7, 8, 9])

C:\etc\src\python>python majung_simple.py 1232344562226
set([3, 6])

ソース（所要時間１時間半くらい）

#! -*- encoding=utf-8 -*-
#! -*- encoding=utf-8 -*-

# 標準入力を扱うため、sysをインポート
import sys

################################################################
# 標準入力を整形し、メインの再帰関数（list_mati）を呼び出す    #
################################################################

def main():
  # 初期化
  li = map(lambda n: int(n), list(sys.argv[1]))
  li.sort()
  print list_mati(li)


################################################################
# メインの再帰関数                                             #
# 渡された牌リストを調べ                                       #
# ・メンツが含まれない場合、待ちを調べる                       #
# ・メンツが含まれない場合、メンツを取り除いた牌リストを用いて #
# 　自身を再帰的に呼び出す                                     #
################################################################

def list_mati(li):

  rtn = set([])

    ###################################################
    # メンツが含まれない場合（牌が１，２枚だった場合）#
    ###################################################

  # 残り1牌だった場合、その牌を返す
  if len(li) == 1:
    return set([li[0]])

  # 残り2牌だった場合
  elif len(li) == 2:
    # トイツができていた場合
    if li[0] == li[1]:
      rtn.add(li[0])
    # ターツができていた場合
    elif li[0]+1 == li[1]:
      if li[0] != 1:
        rtn.add(li[0]-1)
      if li[1] != 9:
        rtn.add(li[1]+1)
    # カンチャン待ちの場合
    elif li[0]+2 == li[1]:
      rtn.add(li[0]+1)
    # 役を作成出来ない場合
    else:
      pass
  else:

    ###################################################
    # メンツが含まれる可能性がある場合                #
    #（牌が３枚以上だった場合）                       #
    # ※ただし、牌が０枚だった場合もここで処理される  #
    ###################################################

    # 次局面（牌リスト）を列挙する

    if len(li) % 3 == 1:
      # まだターツを取り除いていない場合
      # ターツを取り除いた各局面につき再帰する
      for p in enumerate_toitsu_del_situations(li):
        rtn |= list_mati(p)
    # シュンツを取り除いた各局面につき再帰する
    for p in enumerate_shuntsu_del_situations(li):
      rtn |= list_mati(p)
    # コーツを取り除いた各局面について再帰する
    for p in enumerate_kohtsu_del_situations(li):
      rtn |= list_mati(p)

  # 待ち牌のセットを返す
  return rtn

##################################################################
# 与えられた牌リストについて、メンツ（またはコウツ）を取り除いた #
# 牌リストのリストを返すメソッド群                               #
##################################################################

def enumerate_toitsu_del_situations(li):
  rtn = []
  for toex in enumerate_toitsu(li):
    li_aft = li[:]
    li_aft.remove(toex)
    li_aft.remove(toex) 
    rtn.append(li_aft)
  return rtn

def enumerate_shuntsu_del_situations(li):
  rtn = []
  for toex in enumerate_shuntsu(li):
    li_aft = li[:]
    li_aft.remove(toex)
    li_aft.remove(toex+1)
    li_aft.remove(toex+2) 
    rtn.append(li_aft)
  return rtn

def enumerate_kohtsu_del_situations(li):
  rtn = []
  for toex in enumerate_kohtsu(li):
    li_aft = li[:]
    li_aft.remove(toex)
    li_aft.remove(toex)
    li_aft.remove(toex) 
    rtn.append(li_aft)
  return rtn

##################################################################
# 与えられた牌リストについて、メンツ（またはコウツ）を           #
# 列挙するメソッド群                                             #
# ※ただし、返り値は各メンツ（またはコウツ）の先頭牌である       #
# 例）                                                           #
#   enumerate_shuntsu([1,2,3,4])　→　[1,2]                      #
##################################################################

def enumerate_toitsu(li):
  rtn = set([])
  for i in range(0, len(li)-1):
    if li[i] == li[i+1]:
       rtn.add(li[i])
  return rtn

def enumerate_shuntsu(li):
  set0 = set(li)
  set1 = set(map(lambda x: x-1, li))
  set2 = set(map(lambda x: x-2, li))
  return set0 & set1 & set2

def enumerate_kohtsu(li):
  rtn = set([])
  for i in range(0, len(li)-2):
    if li[i] == li[i+2]:
       rtn.add(li[i])
  return rtn


# main関数を呼び出す
if __name__ == '__main__': main()

Solving "Canterbury Puzzles" by Python (2)

続き。今回は、ターン制ゲームの実装。

109. 三目並べ

三目並べ、先手が勝つか、後手が勝つか、それとも引き分けになるか、を分析する問題。

#! -*- encoding=utf-8 -*-

#
# 109. Noughts and Crosses
#

import copy
import math

def main():
  f = Field()
  print who_wins(f, 1)

## field（盤面）とturn（手番、1または-1）とを受け取り、
## 勝利する手が有れば turn を、
## 勝利的ないが引き分けが可能なら 0 を返す。

def who_wins(field, turn):
  if field.check() == change_turn(turn):
    # 既に勝負が付いている場合
    return change_turn(turn)
  elif len(field.unoccupied()) == 0:
    # 盤面が埋まってしまった場合（引き分け）
    return 0
  else:
    rtn = change_turn(turn)

    # 可能な手ごとに、再帰的に who_wins を呼び出す
    for hand in field.unoccupied():
      next_field = copy.deepcopy(field)
      next_field.set(hand[0], hand[1], turn)
      w = who_wins(next_field, change_turn(turn))

      if math.fabs(rtn - turn) > math.fabs(w - turn):
        # 探索済みの手より良い手が見つかった場合
        rtn = w
      if rtn == turn:
        # 勝利する手が見つかった場合
        break
    return rtn

def change_turn(turn):
  return 0 - turn


## 盤面を表すクラス

class Field():

  # 全面を0（空白）で初期化する
  def __init__(self):
    self.field = [[0,0,0],[0,0,0],[0,0,0]]

  # 特定の枡に値を設定する
  def set(self,x,y,turn):
    self.field[x][y] = turn

  # 盤面を表示する
  def show(self):
    for column in self.field:
      print column

  # 値が設定されていない枡のリストを返す
  def unoccupied(self):
    rtn = []
    for i in range(0,3):
      for j in range(0,3):
        if self.field[i][j] == 0:
           rtn.append((i,j))
    return rtn

  # 揃っているラインが有った場合、そのラインの値（1または-1）を返す
  # 揃っているラインが無い場合、0を返す
  def check(self):

    # 縦のラインをチェック
    if self.field[0][0] == self.field[1][0] == self.field[2][0] != 0:
      return self.field[0][0]
    elif self.field[0][1] == self.field[1][1] == self.field[2][1] != 0:
      return self.field[0][1]
    elif self.field[0][2] == self.field[1][2] == self.field[2][2] != 0:
      return self.field[0][2]

    # 横のラインをチェック
    elif self.field[0][0] == self.field[0][1] == self.field[0][2] != 0:
      return self.field[0][0]
    elif self.field[1][0] == self.field[1][1] == self.field[1][2] != 0:
      return self.field[1][0]
    elif self.field[2][0] == self.field[2][1] == self.field[2][2] != 0:
      return self.field[2][0]

    # 斜めのラインをチェック
    elif self.field[0][0] == self.field[1][1] == self.field[2][2] != 0:
      return self.field[0][0]
    elif self.field[0][2] == self.field[1][1] == self.field[2][0] != 0:
      return self.field[0][2]

    else:
      return 0

  # 盤面にユニークなIDを割り当てる（本門んは使用せず）
  def get_id(self):
    rtn = 0
    for i in range(0,3):
      for j in range(0,3):
        rtn += (self.field[i][j] + 1) * 3**(3*i + j)
    return rtn

if __name__ == '__main__': main()

Solving "Canterbury Puzzles" by Python (1)

カンタベリー・パズル
http://djm.cc/library/The_Canterbury_Puzzles_Dudeney_edited.pdf

のいくつかの問題を、Pythonで力技でといてみる。

64. 暴走車

1から始まる5桁の数で、
　・最初の2桁 * 次の3桁 を並べ替えると 元の5桁 になる
ような数を求める問題。

#! -*- endocing=utr-8 -*-

#
# 64. The Runaway Motor-Car. 
#

def main():
  for i in range(11,19):
    for j in range(111,999):
      if j % 100 < 10 or j % 10 == 0:
        continue
      if sorted(list(str(i)) + list(str(j))) \
           == sorted(list(str(i * j))):
        print (1000 * i + j)

if __name__ == '__main__': main()

101. 3台の自動車

要するに、78*345=26910 のように
　・0〜9を全て含む数の組み合わせで（2桁、3桁、5桁）
　・最初の2桁 * 次の3桁 = 最後の5桁　となっている
もののうち
　・最初の2桁が、次の3桁の約数になっているもの
を求める問題。

#! -*- endocing=utr-8 -*-

#
# 101. The Three Motor-Cars. 
#

def main():
  rslt = permutate(range(0,10))
  for t in rslt:
    if ltoi(t,0,2) * ltoi(t,2,3) == ltoi(t,5,5) \
       and ltoi(t,2,3) % ltoi(t,0,2) == 0:
      print t

## Enumerate the all permutation of given list. 
def permutate(l):
  if len(l) == 1:
    return [l]
  else:
    result = []
    for idx in range(0, len(l)):
      l_dup = list(l)
      h = l_dup.pop(idx)
      for xs in permutate(l_dup):
        result.append([h] + xs)
    return result

## Convert the sub-list of given list into integer.
def ltoi(list, start, len):
  result = 0
  for i in range(0,len):
    result += list[start + i] * (10**(len-i-1))
  return result

if __name__ == '__main__': main()

【読書】「レガシーコード改善ガイド」

マインドマップっぽく目次とキーワードを並べてみた。

Hastter（Twitterの投稿をHaskellで解釈して返すBOT） ver0.1 ←現在は稼動していません

状況

• • とりあえず　一　度　動　い　た
  • 『例外処理については、意識していませんが。』
  • いくつかバグ（仕様）あり
    • ASCIIに無い文字が入ってくると落ちる。（日本語化してないUbuntuを使ってるからだろうか）
    • サニタイジングしていないので、嫌な事が起こるかも。（EC2だし、ダメージは無いけど）
    • よく分からないがたまに落ちる。
    • よく分からないがレスポンスを返さない時がある。（主処理に致命的なバグがある気がする）
    • maxId、もっと賢い処理方法が有る気がする。（memcacheとか？）

simple_bot.py

import twitter           # TwitterAPI
import time              # 時刻処理用
import re                # 正規表現処理用
import subprocess        # 外部プロセス呼び出し用
import xml.sax.saxutils  # HTMLエスケープ系処理用

USER="YOUR_TWITTER_USER"
PASS="YOUR_TWITTER_PASS"
BASEDIR="/home/ubuntu/scripts/python"

api=twitter.Api(username=USER, password=PASS)

#############################################
# １つのつぶやき（tweet）を解析し、返信する #
#############################################
def reply_tweet(tweet):
  # "@YOUR_TWITTER_USER" のような返信シンボルを削除
  command = re.compile('@' + USER + ' *', re.I).sub('', xml.sax.saxutils.unescae(tweet.text))
  # バックスラッシュをエスケープしない（やや怪しい処理）
  command = re.compile('\\\\').sub('\\\\', command)
  # tweet本文をHaskell文とみなし評価する
  result = execute_haskell(command)
  # 返信シンボルを付加し、返信をTwitterに投稿
  replyStr = "@" + tweet.GetUser().screen_name + " " + result
  api.PostUpdate(replyStr)

#########################################################
# 文字列をHaskell文として評価し、結果を文字列として返す #
#########################################################
def execute_haskell(command):
  quitStr = ":quit\n" # Haskell処理系（ghci）から抜けるためのコマンド
  # Haskell処理系（ghci）プロセスを呼び出す
  p = subprocess.Popen("ghci", shell=True, cwd="/", stdin=subprocess.PIPE,
                       stdout=subprocess.PIPE, stderr=subprocess.STDOUT, close_fds=True)
  p.stdin.write(command + "\n" + quitStr)
  # 処理結果3行目のみ取得したいので、先頭2行はスキップ
  p.stdout.readline()
  p.stdout.readline()
  # Haskell処理系のプロンプト部分を削除
  return re.compile(r'Prelude> *').sub('', p.stdout.readline()).rstrip()

##########
# 主処理 #
##########
# 同じtweetを2度処理しないよう、これまで処理した最大IDを控えておく。
f_in = open(BASEDIR + '/maxId.txt', 'r')
maxId = int(f_in.readline())
f_in.close()
# 90秒ごとに返信を取得し、それぞれを解析し、返信する。
while(1):
  # 返信は投稿日時（降順）で返されるので、昇順にした後に順次処理。
  for i in reversed(api.GetReplies(since_id=str(maxId))):
    if maxId < i.GetId():
      maxId = i.GetId()
      f_out = open(BASEDIR + '/maxId.txt', 'w')
      f_out.write(str(maxId))
      f_out.close()
      reply_tweet(i) # change if the function changed
  time.sleep(90)

上のスクリプトが落ちた時に再起動するスクリプト。
Cronで

* * * * * sh /home/ubuntu/scripts/sh/restart_bot.sh >/dev/null 2>&1

みたいにしてみたが、shをよく分かっていない。多分ちゃんと動いていない。

restart_bot.sh

#!/bin/sh

psCount=`ps aux | grep -c simple_bot.py`
if [ $psCount -ge 1 ]
then
  date >> /home/ubuntu/scripts/sh/log.txt
  echo "No problem" >> /home/ubuntu/scripts/sh/log.txt
else
  python /home/ubuntu/scripts/python/simple_bot.py & > /home/ubuntu/scripts/python/simple_bot.log 2>&1
  date >> /home/ubuntu/scripts/sh/log.txt
  echo "Restart simple_bot.py" >> /home/ubuntu/scripts/sh/log.txt
fi

PythonからTwitterを利用するまで

• TweetをHaskell文として評価し結果を返すBOTを作る
  • 環境を準備する
  • BOTを作る　　　　　　　←いまここ
  • Haskellと連携させる

Python用Twitter APIのインストール

せっかくPythonの勉強始めたし、現在構想中のツールもPythonで実装する予定。
Google Codesにホスティングされている Python-Twitter を利用することにする。

$ sudo apt-get install python-simplejson
$ wget http://python-twitter.googlecode.com/files/python-twitter-0.6.tar.gz
$ tar xvf python-twitter-0.6.tar.gz

「python-twitter を使ってみる」（http://techno-st.net/2009/07/04/python-twitter.html）を参考に、フォローユーザの取得、Tweetの発信まで成功。

超単純なBotを記述

自身への@Replyが有った際に何らかの処理をするBot。

import twitter
import time

USER="Hoge"
PASS="Fuga"

api=twitter.Api(username=USER, password=PASS)

def reply_tweet(tweet):
  api.PostUpdate("I've got a message from %s !!" % (tweet.GetUser().screen_name))

maxId = 0

while(1):
  for i in reversed(api.GetReplies()):
    if maxId < i.GetId():
      reply_tweet(i) # change if the function changed
      maxId = i.GetId()
  time.sleep(90)

Amazon EC2 で Ubuntu 確保、Haskellコンパイラ（GHC）の起動まで

【仮想マシンの確保】

ElasticFoxにて適当なimageからInstanceを起動。
Linuxはよう分からんが、開発環境とかの準備が楽そうなのでUbuntu選択
> ubuntu-images-testing-us/ubuntu-hardy-daily-i386-server-20100107.manifest.xml

無事にInstanceにログイン。

【開発環境の準備】（参考　http://www.gabuchan.net/blog/archives/32）

ちょっと色々、参考ページと違うことしなきゃいけなかった。

$ tar xvf ghc-6.8.2-i386-unknown-linux.tar.bz2
$ cd ghc-6.8.2
$ sudo apt-get update
$ sudo apt-get install build-essential
$ sudo apt-get libgmp3c2　　　　　　　　　　　←これしないと、./configureでエラーになる。

$ ./configure　　　　　　　　　　　　　　　　 ←成功
$ sudo make install　　　　　　　　　　　　　 ←成功

お、無事にHaskellインタプリタが起動。

色々したいけど、今日は眠いのでこのへんまで。