Facebook Hacker Cup 2014の第1ラウンドのPrologue AAAAAAに対するソリューションを示したいと思います。タスクはかなり大きな検索スペースを持ち、一般的なプログラミング言語の経験豊富なスポーツプログラマーによる解決を目的として作成されました。
タスクの本質：
テストごとに、
N
×
M
グリッド（
N
および
M
最大500）が入力に供給されます。 各グリッドセルには次のいずれかが含まれます
.
'-オープンセル、または'
#
'-クローズドセル（「車でブロック」）。 目標は、パスの各セル（最初のセルを除く）が前のセルの右または下になるように、左上隅から開いているセルに沿って最大長のパス（「人の並び」）を構築することです。
1つの例外が許可されています-パスの連続したセクションを左または上に移動できます。 各オープンセルは1回しか使用できません。
各テストのプログラムの出力は、最長パスの長さです。 1つのファイルに最大20個のテストを含めることができます。
入力および出力データの例：
5 5 5 ..... ..... ..... ..... ..... 1 10 .......... 5 5 ...#. ...#. ...#. ...#. ..... 3 3 ..# #.# ... 3 8 ........ #.#.#.#. #.#.#.#.
Case #1: 17 Case #2: 10 Case #3: 17 Case #4: 5 Case #5: 10
最初の例では、閉じたセルはありません。 最大長の1つの可能な方法：
↓→↓. ↓↑↓.. ↓↑↓.. ↓↑↓.. →↑→→⊕
最後の例の最長の方法：
→→→→→→→↓ #.#.#.#↓ #.#.#.#⊕
私のソリューションでは、 メモ化の形式であるB-Prolog固有の「モード指示タブリング」を使用します。 集計はPrologの標準機能ではないため、プログラムは他のPrologシステムでは動作しません（ XSBとYAPには同様の機能があります）。
このソリューションでは、トップダウンの動的プログラミング手法を使用しています。 ソリューションを理解するために、動的プログラミングの特別な知識は必要ありません。プログラムは単にキューを継続するすべての可能な方法を説明し、B-Prologにこのキューの長さの最大値を見つけるよう求めます。
コンテスト中に作成して送信したコードは次のとおりです。
:- table queue(+, +, +, +, +, +, max). queue(_R, _C, _, _, X, Y, 1) :- \+ car(X, Y). % move down queue(R, C, Used, Prev, X, Y, S) :- X < R, Prev \= up, Xp1 is X + 1, \+ car(Xp1, Y), queue(R, C, Used, down, Xp1, Y, Snext), S is 1 + Snext. % move right queue(R, C, Used, Prev, X, Y, S) :- Y < C, Prev \= left, Yp1 is Y + 1, \+ car(X, Yp1), queue(R, C, Used, right, X, Yp1, Snext), S is 1 + Snext. % move up queue(R, C, Used, Prev, X, Y, S) :- X > 1, (Used =:= 0 ; Prev == up), Prev \= down, Xm1 is X - 1, \+ car(Xm1, Y), queue(R, C, 1, up, Xm1, Y, Snext), S is 1 + Snext. % move left queue(R, C, Used, Prev, X, Y, S) :- Y > 1, (Used =:= 0 ; Prev == left), Prev \= right, Ym1 is Y - 1, \+ car(X, Ym1), queue(R, C, 1, left, X, Ym1, Snext), S is 1 + Snext. do_case(Case_num, R, C) :- queue(R, C, 0, right, 1, 1, S), format("Case #~w: ~w\n", [Case_num, S]). main :- read(T), foreach(Case_num in 1..T, [R, C, N], ( initialize_table, abolish, read([R, C]), read(N), assert(car(-1, -1)), % dummy foreach(_I in 1..N, [X, Y], (read([X, Y]), assert(car(X, Y)))), do_case(Case_num, R, C) )).
最初の行は、
queue
述語の集計モードを設定し
queue
。最初の6つのパラメーターは入力で、最後は出力です。入力パラメーターに複数の異なる出力値が可能な場合、最大化する必要があります。
queue
述語パラメーター：
-
R
グリッド内の行数
-
C
はグリッド内の列の数です
-
Used
-左または上への移動が既に使用されている場合は1、それ以外の場合は0
-
Prev
-前のステップの方向
-
X
は現在のX座標です
-
Y
現在のY座標
-
S
は（X
、Y
）からのパスの長さです。
queue
述語の最初のルールは、セル（
X
、
Y
）が車によってブロックされていない場合、このセルで開始する（少なくとも）長さ1のキューが可能であることを示しています。
次に、キューを継続する4つの可能な方法を説明する4つのルールがあります。下、右、上、左です。
下に進むルール：
- 現在の行
X
の数は、グリッドR
行数より少ない
- 前のステップがアップしていません（「アップ」）
- セル（
X+1
、Y
）は車によってブロックされていません
- 結果のキューの長さは、1プラスセルで始まるキューの長さ（
X+1
、Y
）になります。
右に進むためのルールは、下に進むためのルールに似ています。
上および左に継続するためのルールには、左または上への移動がまだ使用されていないという追加条件が含まれます。または、左/上に順番に移動し続けます。
(Used =:= 0 ; Prev == up)
。
do_case
は
queue
を使用して、左上隅から始まるキューの最大長を見つけます。 集計のおかげで、サブタスクの結果は一度だけ計算されます。
main
はテストの数を読み取り、各テストで
R
、
C
、および車両位置をPrologにとって便利な形式で読み取ります。 車ごとに、ファクトがPrologファクトベースに追加され、
queue
述語ルールで使用されます。
B-Prologでタスクの入力データをすぐに操作することは可能ですが、私は決めました
Pythonスクリプトを使用して前処理するのがはるかに簡単になります
（車ごとに2要素の座標リストが表示され、各行はドットで終わります）：
T = int(raw_input()) print "%d." % T for case_num in range(1, T + 1): R, C = map(int, raw_input().split()) print "[%d, %d]." % (R, C) cars = [] for i in range(R): row = raw_input().strip() for j in range(C): if row[j] == '#': cars.append([i + 1, j + 1]) print "%d." % len(cars) for car in cars: print "[%d, %d]." % (car[0], car[1])
実行するコマンド（
tail
は結果からB-Prologバージョンメッセージを削除します）：
cat in-file | python preprocess.py | bp -g "cl('AAAAAA.pl'),main,halt" -l | tail -n +7 > out-file
特定のソリューションと比較するために、B-Prologは、他の参加者（主にJavaまたはC ++） のソリューションの結果テーブルページからダウンロードできます。 それらのほとんど（すべてではないにしても）は、何らかの形式の動的プログラミングを使用します。