もう5年近く前のことですが、私と同じように解いた解説が出てこないので書いてみます。
問題はこれです。
https://code.google.com/codejam/contest/1363489/dashboard#s=p1
要約すると、
a(0)=A
a(n)=a(n-1)a(n-1)
を満たす配列anの第B項をCで割った余りで答えよ。
このA,B,Cの値の組のテストケース数は500以下
Aの値は1,000以下
Bの値はSmallは2以下、Largeは1,000以下
Cの値は1,000以下
公開鍵暗号の原理と同じで周期から計算できるんだろーなとは思ったんですが、やはりGoogleの解説もそのようになっています。
https://code.google.com/codejam/contest/1363489/dashboard#s=a&a=1
このCode Jam Japanの決勝問題は問題Aが簡単、それに比べて問題B以降が難しく、終了時点で問題AのSmall, Largeだけ解けた人が112位から355位まで大渋滞しています。
https://code.google.com/codejam/contest/1363489/scoreboard#sp=91
200位以内に入れば景品のTシャツがもらえるんですが、問題Aを解いただけでは早く解いた者勝ちです。そこに入れない場合は、どの問題でもいいからSmallだけでも解ければTシャツ圏内に入れる、という状況でした。
で、この問題BのSmallはBが2以下なので、 第2項まで求めればいいようになっています。つまり(AA)(AA)までのmodが計算できれば解けることになります。
X = AA mod C
として、
X(AA)
を求めるわけですが、当然指数のAAはmodは効かずこれ自体が天文学的数字になる可能性があります。どうにかXの方をmodしながらべき乗していって求める方法を考えないとダメそうです。
で、苦し紛れに
(XA)A
で同じにならないかな？と思ってもこれは
X(A*A) = X(A2)
にしかなりません。
掛け算で並べて書けばわかりやすいんですが、例えばAが5とするとXの5乗は
X*X*X*X*X
これのさらに5乗は縦に書き足せば
X*X*X*X*X*
X*X*X*X*X*
X*X*X*X*X*
X*X*X*X*X*
X*X*X*X*X
Xが5*5個なので
X(5*5) = X(52)
にしかなりません。
しかし、これをさらに5乗すれば
X(5*5*5) = X(53)
になります。
ということは、この調子でXを5乗する、を5回繰り返せば
X(5*5*5*5*5) = X(55)
が求まることになります。同様に、X(AA)を求めるためには、XをA乗するのをA回繰り返せばよい、ということになります。
A,B,Cがjavaのintとして与えられているとして、BigIntegerクラスのmodPowを使って書けば、
BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.modPow(a, c);
for (int i = 0; i < A; i++)
X = X.modPow(a, c);
とまあ、とても短いプログラムで求めることができます。
実際私はmodPowメソッドの存在を知らなかったのでこれ相当の関数を自分で作り、終了前15分で解答提出、260位(?)あたりから一気に89位に浮上、終了時点で96位、最終的に93位で無事Tシャツを頂きました。
BigIntegerを使ってキレイに書きなおせば以下のようなコードになります。
import java.math.BigInteger;
import java.util.Scanner;
public class B {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 1; i <= T; i++) {
System.out.println("Case #" + i + ": " +
resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
}
private static int resolv(int A, int B, int C) {
BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.modPow(a, c);
if (B == 2)
for (int i = 0; i < A; i++)
X = X.modPow(a, c);
return X.intValue();
}
}
実はこのBigIntegerクラス、1,0001,000も扱えてしまうので、上で書いたようなことは全く考える必要もなく、そのまま素直にコーディングすれば解けてしまうのでした。
import java.math.BigInteger;
import java.util.Scanner;
public class B2 {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 1; i <= T; i++) {
System.out.println("Case #" + i + ": " +
resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
}
private static int resolv(int A, int B, int C) {
BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.pow(A); // 最大1,0001,000
BigInteger Xm = X.mod(c);
if (B == 2)
Xm = Xm.modPow(X, c); // そのまま計算
return Xm.intValue();
}
}
結局ライブラリ知ってるもん勝ちな問題でした。
2016年2月5日金曜日
2015年4月6日月曜日
javaでRuntime.execしたプロセスのPIDを取得する方法
意外と日本語のページが引っかからなかったので書いときます。
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。
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。
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年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年6月18日火曜日
DEFCON CTF 21 OMGACM 1 Writeup
Google Developer Day 2011参加権争奪DevQuizのスライドパズル(最大6x6、途中に壁あり、全5000問)を簡単にしたような問題(3x3固定、ひねりなし)なので、このブログに自分で作ってさらしたソースコードをダウンロードして流用。
http://apoup.blogspot.jp/2011/09/gdd2011jp-devquiz.html
リンク先で言う双方向とは、初期状態から解けた状態への探索と、解けた状態から初期状態への探索。
マンハッタン距離とは、各パーツが現在いる場所からゴールとなる場所へのマンハッタン距離を合計したもの。
「devquiz 2011 スライドパズル」でぐぐればソース晒し祭りの痕跡が見れます。
以上。
http://apoup.blogspot.jp/2011/09/gdd2011jp-devquiz.html
リンク先で言う双方向とは、初期状態から解けた状態への探索と、解けた状態から初期状態への探索。
マンハッタン距離とは、各パーツが現在いる場所からゴールとなる場所へのマンハッタン距離を合計したもの。
「devquiz 2011 スライドパズル」でぐぐればソース晒し祭りの痕跡が見れます。
以上。
2011年9月13日火曜日
GDD2011JP DevQuiz スライドパズルの回答ソースコード
はっきり言って恥ずかしいコードだけど晒します。
基本、双方向幅優先で物理パワーでねじ伏せる作戦。
優先して残すのは、ゴールまでのマンハッタン距離が近いもの。
以下のコードで-Xmx4608M付けてXeonの6G、64ビットUbuntu10.10マシンで40時間かけると4872問解けます(残り128)。
更に残ったものについて、幅増やしたり上限増やしたりして残り49。
さらに、最初の10手はスタートからの遠さ優先その後ゴールまでの近さ優先、次最初の20手は...と繰り返して行って、残り14。あとは手動で小さいサイズの問題に帰着させて解かせた。
一番原始的な気がする。
基本、双方向幅優先で物理パワーでねじ伏せる作戦。
優先して残すのは、ゴールまでのマンハッタン距離が近いもの。
以下のコードで-Xmx4608M付けてXeonの6G、64ビットUbuntu10.10マシンで40時間かけると4872問解けます(残り128)。
更に残ったものについて、幅増やしたり上限増やしたりして残り49。
さらに、最初の10手はスタートからの遠さ優先その後ゴールまでの近さ優先、次最初の20手は...と繰り返して行って、残り14。あとは手動で小さいサイズの問題に帰着させて解かせた。
一番原始的な気がする。
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Hashtable;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Enumeration;
public class Panel2 {
public static final int MAX_NUM = 10000;
public static final int MAX_COUNT = 100;
public class InnerPanel {
int width, height;
char maxc;
int maxcount;
String panel[];
int distance;
int zerox, zeroy;
StringBuffer route;
/**
* コンストラクタ(初期状態用).
*/
public InnerPanel(int width, int height, String panelstr) {
// 幅高さ
this.width = width;
this.height = height;
// 配列化
panel = new String[height];
for (int i = 0; i < height; i++)
panel[i] = panelstr.substring(width * i, width * (i + 1));
// 一番でかい文字保存＆0位置保存
maxc = '0';
char c;
for (int i = 0; i < panelstr.length(); i++) {
c = panelstr.charAt(i);
if (c == '=')
continue;
if (c == '0') {
zeroy = i / width;
zerox = i % width;
}
if (maxc < c)
maxc = c;
}
maxcount = toInt(maxc);
route = new StringBuffer();
}
/**
* コンストラクタ(ゴール作成用).
*/
private InnerPanel(int width, int height) {
// 幅高さ
this.width = width;
this.height = height;
this.route = new StringBuffer();
}
/**
* ゴール作成.
*/
public InnerPanel makeGoal() {
InnerPanel goal = new InnerPanel(width, height);
goal.maxc = maxc;
goal.maxcount = maxcount;
// 整列した状態作成
goal.panel = new String[height];
int count = 0;
String line = null;
char c;
for (int i = 0; i < height; i++) {
line = panel[i];
StringBuffer sb = new StringBuffer();
for (int j = 0; j < width; j++) {
count++;
c = line.charAt(j);
if (c == '=') {
sb.append(c);
} else if (count > maxcount) {
sb.append('0');
goal.zeroy = i;
goal.zerox = j;
} else {
sb.append(toChar(count));
}
}
goal.panel[i] = sb.toString();
}
return goal;
}
/**
* 文字から数値へ.
*/
public int toInt(char c) {
if ('0' <= c && c <= '9')
return c - '0';
else
return c - 'A' + 10;
}
/**
* 数値から文字へ.
*/
public char toChar(int i) {
if (i < 10)
return (char)('0' + i);
else
return (char)('A' + i - 10);
}
/**
* パネル内容の表示.
*/
public void print() {
System.out.println("======");
for (int i = 0; i < panel.length; i++)
System.out.println(panel[i]);
}
public int getDistance(InnerPanel target) {
String p1[] = panel;
String p2[] = target.panel;
// 文字->座標のHashtable作成
Hashtable<Character, Integer> p1hash =
new Hashtable<Character, Integer>();
Hashtable<Character, Integer> p2hash =
new Hashtable<Character, Integer>();
String p1line = null, p2line = null;
char c1, c2;
for (int i = 0; i < p1.length; i++) {
p1line = p1[i];
p2line = p2[i];
for (int j = 0; j < p1line.length(); j++) {
c1 = p1line.charAt(j);
if (c1 != '=' && c1 != '0') {
p1hash.put(c1, i * 10 + j);
}
c2 = p2line.charAt(j);
if (c2 != '=' && c2 != '0')
p2hash.put(c2, i * 10 + j);
}
}
char c;
Integer xy1, xy2;
int sa, total = 0;
for (int i = 1; i <= maxcount; i++) {
c = toChar(i);
xy1 = p1hash.get(c);
if (xy1 == null)
continue;
xy2 = p2hash.get(c);
sa = Math.abs(xy1 / 10 - xy2 / 10) +
Math.abs(xy1 % 10 - xy2 % 10);
total += sa;
}
return total;
}
/**
* 距離を計算して保存.
*/
public int calculateDistance(InnerPanel target) {
distance = getDistance(target);
return distance;
}
/**
* String表現.
*/
public String toString() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < height; i++)
sb.append(panel[i]);
return sb.toString();
}
/**
* 次の状態.
*/
public InnerPanel[] nextPanels() {
ArrayList<InnerPanel> panel_array = new ArrayList<InnerPanel>();
char up = 0, down = 0, left = 0, right = 0;
if (zeroy > 0)
up = panel[zeroy - 1].charAt(zerox);
if (zeroy < height - 1)
down = panel[zeroy + 1].charAt(zerox);
if (zerox > 0)
left = panel[zeroy].charAt(zerox - 1);
if (zerox < width - 1)
right = panel[zeroy].charAt(zerox + 1);
try {
if (up != 0 && up != '=')
panel_array.add(makeUp());
if (down != 0 && down != '=')
panel_array.add(makeDown());
if (left != 0 && left != '=')
panel_array.add(makeLeft());
if (right != 0 && right != '=')
panel_array.add(makeRight());
} catch (IOException ex) {
;
}
return (InnerPanel[])panel_array.toArray(new InnerPanel[0]);
}
/**
* コピー作成.
*/
public InnerPanel makeCopy() {
InnerPanel copy = new InnerPanel(width, height);
copy.maxc = maxc;
copy.maxcount = maxcount;
copy.panel = new String[panel.length];
for (int i = 0; i < panel.length; i++)
copy.panel[i] = panel[i];
copy.distance = distance;
copy.zerox = zerox;
copy.zeroy = zeroy;
copy.route = new StringBuffer(route.toString());
return copy;
}
/**
* 上へ移動.
*/
public InnerPanel makeUp() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy - 1].getBytes("UTF-8");
byte sline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = sline[zerox];
sline[zerox] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy - 1] = new String(tline, "UTF-8");
copy.panel[zeroy] = new String(sline, "UTF-8");
copy.zeroy--;
copy.route.append('U');
return copy;
}
/**
* 下へ移動.
*/
public InnerPanel makeDown() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy + 1].getBytes("UTF-8");
byte sline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = sline[zerox];
sline[zerox] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy + 1] = new String(tline, "UTF-8");
copy.panel[zeroy] = new String(sline, "UTF-8");
copy.zeroy++;
copy.route.append('D');
return copy;
}
/**
* 左へ移動.
*/
public InnerPanel makeLeft() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = tline[zerox - 1];
tline[zerox - 1] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy] = new String(tline, "UTF-8");
copy.zerox--;
copy.route.append('L');
return copy;
}
/**
* 右へ移動.
*/
public InnerPanel makeRight() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = tline[zerox + 1];
tline[zerox + 1] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy] = new String(tline, "UTF-8");
copy.zerox++;
copy.route.append('R');
return copy;
}
}
/**
* メイン.
*/
public static void main(String args[]) {
int skip = 0;
if (args.length > 0)
skip = Integer.parseInt(args[0]);
try {
InputStreamReader isr = null;
try {
isr = new InputStreamReader(System.in, "UTF-8");
BufferedReader br = null;
try {
br = new BufferedReader(isr);
new Panel2().play(br, skip);
} finally {
if (br != null) br.close();
}
} finally {
if (isr != null) isr.close();
}
} catch (IOException ex) {
ex.printStackTrace();
System.exit(1);
}
System.exit(0);
}
public int lx = 0;
public int rx = 0;
public int ux = 0;
public int dx = 0;
public int cases = 0;
/**
* コンストラクタ.
*/
public Panel2() {
}
/**
* 開始.
*/
public void play(BufferedReader br, int skip) throws IOException {
String numberstr = br.readLine();
String numbers[] = numberstr.split(" ");
lx = Integer.parseInt(numbers[0]);
rx = Integer.parseInt(numbers[1]);
ux = Integer.parseInt(numbers[2]);
dx = Integer.parseInt(numbers[3]);
cases = Integer.parseInt(br.readLine());
for (int i = 0; i < skip; i++)
br.readLine();
for (int i = 0; i < cases; i++) {
solve(skip + i + 1, br.readLine());
}
}
/**
* 1問解く.
*/
public void solve(int panel_num, String line) {
String lines[] = line.split(",");
int width = Integer.parseInt(lines[0]);
int height = Integer.parseInt(lines[1]);
InnerPanel start_panel = new InnerPanel(width, height, lines[2]);
InnerPanel goal_panel = start_panel.makeGoal();
Hashtable<String, String> route_hash = new Hashtable<String, String>();
// 距離設定
start_panel.calculateDistance(goal_panel);
goal_panel.calculateDistance(start_panel);
// 既出状態保存
Hashtable<String, InnerPanel> start_already_hash = new Hashtable<String, InnerPanel>();
Hashtable<String, InnerPanel> goal_already_hash = new Hashtable<String, InnerPanel>();
// 先端状態保存
ArrayList<InnerPanel> start_edge_array = new ArrayList<InnerPanel>();
Hashtable<String, InnerPanel> start_edge_hash =
new Hashtable<String, InnerPanel>();
ArrayList<InnerPanel> start_next_array = new ArrayList<InnerPanel>();
ArrayList<InnerPanel> goal_edge_array = new ArrayList<InnerPanel>();
Hashtable<String, InnerPanel> goal_edge_hash =
new Hashtable<String, InnerPanel>();
ArrayList<InnerPanel> goal_next_array = new ArrayList<InnerPanel>();
// 初期状態にする
start_edge_array.add(start_panel);
start_edge_hash.put(start_panel.toString(), start_panel);
start_already_hash.put(start_panel.toString(), start_panel);
goal_edge_array.add(goal_panel);
goal_edge_hash.put(goal_panel.toString(), goal_panel);
goal_already_hash.put(goal_panel.toString(), goal_panel);
// ここからぶんまわす
InnerPanel onePanel, newPanel, newPanels[], bingo;
String sum = null;
boolean bingo_flg = false;
int loop_count = 0;
while (true) {
++loop_count;
if (loop_count > MAX_COUNT) {
System.out.println(panel_num + ":");
break;
}
// ゴール側からの比較用Hashtableクリア
start_edge_hash = new Hashtable<String, InnerPanel>();
start_next_array = new ArrayList<InnerPanel>();
// スタート状態からの先端状態モノでループ
for (int i = 0; i < start_edge_array.size(); i++) {
onePanel = start_edge_array.get(i);
// 次の状態取得
newPanels = onePanel.nextPanels();
for (int j = 0; j < newPanels.length; j++) {
newPanel = newPanels[j];
sum = newPanel.toString();
// 既出なら捨てる
if (start_already_hash.containsKey(sum))
continue;
// 追加
start_already_hash.put(sum, newPanel);
// 既出とビンゴ？
bingo = goal_already_hash.get(sum);
if (bingo != null) {
checkMate(newPanel, bingo, true, panel_num, route_hash);
bingo_flg = true;
}
// ビンゴ？
bingo = goal_edge_hash.get(sum);
if (bingo != null) {
checkMate(newPanel, bingo, true, panel_num, route_hash);
bingo_flg = true;
}
// 既出じゃなければゴールとの距離計算
newPanel.calculateDistance(goal_panel);
if (newPanel.distance == 0) {
checkMate(newPanel, null, true, panel_num, route_hash);
bingo_flg = true;
}
// 次の先端状態モノに入れる
start_next_array.add(newPanel);
start_edge_hash.put(sum, newPanel);
}
}
start_edge_array = sort(start_next_array);
// スタート側からのがビンゴ
if (bingo_flg)
break;
// スタート側からの比較用Hashtableクリア
goal_edge_hash = new Hashtable<String, InnerPanel>();
goal_next_array = new ArrayList<InnerPanel>();
// ゴール側からの先端状態モノでループ
for (int i = 0; i < goal_edge_array.size(); i++) {
onePanel = goal_edge_array.get(i);
// 次の状態取得
newPanels = onePanel.nextPanels();
for (int j = 0; j < newPanels.length; j++) {
newPanel = newPanels[j];
sum = newPanel.toString();
// 既出なら捨てる
if (goal_already_hash.containsKey(sum))
continue;
// 追加
goal_already_hash.put(sum, newPanel);
// 既出とビンゴ？
bingo = start_already_hash.get(sum);
if (bingo != null) {
checkMate(bingo, newPanel, false, panel_num, route_hash);
bingo_flg = true;
}
// ビンゴ？
bingo = start_edge_hash.get(sum);
if (bingo != null) {
checkMate(bingo, newPanel, false, panel_num, route_hash);
bingo_flg = true;
}
// 既出じゃなければ初期との距離計算
newPanel.calculateDistance(start_panel);
if (newPanel.distance == 0) {
checkMate(null, newPanel, true, panel_num, route_hash);
bingo_flg = true;
}
// 次の先端状態モノに入れる
goal_next_array.add(newPanel);
goal_edge_hash.put(sum, newPanel);
}
}
goal_edge_array = sort(goal_next_array);
// ゴール側からのがビンゴ
if (bingo_flg)
break;
}
Enumeration<String> e = route_hash.keys();
while (e.hasMoreElements()) {
String key = e.nextElement();
System.out.println(panel_num + ":" + route_hash.get(key) + ":" + key);
}
}
public ArrayList<InnerPanel> sort(ArrayList<InnerPanel> source) {
InnerPanel source_array[] = source.toArray(new InnerPanel[0]);
Arrays.sort(source_array, new PanelCompare());
ArrayList<InnerPanel> sorted_list = new ArrayList<InnerPanel>();
for (int i = 0; i < MAX_NUM && i < source_array.length; i++)
sorted_list.add(source_array[i]);
return sorted_list;
}
public class PanelCompare implements Comparator {
public int compare(Object o1, Object o2) {
InnerPanel p1 = (InnerPanel)o1;
InnerPanel p2 = (InnerPanel)o2;
return p1.distance - p2.distance;
}
}
/**
* チェックメイト.
*/
public void checkMate(InnerPanel start_side, InnerPanel goal_side,
boolean even, int panel_num, Hashtable<String, String> route_hash) {
StringBuffer resolv_sb = null;
if (start_side != null)
resolv_sb = new StringBuffer(start_side.route.toString());
else
resolv_sb = new StringBuffer();
StringBuffer goal_sb = null;
if (goal_side != null)
goal_sb = goal_side.route;
else
goal_sb = new StringBuffer();
char c;
for (int i = goal_sb.length() - 1; i >= 0; i--) {
c = goal_sb.charAt(i);
switch (c) {
case 'U':
resolv_sb.append('D');
break;
case 'D':
resolv_sb.append('U');
break;
case 'L':
resolv_sb.append('R');
break;
case 'R':
resolv_sb.append('L');
break;
}
}
String result = resolv_sb.toString();
// カウント
int u_count = 0, d_count = 0, l_count = 0, r_count = 0;
for (int i = 0; i < result.length(); i++) {
c = result.charAt(i);
switch (c) {
case 'U':
u_count++;
break;
case 'D':
d_count++;
break;
case 'L':
l_count++;
break;
case 'R':
r_count++;
break;
}
}
StringBuffer save_sb = new StringBuffer();
save_sb.append("U=");
save_sb.append(u_count);
save_sb.append(",D=");
save_sb.append(d_count);
save_sb.append(",L=");
save_sb.append(l_count);
save_sb.append(",R=");
save_sb.append(r_count);
route_hash.put(save_sb.toString(), result);
}
}
登録:
投稿 (Atom)