意外と日本語のページが引っかからなかったので書いときます。
try {
Field field = process.getClass().getDeclaredField("pid");
field.setAccessible(true);
int pid = field.getInt(process);
} catch (NoSuchFieldException|IllegalAccessException ex) {
ex.printStackTrace();
}
processはRuntime.execが返したjava.lang.Process、Fieldはjava.lang.reflect.Field。
2015年4月6日月曜日
2014年7月19日土曜日
SECCON 2014 オンライン予選 writeup - プログラミング300 あみだ
手動で2時間くらいかけて150問解いたところで挫折、
プログラムで解こうとコーディングを始めて１時間半で終了。
最初から組めや＞自分
手順は以下の通り。
*が開始座標
*の[上下右左]が[||--]ならそれが進行方向、1つ進む
while 現在位置が[||--]
現在位置の進行方向横が[-|]なら[|-]になるまで横にスライド
1つ進行方向に進む
現在位置の文字出力
No.79だけバグってる模様。これだけハードコードで7。
(バグってたのは自分の頭、2014/07/22訂正)
1,000問解いてやっとキーが出てきた。
手順は以下の通り。
*が開始座標
*の[上下右左]が[||--]ならそれが進行方向、1つ進む
while 現在位置が[||--]
現在位置の進行方向横が[-|]なら[|-]になるまで横にスライド
1つ進行方向に進む
現在位置の文字出力
import java.io.*;
import java.util.*;
public class T {
public static final int NO_DIRECTION = 0;
public static final int TO_DOWN = 1;
public static final int TO_UP = 2;
public static final int TO_RIGHT = 3;
public static final int TO_LEFT = 4;
public static void main(String args[]) {
InputStream is = null;
OutputStream os = null;
try {
Process p = Runtime.getRuntime().exec("./amida");
is = p.getInputStream();
os = p.getOutputStream();
} catch (Exception ex) {
ex.printStackTrace();
}
try {
new T().go(is, os);
} catch (Exception ex) {
ex.printStackTrace();
}
}
public void go(InputStream is, OutputStream os) throws Exception {
int no = 1;
while (true) {
int c;
int width = 0;
int height = 0;
while ((c = is.read()) != '\n') {
if (c == -1)
System.exit(1);
System.out.print((char)c);
}
System.out.println();
StringBuffer sb = new StringBuffer();
String line = null;
ArrayList list = new ArrayList();
while ((c = is.read()) != '?') {
if (c == -1)
System.exit(1);
// System.out.println("2:" + c);
if (c == '\n') {
line = sb.toString();
if (line.length() > 0) {
width = line.length();
list.add(line);
sb = new StringBuffer();
}
} else {
sb.append((char)c);
}
}
is.read();
height = list.size();
char amida[][] = new char[height][width];
int startX = 0;
int startY = 0;
for (int i = 0; i < list.size(); i++) {
line = list.get(i);
System.out.println(line);
for (int j = 0; j < line.length(); j++) {
amida[i][j] = line.charAt(j);
if (amida[i][j] == '*') {
startY = i;
startX = j;
}
}
}
//System.out.println(startY + ":" + startX);
int direction = NO_DIRECTION;
int y = startY;
int x = startX;
if (startY == 0 && amida[1][startX] == '|') {
direction = TO_DOWN;
y++;
} else if (startY == height - 1 &&
amida[height - 2][startX] == '|') {
direction = TO_UP;
y--;
} else if (startX == 0 && amida[startY][1] == '-') {
direction = TO_RIGHT;
x++;
} else {
direction = TO_LEFT;
x--;
}
//System.out.println("direction:" + direction);
//System.out.println(y + ":" + x);
while (amida[y][x] == '|' || amida[y][x] == '-') {
// System.out.println(y + ":" + x + ":" + amida[y][x]);
if (direction == TO_DOWN || direction == TO_UP) {
if (x > 0 && amida[y][x - 1] == '-') {
x--;
while (amida[y][x] != '|')
x--;
if (direction == TO_DOWN)
y++;
else
y--;
} else if (x < width - 1 && amida[y][x + 1] == '-') {
x++;
while (amida[y][x] != '|')
x++;
if (direction == TO_DOWN)
y++;
else
y--;
} else {
if (direction == TO_DOWN)
y++;
else if (direction == TO_UP)
y--;
}
} else if (direction == TO_RIGHT || direction == TO_LEFT) {
if (y > 0 && amida[y - 1][x] == '|') {
y--;
while (amida[y][x] != '-')
y--;
if (direction == TO_RIGHT)
x++;
else
x--;
} else if (y < height - 1 && amida[y + 1][x] == '|') {
y++;
while (amida[y][x] != '-')
y++;
if (direction == TO_RIGHT)
x++;
else
x--;
} else {
if (direction == TO_RIGHT)
x++;
else
x--;
}
}
}
os.write(amida[y][x]);
System.out.println("Ans=" + amida[y][x]);
os.write('\n');
os.flush();
no++;
}
}
}
No.1000
*
| | |-| | | | |
|-| | |-| | |-|
| | | | | | | |
| |-| |-| | | |
|-| | | |-| |-|
| |-| | | | | |
|-| | |-| |-| |
| | |-| |-| |-|
| |-| |-| | | |
|-| | | | | |-|
| |-| |-| |-| |
| | |-| | | |-|
| | | | |-| | |
|-| |-| | |-| |
| |-| | | | | |
| | |-| | |-| |
|-| | | |-| | |
| | | |-| |-| |
| | |-| |-| |-|
1 2 3 4 5 6 7 8
Ans=3
FLAG{c4693af1761200417d5645bd084e28f0f2b426bf}
2014年5月1日木曜日
CentOS 6.5 カーネル再構築 2.6.32-431.11.2.el6.x86_64編
CentOSのカーネル再構築メモ。
最新のLinuxカーネルで構築し直すんじゃなくて、今動いているシステムのカーネルソースいじって遊ぶぜ的な人向けの手順です。
バージョンによって前提パッケージが違ったり、ソースをダウンロードしてくるところが違ったり面倒だったので、なるべく汎用性ありそうな書き方で。
まずOS自体を最新バージョンにアップデート。
私がやったとき(2014/04/29)の最新バージョンは2.6.32-431.11.2です。64ビット版です。
続いて開発環境をインストール。これは他サイトからの受け売り。
で、次にその他の前提パッケージのインストール、ってのがありがちな書き方ですが、その前にソースをダウンロードして、インストールを試みます。ソースの置き場所もその時々で違ったりするので、CentOSのサイトで確認するといいんじゃないかと思います。
2014/04/29時点では、トップ→Get CentOS Linux Now→Need the Source?
とたどって、ソース置き場からとってきました。これを一般ユーザでインストールします。
で、rpmbuildを動かすと必要な前提パッケージを教えてくれます。 これがバージョンによって違ったりするようなので、違うバージョンの手順を真似るよりはrpmbuildに聞いた方が確実なんじゃないかと。
で、これらをインストールします。perl(ExtUtils::Embed)はさすがにクォーテーションで囲まないとエラーになると思います。
この後もう一回rpmbuild実行、~/rpmbuild/BUILDの該当バージョンというか、できてるディレクトリの下に行ってmake、インストールします。
ここではMakefileのEXTRAVERSIONを-selinuxにしています(個人的にSELinuxまわりの研究でやっているので)。
この場合OS起動時eをタイプすることで表示されるブートオプションの画面で、構築したカーネルが2.6.32-selinuxと表示されます。
最新のLinuxカーネルで構築し直すんじゃなくて、今動いているシステムのカーネルソースいじって遊ぶぜ的な人向けの手順です。
バージョンによって前提パッケージが違ったり、ソースをダウンロードしてくるところが違ったり面倒だったので、なるべく汎用性ありそうな書き方で。
まずOS自体を最新バージョンにアップデート。
# yum update # reboot
私がやったとき(2014/04/29)の最新バージョンは2.6.32-431.11.2です。64ビット版です。
続いて開発環境をインストール。これは他サイトからの受け売り。
# yum groupinstall "Development tools"
で、次にその他の前提パッケージのインストール、ってのがありがちな書き方ですが、その前にソースをダウンロードして、インストールを試みます。ソースの置き場所もその時々で違ったりするので、CentOSのサイトで確認するといいんじゃないかと思います。
2014/04/29時点では、トップ→Get CentOS Linux Now→Need the Source?
とたどって、ソース置き場からとってきました。これを一般ユーザでインストールします。
$ wget http://vault.centos.org/6.5/updates/Source/SPackages/kernel-2.6.32-431.11.2.el6.src.rpm $ rpm -ivh kernel-2.6.32-431.11.2.el6.src.rpm
で、rpmbuildを動かすと必要な前提パッケージを教えてくれます。 これがバージョンによって違ったりするようなので、違うバージョンの手順を真似るよりはrpmbuildに聞いた方が確実なんじゃないかと。
$ cd ~/rpmbuild/SPECS
$ rpmbuild -bp kernel.spec --target=x86_64
ビルド対象プラットフォーム: x86_64
ターゲット x86_64 用にビルド中
エラー: ビルド依存性の失敗:
xmlto は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
asciidoc は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
elfutils-libelf-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
elfutils-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
zlib-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
binutils-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
newt-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
python-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
audit-libs-devel は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
perl(ExtUtils::Embed) は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
hmaccalc は kernel-2.6.32-431.11.2.el6.x86_64 に必要とされています
で、これらをインストールします。perl(ExtUtils::Embed)はさすがにクォーテーションで囲まないとエラーになると思います。
# yum install xmlto asciidoc elfutils-libelf-devel elfutils-devel zlib-devel binutils-devel newt-devel python-devel audit-libs-devel "perl(ExtUtils::Embed)" hmaccalc
この後もう一回rpmbuild実行、~/rpmbuild/BUILDの該当バージョンというか、できてるディレクトリの下に行ってmake、インストールします。
$ rpmbuild -bp kernel.spec --target=x86_64 $ cd ~/rpmbuild/BUILD/kernel-2.6.32-431.11.2.el6/linux-2.6.32-431.11.2.el6.x86_64 $ vi Makefile EXTRAVERSION = -selinux $ make # make modules_install # make install # reboot
ここではMakefileのEXTRAVERSIONを-selinuxにしています(個人的にSELinuxまわりの研究でやっているので)。
この場合OS起動時eをタイプすることで表示されるブートオプションの画面で、構築したカーネルが2.6.32-selinuxと表示されます。
2014年2月27日木曜日
Ubuntu 13.10 x64 + Hadoop 1.2.1 + Mahout 0.9
Mahout 0.9 のインストールでいろいろ引っかかったのでメモ。
Ubuntu13.10 x64にmahoutユーザでインストール。
ひっかかってた最大の理由はMahout0.9が前提にしているHadoopのバージョンが1.2.1ってことに気づくのが遅かったからでした(Mahout0.9のパッケージの中にlib/hadoop/hadoop-core-1.2.1.jarってのがあった)。
hdfs-site.xmlのdfs.name.dir、dfs.data.dirあたりは書いておかないと/tmpの下に作られるため、システムリブートの度に消されてあとでイラっときます。
6つ起動しない場合は/usr/local/hadoop/logsの下の*.logを参照。ちょっとしたことで動かなくなったりします。
で、ここでMahoutのサンプル起動しますがエラーになります。
いろいろ調べた結果、このサンプルはデータをネットワークからダウンロードしますが、環境変数HADOOP_HOMEが設定されていないとhdfs上にコピーしてくれません。
HADOOPはHADOOP_HOME設定してると「Warning: $HADOOP_HOME is deprecated.」って文句行ってくるのにMahoutのサンプルはそれを前提にしているってオチでした。
すると今度は動きます。
まだ不完全なんだなという印象。
Ubuntu13.10 x64にmahoutユーザでインストール。
ひっかかってた最大の理由はMahout0.9が前提にしているHadoopのバージョンが1.2.1ってことに気づくのが遅かったからでした(Mahout0.9のパッケージの中にlib/hadoop/hadoop-core-1.2.1.jarってのがあった)。
- sshd準備
# apt-get install openssh-server $ ssh-keygen -t rsa -P "" $ cat .ssh/id_rsa.pub >> .ssh/authorized_keys $ chmod 600 .ssh/authorized_keys
- IPv6停止(他サイトの受け売り)
# vi /etc/sysctl.conf (追加) net.ipv6.conf.all.disable_ipv6 = 1 net.ipv6.conf.default.disable_ipv6 = 1 net.ipv6.conf.lo.disable_ipv6 = 1 # reboot
- JDKインストール
$ tar zxvf jdk-7u51-linux-x64.tar.gz # mv jdk1.7.0_51 /usr/local # ln -s /usr/local/jdk1.7.0_51 /usr/local/jdk
- Hadoopインストール
$ tar zxvf hadoop-1.2.1.tar.gz
# mv hadoop-1.2.1 /usr/local
# ln -s /usr/local/hadoop-1.2.1 /usr/local/hadoop
$ vi /usr/local/hadoop/conf/hadoop-env.sh
(追加)
export JAVA_HOME=/usr/local/jdk
$ vi /usr/local/hadoop/conf/core-site.xml
(追加)
<property>
<name>fs.default.name</name>
<value>hdfs://localhost:9000</value>
</property>
$ vi /usr/local/hadoop/conf/hdfs-site.xml
(追加)
<property>
<name>dfs.replication</name>
<value>1</value>
</property>
<property>
<name>dfs.name.dir</name>
<value>/home/hadoop/dfs/name</value>
</property>
<property>
<name>dfs.data.dir</name>
<value>/home/hadoop/dfs/data</value>
</property>
$ vi /usr/local/hadoop/conf/mapred-site.xml
(追加)
<property>
<name>mapred.job.tracker</name>
<value>localhost:9001</value>
</property>
<property>
<name>mapred.local.dir</name>
<value>/home/hadoop/mapred</value>
</property>
hdfs-site.xmlのdfs.name.dir、dfs.data.dirあたりは書いておかないと/tmpの下に作られるため、システムリブートの度に消されてあとでイラっときます。
- Mahoutインストール
$ tar zxvf mahout-distribution-0.9.tar.gz # mv mahout-distribution-0.9 /usr/local # ln -s /usr/local/mahout-distribution-0.9 /usr/local/mahout
- 環境設定
(追加)
JAVA_HOME=/usr/local/jdk
HADOOP_HOME=/usr/local/hadoop
MAHOUT_HOME=/usr/local/mahout
PATH=${JAVA_HOME}/bin:${HADOOP_HOME}/bin:${MAHOUT_HOME}/bin:/usr/lib/lightdm/lightdm:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games
export JAVA_HOME MAHOUT_HOME PATH
$ exit
- ネームノードフォーマット
$ hadoop namenode -format
- Hadoop起動
$ start-all.sh $ jps 4917 JobTracker 4539 NameNode 5105 Jps 4680 DataNode 4832 SecondaryNameNode 5060 TaskTracker
6つ起動しない場合は/usr/local/hadoop/logsの下の*.logを参照。ちょっとしたことで動かなくなったりします。
で、ここでMahoutのサンプル起動しますがエラーになります。
$ cd /usr/local/mahout/examples/bin
$ ./classify-20newsgroups.sh
Please select a number to choose the corresponding task to run
1. cnaivebayes
2. naivebayes
3. sgd
4. clean -- cleans up the work area in /tmp/mahout-work-mahout
Enter your choice : 2
:
:
Exception in thread "main" java.io.FileNotFoundException: File does not exist: /tmp/mahout-work-mahout/20news-all
いろいろ調べた結果、このサンプルはデータをネットワークからダウンロードしますが、環境変数HADOOP_HOMEが設定されていないとhdfs上にコピーしてくれません。
HADOOPはHADOOP_HOME設定してると「Warning: $HADOOP_HOME is deprecated.」って文句行ってくるのにMahoutのサンプルはそれを前提にしているってオチでした。
$ export HADOOP_HOME=/usr/local/hadoop
すると今度は動きます。
======================================================= Statistics ------------------------------------------------------- Kappa 0.8753 Accuracy 90.3805% Reliability 85.7215% Reliability (standard deviation) 0.2163 14/02/27 13:45:07 INFO driver.MahoutDriver: Program took 18474 ms (Minutes: 0.3079)
まだ不完全なんだなという印象。
2014年2月18日火曜日
SECCON 2013 CTF オンライン予選 数毒 writeup
そもそも修論の追い込みで忙しい時期なので今回参加しないつもりでしたが、蓋を開ければ「解かないとあとで何言われるかわからない」数独があったのでしょうがない、この１問だけやりました。
DEFCON CTF 2013のゲリラプログラミングのスライドパズル同様、過去に自分で作って晒したコードをダウンロードして流用パターンです。
出題サーバにtelnetでアクセスするとこんな問題が表示されます。
注：証拠のデータ残していなかったので、問題は別のやつ貼り付けてます。
数独の問題なんですが中にXってのがあって、Xが２の時解はいくつあるか？って聞いてきます。 １盤面あたり複数この質問が来て、クリアすると次の盤面っていう繰り返しです。
以前、自分で作ったPrologのコードはこんなカンジです。
https://github.com/minetosh/sudoku/tree/master/prolog
gprolog --consult-file sudoku.pl で起動した後、問題入力はこうやります。
解は次のように表示されます。
検索してこのプログラムにたどり着いても複数解表示させる方法がわからなければ意味ないんですが、Prologで次の解を表示させるには、解を表示した後の?プロンプトに対して;(セミコロン)を入力します。解がある間これを繰り返します。
１問あたり制限時間は３分なので、この間に全解を手動で表示できる程度であれば、問題をこのプログラムの入力形式に変換してコピペ、セミコロンを入力し続けて解の数を数えればおｋとなります。
解の数が2桁程度までなら上記方法でも十分間に合いますが3桁以上になったらきついと思うので、その時はjavaでI/O制御するプログラム作るつもりでいました。
とりあえず問題変換＆コピペの手法を試すのに、以下のプログラムを作りました。
このプログラムで、
が、
になるので、X手前までPrologへコピペ、Xのところに示された数字入力、Xより後ろコピペ、セミコロン入力しながら数えて、の繰り返しでクリア出来ました。
結局私がやったときは解の数は0,1,2しかなく結構あっさり終わってしまいました。他の方のWriteupを見ると19っていうのもあったようです。
スコア画面に「あなたが一番最初にこの問題をときました」みたいに表示されていたので、多分そうゆうことなんだと思います。
DEFCON CTF 2013のゲリラプログラミングのスライドパズル同様、過去に自分で作って晒したコードをダウンロードして流用パターンです。
出題サーバにtelnetでアクセスするとこんな問題が表示されます。
'suDOKU(su-poison)' challenge for SECCON 2013. by KeigoYAMAZAKI, 2013.11.22- * Stage 1 1 2 3 4 5 6 7 8 9 $-+-+-$-+-+-$-+-+-$ A |8|.|.|.|.|.|.|.|.| B |.|.|3|6|.|.|.|.|.| C |.|7|.|.|9|.|X|.|.| $-+-+-$-+-+-$-+-+-$ D |.|5|.|.|.|7|.|.|.| E |.|.|.|.|4|5|7|.|.| F |.|.|.|1|.|.|.|3|.| $-+-+-$-+-+-$-+-+-$ G |.|.|1|.|.|.|.|6|8| H |.|.|8|5|.|.|.|1|.| I |.|9|.|.|.|.|4|.|.| $-+-+-$-+-+-$-+-+-$ if 'X' is 2, how many solutions does this sudoku have? => answer:
注：証拠のデータ残していなかったので、問題は別のやつ貼り付けてます。
数独の問題なんですが中にXってのがあって、Xが２の時解はいくつあるか？って聞いてきます。 １盤面あたり複数この質問が来て、クリアすると次の盤面っていう繰り返しです。
以前、自分で作ったPrologのコードはこんなカンジです。
https://github.com/minetosh/sudoku/tree/master/prolog
sudoku(Rows) :-
maplist(seigen, Rows), cols(Rows), blks(Rows),
maplist(fd_labeling, Rows).
cols([[]|L]).
cols(L) :-
maplist(nth(1), L, X), seigen(X), maplist(delete, L, X, NL), cols(NL).
blks([]).
blks([X, Y, Z|L]) :- blks2(X, Y, Z), blks(L).
blks2([],_,_).
blks2([X1, X2, X3|XL], [Y1, Y2, Y3|YL], [Z1, Z2, Z3|ZL]) :-
seigen([X1, X2, X3, Y1, Y2, Y3, Z1, Z2, Z3]), blks2(XL, YL, ZL).
seigen(X) :- fd_domain(X, 1, 9), fd_all_different(X).
gprolog --consult-file sudoku.pl で起動した後、問題入力はこうやります。
Row1 = [8, _, _, _, _, _, _, _, _], Row2 = [_, _, 3, 6, _, _, _, _, _], Row3 = [_, 7, _, _, 9, _, 2, _, _], Row4 = [_, 5, _, _, _, 7, _, _, _], Row5 = [_, _, _, _, 4, 5, 7, _, _], Row6 = [_, _, _, 1, _, _, _, 3, _], Row7 = [_, _, 1, _, _, _, _, 6, 8], Row8 = [_, _, 8, 5, _, _, _, 1, _], Row9 = [_, 9, _, _, _, _, 4, _, _], sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).
解は次のように表示されます。
Row1 = [8,1,2,7,5,3,6,4,9] Row2 = [9,4,3,6,8,2,1,7,5] Row3 = [6,7,5,4,9,1,2,8,3] Row4 = [1,5,4,2,3,7,8,9,6] Row5 = [3,6,9,8,4,5,7,2,1] Row6 = [2,8,7,1,6,9,5,3,4] Row7 = [5,2,1,9,7,4,3,6,8] Row8 = [4,3,8,5,2,6,9,1,7] Row9 = [7,9,6,3,1,8,4,5,2] ?
検索してこのプログラムにたどり着いても複数解表示させる方法がわからなければ意味ないんですが、Prologで次の解を表示させるには、解を表示した後の?プロンプトに対して;(セミコロン)を入力します。解がある間これを繰り返します。
１問あたり制限時間は３分なので、この間に全解を手動で表示できる程度であれば、問題をこのプログラムの入力形式に変換してコピペ、セミコロンを入力し続けて解の数を数えればおｋとなります。
解の数が2桁程度までなら上記方法でも十分間に合いますが3桁以上になったらきついと思うので、その時はjavaでI/O制御するプログラム作るつもりでいました。
とりあえず問題変換＆コピペの手法を試すのに、以下のプログラムを作りました。
import java.io.*;
public class P200 {
public static void main(String args[]) {
try {
InputStreamReader isr = null;
try {
isr = new InputStreamReader(System.in, "UTF-8");
BufferedReader br = null;
try {
br = new BufferedReader(isr);
String line = null;
char c;
while (true) {
line = br.readLine();
if (line.charAt(0) != ' ') {
System.out.print("Row");
System.out.print(line.charAt(0) - 'A' + 1);
System.out.print("=[");
System.out.print(a(line.charAt(3))); System.out.print(",");
System.out.print(a(line.charAt(5))); System.out.print(",");
System.out.print(a(line.charAt(7))); System.out.print(",");
System.out.print(a(line.charAt(9))); System.out.print(",");
System.out.print(a(line.charAt(11))); System.out.print(",");
System.out.print(a(line.charAt(13))); System.out.print(",");
System.out.print(a(line.charAt(15))); System.out.print(",");
System.out.print(a(line.charAt(17))); System.out.print(",");
System.out.print(a(line.charAt(19))); System.out.println("],");
if (line.charAt(0) == 'I') {
System.out.println(
"sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9])."
);
}
}
}
} finally {
if (br != null) br.close();
}
} finally {
if (isr != null) isr.close();
}
} catch (Exception ex) {
ex.printStackTrace();
}
}
public static char a(char c) {
if (c == '.')
return '_';
else
return c;
}
}
このプログラムで、
1 2 3 4 5 6 7 8 9 $-+-+-$-+-+-$-+-+-$ A |8|.|.|.|.|.|.|.|.| B |.|.|3|6|.|.|.|.|.| C |.|7|.|.|9|.|X|.|.| $-+-+-$-+-+-$-+-+-$ D |.|5|.|.|.|7|.|.|.| E |.|.|.|.|4|5|7|.|.| F |.|.|.|1|.|.|.|3|.| $-+-+-$-+-+-$-+-+-$ G |.|.|1|.|.|.|.|6|8| H |.|.|8|5|.|.|.|1|.| I |.|9|.|.|.|.|4|.|.| $-+-+-$-+-+-$-+-+-$
が、
Row1 = [8, _, _, _, _, _, _, _, _], Row2 = [_, _, 3, 6, _, _, _, _, _], Row3 = [_, 7, _, _, 9, _, X, _, _], Row4 = [_, 5, _, _, _, 7, _, _, _], Row5 = [_, _, _, _, 4, 5, 7, _, _], Row6 = [_, _, _, 1, _, _, _, 3, _], Row7 = [_, _, 1, _, _, _, _, 6, 8], Row8 = [_, _, 8, 5, _, _, _, 1, _], Row9 = [_, 9, _, _, _, _, 4, _, _], sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).
になるので、X手前までPrologへコピペ、Xのところに示された数字入力、Xより後ろコピペ、セミコロン入力しながら数えて、の繰り返しでクリア出来ました。
結局私がやったときは解の数は0,1,2しかなく結構あっさり終わってしまいました。他の方のWriteupを見ると19っていうのもあったようです。
スコア画面に「あなたが一番最初にこの問題をときました」みたいに表示されていたので、多分そうゆうことなんだと思います。
2013年11月21日木曜日
制約論理プログラミングで数独を解く
GNU Prologの制約論理プログラミングで数独を解くプログラムを作ったところ、ほぼ数独のルールを記述するだけで出来てしまいました。
まずGNU Prologをインストールします。上のGNU Prologのサイトからソースをダウンロードしてインストールします。以下は1.4.4の場合です。
$ tar zxf gprolog-1.4.4.tar.gz
$ cd gprolog-1.4.4/src
$ ./configure
$ make
$ sudo make install
次に以下のプログラム、
をファイル(sudoku.pl)に保存して、以下のようにprologを起動します。
$ gprolog --consult-file sudoku.pl
プロンプト(?-)が表示されたところで、以下のように問題データをセットして呼び出します。
多分、瞬殺で解答が返ってくると思います。問題はこちらのサイトから世界一難しい数独問題を拝借しました。
プログラム、というかルール記述は至って単純で、
Rows = [[X11, ... , X19], ... [X91, ... , X99],
で引数で渡されたRowsの各行を変数X11〜X99に分解、
maplist(seigen, Rows),
で数独による各行の値のルールを指定しています。maplistは2つ目の引数のリストの各要素について1つ目の引数の関数(Prologでは通常は関数と呼ばないようですが)を呼び出します。Rowsの各行についてseigenを呼び出していますが、これは最後の行で以下のように定義されています。
seigen(X) :- fd_domain(X,1,9), fd_all_different(X).
fd_domainで各要素の値の取りうる値を1から9に制限し、fd_all_differentで各要素で重複する値を持つことがない、としています。
Cols = [...
と
Blks = [...
で各列と各ブロックのリストを構成する変数を定義し、同じようにseigenを呼び出しています。
以上、ここまでは文字通り数独のルール記述だけになっています。
maplist(fd_labeling, Rows).
この行で各行のリストの持つ変数、すなわちX11〜X99すべてについて探索開始を指示しています。
問題を設定するところでわざわざRows1〜Rows9のリストとしているのは、結果の表示を見やすくするためです。
こんなに簡単にいけると思わかなった。。。
2013/11/21追記
以下が私の考える最短ソース。ここまで行くとProlog読めないと意味不明。
https://github.com/minetosh/sudoku/tree/master/prolog
まずGNU Prologをインストールします。上のGNU Prologのサイトからソースをダウンロードしてインストールします。以下は1.4.4の場合です。
$ tar zxf gprolog-1.4.4.tar.gz
$ cd gprolog-1.4.4/src
$ ./configure
$ make
$ sudo make install
次に以下のプログラム、
sudoku(Rows) :-
Rows = [ % 引数の各行のリストをX11〜X99の変数に分解
[X11, X12, X13, X14, X15, X16, X17, X18, X19],
[X21, X22, X23, X24, X25, X26, X27, X28, X29],
[X31, X32, X33, X34, X35, X36, X37, X38, X39],
[X41, X42, X43, X44, X45, X46, X47, X48, X49],
[X51, X52, X53, X54, X55, X56, X57, X58, X59],
[X61, X62, X63, X64, X65, X66, X67, X68, X69],
[X71, X72, X73, X74, X75, X76, X77, X78, X79],
[X81, X82, X83, X84, X85, X86, X87, X88, X89],
[X91, X92, X93, X94, X95, X96, X97, X98, X99]
],
maplist(seigen, Rows), % 各行について値を制限
Cols = [ % Colsを各列のリストとして定義
[X11, X21, X31, X41, X51, X61, X71, X81, X91],
[X12, X22, X32, X42, X52, X62, X72, X82, X92],
[X13, X23, X33, X43, X53, X63, X73, X83, X93],
[X14, X24, X34, X44, X54, X64, X74, X84, X94],
[X15, X25, X35, X45, X55, X65, X75, X85, X95],
[X16, X26, X36, X46, X56, X66, X76, X86, X96],
[X17, X27, X37, X47, X57, X67, X77, X87, X97],
[X18, X28, X38, X48, X58, X68, X78, X88, X98],
[X19, X29, X39, X49, X59, X69, X79, X89, X99]
],
maplist(seigen, Cols), % 各列について値を制限
Blks = [ % Blksを各ブロックのリストとして定義
[X11, X12, X13, X21, X22, X23, X31, X32, X33],
[X14, X15, X16, X24, X25, X26, X34, X35, X36],
[X17, X18, X19, X27, X28, X29, X37, X38, X39],
[X41, X42, X43, X51, X52, X53, X61, X62, X63],
[X44, X45, X46, X54, X55, X56, X64, X65, X66],
[X47, X48, X49, X57, X58, X59, X67, X68, X69],
[X71, X72, X73, X81, X82, X83, X91, X92, X93],
[X74, X75, X76, X84, X85, X86, X94, X95, X96],
[X77, X78, X79, X87, X88, X89, X97, X98, X99]
],
maplist(seigen, Blks), % 各ブロックについて値を制限
maplist(fd_labeling, Rows). % 各行の値を探索
% リストXの各値の取る値は1から9で、重複なし
seigen(X) :- fd_domain(X,1,9), fd_all_different(X).
をファイル(sudoku.pl)に保存して、以下のようにprologを起動します。
$ gprolog --consult-file sudoku.pl
プロンプト(?-)が表示されたところで、以下のように問題データをセットして呼び出します。
Row1 = [8, _, _, _, _, _, _, _, _], Row2 = [_, _, 3, 6, _, _, _, _, _], Row3 = [_, 7, _, _, 9, _, 2, _, _], Row4 = [_, 5, _, _, _, 7, _, _, _], Row5 = [_, _, _, _, 4, 5, 7, _, _], Row6 = [_, _, _, 1, _, _, _, 3, _], Row7 = [_, _, 1, _, _, _, _, 6, 8], Row8 = [_, _, 8, 5, _, _, _, 1, _], Row9 = [_, 9, _, _, _, _, 4, _, _], sudoku([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9]).
多分、瞬殺で解答が返ってくると思います。問題はこちらのサイトから世界一難しい数独問題を拝借しました。
Row1 = [8,1,2,7,5,3,6,4,9] Row2 = [9,4,3,6,8,2,1,7,5] Row3 = [6,7,5,4,9,1,2,8,3] Row4 = [1,5,4,2,3,7,8,9,6] Row5 = [3,6,9,8,4,5,7,2,1] Row6 = [2,8,7,1,6,9,5,3,4] Row7 = [5,2,1,9,7,4,3,6,8] Row8 = [4,3,8,5,2,6,9,1,7] Row9 = [7,9,6,3,1,8,4,5,2] ?
プログラム、というかルール記述は至って単純で、
Rows = [[X11, ... , X19], ... [X91, ... , X99],
で引数で渡されたRowsの各行を変数X11〜X99に分解、
maplist(seigen, Rows),
で数独による各行の値のルールを指定しています。maplistは2つ目の引数のリストの各要素について1つ目の引数の関数(Prologでは通常は関数と呼ばないようですが)を呼び出します。Rowsの各行についてseigenを呼び出していますが、これは最後の行で以下のように定義されています。
seigen(X) :- fd_domain(X,1,9), fd_all_different(X).
fd_domainで各要素の値の取りうる値を1から9に制限し、fd_all_differentで各要素で重複する値を持つことがない、としています。
Cols = [...
と
Blks = [...
で各列と各ブロックのリストを構成する変数を定義し、同じようにseigenを呼び出しています。
以上、ここまでは文字通り数独のルール記述だけになっています。
maplist(fd_labeling, Rows).
この行で各行のリストの持つ変数、すなわちX11〜X99すべてについて探索開始を指示しています。
問題を設定するところでわざわざRows1〜Rows9のリストとしているのは、結果の表示を見やすくするためです。
こんなに簡単にいけると思わかなった。。。
2013/11/21追記
以下が私の考える最短ソース。ここまで行くとProlog読めないと意味不明。
https://github.com/minetosh/sudoku/tree/master/prolog
sudoku(Rows) :-
maplist(seigen, Rows), cols(Rows), blks(Rows),
maplist(fd_labeling, Rows).
cols([[]|L]).
cols(L) :-
maplist(nth(1), L, X), seigen(X), maplist(delete, L, X, NL), cols(NL).
blks([]).
blks([X, Y, Z|L]) :- blks2(X, Y, Z), blks(L).
blks2([],_,_).
blks2([X1, X2, X3|XL], [Y1, Y2, Y3|YL], [Z1, Z2, Z3|ZL]) :-
seigen([X1, X2, X3, Y1, Y2, Y3, Z1, Z2, Z3]), blks2(XL, YL, ZL).
seigen(X) :- fd_domain(X, 1, 9), fd_all_different(X).
2013年11月9日土曜日
Linuxで一つのネットワークインターフェースに複数IPアドレス設定する方法
CentOS6から複数IPアドレス設定の方法か変わったらしい、件で書いた、IPエイリアスを使わない方法はUbuntuでも行けました。しかもGUI上一つしか設定できないように見える8.04で。
# ip addr add 192.168.224.132/24 dev eth0
で設定できて、pingが通りました。ifconfigではやっぱり出て来ません。
全部試したわけじゃないけど、きっとLinux共通なんでしょーねー。
自分が知らなかっただけか。
# ip addr add 192.168.224.132/24 dev eth0
で設定できて、pingが通りました。ifconfigではやっぱり出て来ません。
全部試したわけじゃないけど、きっとLinux共通なんでしょーねー。
自分が知らなかっただけか。
登録:
投稿 (Atom)