さんぷるクリプト

g++でコンパイル

2012-11-15T19:40:00.000+09:00

C++のソースをコンパイルしてみた。

で、通らなかった (p_q､)　なんかなぁ。バージョンは常に新しくしたいから結構あげちゃうんだけど、その度洗礼を受ける感じ？

今回の洗礼は、この2個。

で、環境はAWSのEC2で。
なんでかなぁ。とおもっていても仕方ないので、やっつける (`･ω･´+) ｷﾘｯ
-------------

warning: enumeration value ‘***’ not handled in switch [-Wswitch]

-Wswitch というオプションによって、列挙型の項目すべてが指定されていない為にでる警告。

例えば、enum hoge {1, 2, 3}; とし、switch 文で case 1:... case 3:... のみで case 2:... を書いていない場合、この警告がでる。
default: を使ってしまうと、(書くのを忘れてしまった) case 2: の場合が当てはまり、警告は出ない。
用途によっては意図したものにならない可能性もあるので default を書かずおけば、パターンが確認できたりする。

warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]

-Wparentheses というオプションによって、括弧が省略されているため（優先順位がわからない）にでる警告。

例えば、これだと警告が出ちゃいます。なので・・・・とすると警告が出なくなります。
0x80 | ((0xFC&snd)>>2) これを評価した後で、+0x10 なのかあやふやだからだと思われます。

コンパイルオプションに付いてはこちらを参照
http://gcc.gnu.org/onlinedocs/gcc-4.3.3/gcc/Warning-Options.html
http://www.geocities.jp/woodwood77777/gcc_gnu.htm

-Wall をつけているので、いろいろ警告が出た模様。。。。
headerファイルも変わったみたい。。。
http://gcc.gnu.org/gcc-4.3/porting_to.html
いろいろ大変ですね。おしまい (´･ω･`)

AmazonEC2でEBS

2012-11-06T00:57:00.003+09:00

AmazonEC2で使うストレージにEBSというのがあります。
ここではEBSを使えるようにする二つの方法を＿φ(｡_｡*)ﾒﾓﾒﾓします。
EBSとは Amazon Elastic Block Store の略で、私はイー・ビー・エスっていいます。

二つの方法

新規にVolumeをAttachする場合
snapshotからVolumeを作成しAttachする場合

★共通の注意事項
インスタンスに Attach にできる Volume は同じ availability zone 内に限られるので、作成時に確認する。
パンくず：services > Compute & Networking > EC2
アマゾンウェブサービス　にアクセス。

新規にVolumeをAttachする場合

主に、メインのストレージは既にあってログやバックアップを別のストレージに分ける場合に使用しています。
一般的なWebサービスを提供するインスタンスを作る場合、Root Partition（ルートパーティション）＜OSが入っている部分＞は、32GiBくらいにしておけば十分だと思っているからです。
一概には言えないですけどね (´･ω･`)

新規Volume（ヴォリューム）作成
パンくず（左メニュー）：ELASTIC BLOCK STORE > Volumes

右上メニュー：Create Volume
入力項目：
Size: *** GiB ( GiB / TiB )
Availability Zone: ap-northeast-1a
( ap-northeast-1b / ap-northeast-1b / ap-northeast-1b )
Snapshot: --- No Snapshot ---
Volume Type: Standard
『Yes, Create』
作ったVolumeが何か分かるように名前を付けておく。
できたVolumeを選択すると下段に以下のタブとともに情報が表示される。
[Details] , [Status Checks] , [Monitoring] , [Tags]
パンくず：Tags > Add/Edit Tags
Key=Name , Value=任意の名前 --> Save Tags

インスタンスにAttach（アタッチ）する

右上メニュー：Attach Volume
入力項目：
Volume: vol-******* in <availability zone>
Instances: [Select Instance] in <availability zone>
Device: /dev/sd*
『Yes, Attach』

Volumeを使えるようにする

使えるファイルシステムにフォーマット
マウント
インスタンスを再起動しても自動的にマウントさせる

これで、ディスクが追加されたように使えます (￣ー+￣)

ちなみに、RootPartitionではないのでインスタンスをSTOPしなくても追加されます！

つぎは、snapshotからEBSをつくりRootPartitionにする方法を＿φ(｡_｡*)ﾒﾓﾒﾓします。

snapshotからVolumeを作成しAttachする場合

CのApache-module：：subprocess_env構造体

2012-10-17T17:53:00.006+09:00

r->subprocess_env構造体には何が入っているか調べてみました。
概要
Apacheにはリクエスト毎の情報をもつ request_rec 構造体があります。 subprocess_env構造体は、環境変数の配列です。

include/httpd.h にて、下記のように定義されています。

この subprocess_env構造体は、apr_table_t 型なので、r->headers_in 等と同じように取り出し可能です。
と、いわれましても。。。って思いませんか？

subprocess_env構造体の全容というか、いったい何が入っているのか気になる！

お決まりのようにググってみましたけども、ちっとも出てきません。
そこで全部の中身をだしちゃうコードを書く事にしました。

あとは、きっと環境が変われば中身も変わる物だから、こんなんですよーってのが無いんだと固く信じてます (*´∀`*)
（英語力が他かければドキュメントが見つかるのだろうか？むかしなら「Doxygen」のマニュアルが沢山出てきたんだけどなぁ。。。）

では、早速コードを。さて、何がでてくるかな？
QUERY_STRINGを取って見ているので、適当に ?hoge=bar なんてつけてみる。

■出力結果↓ Σ(゜∀゜ノ)ノマジか！
【NULL】　じゃん。。。なんで？
その辺のサンプルコードってよく書いてあるよね？何が違うんだろう。。。と、思っています？

なんと、これにはちゃんとした訳があります。現時点では当然の振る舞いです。
subprocess_env構造体の値を取得する前に、とある処理を入れてあげないと、KEY=VALの形でデータがsubprocess_env構造体に入ってこないのです。
その処理が。。。【ap_add_cgi_vars関数】です。

では、早速コードに追記して実行してみます。さて、何がでてくるかな？
QUERY_STRINGを取って見ているので、適当に ?hoge=bar なんてつけてみる。
ついでに、REMOTE_ADDRも取ってみましょう (*´∀`*)
■出力結果↓ やったヾ(＠⌒▽⌒＠)ノとれました。
この ap_add_cgi_vars関数は下記のように定義されています。

void ap_add_cgi_vars (request_rec * r )

Add CGI environment variables required by HTTP/1.1 to the request's environment table

Parameters:

the current request

さて、QUERY_STRINGを取得したい場合は、これだけでOKですが、、、、REMOTE_ADDRを取得したい人はどうしましょう？【NULL】　じゃん。。。なんで？
取れない？？

なんて事はありません (*´∀`*)ちゃんと取得できるようになっています。
その処理が。。。【ap_add_common_vars関数】です。

さてさて、コードに追記して実行してみます。さて、取れるでしょうか？
QUERY_STRINGを取って見ているので、適当に ?hoge=bar なんてつけてみる。
ついでに、REMOTE_ADDRも取ってみましょう (*´∀`*)
■出力結果↓ やったヾ(＠⌒▽⌒＠)ノ完璧。
この ap_add_common_vars関数は下記のように定義されています。

void ap_add_common_vars (request_rec * r )

Add common CGI environment variables to the requests environment table

Parameters:

the current request

これで必要な情報を取る事ができますね〜 (*´∀`*)
おしまい。

AmazonEC2を使ってみる

2012-10-17T16:30:00.000+09:00

0.アカウントを作る

アマゾンウェブサービス　にアクセスして作成。
この時、クレジットカードが無いと使う事ができないので手元に用意しておくしかない。

1.インスタンスを立ち上げる

2.まずはじめにやる事

■rootのパスワード設定 ■タイムゾーンの設定 [以後変更されないように設定] 変更されないようにこうすれば良いっていろんなサイトにあるのだけど、今のところ効かない・・・・・

■ホスト名の変更
■swap領域の確保
メモリの2倍で。Diskの小さいのはメモリと同じくらいかなぁ。これはラージの場合。
smallは何かしらデフォルトで確保されているので、とくに設定は変えないでおいてみた。
・領域の確保　・swap領域として初期化（まだ認識はされない）・swapとして有効に　・再起動しても確保されるように　

初めて symfony でプロジェクトを作ってみた

2012-05-23T20:03:00.001+09:00

PHPのフレームワークを使ってみた。あんまり好きじゃないけどお仕事ですからね〜 (>_<)

1．取りあえずrootで作っちゃう

⇒　本当はアプリケーションアカウントを作って実施すべし。

$ sudo su -

2．プロジェクト用のディレクトリを作成

# cd /var/www/html/
# mkdir world
# cd world/

3．プロジェクト（スケルトン）作成

# symfony init-project world
  Task "init-project" is not defined.

ってエラーが出たら、v1.4系なのにv1.0系のコマンドを使った証拠。やりなおし。バージョン調べたければ事前に「$ symfony -V」してみる。

# symfony generate:project world
>> file+     /var/www/html/world/symfony
....
>> tokens    /var/www/html/world/config/doctrine/schema.yml
>> tokens    /var/www/html/world/lib/form/BaseForm.class.php
#

いろいろいる物を作ってくれる。何も無かったところがこんな感じに。

# ls -l
drwxr-xr-x 2 root root 4096 May 23 11:26 apps
drwxrwxrwx 2 root root 4096 May 23 11:26 cache
drwxr-xr-x 3 root root 4096 May 23 11:26 config
drwxr-xr-x 3 root root 4096 May 23 11:26 data
drwxr-xr-x 3 root root 4096 May 23 11:26 lib
drwxrwxrwx 2 root root 4096 May 23 11:26 log
drwxr-xr-x 2 root root 4096 May 23 11:26 plugins
-rwxrwxrwx 1 root root  446 May 23 11:26 symfony
drwxr-xr-x 5 root root 4096 May 23 11:26 test
drwxr-xr-x 6 root root 4096 May 23 11:26 web

4．アプリケーション設置

# symfony generate:app traveler
>> dir+      /var/www/html/world/apps/traveler/modules
....
>> tokens    /var/www/html/public_html/lib/form/BaseForm.class.php
#

なんかまた作ってくれる。

# ls -l ../world/apps/traveler/
drwxr-xr-x 2 root root 4096 May 23 16:41 config
drwxr-xr-x 2 root root 4096 May 23 16:41 i18n
drwxr-xr-x 2 root root 4096 May 23 16:41 lib
drwxr-xr-x 2 root root 4096 May 23 16:41 modules
drwxr-xr-x 2 root root 4096 May 23 16:41 templates

5．開発用ファイルを使えるようにする

# vi web/traveler_dev.php
この部分をコメントアウト
if (!in_array(@$_SERVER['REMOTE_ADDR'], array('127.0.0.1', '::1')))
{
  die('You are not allowed to access this file. Check '.basename(__FILE__).' for more information.');
}

コメントアウトしないと開発環境のアプリケーションにアクセスした時に、 http://hogehoge.jp/hoge1_dev.php/ 「You are not allowed to access this file. Check traveler_dev.php for more information.」ってでて見えない。

6．Apacheの設定

# vi /etc/httpd/conf.d/vhost.conf
NameVirtualHost *:80


  ServerName world.hoge.jp
  DocumentRoot "/home/web-apps/world/web"
  DirectoryIndex index.php
  
    AllowOverride All
    Allow from All
  

  Alias /sf /usr/share/pear/data/symfony/web/sf
  
    AllowOverride All
    Allow from All

あとは、Apache起動させてOK.おなじみの画面でたし (*´∀`*)

参考：Practical symfony | symfony | Web PHP Framework

AmazonEC2にS3領域をマウントしてみる

2012-02-22T11:43:00.004+09:00

今日は、EC2にS3のバケットをマウントしてみました。
手順はこんな感じ。

FUSEにいる物をインストール
FUSEインストール
f3sfインストール
A3にバケット作成
マウント
再起動してもマウント

参考にしたこちらのサイト通りでほぼOKです。
memorycraft: S3ってなんじゃ？(s3fs編)

では、インストールログを。。

1.FUSEにいる物をインストール

# yum -y install gcc
# yum -y install gcc-c++
# yum -y install libstdc++-devel
# yum -y install pkgconfig
# yum -y install make
# yum -y install curl-devel
# yum -y install libxml2-devel
# yum -y install openssl-devel

2.FUSEインストール

バージョン確認 2.8.4より新しくないと駄目。 yumで入れられない場合は⇒http://sourceforge.net/projects/fuse/files/fuse-2.X/

$ yum list | grep fuse
fuse.x86_64                           2.8.6-1.10.amzn1             amzn-updates
fuse-devel.x86_64                     2.8.6-1.10.amzn1             amzn-updates

インストール

# yum -y install fuse
# yum -y install fuse-devel

環境変数設定

# export PKG_CONFIG_PATH=/usr/lib64/pkgconfig

カーネルにロード

# ldconfig 
# modprobe fuse

3.f3sfインストール

# cd /usr/local/src
# wget http://s3fs.googlecode.com/files/s3fs-1.40.tar.gz
# tar zxvf s3fs-1.40.tar.gz 
# cd s3fs-1.40
# ./configure prefix=/usr
# make
# make install

4.A3にバケット作成

5.マウント

キー情報を記載

単一認証
# echo アクセスキー:シークレットキー > /etc/passwd-s3fs
複数認証http://www.blogger.com/blogger.g?blogID=9198835639547511373#editor/target=post;postID=8405377529952507279
# echo バケット名:アクセスキー:シークレットキー > /etc/passwd-s3fs

# chmod 640 /etc/passwd-s3fs

マウント

# mkdir /mnt/s3
# s3fs myfirst-bucket /mnt/s3
# df -kh
Filesystem            Size  Used Avail Use% Mounted on
/dev/xvda1            7.9G  2.4G  5.5G  30% /
tmpfs                 3.7G     0  3.7G   0% /dev/shm
s3fs                  256T     0  256T   0% /mnt/s3

6.再起動してもマウント

# vi /etc/fstab
+++ s3fs#myfirst-bucket /mnt/s3 fuse allow_other,default_acl=public-read 0 0

# vi /etc/rc.d/rc.sysinit
...
. /etc/init.d/functions
+++ modprobe fuse

＊＊＊　うーんうまくできなかった (´；ω；`)ｳｯ…　＊＊＊

微妙な感じでうまくいかない。見えたり、見えなかったり。。。よって、こちらのバージョンにした。

cloudpack ブログ - S3ってなんじゃ？(s3cmd編) -
オフィシャル：Amazon S3 tools: s3cmd : command line S3 client

CでDevquiz２０１１スライドパズル　その３

2011-09-24T00:54:00.001+09:00

スライドパズルに関するアルゴリズムのサマリー

ソースさらし祭り(?)に参加されている人の解説などを含め今回調べたアルゴリズムを整理したページです。

広く浅く、全体を俯瞰できるようにすることを目標に書いてみます。

☆問題の定式化

駒数をKとすると可能な盤面はK！個あり、それらを要素とする集合Sを考える。

Sの各要素は駒を一回移動することで遷移できる要素と繋がっていると考えることで無向グラフとみなすことができる。

与えられた問題面ノードからゴールノードまでの経路探索問題と解釈できる。
なお、Kが３６の場合K!は３．７×１０^３６となり、無限の要素を持つと思って考えていい。

今後、n,g,h,h'を以下の意味で使う。

n：与えられた盤面

g(n)：スタートの盤面からnまでの駒の移動回数

h(n)：nからゴールまでの最短経路の駒の移動回数

h'(n)：h(n)の推定値。（マンハッタンディスタンスなどを利用したnからゴールまでの駒の移動回数の推定値）

☆経路探索アルゴリズム：幅探優先探索

駒の移動回数の小さい順に探索していくアルゴリズム。

見つかったノードをキューに入れていく形で実装。

過去の盤面をメモリーに保存するため、メモリーサイズで探索できるノード数が限られる。

http://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

☆経路探索アルゴリズム：深さ優先探索

ノードが途切れるか、ゴールに到達するまで深く探索していき、その後はバックトラック。

スライドパズルのような開いた木の最適解を求めるためには下記のIDDFSやIDA*のような手法を使う。

過去の盤面を保存しないのでメモリー消費は小さい。

http://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

☆経路探索アルゴリズム：IDA*

深さ優先探索で以下の閾値を設けて探索を行う。

g(n) + h'(n) <Threshold

ある閾値でゴールが見つからなかった場合は、閾値を徐々に増大させながら探索を繰り返す。

ここでh'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。

0 ≦ h'(n) ≦ h(n)

この閾値の評価を単に

g(n) < Threshold

としたものは反復深化深さ優先探索(IDDFS)と呼ばれる。

木構造の根元に近い部分を何度も調べることになるため無駄のように見えるが、ノードの多くは木構造の底辺にあるため、それほどコスト増大にはならない。（深さNに応じてx＾Nでノード数は増大するため、たとえばx=2の場合、高々2倍の演算量にしかならない）

http://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1%E5%8C%96%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

☆経路探索アルゴリズム：A*

幅優先のキューをプライオリティキューにして、もっとも推定コストの小さいノードを優先して探索しているアルゴリズム。

推定コストとは

f(n) = g(n) + h'(n)

ここでIDA*同様h'(n)が以下を満たす時、最初に見つけた経路が最短経路である事が証明できる。

0 ≦ h'(n) ≦ h(n)

幅優先探索の拡張であるのでメモリが探索深度に応じ指数関数的に消費されていくため、ある程度以上の深度まで探索しようとすると、使われないノードを一旦破棄し必要に応じて再利用（SMA*）が必要になる。

http://ja.wikipedia.org/wiki/A*

☆評価関数h'(n)

高得点を得ていたアルゴリズムはほぼA*かIDA*を利用したものだったが、これらのアルゴリズムでは評価関数h'(n)の精度が重要になる。
h'(n)がh(n)に近ければ近いほど演算量は小さくなるので、いかにh(n)に近い関数を見つけるかがとても重要！

以下で説明するようにいくつかの手法が考案されており、これらを組み合わせて使う（もっとも値の大きいh'(n)の値を利用する）こともできる。

☆マンハッタンディスタンス（MD)

個々の駒に関してゴール位置への移動回数を計算したもの。

http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2

パターンデータベース（PDB）

前もって特定のパターンとそのパターンのh(n)を計算しておき、それをハッシュ化して保存しておきh'(n)の計算に利用する手法。

http://www.ise.bgu.ac.il/faculty/felner/research/jairpdb.pdf

☆ギャップ集合

MDを利用したh'(n)とh(n)とのギャップがいくつであるかに応じたデータベースをあらかじめ作っておく。
探索時にそのDBを参照し、ギャップに応じてMDに値を加算する。

http://www.jstage.jst.go.jp/article/tjsai/26/2/419/_pdf/-char/ja/

☆転倒距離

駒の並びを順列と考え、小さい順に並んでいない駒の数（転倒が起こっている回数）を利用

http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

☆ウォーキングディスタンス

ゴール盤面で各行（または各列）に属している駒が、その盤面でそれぞれの各行（または各列）に何個あるかというパターンをデータベース化したもの。
PDBの一種（？）
４×４くらいまでは有効だが、５×５以上ではデータベースが膨大になり現実的ではない。

http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

☆最短経路以外の解を求める探索

ここまでは全て最短経路を求めるためのアルゴリズムだが、今回のDevquizの問題は与えられた移動可能駒数に余裕があり、参加者の多くは非最短解を求めるアルゴリズムを考案・採用されていた。

大別すると以下のパターンに分類できる。

☆上限を守らない評価関数

上に述べたように任意の盤面nに対し

0 ≦ h'(n) ≦ h(n)

を満たすような評価関数であれば、最短経路である事が保障されますが、この上限をあえて守らない事でより早くゴールにたどり着こうという発想。

具体的には、MD値を各コマに対して足し上げる際に端の駒の重みを大きくしたり、駒の並び順に応じてペナルティスコアを加算したり等。

☆段階を置いてゴールに辿りつこうという方法

いきなりゴール面までの探索をする代わりに、途中に中継点を置いて中継点までの探索を行い、中継点からゴールまでの探索を再度行う方法。

私が行った、端優先、ステップ実行はこれにあたる。
（端優先、ステップ実行という名前は私が勝手に付けた）

☆キューのサイズに上限を設ける方法

A*など幅優先系のアルゴリズムでプライオリティキューのサイズに上限を設け、上限に達したらプライオリティのもっとも低いノードをキューから削除する方法。

☆経路探索アルゴリズム：双方向探索

逆方向からも探索する事で演算量を下げる方法。
やり方によっては最適解にもなる。

x^Nがx^(N/2)となり、大幅に演算量を下げることができる。

http://ja.wikipedia.org/wiki/%E5%8F%8C%E6%96%B9%E5%90%91%E6%8E%A2%E7%B4%A2

CでDevquiz２０１１スライドパズル　その２

2011-09-13T23:25:00.000+09:00

解説1

昨日公開したスライドパズルのソースの解説をしていこうと思います。
まずは特に独自性がありそうな、端優先、ステップ実行と書いたアルゴリズムの解説です。

端優先

１	２	３
４	５	６
７	８	０

このような３X３のブロックなしの問題が与えられた場合、人力で解く際は通常、まず１をそろえて、その次２、３、その次４、７、最後に５、６、８と合わせますよね。

このロジックを実装したアルゴリズムです。

ここで２、３を一緒に合わせるのは２を先に合わせて固定してしまうと３が入らなくなるからですが、これは「ある駒（この場合２の駒）を固定することで1方向にしか移動できなくなる駒（この場合は３の駒）を一緒に合わせる必要がある」という考えで一般化でき、具体的には

recurs_func(　駒A　）{
 駒Aを固定する
 for　(　駒B　∈　Aと隣り合っている駒で1方向にしか動かせない駒　）
　　recurs_func(　駒B　）
}

といった再帰で実現できます。

このロジックはブロックがある場合にも拡張でき、例えば

１	２	３	４
５	６	＝	８
９	A	B	C
D	E	F	０

といったケースにもうまく適応できます。

この場合

{1}
{2,3,4,8}
{5,6}
{9,D}
{AE}
{BCF}

といった形の配列を作成し、上から順番にIDA*を利用して揃えていくという事を行っています。

なお、上からそろえる、左からそろえる、左上（０から遠いところから）揃えると3パターンで試してみましたが、これら３つはほぼ等価で、上からそろえてうまくいくものは、左からでも左上からでもうまくいくし、ダメなものはだめという結果でした。

この理由はダメな場合はこの例の｛2,3,4,8}のように一緒に揃えないといけない駒の数が多いとき、IDA*では現実的な計算量に収まらないという状況のようです。
ここは、マンハッタンディスタンス（MD)に加え並び順も考慮することで改善の余地がありそうだったので時間があればもうちょっと開発したかった部分です。

ステップ実行

一般に、駒の移動回数Nが増えるに従いx^Nのオーダーで計算量が増えていきます。

ここで、xは与えられた問題に依存する1から3の間の実数です。（3より小さいのは上下左右4つの方向のうち1方向は前回の盤面に戻る移動なので省略しているから）移動回数とMDの輪が閾値以下という条件で枝刈りするにしてもNが増えると（閾値が増えると）計算量はどうしても膨大になります。

そこで最短経路解を取りこぼしてでも（移動回数の制限はかなりあまいという事がわかっていたので）強めの枝刈りを考える事になるのですが、ここではたとえば1億ノードとか指定してあげて、そのノード数探索して見つからなかったら、それまでに探索したノード内で最もMDの小さい値を初期ノードとして再探索するという事を行いました。つまり、最小値を持つモード以外すべて枝刈りするという大胆な方法です。

双方向探索と同じようにx^Nをx^(N/2)としてあげようという発想ですね。

この方法のメリットはなんといっても実装が簡単である事。

また、ステップ毎に強めの枝刈りをして深く探索していく方法だとローカルミニマムにとらわれて脱出できないリスクが高くなりますが、この方法だと無駄だと思われるノードに対しても与えられた探索回数までは広く探索を行うので、ローカルミニマムから脱出する可能性が高くなるというメリットもあります。

実際、この方法は強力で単純なIDA*では見つけられなかった問題（計算に時間がかかりすぎた問題）のかなりの数を回答しています。

これらのアルゴリズムの位置づけに関してはこちらの記事を参照してください。

CでDevquiz２０１１スライドパズル

2011-09-12T18:47:00.000+09:00

Devquizへの参加記念にソースコードを晒しておきます。

アルゴリズム

１、IDA*
過去のステップ数と残りの距離見積りの和で与えた閾値を上げながら反復深化
２、双方向探索
ゴールから幅優先探索、前方からIDA*を実行しマッチング
実装中に他の方法で万点取れる目途が付いたので中途半端（というかまだ動いていなかった。。）になっています。
３、端優先
人がパズルを組み立てる時のように端から順に揃えていくアルゴリズム。
４、ステップ実行
指定された回数探索を行い、それまでにゴールに達しなかった場合、過去に見つかった残りの距離見積りが最小のものをスタートに再度探索を繰り返す。（それ以外のノードを捨てる）
５、半自動シミュレーション
上記で解けない問題が7問残った。この残った問題を半自動で解くためのヒントを元に解いていくシュミレーター。

*距離関数としてはブロックを考慮したマンハッタンディスタンスを使用。
*２だけはゴールを広げる程度に幅優先でメモリー使ってますが、基本的にはメモリーを消費しない深さ優先をベースに作っています。辿ったノードを記憶しておく幅優先系ではメモリーが厳しいかなと予想してたんですが、A*で大半の問題を解いた人もいるようですね。

excuse

高得点を取る事だけを目的に書いていたプログラムなので、書きかけのコードが入っていたりグローバル変数使いまくりのコードになってます。
きちんと書いて今後公開しますが(気が向いたときw）、一旦提出したそのままのコードをUPします。

150点取れたときの画像(@o@)

実際のソース

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <unistd.h>

#define YOKO_YUSEN
//#define INVD
#define MAXIDTBL 600
#define MAX_STACK_LEVEL 5000
#define MAX_HANPUKU 2000
#define   MIN(a,b)  ( ((a)<(b) ) ? (a) : (b) )
#define   MAX(a,b)  ( ((a)>(b) ) ? (a) : (b) )

int matrix_size;
int matrix_size_x;
int matrix_size_y;
int hanpuku_done;
int step_done;
int shurink;
int shurink_mask;
unsigned long long max_count;
unsigned long long count_hanpuku;
int step_dist;

unsigned long long level_counter[MAX_STACK_LEVEL+1];
int level_max_md_counter[MAX_STACK_LEVEL+1];
int level_min_md_counter[MAX_STACK_LEVEL+1];
int moving_history[MAX_STACK_LEVEL+1];
int mh_cnt;
int simflg;

int pre_result_threshold;
char *pre_result_string;
char *mondai;
char *kaitou;

enum STACK {UP, DOWN};
enum MODE2 {MOVE, HANPUKU, STEP, STEP_TARGET, FIX,UNFIX};

struct MATRIX{
        char mval[40];
        int sp_pos;
};

struct HASH_LIST {
        struct MATRIX *matrix;
        struct HASH_LIST *next;
};

struct HABA_STACK{
        char mval[36];
};

struct Stock_Arr{
        char r;
        char sp_pos;
        char new_pos[4];
        int md;
        int wd;
        int sd;
        int id;
        int id1;
        int id2;
        int inv1;
        int inv2;
};

struct Stock_Arr stock_arr[MAX_STACK_LEVEL+4];

char New_Pos[36][4];

struct HARR{
        int arr[36][36];
        int arr_len[36];;
        int arr_num;
};


struct MATRIX Matrix;
struct MATRIX Matrix_Min;
struct MATRIX Matrix_Parity;
struct MATRIX Matrix_backup;
struct HARR HArr;
int CrrHarrIdx;

int Threshold;
int Pair_Threshold;
int StackPath[MAX_STACK_LEVEL+1];
int StackPath_Min[MAX_STACK_LEVEL+1];
int *IDTBL1;
int *IDTBL2;
int IDTBL3[MAXIDTBL];
int IDTBL4[MAXIDTBL];
int IDTBL5[MAXIDTBL];
int IDTBL6[MAXIDTBL];
int M_Distance[36][36];
int R_Distance[36][36];
int Parity_omote2ura[36];
int Parity_ura2omote[36];
int max_haba_stack;
struct HASH_LIST **hash_table;
struct HASH_LIST *Hash_List;
int stack_cnt,stack_tail;
int hash_cnt;
int haba;
struct MATRIX *haba_stack;
int min_depth;
int mode=1;

enum Dir {U,L,D,R};
int DirectionX[4] = {0, -1, 0, 1};
int DirectionY[4] = {-1, 0, 1, 0};
char Direction[4] = {'U', 'L', 'D', 'R'};


void dump_harr(){
        int i,j;

        printf("arr_num:%d\n",HArr.arr_num);
        for(i=0;i<HArr.arr_num;i++){
                printf("[%d(arr_len:%d) ->",i,HArr.arr_len[i]);
                for(j=0;j<HArr.arr_len[i];j++){
                        printf(" %d",HArr.arr[i][j]);
                }
                printf("]\n");
        }
}

void dump_matrix(struct MATRIX *m){
        int i;
        char c,p;

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
        for(i=0;i<matrix_size;i++){
                p = m->mval[i];

                if(p > 8){
                        c = p + 'A' - 9;
                } else if(p == -2){
                        c = '=';
                } else if(p == -1){
                        c = '.';
                } else {
                        c = p + '1';
                }
                printf("%c",c);

                if(i%matrix_size_x == matrix_size_x - 1){
                        printf("\n");
                }
        }
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
}

void dump_matrix2(struct MATRIX *m){
        int i,x,y;
        char c,p;

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("       ");
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");

        for(y=0;y<matrix_size_y;y++){
                for(x=0;x<matrix_size_x;x++){
                        i = y*matrix_size_x+x;
                        p = m->mval[i];
                        if(p > 8){
                                c = p + 'A' - 9;
                        } else if(p == -2){
                                c = '=';
                        } else if(p == -1){
                                c = '.';
                        } else {
                                c = p + '1';
                        }
                        printf("%c",c);
                }
                printf("       ");
                for(x=0;x<matrix_size_x;x++){
                        i = y*matrix_size_x+x;
                        p = m->mval[i];
                        if(p == -2){
                                c = '=';
                        } else if(i == matrix_size-1){
                                c = '.';
                        } else if(i > 8){
                                c = i + 'A' - 9;
                        } else {
                                c = i + '1';
                        }
                        printf("%c",c);
                }
                printf("\n");
        }

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("       ");
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
}

void mv_koma(int this_r){
        int sp_pos,new_sp_pos;
        int tgt;

        sp_pos = Matrix.sp_pos;
        new_sp_pos = New_Pos[sp_pos][this_r];
        tgt = Matrix.mval[new_sp_pos];
        Matrix.mval[sp_pos] = tgt;
        Matrix.mval[new_sp_pos] = -1;
        Matrix.sp_pos = new_sp_pos;

}


void make_goal(struct MATRIX *tgt, struct MATRIX *org){
        int i,j;

        for(i=0, j=0; i<matrix_size; i++){
                if(org->mval[i] == -2){
                        tgt->mval[i] = -2;
                } else {
                        tgt->mval[i] = i;
                        j=i;
                }
        }
        tgt->mval[j] = -1;

        tgt->sp_pos = org->sp_pos;

}



void check_matrix(struct MATRIX *m){
        int i;

        for(i=0;i<matrix_size;i++){
                if(m->mval[i] == -1){
                        return;
                }
        }
        printf("ERR: not found space\n");
        fflush(stdout);
        sleep(100);


}

int fix_mval(char p){
        int c;

        if(p > 8){
                c = p + 'A' - 9;
        } else if(p == -2){
                c = '=';
        } else {
                c = p + '1';
        }

        return c;
}


void dump_matrix_parity(struct MATRIX *m){
        int i;
        char c,p;

        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
        for(i=0;i<matrix_size;i++){
                p = m->mval[Parity_omote2ura[i]];

                if(p > 8){
                        c = p + 'A' - 9;
                } else if(p == -2){
                        c = '=';
                } else {
                        c = p + '1';
                }
                printf("%c",c);

                if(i%matrix_size_x == matrix_size_x-1){
                        printf("\n");
                }
        }
        for(i=0;i<matrix_size_x;i++){
                printf("-");
        }
        printf("\n");
}

int comp(const void *a, const void *b)
{
        return R_Distance[matrix_size-1][*(int*)b] - R_Distance[matrix_size-1][*(int*)a];

}

int next_harr_saiki(int *stack_cnt, int *stack, int crr, struct MATRIX *m){
        int px, py, cx, cy,nx,ny;
        int r1,r2;
        int p_cnt;

        m->mval[crr] = -2;
        stack[stack_cnt[0]] = crr;
        stack_cnt[0]++;

        px = crr % matrix_size_x;
        py = crr / matrix_size_x;

        for ( r1 = 0; r1 < 4; r1++ ){
                cx = px + DirectionX[r1];
                cy = py + DirectionY[r1];

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(m->mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                p_cnt=0;
                for(r2 = 0;r2 < 4;r2++){
                        nx = cx + DirectionX[r2];
                        ny = cy + DirectionY[r2];
                        if ( nx < 0 || ny < 0 || nx >= matrix_size_x || ny >= matrix_size_y ){
                                continue;
                        }
                        if(m->mval[ny*matrix_size_x+nx] == -2){
                                continue;
                        }
                        p_cnt++;
                }

                if(p_cnt < 2 || m->mval[matrix_size-1] == -2){
                        next_harr_saiki(stack_cnt, stack, cy*matrix_size_x+cx ,m);
                }
        }
        return 0;
}

int add_harr(int list_len, int *ranked_list, struct MATRIX *mtr){
        int stck[36];
        int cnt,i,j,found;

        cnt = 0;
        next_harr_saiki(&cnt,stck,ranked_list[0],mtr);
        if(cnt <= 0){
                exit(0);
        }

        for(i=0;i<cnt;i++){
                HArr.arr[HArr.arr_num][i] = stck[i];
        }

        HArr.arr_len[HArr.arr_num] = cnt;
        HArr.arr_num++;

        for(i=0;i<cnt;i++){
                found = 0;
                for(j=0;j<list_len;j++){
                        if(found == 1){
                                ranked_list[j-1] = ranked_list[j];
                        } else if(ranked_list[j] == stck[i]){
                                found = 1;
                        }
                }
        }


        return list_len - cnt;
}


void make_harr(struct MATRIX *m){
        int x,y,i,j,list_len;
        int ranked_list[36];
        int ranked_list_tmp[36];
        struct MATRIX tmp_m;

        CrrHarrIdx=0;
        HArr.arr_num = 0;

        for(i=0,j=0;i<matrix_size-1;i++){
                if(m->mval[i] != -2){
                        ranked_list[j++] = i;
                }
        }
        list_len = j;

        if(step_dist == 1){
                /*do nothing*/
        } else if(step_dist == 2){
                for(i=0;i<matrix_size;i++) ranked_list_tmp[i] = ranked_list[i];
                for(x=0;x<matrix_size_x;x++)
                        for(y=0;y<matrix_size_y;y++)
                                ranked_list[y*matrix_size_x+x] = ranked_list_tmp[y*matrix_size_x+x];
        } else {
                qsort(ranked_list,list_len,sizeof(int),comp);
        }

        tmp_m = Matrix;
        while(1){
                if(list_len <= 0){
                        break;
                }

                list_len = add_harr(list_len, ranked_list, &tmp_m);
        }
}

void set_m_distance(){
        int i,j;

        for ( i = 0; i < matrix_size; i++ ){
                for ( j = 0; j < matrix_size; j++ ){
                        M_Distance[i][j] = abs(i/matrix_size_x-j/matrix_size_x) + abs(i%matrix_size_x-j%matrix_size_x);
                }
        }
}


int pair_saiki(int depth, int pre_r,int crr, int end){
        int ret;
        int px, py, cx, cy;
        int r;
        int diff;
        int d;

        if ( crr == end ){
                return 1;
        }

        d = M_Distance[crr][end];
        if ( depth + d > Pair_Threshold ){
                return 0;
        }

        px = crr % matrix_size_x;
        py = crr / matrix_size_x;

        for ( r = 0; r < 4; r++ ){
                cx = px + DirectionX[r];
                cy = py + DirectionY[r];
                if(pre_r > r){
                        diff = pre_r - r;
                } else {
                        diff = r - pre_r;
                }
                if(diff == 2){
                        continue;
                }

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                ret = pair_saiki( depth+1, r , cy*matrix_size_x+cx, end);
                if (ret) {

                        return 1;
                }
        }
        return 0;
}


void set_r_distance(struct MATRIX *m){
        int i,j,ret;

        ret = 0;
        for ( i = 0; i < matrix_size; i++ ){
                if(m->mval[i] == -2) continue;
                for ( j = 0; j < matrix_size; j++ ){
                        if(m->mval[j] == -2) continue;
                        for ( Pair_Threshold = M_Distance[i][j]; Pair_Threshold <= MAX_STACK_LEVEL; Pair_Threshold += 2 ){
                                ret = pair_saiki(0, -4,i,j);

                                if ( ret ){
                                        R_Distance[i][j] = Pair_Threshold;
                                        break;
                                }

                        }
                        if(ret < 0){
                                printf("ERR: R_Distance not fund for [%d][%d]",i,j);
                                exit(1);
                        }
                }
        }
}

int inv_distance1(){
        int i,j,inv,val1,val2;

        inv = 0;
        for (i=0; i<matrix_size; i++) {
                val1 = Matrix.mval[i];
                if (val1 == -1) continue;
                if (val1 == -2) val1 = i;
                for (j=i+1; j<matrix_size; j++) {
                        val2 = Matrix.mval[j];
                        if (val2 == -1) continue;
                        if (val2 == -2) val2 = j;
                        if (val2<val1){
                                inv++;
                        }
                }
        }
        return inv;
}


int inv_distance2(){
        int i,j,inv,val1,val2;

        inv = 0;
        for (i=0; i<matrix_size; i++) {
                val1 = Matrix_Parity.mval[i];
                if (val1 == -1) continue;
                if (val1 == -2) val1 = i;
                for (j=i+1; j<matrix_size; j++) {
                        val2 = Matrix_Parity.mval[j];
                        if (val2 == -1) continue;
                        if (val2 == -2) val2 = j;
                        if (val2<val1){
                                inv++;
                        }
                }
        }
        return inv;
}

int i_distance(){
        int inv1,inv2;

        inv1 = inv_distance1();
        inv2 = inv_distance2();
        return IDTBL1[inv1]+IDTBL2[inv2];
}

int m_distance(){
        int md;
        int i;

        md = 0;
        for(i = 0; i < matrix_size; i++){
                if ( Matrix.mval[i] < 0 )continue;
                md += R_Distance[i][(int)Matrix.mval[i]];
        }

        return md;
}

int w_distance(){
        int md;
        int id;

        md = m_distance();
        id = i_distance();

        return MAX(md,id);;
}

int step_distance(){
        int sum;
        int i,j,k;
        char c;

        sum = 0;
        for(i = 0; i < HArr.arr_len[CrrHarrIdx]; i++){
                k = HArr.arr[CrrHarrIdx][i];
                c = k;
                for(j=0;j<matrix_size;j++){
                        if(Matrix.mval[j] == c){
                                sum += R_Distance[j][k];
                        }
                }

        }
        return sum;
}

int check_goal(){
        int i;
        for ( i = matrix_size-2; i >= 0; i-- ){
                if ( Matrix.mval[i] != i && Matrix.mval[i] != -2 ){
                        return 0;
                }
        }
        return 1;
}

int check_step_goal(){
        int i,j;
        for (i=0;i<HArr.arr_len[CrrHarrIdx];i++){
                j = HArr.arr[CrrHarrIdx][i];
                if ( Matrix.mval[j] != j && Matrix.mval[j] != -2){
                        return 0;
                }
        }
        return 1;
}

int heuristic_distance(){


        return 0;
}

int get_r(char *c){
        int this_r;

        if(*c=='U' || *c=='u') this_r = 0;
        else if(*c=='L' || *c=='l') this_r = 1;
        else if(*c=='D' || *c=='d') this_r = 2;
        else if(*c=='R' || *c=='r') this_r = 3;
        else this_r = -1;

        return this_r;
}



int steploop(int pre_depth, int depth, int pre_r){
        int i;
        int this_r;
        int sp_pos,new_sp_pos;
        int stack_dir;
        int crr_depth;
        char *npp;
        int found;
        int tgt;
        int sd;
        int harr_arr_len;

        struct MATRIX tmp;

        harr_arr_len = HArr.arr_len[CrrHarrIdx];

        tmp = Matrix;

        found = 0;
        crr_depth = 0;

        stack_dir = DOWN;
        sp_pos = Matrix.sp_pos;
        stock_arr[crr_depth].sp_pos = sp_pos;


        sd = step_distance();
        if(sd == 0){
                found = 1;
                return 1;
        }
        stock_arr[crr_depth].sd = sd;

        if ( sd > Threshold - crr_depth ){
                return 0;
        }

        memcpy(stock_arr[crr_depth].new_pos,New_Pos[Matrix.sp_pos],sizeof(char)*4);
        npp = stock_arr[crr_depth].new_pos;

        for(i=0;i<4;i++){
                if(pre_r - i == 2 || i - pre_r == 2){
                        npp[i] = -1;
                        break;
                }
        }

        for(this_r=-1,i=0;i<4;i++){
                if(npp[i] >= 0){
                        this_r = i;
                        break;
                }
        }

        if(this_r >= 0){
                npp[this_r] = -1;
                stack_dir = DOWN;
        } else {
                fprintf(stderr,"ERR11\n");
                return 0;
        }

        while(1){


                if(stack_dir == DOWN){
                        /* use stack_dir, this_r, sp_pos */

                        if(crr_depth >= MAX_STACK_LEVEL){
                                fprintf(stderr, "ERR: crr_depth over\n");
                                return 0;
                        }
                        crr_depth++;

                        if(count_hanpuku > max_count){
                                hanpuku_done = 1;
                                return 0;
                        }
                        count_hanpuku++;

                        stock_arr[crr_depth].r = this_r;
                        new_sp_pos = New_Pos[sp_pos][this_r];
                        stock_arr[crr_depth].sp_pos = new_sp_pos;
                        tgt = Matrix.mval[new_sp_pos];
                        Matrix.mval[sp_pos] = tgt;
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;
                        sd = stock_arr[crr_depth-1].sd;
                        for(i=0;i<harr_arr_len;i++){
                                if(HArr.arr[CrrHarrIdx][i] == tgt){
                                        sd += R_Distance[sp_pos][tgt] - R_Distance[new_sp_pos][tgt];
                                        break;
                                }
                        }

                        if(sd == 0){
                                found = 1;
                                break;
                        }
                        stock_arr[crr_depth].sd = sd;

                        if ( sd > Threshold - crr_depth ){
                                sp_pos = new_sp_pos;
                                stack_dir = UP;
                                continue;
                        }

                        memcpy(stock_arr[crr_depth].new_pos,New_Pos[new_sp_pos],sizeof(char)*4);
                        npp = stock_arr[crr_depth].new_pos;

                        for(i=0;i<4;i++){
                                if(this_r - i == 2 || i - this_r == 2){
                                        npp[i] = -1;
                                        break;
                                }
                        }

                        if(npp[0] >= 0) this_r = 0;
                        else if(npp[1] >= 0) this_r = 1;
                        else if(npp[2] >= 0) this_r = 2;
                        else if(npp[3] >= 0) this_r = 3;
                        else this_r = -1;

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }


                } else { // UP
                        if(crr_depth == 0){
                                return 0;
                        }
                        crr_depth--;

                        new_sp_pos = stock_arr[crr_depth].sp_pos;
                        Matrix.mval[sp_pos] = Matrix.mval[new_sp_pos];
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;

                        npp =  stock_arr[crr_depth].new_pos;
                        for(this_r = -1,i=0;i<4;i++){
                                if(npp[i] >= 0){
                                        this_r = i;
                                        break;
                                }
                        }

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }

                }
        }

        if(found){
                for(i=0;i<crr_depth;i++){
                        StackPath[pre_depth+i] = stock_arr[i+1].r;
                }
                StackPath[pre_depth+i] = 0;
        }

        return 1;
}

int stepsaiki(int depth, int pre_r){
        int ret;
        int px, py, cx, cy;
        int r;
        int diff;
        int wd;
        struct MATRIX tmp;

        wd = step_distance();
        if(wd == 0){
                Matrix_backup = Matrix;
                return 1;
        }

        if ( depth + wd > Threshold ){
                return 0;
        }

        count_hanpuku++;
        if(count_hanpuku > max_count){
                return 0;
        }

        px = Matrix.sp_pos % matrix_size_x;
        py = Matrix.sp_pos / matrix_size_x;

        for ( r = 0; r < 4; r++ ){
                cx = px + DirectionX[r];
                cy = py + DirectionY[r];
                if(pre_r > r){
                        diff = pre_r - r;
                } else {
                        diff = r - pre_r;
                }
                if(diff == 2){
                        continue;
                }

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                tmp = Matrix;
                Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
                Matrix.mval[cy*matrix_size_x+cx] = -1;
                Matrix.sp_pos = cy*matrix_size_x+cx;
                ret = stepsaiki( depth+1, r );
                if (ret) {
                        StackPath[depth] = r;
                        return 1;
                }
                Matrix = tmp;
        }
        return 0;
}

int check_pre_result_path(){
        int i,x;
        char *c;
        int done;
        int px,py,cx,cy;


        c = pre_result_string;
        if(c == NULL || strncmp(c,"not",3)==0){
                printf("not checked\n");

                return 0;
        }

        for(x=0;c[x];x++){

                done = 0;
                for(i=0;i<4;i++){
                        if(Direction[i] == c[x]){
                                done = 1;
                                break;
                        }
                }
                if(done == 0){
                        printf(":ERR0: no direction[%d][%s]\n",x,c);
                        return 0;
                }

                px = Matrix.sp_pos % matrix_size_x;
                py = Matrix.sp_pos / matrix_size_x;
                cx = px + DirectionX[i];
                cy = py + DirectionY[i];

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        printf(":ERR1: bad direction[%d][%s]\n",x,c);
                        return 0;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        printf(":ERR2: bad direction[%d][%s]\n",x,c);
                        continue;
                }

                Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
                Matrix.mval[cy*matrix_size_x+cx] = -1;
                Matrix.sp_pos = cy*matrix_size_x+cx;
        }
        if ( m_distance() ){
                printf(":ERR3: bad path[%s]\n",c);
                return 0;
        } else {
                printf("%s ok\n",mondai);
                return 1;
        }
}

int check_id(int inv1, int inv2, struct MATRIX *m){

        if( inv1 != inv_distance1()){
                return 0;
        }
        if( inv2 != inv_distance2()){
                return 0;
        }

        return 1;
}

void make_new_pos(struct MATRIX *mtr){
        int px, py, cx, cy,i,r;
        int npos;

        for(i=0;i<matrix_size;i++){
                for(r=0;r<4;r++){
                        px = i % matrix_size_x;
                        py = i / matrix_size_x;

                        cx = px + DirectionX[r];
                        cy = py + DirectionY[r];

                        npos = cy*matrix_size_x+cx;

                        if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        if(Matrix.mval[npos] == -2){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        New_Pos[i][r] = npos;
                }

        }
}

void fix_new_pos(struct MATRIX *mtr){
        int px, py, cx, cy,i,r;
        int npos;

        for(i=0;i<matrix_size;i++){
                for(r=0;r<4;r++){
                        px = i % matrix_size_x;
                        py = i / matrix_size_x;

                        cx = px + DirectionX[r];
                        cy = py + DirectionY[r];

                        npos = cy*matrix_size_x+cx;

                        if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        if(Matrix.mval[npos] == -2){
                                New_Pos[i][r] = -1;
                                continue;
                        }

                        New_Pos[i][r] = npos;
                }

        }
}

int hash_func(struct MATRIX *matrix){
        int hash,i;

        hash = 1;
        for(i=0;i<matrix_size;i++){
                hash += 137 + (matrix->mval[i]+13)*i;
        }
        return hash % max_haba_stack;

}

void dump_hash(){
        int i;
        struct HASH_LIST *hlp;

        for(i=0;i<max_haba_stack;i++){
                for (hlp = hash_table[i]; hlp != NULL; hlp = hlp->next){
                        printf("key:%d\n",i);
                        dump_matrix(hlp->matrix);
                }

        }
}

struct MATRIX *get_hash(struct MATRIX *this_matrix, int hash_val){
        int found,i;
        struct HASH_LIST *hlp;
        char *mval;

        if(hash_val < 0){
                hash_val = hash_func(this_matrix);
        }

        for (hlp = hash_table[hash_val]; hlp != NULL; hlp = hlp->next){
                found = 1;
                mval = hlp->matrix->mval;

                /**/
                for(i=0;i<matrix_size;i++){
                        if(mval[i] != this_matrix->mval[i]){
                                found = 0;
                                break;
                        }
                }
                if(found == 1){

                        return hlp->matrix;
                }
        }

        return NULL;
}

int set_hash(struct MATRIX *this_matrix, int this_r){
        int sp_pos,new_sp_pos;
        int tgt;
        struct HASH_LIST *hash_list, *hlp;
        struct MATRIX *m;
        int hash_val;

        hash_list = &Hash_List[hash_cnt];
        memcpy(&haba_stack[stack_tail],this_matrix,sizeof(struct MATRIX));
        this_matrix = &haba_stack[stack_tail];

        sp_pos = this_matrix->sp_pos;
        new_sp_pos = New_Pos[sp_pos][this_r];
        tgt = this_matrix->mval[new_sp_pos];
        this_matrix->mval[sp_pos] = tgt;
        this_matrix->mval[new_sp_pos] = -1;
        this_matrix->sp_pos = new_sp_pos;

        hash_val = hash_func(this_matrix);
        m = get_hash(this_matrix,hash_val);
        if(m != NULL){
                return 1;
        }

        hash_list->matrix = &haba_stack[stack_tail];
        hash_list->next = NULL;
        hash_cnt++;
        stack_tail++;

        if (hash_table[hash_val] == NULL) {
                hash_table[hash_val] = hash_list;
        } else {
                hlp = hash_table[hash_val];
                while (hlp->next != NULL)
                        hlp = hlp->next;
                hlp->next = hash_list;
        }
        return 0;
}

int haba_tansaku(){
        int i;
        struct MATRIX *this_matrix;
        char *npp;

        stack_cnt=0;
        stack_tail=0;

        haba_stack = malloc(sizeof(struct MATRIX)*max_haba_stack);
        if(haba_stack == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }

        hash_table = malloc(sizeof(struct HASH_LIST **)*max_haba_stack);
        if(hash_table == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }
        bzero(hash_table,sizeof(struct HASH_LIST **)*max_haba_stack);

        Hash_List = malloc(sizeof(struct HASH_LIST)*max_haba_stack);
        if (Hash_List == NULL) {
                fprintf(stderr, "ERR: cant alloc memmory\n");
                exit(1);
        }

        this_matrix = &haba_stack[stack_tail];
        memcpy(this_matrix,&Matrix,sizeof(struct MATRIX));
        stack_tail++;

        while(stack_cnt < stack_tail){

                this_matrix = &haba_stack[stack_cnt];
                npp = New_Pos[this_matrix->sp_pos];

                for(i=0;i<4;i++){
                        if(npp[i] >= 0){

                                count_hanpuku++;
                                if(count_hanpuku >= max_count){
                                        return 1;
                                }

                                stack_cnt++;
                                if(stack_tail >= max_haba_stack){
                                        return 1;
                                }

                                set_hash(this_matrix,i);
                        }
                }

        }

        return 0;

}
void free_hash(){

        free(hash_table);
        free(haba_stack);
        free(Hash_List);

        hash_table=NULL;
        haba_stack=NULL;
        Hash_List=NULL;

}

int loop(int depth, int pre_r){
        int i;
        int wd;
        int id;
        int md;
        int this_r;
        int sp_pos,sp_pos_p,new_sp_pos;
        int stack_dir;
        int crr_depth;
        char *npp;
        int found;
        int tgt;
#ifdef INVD
        int new_sp_pos_p;
        int val;
        int tgt_p;
#endif
        int inv1,inv2;
        int id1,id2;

        struct MATRIX tmp;
        struct MATRIX tmp_p;
        struct MATRIX *hash_ret;

        tmp = Matrix;
        tmp_p = Matrix_Parity;

        found = 0;
        crr_depth = 0;

        stack_dir = DOWN;
        sp_pos = Matrix.sp_pos;
        stock_arr[crr_depth].sp_pos = sp_pos;
        sp_pos_p = Parity_omote2ura[sp_pos];


        md = m_distance();
        inv1 = inv_distance1();
        inv2 = inv_distance2();
        id1 = IDTBL1[inv1];
        id2 = IDTBL2[inv2];
        id = id1+id2;
        wd = MAX(md,id);
        if(wd == 0){
                found = 1;
                return 1;
        }

        if(haba == 1){
                hash_ret = get_hash(&Matrix, -1);
                if(hash_ret != NULL){
                        return 0;
                }
        }
#ifdef DEBUG
        level_max_md_counter[crr_depth] = md;
        level_min_md_counter[crr_depth] = md;
#endif

        stock_arr[crr_depth].md = md;
        stock_arr[crr_depth].id = id;
        stock_arr[crr_depth].inv1 = inv1;
        stock_arr[crr_depth].inv2 = inv2;
        stock_arr[crr_depth].wd = wd;

        if ( wd > Threshold - crr_depth ){
                return -1;
        }

        memcpy(stock_arr[crr_depth].new_pos,New_Pos[Matrix.sp_pos],sizeof(char)*4);
        npp = stock_arr[crr_depth].new_pos;

        for(this_r=-1,i=0;i<4;i++){
                if(npp[i] >= 0){
                        this_r = i;
                        break;
                }
        }

        if(this_r >= 0){
                npp[this_r] = -1;
                stack_dir = DOWN;
        } else {
                fprintf(stderr,"ERR11\n");
                return -1;
        }

        while(1){


                if(stack_dir == DOWN){
                        /* use stack_dir, this_r, sp_pos */

                        if(crr_depth >= MAX_STACK_LEVEL){
                                return -1;
                        }

                        crr_depth++;
                        count_hanpuku++;
                        level_counter[crr_depth]++;
                        if(count_hanpuku > max_count){
                                hanpuku_done = 1;
                                if(shurink > 0){
                                        return -1;
                                }
                        }
                        stock_arr[crr_depth].r = this_r;
                        new_sp_pos = New_Pos[sp_pos][this_r];
                        stock_arr[crr_depth].sp_pos = new_sp_pos;
                        tgt = Matrix.mval[new_sp_pos];
                        Matrix.mval[sp_pos] = tgt;
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;
                        md = stock_arr[crr_depth-1].md - R_Distance[new_sp_pos][tgt] +  R_Distance[sp_pos][tgt];
                        if(md > level_max_md_counter[crr_depth]) level_max_md_counter[crr_depth] = md;
                        if(md < level_min_md_counter[crr_depth]){
                                level_min_md_counter[crr_depth] = md;
                                Matrix_Min = Matrix;
                                min_depth = crr_depth;
                                for(i=0;i<crr_depth;i++) StackPath_Min[i] = stock_arr[i+1].r;
                        }

#ifdef INVD
                        sp_pos_p = Parity_omote2ura[sp_pos];
                        new_sp_pos_p = Parity_omote2ura[new_sp_pos];
                        tgt_p = Matrix_Parity.mval[new_sp_pos_p];
                        Matrix_Parity.mval[sp_pos_p] = tgt_p;
                        Matrix_Parity.mval[new_sp_pos_p] = -1;
                        inv1 = stock_arr[crr_depth-1].inv1;
                        inv2 = stock_arr[crr_depth-1].inv2;

                        if(this_r == U){
                                for(i=new_sp_pos+1;i<sp_pos;i++){
                                        if(Matrix.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix.mval[i];
                                        }
                                        if (val > tgt){
                                                inv1++;
                                        } else {
                                                inv1--;
                                        }
                                }
                        } else if(this_r == D){
                                for(i=sp_pos+1;i<new_sp_pos;i++){
                                        if(Matrix.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix.mval[i];
                                        }
                                        if (val > tgt){
                                                inv1--;
                                        } else {
                                                inv1++;
                                        }
                                }
                        } else if(this_r == L){
                                for(i=new_sp_pos_p+1;i<sp_pos_p;i++){
                                        if(Matrix_Parity.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix_Parity.mval[i];
                                        }
                                        if (val > tgt_p){
                                                inv2++;
                                        } else {
                                                inv2--;
                                        }
                                }
                        } else /* R */{
                                for(i=sp_pos_p+1;i<new_sp_pos_p;i++){
                                        if(Matrix_Parity.mval[i] < 0){
                                                val = i;
                                        } else {
                                                val = Matrix_Parity.mval[i];
                                        }
                                        if (val > tgt_p){
                                                inv2--;
                                        } else {
                                                inv2++;
                                        }
                                }
                        }

                        id1 = IDTBL1[inv1];
                        id2 = IDTBL2[inv2];
                        id = id1+id2;

                        stock_arr[crr_depth].id1 = id1;
                        stock_arr[crr_depth].id2 = id2;
                        stock_arr[crr_depth].inv1 = inv1;
                        stock_arr[crr_depth].inv2 = inv2;
                        wd = MAX(id,md);
                        stock_arr[crr_depth].wd = wd;

                        /**/    md = wd;
#endif

                        if(md == 0){
                                found = 1;
                                break;
                        }
                        stock_arr[crr_depth].md = md;

                        if(haba == 1){
                                hash_ret = get_hash(&Matrix, -1);
                                if(hash_ret != NULL){
                                        found = crr_depth;
                                        break;
                                }
                        }

                        if ( md > Threshold - crr_depth ){
                                sp_pos = new_sp_pos;
                                stack_dir = UP;
                                continue;
                        }

                        memcpy(stock_arr[crr_depth].new_pos,New_Pos[new_sp_pos],sizeof(char)*4);
                        npp = stock_arr[crr_depth].new_pos;

                        for(i=0;i<4;i++){
                                if(this_r - i == 2 || i - this_r == 2){
                                        npp[i] = -1;
                                        continue;
                                }
                        }

# ifdef YOKO_YUSEN
                        if(npp[1] >= 0) this_r = 1;
                        else if(npp[0] >= 0) this_r = 0;
                        else if(npp[3] >= 0) this_r = 3;
                        else if(npp[2] >= 0) this_r = 2;
                        else this_r = -1;
# else
                        if(npp[0] >= 0) this_r = 0;
                        else if(npp[1] >= 0) this_r = 1;
                        else if(npp[2] >= 0) this_r = 2;
                        else if(npp[3] >= 0) this_r = 3;
                        else this_r = -1;
# endif

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }


                } else {
                        if(crr_depth == 0){
                                return -1;
                        }
                        crr_depth--;

                        new_sp_pos = stock_arr[crr_depth].sp_pos;
                        Matrix.mval[sp_pos] = Matrix.mval[new_sp_pos];
                        Matrix.mval[new_sp_pos] = -1;
                        Matrix.sp_pos = new_sp_pos;

#ifdef INVD
                        sp_pos_p = Parity_omote2ura[sp_pos];
                        new_sp_pos_p = Parity_omote2ura[new_sp_pos];
                        Matrix_Parity.mval[sp_pos_p] = Matrix_Parity.mval[new_sp_pos_p];
                        Matrix_Parity.mval[new_sp_pos_p] = -1;
#endif

                        npp =  stock_arr[crr_depth].new_pos;
                        for(this_r = -1,i=0;i<4;i++){
                                if(npp[i] >= 0){
                                        this_r = i;
                                        break;
                                }
                        }

                        sp_pos = new_sp_pos;
                        if(this_r >= 0){
                                npp[this_r] = -1;
                                stack_dir = DOWN;
                        } else {
                                stack_dir = UP;
                        }

                }
        }

        if(found){
                for(i=0;i<crr_depth;i++){
                        StackPath[i] = stock_arr[i+1].r;
                }
                StackPath[i] = 0;
        }

        Matrix = tmp;
        return found;
}

int saiki(int depth, int pre_r){
        int ret;
        int px, py, cx, cy;
        int r;
        int diff;
        int wd;
        struct MATRIX tmp;

        if ( check_goal() ){
                return 1;
        }

        wd = m_distance();
        if ( depth + wd > Threshold ){
                return 0;
        }

        count_hanpuku++;
        if(count_hanpuku > max_count){
                return 0;
        }

        px = Matrix.sp_pos % matrix_size_x;
        py = Matrix.sp_pos / matrix_size_x;

        for ( r = 0; r < 4; r++ ){
                cx = px + DirectionX[r];
                cy = py + DirectionY[r];
                if(pre_r > r){
                        diff = pre_r - r;
                } else {
                        diff = r - pre_r;
                }
                if(diff == 2){
                        continue;
                }

                if ( cx < 0 || cy < 0 || cx >= matrix_size_x || cy >= matrix_size_y ){
                        continue;
                }

                if(Matrix.mval[cy*matrix_size_x+cx] == -2){
                        continue;
                }

                tmp = Matrix;
                Matrix.mval[py*matrix_size_x+px] = Matrix.mval[cy*matrix_size_x+cx];
                Matrix.mval[cy*matrix_size_x+cx] = -1;
                Matrix.sp_pos = cy*matrix_size_x+cx;
                ret = saiki( depth+1, r );
                if (ret) {
                        StackPath[depth] = r;

                        Matrix = tmp;
                        return 1;
                }
                Matrix = tmp;
        }
        return 0;
}



int HanpukuShinka(){
        int i;
        int sdcnt[3],sdsum[3],max=0,maxi=0;
        count_hanpuku = 0;
        hanpuku_done = 0;
        struct MATRIX matrix_backup, matrix_goal;
        int ret;

        matrix_backup = Matrix;
        if(pre_result_threshold > 0){
                Threshold = pre_result_threshold;
        } else {
                Threshold = m_distance();
        }
        for (ret = 0 ; Threshold <= MAX_STACK_LEVEL; Threshold += 2 ){
                if(haba == 1){
                        make_goal(&matrix_goal,&Matrix);
                        Matrix = matrix_goal;
                        haba_tansaku();
                        Matrix = matrix_backup;

                }
#ifdef DEBUG
                for(i=0;i<MAX_STACK_LEVEL;i++) level_counter[i] = 0;
                for(i=0;i<MAX_STACK_LEVEL;i++) level_max_md_counter[i] = 0;
                for(i=0;i<MAX_STACK_LEVEL;i++) level_min_md_counter[i] = 100000;
#endif
                ret = loop(0, -4);
                if(haba == 1){
                        free_hash();

                        if(ret >= 0){
                                for ( i = 0; i < ret; i++ ) printf("%c",Direction[StackPath[i]]);
                                fflush(stdout);
                                break;
                        }
                }

                if (ret >= 0){
                        for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[i]]);
                        printf("\n");
                        fflush(stdout);
                        return 1;
                } else {
                        if(hanpuku_done > 0) {
                                if(shurink > 0){
                                        hanpuku_done=0;
                                        count_hanpuku = 0;
                                        Matrix=Matrix_Min;
                                        if(shurink_mask > 0){
                                                for(i=0;i<3;i++){
                                                        max=0;
                                                        maxi=0;
                                                        step_dist = i;
                                                        make_harr(&Matrix);
                                                        sdsum[i] = 0;
                                                        for(CrrHarrIdx=0;CrrHarrIdx<HArr.arr_num;CrrHarrIdx++){
                                                                if(step_distance() == 0){
                                                                        sdsum[i] += HArr.arr_len[i];
                                                                } else {
                                                                        break;
                                                                }
                                                        }
                                                        sdcnt[i] = CrrHarrIdx;

                                                        if(sdsum[i] > max){
                                                                max = sdsum[i];
                                                                maxi = i;
                                                        }
                                                }
                                                step_dist = maxi;
                                                make_harr(&Matrix);

                                                if(shurink_mask > 1 && sdsum[maxi] > 0){
                                                        for(CrrHarrIdx=0;CrrHarrIdx<sdcnt[maxi];CrrHarrIdx++){
                                                                for(i=0;i<HArr.arr_len[CrrHarrIdx];i++){
                                                                        Matrix.mval[HArr.arr[CrrHarrIdx][i]] = -2;
                                                                }
                                                        }
                                                }
                                        }
                                        Threshold = m_distance();
                                        for ( i = 0; i < min_depth; i++ ) printf("%c",Direction[StackPath_Min[i]]);
                                        shurink--;
                                        continue;
                                }
                                break;
                        }
                }

        }

        if(ret < 2){
                printf(" not found in HanpukuShinka(start distance(%d),count_hanpuku(%lld)) for Threshold:%d\n",m_distance(),count_hanpuku,Threshold+2);
                fflush(stdout);
                return 0;
        }

        Threshold = m_distance();
        for ( ; Threshold <= MAX_STACK_LEVEL; Threshold += 2 ){
                haba = 0;
                ret = loop(0, -4);
                haba = 1;

                if (ret != 0){
                        for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[i]]);
                        printf("\n");
                        fflush(stdout);
                        return 1;
                } else {
                        if(hanpuku_done > 0) {
                                break;
                        }
                }
        }

        printf(" not found in HabaYusen & HanpukuShinka(start distance(%d),count_hanpuku(%lld)) for Threshold:%d\n",m_distance(),count_hanpuku,Threshold+2);
        fflush(stdout);
        return 0;
}

int StepShinka(){
        int i;
        int ret;
        int this_r;
        int pre_depth;

        count_hanpuku = 0;
        this_r = -4;
        pre_depth = 0;
        for(CrrHarrIdx=0;CrrHarrIdx<HArr.arr_num;CrrHarrIdx++){
                ret = 0;
                for ( Threshold = step_distance(); Threshold <= MAX_STACK_LEVEL; Threshold++ ){
                        Matrix_backup = Matrix;
                        ret = steploop(pre_depth, 0, this_r);
                        if ( ret > 0 ){
                                break;
                        }

                        if(count_hanpuku > max_count){
                                break;
                        }
                        Matrix = Matrix_backup;
                }


                if(ret == 0){
                        printf(" not found in StepShinka(count_hanpuku(%lld)) for Threshold(%d),CrrHarrIdx(%d)\n",count_hanpuku,Threshold+1,CrrHarrIdx);
                        fflush(stdout);
                        return 0;
                }



                for ( i = 0; i < Threshold; i++ ) printf("%c",Direction[StackPath[pre_depth+i]]);
                if(simflg) for ( i = 0; i < Threshold; i++ ) moving_history[mh_cnt++] = StackPath[pre_depth+i];
                pre_depth += Threshold;
                this_r = StackPath[Threshold-1];
                for(i=0;i<HArr.arr_len[CrrHarrIdx];i++){
                        Matrix.mval[HArr.arr[CrrHarrIdx][i]] = -2;
                }
                fix_new_pos(&Matrix);
        }
        printf("\n");
        fflush(stdout);

        return 1;
}

int get_tgt(char c){

        if(c == '='){
                c = -2;
        } else if('Z' >= c && c >= 'A'){
                c = c - 'A' + 9;
        } else if('z' >= c && c >= 'a'){
                c = c - 'a' + 9;
        } else if('9' >= c && c >= '1'){
                c = c - '1';
        } else if(c == '.' || c == '0'){
                c = -1;
        } else {
                c = -3;
        }
        return c;
}

void sim(){
        int md,i,j;
        char buff[MAXIDTBL];
        int mode2=-1;
        int this_r;
        char *c;
        int tgt;
        struct MATRIX Matrix_org,Matrix_tmp,Matrix_stp;
        int ret;
        char New_Pos_org[36][4];

        Matrix_tmp = Matrix;
        Matrix_org = Matrix;
        memcpy(New_Pos_org,New_Pos,sizeof(New_Pos));
        mh_cnt = 0;
        if(kaitou){
                printf("%s %s\n",mondai,kaitou);
        } else {
                printf("%s\n",mondai);
        }
        printf("\n");
        dump_matrix2(&Matrix);

        if(kaitou){


                c = kaitou;
                while(*c){
                        this_r = get_r(c);
                        if(this_r < 0) continue;

                        if(New_Pos[Matrix.sp_pos][this_r]>=0){
                                mv_koma(this_r);
                                moving_history[mh_cnt++] = this_r;
                        }
                        c++;
                }

                printf("\n");
                dump_matrix2(&Matrix);
        }

        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");

        while(fgets(buff,MAXIDTBL-1,stdin) != NULL){
                for(i=0;buff[i];i++){
                        if(mode == 0){
                                if(i==0){
                                        if(buff[0] == 'c'){
                                                mode = 1;
                                                dump_matrix2(&Matrix);
                                                if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                                break;
                                        }
                                }
                                if(buff[i] == '\n'){
                                        dump_matrix2(&Matrix);
                                        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                        break;
                                }
                                this_r = -1;
                                if(buff[i]=='U' || buff[i]=='u') this_r = 0;
                                if(buff[i]=='L' || buff[i]=='l') this_r = 1;
                                if(buff[i]=='D' || buff[i]=='d') this_r = 2;
                                if(buff[i]=='R' || buff[i]=='r') this_r = 3;

                                if(buff[i] == 0x1b && buff[i+1] == '['){
                                        if(buff[i+2] == 'A'){this_r = 0; i+=2;}
                                        if(buff[i+2] == 'B'){this_r = 2; i+=2;}
                                        if(buff[i+2] == 'C'){this_r = 3; i+=2;}
                                        if(buff[i+2] == 'D'){this_r = 1; i+=2;}
                                }

                                if(this_r < 0) continue;



                                if(this_r < 0) continue;
                                if(New_Pos[Matrix.sp_pos][this_r]>=0){
                                        mv_koma(this_r);
                                        moving_history[mh_cnt++] = this_r;
                                }

                                md = m_distance();
                                if(md == 0){
                                        dump_matrix2(&Matrix);
                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                        printf("\n");
                                        printf("done\n");
                                        return;
                                }

                        } else { //command mode
                                if(buff[i] == '\n'){
                                        if(mode2 == STEP){
                                                Matrix_stp = Matrix;
                                                ret = StepShinka();
                                                if(ret <=0){
                                                        Matrix = Matrix_stp;
                                                }
                                                md = m_distance();
                                                if(md == 0){
                                                        dump_matrix2(&Matrix);
                                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                        printf("\n");
                                                        printf("done\n");
                                                        return;
                                                }
                                        }

                                        dump_matrix2(&Matrix);
                                        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                        mode2 = -1;
                                        break;
                                }
                                if(i==0){
                                        if(buff[0] == 'm') {
                                                if(buff[1] == '\n'){
                                                        mode = 0;
                                                        if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                        for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                                        break;
                                                } else {
                                                        mode2 = MOVE;
                                                }
                                        }else if(buff[0] == 'h') mode2 = HANPUKU;
                                        else if(buff[0] == 's'){
                                                mode2 = STEP;
                                                HArr.arr_num = 1;
                                                HArr.arr_len[0] = 0;
                                        }else if(buff[0] == 'S') mode2 = STEP_TARGET;
                                        else if(buff[0] == 'i'){
                                                printf("mh_cnt:[%d]\n",mh_cnt);
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                printf("\n");

                                        }else if(buff[0] == 'f') mode2 = FIX;
                                        else if(buff[0] == 'F') mode2 = UNFIX;
                                        else if(buff[0] == 'U'){
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                printf("\n");
                                                Matrix = Matrix_org;
                                                Matrix_tmp = Matrix;
                                                memcpy(New_Pos,New_Pos_org,sizeof(New_Pos));
                                                mh_cnt = 0;
                                                if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                break;
                                        }else if(buff[0] == 'm'){
                                                mode2 = MOVE;
                                        }else if(buff[0] == 'N'){
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]);
                                                printf("\n");
                                                return;
                                        }else if(buff[0] == 'b') {

                                        }else {
                                                dump_matrix(&Matrix);
                                                printf("bad command...ignored.\n");
                                                if(mode == 0) printf("moving mode input:\n"); else printf("command mode input:\n");
                                                break;
                                        }
                                        continue;
                                }
                                if(mode2 == MOVE){
                                        this_r = -1;
                                        if(buff[i]=='U' || buff[i]=='u') this_r = 0;
                                        if(buff[i]=='L' || buff[i]=='l') this_r = 1;
                                        if(buff[i]=='D' || buff[i]=='d') this_r = 2;
                                        if(buff[i]=='R' || buff[i]=='r') this_r = 3;

                                        if(buff[i] == 0x1b && buff[i+1] == '['){
                                                if(buff[i+2] == 'A'){this_r = 0; i+=2;}
                                                if(buff[i+2] == 'B'){this_r = 2; i+=2;}
                                                if(buff[i+2] == 'C'){this_r = 3; i+=2;}
                                                if(buff[i+2] == 'D'){this_r = 1; i+=2;}
                                        }
                                        if(this_r < 0) continue;
                                        if(New_Pos[Matrix.sp_pos][this_r]>=0){
                                                mv_koma(this_r);
                                                moving_history[mh_cnt++] = this_r;
                                        }
                                        md = m_distance();
                                        if(md == 0){
                                                dump_matrix2(&Matrix);
                                                for ( j = 0; j < mh_cnt; j++ ) printf("%c",Direction[moving_history[j]]); printf("\n");
                                                printf("done\n");
                                                return;
                                        }

                                }
                                if(mode2 == STEP){
                                        tgt = get_tgt(buff[i]);
                                        if(tgt >= 0){
                                                HArr.arr[0][HArr.arr_len[0]] = tgt;
                                                HArr.arr_len[0]++;
                                        }
                                }
                                if(mode2 == FIX){
                                        tgt = get_tgt(buff[i]);

                                        if(tgt >=0){
                                                if(Matrix.mval[tgt] >= 0){
                                                        Matrix_tmp.mval[tgt] = Matrix.mval[tgt];
                                                        Matrix.mval[tgt] = -2;
                                                }
                                        }
                                }
                                if(mode2 == UNFIX){
                                        tgt = get_tgt(buff[i]);

                                        if(tgt >=0){
                                                if(Matrix_tmp.mval[tgt] >= 0){
                                                        Matrix.mval[tgt] = Matrix_tmp.mval[tgt];
                                                        Matrix_tmp.mval[tgt] = -3;
                                                }
                                        }
                                }


                                //}//for

                }//command mode

        }
}

}
int set_data(char *in_file){
        int i,j;
        char *c,*p,*t;
        static char buf[1024];
        static char str[1024];
        int len;
        static FILE  *fp=NULL;
        int x,y;
        char *ret;

        if(fp == NULL){
                fp = fopen(in_file, "r");

#ifdef INVD
                for(i=0; i<MAXIDTBL; i++){
                        IDTBL3[i] = (i/2);
                        IDTBL4[i] = (i/3) + (i%3);
                        IDTBL5[i] = (i/4) + (i%4)/2;
                        IDTBL6[i] = (i/5) + (i%5)/3 + ((i%5)%3);
                }
#endif

        }
        if(fp == NULL){
                printf("ERR: cant open [%s]\n",in_file);
                exit(0);
        }

        while(1){
                ret = fgets( buf, 1023, fp );
                if(ret == NULL){
                        return 0;
                }

                if(strchr(buf,',')){
                        break;
                }
        }


        len = strlen(buf);
        buf[len-1] = 0;

        if(strstr(buf,"input ")){
                strcpy(str,&buf[6]);
                mondai = &buf[6];
        } else {
                strcpy(str,buf);
                mondai = buf;
        }

        t=strchr(mondai,' ');
        if(t){
                *t++ = 0;
                kaitou = t;
                if((t =strchr(kaitou,' ')) != NULL){
                        *t = 0;
                }
        } else {
                kaitou = NULL;
        }

        // file format
        // [4,5,5G3486F7092C1ADJEHBI:not found in HanpukuShinka for Threshold:201]
        // [6,5,82935=174ABCD=RHTNJKFLI0PQSOGM ULDDRUULLULULLDRURRDDDLURDRDLLUURDRDRULDR]

        str[1] = 0;
        str[3] = 0;
        matrix_size_x = atoi(str);
        matrix_size_y = atoi(&str[2]);
        matrix_size = matrix_size_x * matrix_size_y;

        c = &str[4];

        t = strchr(c,' ');
        if(t){
                *t++ = 0;
                pre_result_string = t;
        } else {
                pre_result_string = NULL;
        }


        if(t){
                p = strchr(t,':');
        } else {
                p = NULL;
        }
        if(p){
                *p++ = 0;
                pre_result_threshold = atoi(p);
        } else {
                pre_result_threshold = 0;
        }


        for ( i = 0; i < matrix_size; i++ ){
                if(c[i] == '='){
                        c[i] = -2;
                } else if(c[i] >= 'A'){
                        c[i] = c[i] - 'A' + 9;
                } else {
                        c[i] = c[i] - '1';
                }
                Matrix.mval[i] = c[i];
                if(c[i] == -1){
                        Matrix.sp_pos = i;
                }
        }


        for(i=0;i<matrix_size;i++){
                x = i % matrix_size_x;
                y = i / matrix_size_x;
                Parity_omote2ura[i] = x*matrix_size_y+y;

                x = i % matrix_size_y;
                y = i / matrix_size_y;
                Parity_ura2omote[i] = x*matrix_size_x+y;
        }

        for(i=0;i<matrix_size;i++){
                j = Matrix.mval[Parity_ura2omote[i]];
                if(j == -1){
                        Matrix_Parity.mval[i] = j;
                } else if(j == -2){
                        Matrix_Parity.mval[i] = j;
                } else {
                        Matrix_Parity.mval[i] = Parity_omote2ura[j];
                }
        }



        if(matrix_size_x == 3) IDTBL1 = IDTBL3;
        if(matrix_size_x == 4) IDTBL1 = IDTBL4;
        if(matrix_size_x == 5) IDTBL1 = IDTBL5;
        if(matrix_size_x == 6) IDTBL1 = IDTBL6;

        if(matrix_size_y == 3) IDTBL2 = IDTBL3;
        if(matrix_size_y == 4) IDTBL2 = IDTBL4;
        if(matrix_size_y == 5) IDTBL2 = IDTBL5;
        if(matrix_size_y == 6) IDTBL2 = IDTBL6;

        set_m_distance();
        set_r_distance(&Matrix);

        make_harr(&Matrix);

        make_new_pos(&Matrix);


        return 1;
}

int main(int ac, char **av){
        char *in;
        int ret;
        int i,cnt;;

        if(ac < 3){
                printf("useage:cmd inputfile how [max_count]\n");
                exit(0);
        }

        in = av[1];
        if(ac >= 4){
                max_count = (long long)atoi(av[3]) * (long long)10000;
        } else {
                max_count = (long long)MAX_HANPUKU * (long long)10000;
        }



        haba_stack = malloc(sizeof(struct MATRIX)*max_haba_stack);
        if(haba_stack == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }

        hash_table = malloc(sizeof(struct HASH_LIST **)*max_haba_stack);
        if(hash_table == NULL){
                fprintf(stderr,"ERR: cant allocate memmory\n");
                exit(0);
        }
        bzero(hash_table,sizeof(struct HASH_LIST **)*max_haba_stack);

        Hash_List = malloc(sizeof(struct HASH_LIST)*max_haba_stack);





        while(1){
                ret = set_data(in);
                if(ret == 0){
                        exit(0);
                }

                if(matrix_size_x < 3 || matrix_size_x > 6 || matrix_size_y < 3 || matrix_size_y > 6){
                        continue;
                }

                if(strcmp(av[2],"check") == 0){
                        check_pre_result_path();
                        continue;
                }

                if(strcmp(av[2],"sim") == 0){
                        simflg = 1;
                        sim();
                        continue;
                }

                if(kaitou){
                        for(cnt=0,i=0;kaitou[i];i++){
                                if(kaitou[i] != 'U' && kaitou[i] != 'L' && kaitou[i] != 'D' && kaitou[i] != 'R') cnt++;
                        }
                        if(cnt == 0){

                                printf("input %s %s\n", mondai,kaitou);
                                fflush(stdout);
                                continue;
                        }
                }


                if(strcmp(av[2],"md") == 0){
                        printf("%d\t%s\n",m_distance(),mondai);
                        continue;
                }
                printf("input %s ", mondai);
                fflush(stdout);

                if(strcmp(av[2],"hanpuku") == 0){
                        HanpukuShinka();
                        continue;
                }

                if(strcmp(av[2],"shurink") == 0){
                        if(ac >= 5){
                                shurink = atoi(av[4]);
                        } else {
                                shurink = 1;
                        }

                        if(ac >=6){
                                shurink_mask = atoi(av[5]);
                        } else {
                                shurink_mask = 0;
                        }
                        HanpukuShinka();
                        continue;
                }

                if(strcmp(av[2],"haba") == 0){
                        if(ac >= 5){
                                max_haba_stack = atoi(av[4]) * 1024*1024/(sizeof(struct MATRIX)*sizeof(struct HASH_LIST **)*2);
                        } else {
                                max_haba_stack = 1024*1024/(sizeof(struct MATRIX)*sizeof(struct HASH_LIST **)*2);
                        }

                        haba = 1;
                        HanpukuShinka();
                        continue;
                }

                if(strcmp(av[2],"step") == 0){
                        if(ac >= 5){
                                step_dist = atoi(av[4]);
                        } else {
                                step_dist = 0;
                        }
                        StepShinka();
                }

                if(strcmp(av[2],"matrix") == 0){
                        dump_matrix(&Matrix);
                        continue;
                }

        }
        exit(0);
}

PHPでpcntl_forkでふぉーくの薀蓄

2011-04-14T15:50:00.015+09:00

えー、勢いあまってPHPでマルチプロセスを実装してみました。
ある意味血迷ってるといまさらながら思いますが、最初は・・・言語かえるのやだし、ちょこっとググッたらできそうな感じだったので。。。

もちろん、やっとちゃんと動きましたよ。
ええかなりちゃんとしてます。
でも、、、Cとかお流行のJAVAに書き換える日はもう見えてるんで。ええ。

ググれば出てくるさんぷるクリプト

大体、「PHP　pcntl_fork」でぐぐればいっぱい使い方が見つかります。みつかるけど・・・これだけではなんだかようわからない。
PHP: pcntl_fork - Manual

//子プロセス生成
$pid = pcntl_fork();
if ($pid == -1)
{
  // fork失敗
  echo 'Failed forc process.';
  exit(1);
}
else if ($pid) 
{
  //親プロセス
  $mypid = getmypid();
  printf("mypid:%d pid:%d\n", $mypid, $pid);
  pcntl_waitpid($status);
}else{
  // 子プロセス
  $mypid = getmypid();
  printf("mypid:%d pid:%d\n", $mypid, $pid);
  exit(0);
}

実装したい場合って割と複雑なんですね。で、特にApacheと一緒に使うわけじゃないので、更にいろいろとあるわけです。（Apacheと一緒に使うならこれは使わないほうがいい。）

batch処理をするのにPHPを選んでる時点でちょっと負けた気がする。。。
ちなみに、batchで使うときのPHPはクライアントモードとかCGIモードとか言うみたいなのだけれど、本当かどうかは不明。

で、このクライアントモードでしか使わないので、いろいろな制限を無制限にしちゃったりしている。
その上でマルチプロセスで一気に平行処理をして歩いいというのが今回の目的。

実装する仕事

・リモートファイルの取得
・中身の集計
・各ジャンルごとにデータベース（MySQL）に集計結果を格納

この流れで平行で10個くらい走って間もらいます。ちなみに、直列でも可。
ただ1日は24時間しかなくて1個2時間かかってたらずーっと仕事してることになって効率が悪い。
マルチプロセスでそれぞれ仕事してくれたらまぁ3時間で全部終わるくらいになることを期待しているのん。

さて、さて。。結局はちら様のソースを元に作らせていただいた↓
PHPでの並列処理について - With-No-Parachute D-side

ただ、すんなりこのとおりでは動かなかった。
こちら様の前提は、PHP5.3.ｘで、うちはなんと、PHP5.2.ｘ
そんなに大事ではないのだけれど、ちょっとかっこいいなぁって思っていた「無名関数」っていうのが使えないので

// 子プロセスで行う仕事
if (!is_array($this->work)) //外部クロージャが設定されている場合
{
  $function = $this->work;
  $function($arg);
}

これが使えない。もう一個の方は問題なく実行できたのでそちらのみ利用。しかし、両方書いておいて下さるなんて素敵だ。

あとは、ファイル分割をしたときのスコープがいろいろと変わってくるので、何度と無くテストをして動いてくれるまで持っていく。
このときに注意が必要なのは、シグナルハンドラのセット位置と、declare(ticks=1) {}の記述場所。

位置を間違えると期待通りの振る舞いにはならない。
あと忘れてはならないのが、MySQLのこと。こちら様の例にはMySQLの例は記載されていないので、やはりまたぐぐる。
次に参考にさせていただいたのがこちら様↓
小泉守義のPHPソースコードウォッチ - pcntl_fork() - fork() で複製される fd に注意セヨ....

こちらにも書かれているとおり、接続する場所がとても重要。親と子の間でデータが渡せるとはいえ、コネクションはNGなのだ。
なぜか共有すると、誰かの処理が終わった時点でみんなのコネクション（オブジェクト？）が破棄されているような振る舞いになる。
あの大嫌いな。。。。。あれが出る。
Lost connection to MySQL server
MySQL server has gone away
とかとか。毎回同じのが出るわけでもないし、ある種ハマルこと間違いない（－－

ここはひとつ素直におまじないだと思って、子プロセスでコネクションを張ろうと心に誓うのがよい。
が、しかーし。。更に大きな落とし穴がある。
こちら様や、ほかの方々の例をみるとみなさま全てmysql_connect()を使っていらっしゃる。実はこれが大きなヒント！

自分、PDOっス（－－

と思っては見たものの、中身はmysql_connect()なわけだから、何も考えずに実装。
意外と問題なくて、mysql_connect()のところを　$dbh = new PDO();　煮してあげればO.K.

が、しかーし、地獄はここから始まった。。。苦節2weekぐらいかも。なれないstraceとかして原因を探るとか（意味わかんないから眺めて勘だより）ぐぐりまくりましたよ。
もちろんBugも疑い、「バグジャン」っていってる外人さんに「バグじゃないよ。ちゃんと使い方みな」なんて書いてるPHPの中の人らしきコメントを読んだり。。。
マジ疲れました。
で、結局。PHPの中の人が正しい　（＊'▽'）db（'▽'＊）　ねー。

さんぷるクリプト

なんか切れるほう

try{
  $pdo = new PDO( $dns, $user, $pass, array(
    PDO::ATTR_PERSISTENT => true,
    PDO::MYSQL_ATTR_LOCAL_INFILE => true,
    PDO::MYSQL_ATTR_INIT_COMMAND => 'SET CHARACTER SET ujis;'
  ));
  $pdo->setAttribute( PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION );
}catch( PDOException $e ){
  printf("PDOException:%s\n",$e->getMessage());
  exit(1);
}

切れないほう

try{
  $pdo = new PDO( $dns, $user, $pass, array(
    PDO::MYSQL_ATTR_LOCAL_INFILE => true,
    PDO::MYSQL_ATTR_INIT_COMMAND => 'SET CHARACTER SET ujis;'
  ));
  $pdo->setAttribute( PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION );
}catch( PDOException $e ){
  printf("PDOException:%s\n",$e->getMessage());
  exit(1);
}

どっちも繋がるのだけど、切れるほうは割と始めのほうで切れる。それいご切れないのに、最初の何かがきれうる。
ずーっと悩んでたんですけどね、あれです、見ていただいたとおり。。。
子プロセスに仕事させたいなら持続的な接続ってやつはご法度なんです（－－　mysql_pconnect()　は、つかっちゃーいかんのです！

PHP: mysql_pconnect - Manual

1 番目の違いとして、この関数は接続時にまず 同じホスト、ユーザ名、パスワードを有する(持続的)リンクが すでにオープンされていないかどうかを調べます。
 それがみつかった場合、新規の接続をオープンする代わりに そのリンクの ID が返されます。

ほかの子プロセスのを掴んじゃったりするんじゃないかい・・・・

2 番目の違いは、スクリプトの実行が終了しても SQL サーバとの接続が 閉じられないということです。
そのかわりに、将来再利用されるために リンクがオープンされたままとなります（mysql_close() は、mysql_pconnect()によって確立されたリンクを 閉じません）。

けっこういっぱいプロセスがいるから、また変なのをつかんじゃうよね？

と、思うしだいでありました。
本当のところはわからないのだけれど、変えたら切れなくなったし。。。
まだまだ謎がおおいんですね。

お世話になったリンクのまとめ

PHP: pcntl_fork - Manual
PHP: mysql_pconnect - Manual
PHPでの並列処理について - With-No-Parachute D-side
小泉守義のPHPソースコードウォッチ - pcntl_fork() - fork() で複製される fd に注意セヨ....

system callのtraceについて - YutaKikuchiのTechBlog

mysql.php at PHPPDO - Free PHP Code

PHPでビット演算、シフト演算

2011-01-26T14:53:00.003+09:00

ビットをフラグ代りに使うことが増えてきたので。。。
1ビット1アイテムって思うと、最大で63個まで持ってるか分かるようになる的な。
なんで63個かっていうと64個だとMySQLにしまえない可能性があるみたい。
（使ってるVerが古いってのもあるし、そもそも勘違いかもだけどー。）
とりあえず、PHPで書いたさんぷる。

さんぷるクリプト


// 色情報
$items=array('red'=>1, 'blue'=>2, 'green'=>3, 'white'=>4, 'black'=>5);
// 人情報
$peoples = array('LILY'=>0, 'LOGAN'=>0, 'OLIVIA'=>0);
/*
 * 選択情報を作る
 */
$peoples['LILY'] =
 (1 << $items['red'])
 | (1 << $items['green'])
 | (1 << $items['black']) ;  // red, green, black を選ぶ

printf("name:% 7s int:% 4d bit:%08b\n",
 'LILY', $peoples['LILY'], $peoples['LILY']);

$peoples['LOGAN'] =
 (1 << $items['blue'])
 | (1 << $items['green'])
 | (1 << $items['black']) ;  // blue, green, black を選ぶ

printf("name:% 7s int:% 4d bit:%08b\n",
 'LOGAN', $peoples['LOGAN'], $peoples['LOGAN']);

$peoples['OLIVIA'] =
 (1 << $items['red'])
 | (1 << $items['white'])
 | (1 << $items['black']) ;  // red, white, black を選ぶ

printf("name:% 7s int:% 4d bit:%08b\n",
 'OLIVIA', $peoples['OLIVIA'], $peoples['OLIVIA']);

print "======================\n";

/*
 * 皆が選択している色だけを選らぶ
 * (論理積)
 */
$common_col=0;
$common_col=
 $peoples['LILY'] & $peoples['LOGAN'] & $peoples['OLIVIA'] ;
printf("common colors int:% 4d bit:%08b\n", $common_col, $common_col);
chkSelections($common_col);

print "======================\n";

/*
 * 選択されている全ての色を選ぶ
 * (論理和)
 */
$common_col=0;
$common_col=
 $peoples['LILY'] | $peoples['LOGAN'] | $peoples['OLIVIA'] ;
printf("common colors int:% 4d bit:%08b\n", $common_col, $common_col);
chkSelections($common_col);

exit;

/*
 * ビットが立っているものを探す
 */
function chkSelections($selections)
{
  global $items;
  
  foreach ( $items as $col_name => $col_num )
  {
    $chk_bit=( 1 << $col_num );
    if( $selections & $chk_bit ) // ビットが立ってる
    {
      printf("Select color:% 6s\n", $col_name);
    }
  }
}

シフト演算でビットが立っているところを探していく方法もあるけど。


$col_num=0;
while( $selections )
{
  if( $selections & 1 )
  {
    printf("Select color number:%d bit:%08b\n", $col_num, $selections);
  }
   $selections = $selections >> 1;
  $col_num++;
}

MySQL

選択情報をMySQLに格納して、クエリで取得することもできる。


SELECT * hoge WHERE select_bit & ${col_num} ;

これでその色を選択している情報が引っ張れるです。

PerlのImage::Magick

2010-12-21T15:59:00.001+09:00

画像合成をする場合に使うライブラリのさんぷるクリプト

ImageMagick

さんぷるクリプト


#!/usr/bin/perl

use strict;
use warnings;

use Image::Magick;

my $dir = 'images';
my $width = 192;
my $height= 53;

my $i3 = Image::Magick->new(width=>$width, height=>$height, magick=>'GIF');
$i3->Read("$dir/layer3.gif");

my $i2 = Image::Magick->new(width=>$width, height=>$height, magick=>'GIF');
$i2->Read("$dir/layer2.gif");
$i3->Composite(image=>$i2, compose=>'Over', x=>0, y=>0);

my $i1 = Image::Magick->new(width=>$width, height=>$height, magick=>'GIF');
$i1->Read("$dir/layer1.gif");
$i3->Composite(image=>$i1, compose=>'Over', x=>0, y=>0);

$i3->Write("$dir/mix_i.gif");

#binmode STDOUT;
#$i3->Write('gif:-');

exit;

PerlのGD

2010-12-21T15:54:00.003+09:00

画像合成をする場合に使うライブラリのさんぷるクリプト

GD

さんぷるクリプト


#!/usr/bin/perl

use strict;
use warnings;

use GD;

my $dir = 'images';
my $width = 192;
my $height= 53;

my $image = new GD::Image($width, $height);

my $i3 = new GD::Image("$dir/layer3.gif");
$image->copy($i3, 0, 0, 0, 0, $width, $height);

my $i2 = new GD::Image("$dir/layer2.gif");
my $i1 = new GD::Image("$dir/layer1.gif");
$i2->copy($i1, 0, 0, 0, 0, $width, $height);
$image->copy($i2, 0, 0, 0, 0, $width, $height);

open(OUT, ">$dir/mix.gif");
binmode OUT;
print OUT $image->gif;
close(OUT);

exit;

CのApache-module：：基本GETパラメータ

2010-12-20T16:43:00.011+09:00

apacheモジュールでGETパラメータを受け取る方法。
GETとPOSTでは処理が違うのがミソですね。。POST難しい。。。

GETパラメータはrequest_rec構造体のメンバであるargsに文字列として渡されます。
1個しかないと分かっていれば簡単ですけど、つらつらと渡されることもあるので、複数のパラメータがあると想定します。

方法はループ処理で取得するのでお好みなのを使えばいいと思うのですが、とりあえず2個のサンプルを書いてみました。

for 文を使う

do ... while 文を使う

個々のパラメータ処理

keyとvalをハッシュに格納します。
また、同一keyで異なるパラメータが送られてきても受け取れるようにvalは配列にします。

○確認方法
curllが入っていれば簡単。複数パラメータは、” --- ” でくくらないと切れてしまいますー。

Telnetの場合はこんなん ○関数メモ

CのApache-module：：基本

2010-12-16T18:27:00.007+09:00

apacheモジュールの超基本形。スタティックページならこんなんでOK.
ついでにapacheの設定も書いておきましょ。。

httpd.confに書くこと

PerlのImage::Imlib2

2010-12-01T15:14:00.005+09:00

画像合成をする場合に使うライブラリのさんぷるクリプト

Imlib2：インストール方法は簡単なyum使ってるのでまぁ・・・参考程度で。

取り合えずgifが作られればいいので、必要だというlibgifとlibungifを入れる。
libungifにlibgifも入っているらしいので、libungifを入れる。

本体入れる

Perlモジュール入れる

使う

さんぷるクリプト


#!/usr/bin/perl

use strict;
use warnings;

use Image::Imlib2;

my $dir = 'images';

my $image = Image::Imlib2->load("$dir/layer3.gif");

my $i2 = Image::Imlib2->load("$dir/layer2.gif");
$image->blend($i2, 0, 0, 0, $image->width, $image->height, 0, 0, $image->width, $image->height);

my $i1 = Image::Imlib2->load("$dir/layer1.gif");
$image->blend($i1, 0, 0, 0, $image->width, $image->height, 0, 0, $image->width, $image->height);

$image->set_quality(100);
$image->image_set_format('png');
$image->save("$dir/mix.png");

exit;

さんぷるクリプト

g++でコンパイル

warning: enumeration value ‘***’ not handled in switch [-Wswitch]

warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]

AmazonEC2でEBS

新規にVolumeをAttachする場合

snapshotからVolumeを作成しAttachする場合

CのApache-module：：subprocess_env構造体

AmazonEC2を使ってみる

0.アカウントを作る

1.インスタンスを立ち上げる

2.まずはじめにやる事

初めて symfony でプロジェクトを作ってみた

1．取りあえずrootで作っちゃう

2．プロジェクト用のディレクトリを作成

3．プロジェクト（スケルトン）作成

4．アプリケーション設置

5．開発用ファイルを使えるようにする

6．Apacheの設定

AmazonEC2にS3領域をマウントしてみる

1.FUSEにいる物をインストール

2.FUSEインストール

3.f3sfインストール

4.A3にバケット作成

5.マウント

6.再起動してもマウント

＊＊＊ うーんうまくできなかった (´；ω；`)ｳｯ… ＊＊＊

CでDevquiz２０１１スライドパズル その３

スライドパズルに関するアルゴリズムのサマリー

CでDevquiz２０１１スライドパズル その２

解説1

端優先

ステップ実行

CでDevquiz２０１１スライドパズル

アルゴリズム

excuse

実際のソース

PHPでpcntl_forkでふぉーくの薀蓄

ググれば出てくるさんぷるクリプト

実装する仕事

さんぷるクリプト

お世話になったリンクのまとめ

PHPでビット演算、シフト演算

さんぷるクリプト

MySQL

PerlのImage::Magick

さんぷるクリプト

PerlのGD

さんぷるクリプト

CのApache-module：：基本GETパラメータ

for 文を使う

do ... while 文を使う

個々のパラメータ処理

CのApache-module：：基本

httpd.confに書くこと

PerlのImage::Imlib2

さんぷるクリプト

＊＊＊　うーんうまくできなかった (´；ω；`)ｳｯ…　＊＊＊

CでDevquiz２０１１スライドパズル　その３

CでDevquiz２０１１スライドパズル　その２