私の回答と探索に使用したソースコード。コードはムダに長いし地形の解析を途中まで実装したが探索には使っていない。
探索ロジックはあまり賢くない。たぶんLv2 は同じところをなんども回ってたり。一応工夫した点のメモを残す。
hlllkjllkkhhhkhhkhhhjjjjllkklkllklllj
kkkllljjjhhhkkkllkkkllljjjh.lljjjlllllhhkkklllllkkkllljjj.hhjjjhhhkkk.ll.kkkhkk lljjhhhhhhhh.ljjjhhjk.hkkklkkhhhhjjhhkklllkkklhhkkkllljjjlllkkklllllhhjjjhhjjjh llllkkkllkkkllljjjhhjjjlljjjjjhhhhhhhhhhhjjjhhhkkkllllllllkkkkkhhhhhhhjkllkkkhk kklhhhhjjjlllhhhhhjj
hhkkhhlljjlllkklllkllllkkkkkkkklllllllljjjjjhhhllljjjhhhhhllllllllljjjhhhhhhhhh hhhhhhhkkkkkkkkkkkkkklllljjjjjjjjjjjlllllllllllljjjhhhhhhkkkllkkkkkkkkllllkkkhh hhhhhhhhhhhhhhhhhhhhhhhjjjhhhhhhhhjjjjjjjjhhhhhhhhhhhhhhhhhhhhhhjjjlllllkkkhkkk kkkkkhhhhkkklllllllllllllllllllllllllllllljjjlllllllllkkklllllllllljjjhhhhhhjjj jjjjjhhhhkkhhhhhhhhhjjhhhhhhhhhhhjjjlllllllllllkkkkkkkkkkkhhhhhhhhhhhhhhhhkkkhh hhhhhhhhjjjjjjjjjjjljjjlllllllllllkkkhhkkkkkkkhhhhhhjjjl
ボードに対する上下左右を UP, DOWN, LEFT, RIGHT として実装を始めてしまったが、進行方向の上下左右を使いたくなったので東西南北に変更したが、一部のメソッドの名前が古いまま。経験値の不足を感じる。
PacManBfsSolverMain.java のBfsPacManSolver#solve() に探索ロジックを実装。
探索順にほぼ意味が無いので、どこを探索しないかに注力。まぁ、結局はたいしたことはしていない...
PacManDfsSolverMain.java の DFSPacManSolver#solve() に探索ロジックを記述。
eclipse のプロジェクトを zip で固めたものを置いておきます。依存ライブラリとして google-collection の 1.0 を使用しています。プロジェクトの設定としては GoogleCollections という名前のユーザライブラリが定義されているとして依存を指定しているので、import する場合はユーザライブラリを定義してください。
一応ここにも貼っておきます(シミュレータはアーカイブの中のみ)。
PacMan.java
/*
* パックマンのモデルを提供するクラス群。
*
* (C) YAMAZAKI Makoto <makoto1975@gmail.com> 2010.
*
* 本来なら各クラスを独立したファイルにするところだが、提出用に BFD で探索するクラスと同じファイルに
* 記述してあった。複数ファイルの提出もOKとのことなので、とりあえず BFS/DFS で共通のものは独立した
* ファイルに分割した。
*
* 依存ライブラリとして Google Collections を使用している。
*
* $Id: PackMan.java 135 2010-08-22 10:37:53Z zaki $
*/
package org.zakky.gdd2010.pacman;
import static org.zakky.gdd2010.pacman.Board.Direction.DOWN;
import static org.zakky.gdd2010.pacman.Board.Direction.LEFT;
import static org.zakky.gdd2010.pacman.Board.Direction.RIGHT;
import static org.zakky.gdd2010.pacman.Board.Direction.STAY;
import static org.zakky.gdd2010.pacman.Board.Direction.UP;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.regex.Pattern;
import org.zakky.gdd2010.pacman.Board.Direction;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
final class Board {
public static final char WALL = '#';
public static final char DEADEND = 'd';
public static final char WALKWAY = 'w';
public static final char INTERSECTION = 'i';
public static final char BLANK = ' ';
public static final char DOT = '.';
public static final char PACMAN = '@';
public static final char ENEMY_L = 'L';
public static final char ENEMY_R = 'R';
public static final char ENEMY_J = 'J';
public static final char ENEMY_V = 'V';
public static final char ENEMY_H = 'H';
public static final Map<Integer, String> KNOWN_MAPS = ImmutableMap.of(
Integer.valueOf(-957077586), "Lv1", Integer.valueOf(-1956186425),
"Lv2", Integer.valueOf(106332079), "Lv3");
public enum Direction {
LEFT('h', -1, 0), DOWN('j', 0, 1), UP('k', 0, -1), RIGHT('l', 1, 0), STAY(
'.', 0, 0);
public final char literal;
public final int dx;
public final int dy;
Direction(char literal, int dx, int dy) {
this.literal = literal;
this.dx = dx;
this.dy = dy;
}
public Direction opposite() {
return getDirection(0, 0, dx, dy);
}
public static Direction fromLiteral(char literal) {
for (Direction d : values()) {
if (literal == d.literal) {
return d;
}
}
throw new IllegalArgumentException("invalid Direction literal: "
+ literal);
}
public static Direction getDirection(int x, int y, int prevX, int prevY) {
if (x != prevX) {
assert y == prevY;
return (prevX < x) ? RIGHT : LEFT;
}
if (y != prevY) {
assert x == prevX;
return (prevY < y) ? DOWN : UP;
}
return STAY;
}
public static List<Direction> filter(ImmutableList<Direction> list,
Direction... toBeDropped) {
final List<Direction> result = Lists.newArrayList(list);
for (Direction d : toBeDropped) {
result.remove(d);
}
return result;
}
}
public static int turnToLeftX(int x, int y, int prevX, int prevY) {
return x + (y - prevY);
}
public static int turnToLeftY(int x, int y, int prevX, int prevY) {
return y + (prevX - x);
}
public static int turnToRightX(int x, int y, int prevX, int prevY) {
return x + (prevY - y);
}
public static int turnToRightY(int x, int y, int prevX, int prevY) {
return y + (x - prevX);
}
public static int goAheadX(int x, int y, int prevX, int prevY) {
return x * 2 - prevX;
}
public static int goAheadY(int x, int y, int prevX, int prevY) {
return y * 2 - prevY;
}
public static boolean canTurnToLeft(Board b, int x, int y, int prevX,
int prevY) {
return !b.isWall(turnToLeftX(x, y, prevX, prevY),
turnToLeftY(x, y, prevX, prevY));
}
public static boolean canTurnToRight(Board b, int x, int y, int prevX,
int prevY) {
return !b.isWall(turnToRightX(x, y, prevX, prevY),
turnToRightY(x, y, prevX, prevY));
}
public static boolean canGoAhead(Board b, int x, int y, int prevX, int prevY) {
return !b.isWall(goAheadX(x, y, prevX, prevY),
goAheadY(x, y, prevX, prevY));
}
public static boolean canGoBack(Board b, int x, int y, int prevX, int prevY) {
return !b.isWall(prevX, prevY);
}
public static Board buildBoard(BufferedReader reader, boolean useStay)
throws IOException {
final int timeLimit = Integer.parseInt(reader.readLine());
final String[] sizeStrs = reader.readLine().split(Pattern.quote(" "));
final int width = Integer.parseInt(sizeStrs[0]);
final int height = Integer.parseInt(sizeStrs[1]);
final List<char[]> fixedOnBoard =
Lists.newArrayListWithCapacity(height);
final List<Enemy> enemies = Lists.newArrayList();
final Collection<Point> dots = Lists.newArrayList();
final Point pacman = new Point(-1, -1);
for (int hIndex = 0; hIndex < height; hIndex++) {
final String line = reader.readLine();
if (line == null) {
throw new IOException("input data is shorter than expected.");
}
final char[] row = new char[width];
for (int wIndex = 0; wIndex < width; wIndex++) {
final char c = line.charAt(wIndex);
switch (c) {
case WALL: // 壁
row[wIndex] = WALL;
break;
case BLANK: // 空きマス
row[wIndex] = BLANK;
break;
case DOT: // ドット
row[wIndex] = BLANK;
dots.add(new Point(wIndex + 1, hIndex + 1));
break;
case PACMAN: // 自機
row[wIndex] = BLANK;
if (0 < pacman.x || 0 < pacman.y) {
// Pac-Man が２つ
throw new RuntimeException(
"duplicate Pac-Man found on the board");
}
pacman.x = wIndex + 1;
pacman.y = hIndex + 1;
break;
case ENEMY_V:
row[wIndex] = BLANK;
enemies.add(new EnemyV(wIndex + 1, hIndex + 1));
break;
case ENEMY_H:
row[wIndex] = BLANK;
enemies.add(new EnemyH(wIndex + 1, hIndex + 1));
break;
case ENEMY_L:
row[wIndex] = BLANK;
enemies.add(new EnemyL(wIndex + 1, hIndex + 1));
break;
case ENEMY_R:
row[wIndex] = BLANK;
enemies.add(new EnemyR(wIndex + 1, hIndex + 1));
break;
case ENEMY_J:
row[wIndex] = BLANK;
enemies.add(new EnemyJ(wIndex + 1, hIndex + 1));
break;
default:
throw new RuntimeException("unexpected char '" + c
+ "' at x: " + (wIndex + 1) + ", y: "
+ (hIndex + 1));
}
}
fixedOnBoard.add(row);
}
// データの確認と、処理のための前準備
// Pac-Man が存在すること
if (pacman.x <= 0 || pacman.y <= 0) {
throw new RuntimeException("Pac-Man not found on the board");
}
// 周囲が壁であることの確認と、空白の分類
for (int hIndex = 0; hIndex < height; hIndex++) {
final char[] row = fixedOnBoard.get(hIndex);
// 最初と最後の行は全てが壁であること
if (hIndex == 0 || hIndex == height - 1) {
for (char edge : row) {
if (edge != WALL) {
throw new RuntimeException(
"edge of the board must be wall: y: "
+ (hIndex + 1));
}
}
continue;
}
// 最初と最後の行以外は両端が壁であること
if (row[0] != WALL || row[row.length - 1] != WALL) {
throw new RuntimeException(
"edge of the board must be wall: y: " + (hIndex + 1));
}
for (int wIndex = 1; wIndex < width - 1; wIndex++) {
if (isWall(fixedOnBoard, wIndex + 1, hIndex + 1)) {
continue;
} else if (isWalkWay(fixedOnBoard, wIndex + 1, hIndex + 1)) {
row[wIndex] = WALKWAY;
} else if (isIntersection(fixedOnBoard, wIndex + 1, hIndex + 1)) {
row[wIndex] = INTERSECTION;
} else if (isDeadEnd(fixedOnBoard, wIndex + 1, hIndex + 1)) {
row[wIndex] = DEADEND;
} else {
throw new RuntimeException("unknown object on board ("
+ (wIndex + 1) + ", " + (hIndex + 1) + ").");
}
}
}
// TODO そのうち全てのドットに到達可能であることを確認してみる
return new Board(timeLimit, fixedOnBoard, pacman.x, pacman.y, dots,
enemies, useStay);
}
private final int timeLimit_;
private final int initialPacmanX_;
private final int initialPacmanY_;
private final Collection<Point> initialDots_; // Point は mutable なのでそのうち自前に。
private final ImmutableList<Enemy> initialEnemies_;
private final ImmutableList<Enemy> initialIntelligentEnemies_;
private final ImmutableList<Enemy> initialNonIntelligentEnemies_;
private ImmutableList<ImmutableList<Enemy>> nonIntelligentEnemiesCache_ =
null;
private final List<char[]> fixedOnBoard_;
private final boolean useStay_;
private final ImmutableList<ImmutableList<CellDetail>> cellDetails_;
private Board(int timeLimit, List<char[]> wallsOnBoard, int initPacmanX,
int initPacmanY, Collection<Point> initDots,
List<Enemy> initEnemies, boolean useStay) {
timeLimit_ = timeLimit;
fixedOnBoard_ = Collections.unmodifiableList(wallsOnBoard);
initialPacmanX_ = initPacmanX;
initialPacmanY_ = initPacmanY;
initialDots_ = initDots;
initialIntelligentEnemies_ = toIntelligentEnemiesOnly(initEnemies);
initialNonIntelligentEnemies_ =
toNonIntelligentEnemiesOnly(initEnemies);
initialEnemies_ = ImmutableList.copyOf(initEnemies);
useStay_ = useStay;
final ImmutableList.Builder<ImmutableList<CellDetail>> rows =
ImmutableList.builder();
for (int y = 1; y <= wallsOnBoard.size(); y++) {
final ImmutableList.Builder<CellDetail> columns =
ImmutableList.builder();
for (int x = 1; x <= wallsOnBoard.get(y - 1).length; x++) {
columns.add(new CellDetail(this, x, y, useStay));
}
rows.add(columns.build());
}
cellDetails_ = rows.build();
// 詳細情報さらにセットする
for (int y = 1; y <= wallsOnBoard.size(); y++) {
for (int x = 1; x <= wallsOnBoard.get(y - 1).length; x++) {
if (isDeadEnd(x, y)) {
final ImmutableList.Builder<Direction> wayToDeadEnd =
ImmutableList.builder();
final ImmutableList<Direction> openWays =
getDetail(x, y).getOpenWays();
Direction toCurrent =
Direction.filter(openWays, STAY).get(0);
int currentX = x + toCurrent.dx;
int currentY = y + toCurrent.dy;
while (isWalkWay(currentX, currentY)) {
wayToDeadEnd.add(toCurrent.opposite());
final CellDetail detail = getDetail(currentX, currentY);
detail.setWayToDeadEnd(wayToDeadEnd.build());
toCurrent =
Direction.filter(detail.getOpenWays(), STAY,
toCurrent.opposite()).get(0);
currentX += toCurrent.dx;
currentY += toCurrent.dy;
}
}
}
}
}
public boolean useStay() {
return useStay_;
}
public CellDetail getDetail(int x, int y) {
return cellDetails_.get(y - 1).get(x - 1);
}
public static class CellDetail {
private final char type_;
private final ImmutableList<Direction> openWays_;
private ImmutableList<Direction> wayToDeadEnd_ = null;
CellDetail(Board board, int x, int y, boolean useStay) {
type_ = Board.getType(board.fixedOnBoard_, x, y);
if (type_ == WALL) {
openWays_ = ImmutableList.of();
} else {
final ImmutableList.Builder<Direction> builder =
ImmutableList.builder();
for (Direction dir : Direction.values()) {
if (!board.canGo(x, y, dir)) {
continue;
}
builder.add(dir);
}
openWays_ = builder.build();
}
}
void setWayToDeadEnd(ImmutableList<Direction> way) {
if (type_ == INTERSECTION) {
throw new RuntimeException(
"can't set way to deadend on INTERSECTION");
}
wayToDeadEnd_ = way;
}
public ImmutableList<Direction> getWayToDeadEnd() {
return wayToDeadEnd_;
}
public ImmutableList<Direction> getOpenWays() {
return openWays_;
}
}
private static ImmutableList<Enemy> toIntelligentEnemiesOnly(
List<Enemy> allEnemies) {
final ImmutableList.Builder<Enemy> intelligents =
ImmutableList.builder();
for (Enemy enemy : allEnemies) {
if (!enemy.isIntelligent()) {
continue;
}
intelligents.add(enemy);
}
return intelligents.build();
}
private static ImmutableList<Enemy> toNonIntelligentEnemiesOnly(
List<Enemy> allEnemies) {
final ImmutableList.Builder<Enemy> nonIntelligents =
ImmutableList.builder();
for (Enemy enemy : allEnemies) {
if (enemy.isIntelligent()) {
continue;
}
nonIntelligents.add(enemy);
}
return nonIntelligents.build();
}
public static ImmutableList<Enemy> updateEnemies(Board board,
Iterable<Enemy> enemies, int myX, int myY) {
final ImmutableList.Builder<Enemy> newEnemies = ImmutableList.builder();
for (Enemy enemy : enemies) {
final Enemy updated = enemy.getNext(board, myX, myY);
newEnemies.add(updated);
}
return newEnemies.build();
}
private static ImmutableList<ImmutableList<Enemy>> buildNonIntelligentEnemiesCache(
Board board, int limit) {
ImmutableList<Enemy> prevNonIntelligents =
board.getInitialNonIntelligentEnemies();
final ImmutableList.Builder<ImmutableList<Enemy>> builder =
ImmutableList.builder();
for (int time = 0; time <= limit; time++) {
// non intelligent 限定なので、自機の位置は適当
prevNonIntelligents =
updateEnemies(board, prevNonIntelligents, 1, 1);
builder.add(prevNonIntelligents);
}
return builder.build();
}
public int getWidth() {
return fixedOnBoard_.get(0).length;
}
public int getHeight() {
return fixedOnBoard_.size();
}
public int getTimeLimit() {
return timeLimit_;
}
public int getInitialPacmanX() {
return initialPacmanX_;
}
public int getInitialPacmanY() {
return initialPacmanY_;
}
public Collection<Point> getInitialDots() {
return initialDots_;
}
public ImmutableList<Enemy> getInitialEnemies() {
return initialEnemies_;
}
public ImmutableList<Enemy> getInitialIntelligentEnemies() {
return initialIntelligentEnemies_;
}
public ImmutableList<Enemy> getInitialNonIntelligentEnemies() {
return initialNonIntelligentEnemies_;
}
public boolean isWall(int x, int y) {
return isWall(fixedOnBoard_, x, y);
}
public static boolean isSafe(Iterable<Enemy> currentEnemies, int currentX,
int currentY, int previousX, int previousY) {
for (Enemy enemy : currentEnemies) {
// 重なるのはアウト
if (enemy.x() == currentX && enemy.y() == currentY) {
return false;
}
// 入れ替わるのもアウト
if (enemy.x() == previousX && enemy.y() == previousY
&& enemy.prevX() == currentX && enemy.prevY() == currentY) {
return false;
}
}
return true;
}
public boolean canGo(int x, int y, Direction d) {
switch (d) {
case LEFT:
return canGoW(fixedOnBoard_, x, y);
case RIGHT:
return canGoE(fixedOnBoard_, x, y);
case UP:
return canGoN(fixedOnBoard_, x, y);
case DOWN:
return canGoS(fixedOnBoard_, x, y);
case STAY:
return true;
default:
throw new RuntimeException("inknown direction: " + d);
}
}
public boolean canGoW(int x, int y) {
return canGoW(fixedOnBoard_, x, y);
}
public boolean canGoE(int x, int y) {
return canGoE(fixedOnBoard_, x, y);
}
public boolean canGoN(int x, int y) {
return canGoN(fixedOnBoard_, x, y);
}
public boolean canGoS(int x, int y) {
return canGoS(fixedOnBoard_, x, y);
}
public boolean isDeadEnd(int x, int y) {
return isDeadEnd(fixedOnBoard_, x, y);
}
public boolean isWalkWay(int x, int y) {
return isWalkWay(fixedOnBoard_, x, y);
}
public boolean isIntersection(int x, int y) {
return isIntersection(fixedOnBoard_, x, y);
}
public int getScore(Collection<Point> dots, int time) {
final int timeScore =
dots.isEmpty() ? Math.max(0, getTimeLimit() - time) : 0;
final int dotScore = getInitialDots().size() - dots.size();
return timeScore + dotScore;
}
/*
* 指定された時刻での移動が完了した状態の敵リストを返します。
* 返すのは自機の位置に関係しない敵(LRJ)のみです。
*/
public ImmutableList<Enemy> getNonIntelligentEnemies(int time) {
if (nonIntelligentEnemiesCache_ == null) {
nonIntelligentEnemiesCache_ =
buildNonIntelligentEnemiesCache(this, getTimeLimit());
}
if (time < 0 || getTimeLimit() < time) {
throw new IllegalArgumentException("invalid time: " + time);
}
return nonIntelligentEnemiesCache_.get(time);
}
private static boolean canGoW(List<char[]> fixedOnBoard, int x, int y) {
if (isWall(fixedOnBoard, x, y)) {
// 現在地が壁ならどこにもいけない
return false;
}
return !isWall(fixedOnBoard, x + LEFT.dx, y + LEFT.dy);
}
private static boolean canGoE(List<char[]> fixedOnBoard, int x, int y) {
if (isWall(fixedOnBoard, x, y)) {
// 現在地が壁ならどこにもいけない
return false;
}
return !isWall(fixedOnBoard, x + RIGHT.dx, y + RIGHT.dy);
}
private static boolean canGoN(List<char[]> fixedOnBoard, int x, int y) {
if (isWall(fixedOnBoard, x, y)) {
// 現在地が壁ならどこにもいけない
return false;
}
return !isWall(fixedOnBoard, x + UP.dx, y + UP.dy);
}
private static boolean canGoS(List<char[]> fixedOnBoard, int x, int y) {
if (isWall(fixedOnBoard, x, y)) {
// 現在地が壁ならどこにもいけない
return false;
}
return !isWall(fixedOnBoard, x + DOWN.dx, y + DOWN.dy);
}
private static final int countNexts(List<char[]> fixedOnBoard, int x, int y) {
int nexts = 0;
if (canGoS(fixedOnBoard, x, y)) {
nexts++;
}
if (canGoW(fixedOnBoard, x, y)) {
nexts++;
}
if (canGoN(fixedOnBoard, x, y)) {
nexts++;
}
if (canGoE(fixedOnBoard, x, y)) {
nexts++;
}
return nexts;
}
private static boolean isDeadEnd(List<char[]> fixedOnBoard, int x, int y) {
final char type = getType(fixedOnBoard, x, y);
if (type == DEADEND) {
return true;
}
if (type == WALKWAY || type == INTERSECTION
|| isWall(fixedOnBoard, x, y)) {
return false;
}
final int nexts = countNexts(fixedOnBoard, x, y);
return nexts <= 1;
}
private static boolean isWalkWay(List<char[]> fixedOnBoard, int x, int y) {
final char type = getType(fixedOnBoard, x, y);
if (type == WALKWAY) {
return true;
}
if (type == INTERSECTION || type == DEADEND
|| isWall(fixedOnBoard, x, y)) {
return false;
}
final int nexts = countNexts(fixedOnBoard, x, y);
return nexts == 2;
}
private static boolean isIntersection(List<char[]> fixedOnBoard, int x,
int y) {
final char type = getType(fixedOnBoard, x, y);
if (type == INTERSECTION) {
return true;
}
if (type == WALKWAY || type == DEADEND || isWall(fixedOnBoard, x, y)) {
return false;
}
final int nexts = countNexts(fixedOnBoard, x, y);
return 3 <= nexts;
}
private static boolean isOutOfRange(List<char[]> fixedOnBoard, int x, int y) {
return (x <= 0 || y <= 0 || fixedOnBoard.get(0).length <= x || fixedOnBoard.size() <= y);
}
private static boolean isWall(List<char[]> fixedOnBoard, int x, int y) {
if (isOutOfRange(fixedOnBoard, x, y)) {
return true;
}
return getType(fixedOnBoard, x, y) == WALL;
}
private static char getType(List<char[]> fixedOnBoard, int x, int y) {
return fixedOnBoard.get(y - 1)[x - 1];
}
public boolean existsDot(int x, int y, Iterable<Point> dots) {
final Point target = new Point(x, y);
for (Point dot : dots) {
if (dot.equals(target)) {
return true;
}
}
return false;
}
private transient String stringRep_ = null;
@Override
public int hashCode() {
return toString().hashCode();
}
@Override
public boolean equals(Object obj) {
// timeLimit は同値判定に使用しません。
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
if (hashCode() != obj.hashCode()) {
return false;
}
final Board other = (Board) obj;
return toString().equals(other.toString());
}
public String toString() {
String stringRep = stringRep_;
if (stringRep == null) {
stringRep = toString(this).intern();
stringRep_ = stringRep;
}
return stringRep;
}
public static String toString(Board b) {
final int width = b.getWidth();
final int height = b.getHeight();
final ImmutableList<Enemy> enemies = b.getInitialEnemies();
final Collection<Point> dots = b.getInitialDots();
final int pacmanX = b.getInitialPacmanX();
final int pacmanY = b.getInitialPacmanY();
boolean detailOfPacmanWritten = false;
final Iterator<Enemy> enemiesToPrintDetails = enemies.iterator();
final StringBuilder whole = new StringBuilder();
final StringBuilder line = new StringBuilder();
for (int y = 1; y <= height; y++) {
line.delete(0, line.length());
// write wall
for (int x = 1; x <= width; x++) {
line.append(b.isWall(x, y) ? WALL : BLANK);
}
// write dots
for (Point dot : dots) {
if (dot.y != y) {
continue;
}
line.setCharAt(dot.x - 1, DOT);
}
// write enemies
for (Enemy enemy : enemies) {
if (enemy.y() != y) {
continue;
}
line.setCharAt(enemy.x() - 1, enemy.getName());
}
// write PacMan
if (pacmanY == y) {
line.setCharAt(pacmanX - 1, PACMAN);
}
// PacMan と 敵の詳細を表示
if (!detailOfPacmanWritten) {
detailOfPacmanWritten = true;
line.append(" " + Board.PACMAN + " at (" + pacmanX + ", "
+ pacmanY + ")");
} else if (enemiesToPrintDetails.hasNext()) {
line.append(" ").append(
enemiesToPrintDetails.next().toString());
}
line.append("\r\n");
whole.append(line);
}
while (enemiesToPrintDetails.hasNext()) {
line.delete(0, line.length());
for (int i = 0; i < width; i++) {
line.append(' ');
}
line.append(" ").append(enemiesToPrintDetails.next().toString());
line.append("\r\n");
whole.append(line);
}
return whole.toString();
}
public static void printInitialBoard(Board b) {
printInitialBoard(b, false);
}
public static void printInitialBoard(Board b, boolean printNext) {
Board.printBoard(b, 0, b.getInitialDots(), b.getInitialEnemies(),
b.getInitialPacmanX(), b.getInitialPacmanY(), new char[0],
printNext);
}
public static void printBoard(Board b, BoardState state, boolean writeNext) {
final List<Enemy> nonIntelligentEnemies =
state.getTime() == 0 ? b.getInitialNonIntelligentEnemies()
: b.getNonIntelligentEnemies(state.getTime() - 1);
printBoard(
b,
state.getTime(),
state.getDots(),
Iterables.concat(nonIntelligentEnemies,
state.getIntelligentEnemies()), state.getPacmanX(),
state.getPacmanY(), state.getHistory(), false);
}
public static void printBoard(Board b, BoardState state) {
printBoard(b, state, false);
}
public static void printBoard(Board b, int time, Collection<Point> dots,
Iterable<Enemy> enemies, int pacmanX, int pacmanY, char[] history,
boolean writeNext) {
final PrintStream out = System.out;
Iterable<Enemy> nextEnemies =
(!writeNext) ? null : Board.updateEnemies(b, enemies, pacmanX,
pacmanY);
out.println();
out.print("time: ");
out.println(time);
out.print("remaining dots: ");
out.println(dots.size());
out.print("score: ");
out.println(b.getScore(dots, time));
out.print("history: ");
out.println(history);
final int width = b.getWidth();
final int height = b.getHeight();
boolean detailOfPacmanWritten = false;
final Iterator<Enemy> enemiesToPrintDetails = enemies.iterator();
final StringBuilder sb = new StringBuilder();
for (int y = 1; y <= height; y++) {
sb.delete(0, sb.length());
final int offsetForNext = b.getWidth() + 1/* one space */;
writeWalls(sb, b, y);
if (writeNext) {
sb.append(' ');
writeWalls(sb, b, y);
}
writeDots(sb, b, y, dots, 0);
if (writeNext) {
sb.append(' ');
writeDots(sb, b, y, dots, offsetForNext);
}
writeEnemies(sb, b, y, enemies, 0);
if (writeNext) {
sb.append(' ');
writeEnemies(sb, b, y, nextEnemies, offsetForNext);
}
// write PacMan
writePacMan(sb, b, y, pacmanX, pacmanY, 0);
if (writeNext) {
sb.append(' ');
writePacMan(sb, b, y, pacmanX, pacmanY, offsetForNext);
}
// PacMan と 敵の詳細を表示
if (!detailOfPacmanWritten) {
detailOfPacmanWritten = true;
sb.append(" " + Board.PACMAN + " at (" + pacmanX + ", "
+ pacmanY + ")");
} else if (enemiesToPrintDetails.hasNext()) {
sb.append(" ").append(enemiesToPrintDetails.next().toString());
}
out.println(sb.toString());
}
while (enemiesToPrintDetails.hasNext()) {
sb.delete(0, sb.length());
for (int i = 0; i < width + (!writeNext ? 0 : 2 + width); i++) {
sb.append(' ');
}
sb.append(" ").append(enemiesToPrintDetails.next().toString());
out.println(sb.toString());
}
}
private static void writeWalls(StringBuilder sb, Board b, int y) {
for (int x = 1; x <= b.getWidth(); x++) {
sb.append(b.isWall(x, y) ? WALL : BLANK);
}
}
private static void writeDots(StringBuilder sb, Board b, int y,
Collection<Point> dots, int offset) {
for (Point dot : dots) {
if (dot.y != y) {
continue;
}
sb.setCharAt(offset + dot.x - 1, DOT);
}
}
private static void writeEnemies(StringBuilder sb, Board b, int y,
Iterable<Enemy> enemies, int offset) {
for (Enemy enemy : enemies) {
if (enemy.y() != y) {
continue;
}
sb.setCharAt(offset + enemy.x() - 1, enemy.getName());
}
}
private static void writePacMan(StringBuilder sb, Board b, int y,
int pacmanX, int pacmanY, int offset) {
if (pacmanY == y) {
sb.setCharAt(offset + pacmanX - 1, PACMAN);
}
}
}
abstract class Enemy {
private final int currX_;
private final int currY_;
private final int prevX_;
private final int prevY_;
public Enemy(final int x, final int y) {
if (x <= 0 || y <= 0) {
throw new IllegalArgumentException("invalid coord. x: " + x
+ ", y: " + y);
}
currX_ = x;
currY_ = y;
prevX_ = -1;
prevY_ = -1;
}
protected Enemy(final int x, final int y, final Enemy prev) {
if (x <= 0 || y <= 0) {
throw new IllegalArgumentException("invalid coord. x: " + x
+ ", y: " + y);
}
currX_ = x;
currY_ = y;
prevX_ = prev.x();
prevY_ = prev.y();
}
public abstract char getName();
public final Enemy getNext(Board b, int myX, int myY) {
if (isInitialPosition()) {
return firstMove(b);
}
final int x = x();
final int y = y();
if (b.isWalkWay(x, y)) {
if (!fromN() && b.canGoN(x, y)) {
return goN(b);
} else if (!fromS() && b.canGoS(x, y)) {
return goS(b);
} else if (!fromW() && b.canGoW(x, y)) {
return goW(b);
} else {
assert !fromE() && b.canGoE(x(), y());
return goE(b);
}
}
if (b.isDeadEnd(x, y)) {
if (b.canGoN(x, y)) {
return goN(b);
} else if (b.canGoS(x, y)) {
return goS(b);
} else if (b.canGoW(x, y)) {
return goW(b);
} else {
assert b.canGoE(x(), y());
return goE(b);
}
}
if (b.isWall(x, y)) {
throw new RuntimeException(getName()
+ " is on the wall. current: (" + x + ", " + y + ")");
}
assert b.isIntersection(x, y);
return getNextAtIntersection(b, myX, myY);
}
protected abstract Enemy getNextAtIntersection(Board b, int myX, int myY);
protected abstract Enemy createNextEnemy(Board b, int nextX, int nextY);
protected abstract boolean isIntelligent();
public final int x() {
return currX_;
}
public final int y() {
return currY_;
}
public final int prevX() {
return prevX_;
}
public final int prevY() {
return prevY_;
}
public final boolean isInitialPosition() {
return prevX_ <= 0 || prevY_ <= 0;
}
protected final Enemy firstMove(Board b) {
final int x = x();
final int y = y();
if (b.canGoS(x, y)) {
return goS(b);
} else if (b.canGoW(x, y)) {
return goW(b);
} else if (b.canGoN(x, y)) {
return goN(b);
} else if (b.canGoE(x, y)) {
return goE(b);
} else {
throw new RuntimeException("can't move from (" + x + "," + y + ")");
}
}
public final boolean fromW() {
return prevX_ - currX_ < 0;
}
public final boolean fromE() {
return 0 < prevX_ - currX_;
}
public final boolean fromN() {
return prevY_ - currY_ < 0;
}
public final boolean fromS() {
return 0 < prevY_ - currY_;
}
protected final Enemy goW(Board b) {
final int x = x();
final int y = y();
if (!b.canGoW(x, y)) {
throw new RuntimeException("can't go to left. current: (" + x
+ ", " + y + ")");
}
return createNextEnemy(b, x - 1, y);
}
protected final Enemy goE(Board b) {
final int x = x();
final int y = y();
if (!b.canGoE(x, y)) {
throw new RuntimeException("can't go to right. current: (" + x
+ ", " + y + ")");
}
return createNextEnemy(b, x + 1, y);
}
protected final Enemy goN(Board b) {
final int x = x();
final int y = y();
if (!b.canGoN(x, y)) {
throw new RuntimeException("can't go to up. current: (" + x + ", "
+ y + ")");
}
return createNextEnemy(b, x, y - 1);
}
protected final Enemy goS(Board b) {
final int x = x();
final int y = y();
if (!b.canGoS(x, y)) {
throw new RuntimeException("can't go to down. current: (" + x
+ ", " + y + ")");
}
return createNextEnemy(b, x, y + 1);
}
@Override
public String toString() {
return "" + getName() + " at (" + x() + ", " + y() + ") to "
+ Direction.getDirection(x(), y(), prevX(), prevY());
}
}
final class EnemyV extends Enemy {
public EnemyV(int x, int y) {
super(x, y);
}
EnemyV(int x, int y, Enemy prev) {
super(x, y, prev);
}
@Override
public char getName() {
return Board.ENEMY_V;
}
@Override
protected Enemy getNextAtIntersection(Board b, int myX, int myY) {
final int x = x();
final int y = y();
final int dx = myX - x();
final int dy = myY - y();
if (dy != 0) {
if (0 < dy && b.canGoS(x, y)) {
return goS(b);
} else if (dy < 0 && b.canGoN(x, y)) {
return goN(b);
}
}
if (dx != 0) {
if (0 < dx && b.canGoE(x, y)) {
return goE(b);
} else if (dx < 0 && b.canGoW(x, y)) {
return goW(b);
}
}
// 上記の条件に当てはまらなければ、最初と同じ移動
return firstMove(b);
}
@Override
protected EnemyV createNextEnemy(Board b, int nextX, int nextY) {
return new EnemyV(nextX, nextY, this);
}
@Override
protected boolean isIntelligent() {
return true;
}
}
final class EnemyH extends Enemy {
public EnemyH(int x, int y) {
super(x, y);
}
EnemyH(int x, int y, Enemy prev) {
super(x, y, prev);
}
@Override
public char getName() {
return Board.ENEMY_H;
}
@Override
protected Enemy getNextAtIntersection(Board b, int myX, int myY) {
final int x = x();
final int y = y();
final int dx = myX - x();
final int dy = myY - y();
if (dx != 0) {
if (0 < dx && b.canGoE(x, y)) {
return goE(b);
} else if (dx < 0 && b.canGoW(x, y)) {
return goW(b);
}
}
if (dy != 0) {
if (0 < dy && b.canGoS(x, y)) {
return goS(b);
} else if (dy < 0 && b.canGoN(x, y)) {
return goN(b);
}
}
// 上記の条件に当てはまらなければ、最初と同じ移動
return firstMove(b);
}
@Override
protected EnemyH createNextEnemy(Board b, int nextX, int nextY) {
return new EnemyH(nextX, nextY, this);
}
@Override
protected boolean isIntelligent() {
return true;
}
}
final class EnemyL extends Enemy {
public EnemyL(int x, int y) {
super(x, y);
}
EnemyL(int x, int y, Enemy prev) {
super(x, y, prev);
}
@Override
public char getName() {
return Board.ENEMY_L;
}
@Override
protected Enemy getNextAtIntersection(Board b, int myX, int myY) {
return getNextAtIntersection(b, this);
}
static Enemy getNextAtIntersection(Board b, Enemy prev) {
final int x = prev.x();
final int y = prev.y();
final int prevX = prev.prevX();
final int prevY = prev.prevY();
if (Board.canTurnToLeft(b, x, y, prevX, prevY)) {
return prev.createNextEnemy(b,
Board.turnToLeftX(x, y, prevX, prevY),
Board.turnToLeftY(x, y, prevX, prevY));
} else if (Board.canGoAhead(b, x, y, prevX, prevY)) {
return prev.createNextEnemy(b, Board.goAheadX(x, y, prevX, prevY),
Board.goAheadY(x, y, prevX, prevY));
} else {
assert Board.canTurnToRight(b, x, y, prevX, prevY);
return prev.createNextEnemy(b,
Board.turnToRightX(x, y, prevX, prevY),
Board.turnToRightY(x, y, prevX, prevY));
}
}
@Override
protected EnemyL createNextEnemy(Board b, int nextX, int nextY) {
return new EnemyL(nextX, nextY, this);
}
@Override
protected boolean isIntelligent() {
return false;
}
}
final class EnemyR extends Enemy {
public EnemyR(int x, int y) {
super(x, y);
}
private EnemyR(int x, int y, Enemy prev) {
super(x, y, prev);
}
@Override
public char getName() {
return Board.ENEMY_R;
}
@Override
protected Enemy getNextAtIntersection(Board b, int myX, int myY) {
return getNextAtIntersection(b, this);
}
static Enemy getNextAtIntersection(Board b, Enemy prev) {
final int x = prev.x();
final int y = prev.y();
final int prevX = prev.prevX();
final int prevY = prev.prevY();
if (Board.canTurnToRight(b, x, y, prevX, prevY)) {
return prev.createNextEnemy(b,
Board.turnToRightX(x, y, prevX, prevY),
Board.turnToRightY(x, y, prevX, prevY));
} else if (Board.canGoAhead(b, x, y, prevX, prevY)) {
return prev.createNextEnemy(b, Board.goAheadX(x, y, prevX, prevY),
Board.goAheadY(x, y, prevX, prevY));
} else {
assert Board.canTurnToLeft(b, x, y, prevX, prevY);
return prev.createNextEnemy(b,
Board.turnToLeftX(x, y, prevX, prevY),
Board.turnToLeftY(x, y, prevX, prevY));
}
}
@Override
protected EnemyR createNextEnemy(Board b, int nextX, int nextY) {
return new EnemyR(nextX, nextY, this);
}
@Override
protected boolean isIntelligent() {
return false;
}
}
class EnemyJ extends Enemy {
private final boolean actAsL_;
public EnemyJ(int x, int y) {
super(x, y);
actAsL_ = false; // 最初の交差点進入でL なので、最初は R にしておく
}
EnemyJ(int x, int y, EnemyJ prev, Board b) {
super(x, y, prev);
// 交差点に入ったら LR の入れ替え
actAsL_ = b.isIntersection(x, y) ? !prev.actAsL() : prev.actAsL();
}
@Override
public final char getName() {
return Board.ENEMY_J;
}
private boolean actAsL() {
return actAsL_;
}
@Override
protected Enemy getNextAtIntersection(Board b, int myX, int myY) {
if (actAsL_) {
return EnemyL.getNextAtIntersection(b, this);
} else {
return EnemyR.getNextAtIntersection(b, this);
}
}
@Override
protected EnemyJ createNextEnemy(Board b, int nextX, int nextY) {
return new EnemyJ(nextX, nextY, this, b);
}
@Override
protected boolean isIntelligent() {
return false;
}
@Override
public String toString() {
return super.toString() + " act as "
+ (actAsL_ ? Board.ENEMY_L : Board.ENEMY_R);
}
}
class BoardState {
private final int pacmanX_;
private final int pacmanY_;
private final Collection<Point> dots_;
private final ImmutableList<Enemy> intelligentEnemies_;
private final int time_;
private final char[] history_;
private final boolean backUsedOnThisWalkWay_;
private final boolean stayUsedOnThisWalkWay_;
public BoardState(Board board) {
pacmanX_ = board.getInitialPacmanX();
pacmanY_ = board.getInitialPacmanY();
dots_ = board.getInitialDots();
intelligentEnemies_ = board.getInitialIntelligentEnemies();
time_ = 0;
history_ = new char[0];
stayUsedOnThisWalkWay_ = false;
backUsedOnThisWalkWay_ = false;
}
public BoardState(int pacmanX, int pacmanY, Collection<Point> dots,
ImmutableList<Enemy> intelligentEnemies, BoardState prevState,
boolean backUsedOnThisWalkWay, boolean stayUsedOnThisWalkWay) {
pacmanX_ = pacmanX;
pacmanY_ = pacmanY;
dots_ = dots;
intelligentEnemies_ = intelligentEnemies;
time_ = prevState.getTime() + 1;
final char[] prevHistory = prevState.getHistory();
history_ = new char[prevHistory.length + 1];
System.arraycopy(prevHistory, 0, history_, 0, prevHistory.length);
history_[prevHistory.length] =
Direction.getDirection(pacmanX, pacmanY,
prevState.getPacmanX(), prevState.getPacmanY()).literal;
backUsedOnThisWalkWay_ = backUsedOnThisWalkWay;
stayUsedOnThisWalkWay_ = stayUsedOnThisWalkWay;
}
public final int getPacmanX() {
return pacmanX_;
}
public final int getPacmanY() {
return pacmanY_;
}
public final Collection<Point> getDots() {
return dots_;
}
public final int getEatenDotCount(Board b) {
return b.getInitialDots().size() - getDots().size();
}
public final ImmutableList<Enemy> getIntelligentEnemies() {
return intelligentEnemies_;
}
public final int getTime() {
return time_;
}
public final int getScore(Board b) {
return b.getScore(getDots(), getTime());
}
public final char[] getHistory() {
return history_;
}
public final boolean backUsedOnThisWalkWay() {
return backUsedOnThisWalkWay_;
}
public final boolean stayUsedOnThisWalkWay() {
return stayUsedOnThisWalkWay_;
}
public boolean isAlive() {
return true;
}
public final boolean isCleared() {
return isAlive() && dots_.isEmpty();
}
public final BoardState move(Board board, Direction direction,
ImmutableList<Enemy> nextIntelligentEnemies, boolean isBack) {
final int x = getPacmanX() + direction.dx;
final int y = getPacmanY() + direction.dy;
if (board.getTimeLimit() <= getTime()
|| !Board.isSafe(Iterables.concat(
board.getNonIntelligentEnemies(getTime()),
nextIntelligentEnemies), x, y, getPacmanX(),
getPacmanY())) {
return new GameOverBoardState(x, y, getDots(),
nextIntelligentEnemies, this);
}
final Collection<Point> currentDots = Lists.newArrayList(getDots());
currentDots.remove(new Point(x, y));
final BoardState newState =
new BoardState(
x,
y,
// 変更がなければドットのリストを共有する
(getDots().size() == currentDots.size()) ? getDots()
: currentDots,
nextIntelligentEnemies,
this,
board.isWalkWay(x, y)
&& board.isWalkWay(getPacmanX(), getPacmanY())
&& (isBack || backUsedOnThisWalkWay()),
board.isWalkWay(x, y)
&& board.isWalkWay(getPacmanX(), getPacmanY())
&& (direction == STAY || stayUsedOnThisWalkWay()));
return newState;
}
public static BoardState batchMove(BoardState state, Board board,
char[] route) {
if (route == null) {
return state;
}
for (char commandChar : route) {
final Direction nextCommand = Direction.fromLiteral(commandChar);
final int prevTime = state.getTime();
state = doCommand(state, board, nextCommand);
if (state.getTime() == prevTime) {
// 進まなかったということはエラーなので、できたところまでを返す。
return state;
}
if (!state.isAlive()) {
System.out.println("");
System.out.println("GameOver!");
return state;
}
if (state.isCleared()) {
System.out.println("");
System.out.println("Cleared!");
return state;
}
}
return state;
}
private static BoardState doCommand(BoardState state, Board board,
Direction nextCommand) {
if (!board.canGo(state.getPacmanX(), state.getPacmanY(), nextCommand)) {
System.out.println("can't move to " + nextCommand);
return state;
}
final ImmutableList<Enemy> nextIntelligentEnemies =
Board.updateEnemies(board, state.getIntelligentEnemies(),
state.getPacmanX(), state.getPacmanY());
state =
state.move(board, nextCommand, nextIntelligentEnemies, false/*厳密には違うが*/);
Board.printBoard(board, state, true);
return state;
}
}
/**
* GameOver を表す特別な {@link BoardState}。
*
* {@link BoardState} は大量にインスタンスが作られる可能性があるため、フラグを持たせると
* メモリが無駄に消費される。GameOver なインスタンスは殆ど作られないため、サブクラスとして
* 表現してみた。
*/
final class GameOverBoardState extends BoardState {
public GameOverBoardState(int pacmanX, int pacmanY, Collection<Point> dots,
ImmutableList<Enemy> intelligentEnemies, BoardState prevState) {
super(pacmanX, pacmanY, dots, intelligentEnemies, prevState, true, true);
}
@Override
public boolean isAlive() {
return false;
}
}
PacManBfsSolverMain.java
/*
* PacMan を幅優先探索で解くプログラム。状態数が多くなるので、せいぜい Lv1 程度が限度。
*
* (C) YAMAZAKI Makoto <makoto1975@gmail.com> 2010.
*
* 戻りを制限しないとメモリはたくさん必要。 main メソッド中の backOnWalkWayTimeLimit を
* Integer.MAX_VALE にすると無制限になるが、その場合は -Xmx4096m とかでないと解が求まらない。
* とりあえず制限時間の 20% にしているが、根拠なし。 Lv1 の問題であれば、 t=6 以降は戻り不要。
*
* 単純に全ての動きを探索するとさすがに状態が多すぎるので、戻る操作は通路内で2回以上行えないように
* 制限している。
* その場にとどまる操作を使用するかどうかを選択できるようにしているが、使用する場合であっても2回続けて
* 使用するパターンは探索から除外している。
*
* 依存ライブラリとして Google Collections を使用している。
*
* $Id: PacManBfsSolverMain.java 134 2010-08-22 10:35:46Z zaki $
*/
package org.zakky.gdd2010.pacman;
import static org.zakky.gdd2010.pacman.Board.Direction.STAY;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.List;
import org.zakky.gdd2010.pacman.Board.Direction;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Lists;
final class BFSPacManSolver {
private final Board board_;
private final char[] staticRoute_;
private final Deque<BoardState> queue_ = Lists.newLinkedList();
private final int backOnWalkWayTimeLimit_;
public BFSPacManSolver(Board board, int backOnWalkWayTimeLimit,
char[] staticRoute) {
assert board != null;
board_ = board;
backOnWalkWayTimeLimit_ = backOnWalkWayTimeLimit;
staticRoute_ = staticRoute;
}
public BoardState solve() throws Exception {
final BoardState initialState = new BoardState(board_);
// まずは最初の状態をベストとしておく。
BoardState bestState =
BoardState.batchMove(initialState, board_, staticRoute_);
int bestScore = bestState.getScore(board_);
// 最初は新しい時刻と判定されるように -1 しておく。
int prevTime = bestState.getTime() - 1;
enqueue(bestState);
while (hasMoreState()) {
final BoardState state = dequeue();
if (state.getTime() != prevTime) {
// 新しい時刻に入った
prevTime = state.getTime();
System.out.println("searching " + state.getTime()
+ " step path. state count in queue is "
+ (queue_.size() + 1));
}
// 直前の PacMan の位置
final int prevX = state.getPacmanX();
final int prevY = state.getPacmanY();
final ImmutableList<Enemy> nextIntelligentEnemies =
Board.updateEnemies(board_, state.getIntelligentEnemies(),
prevX, prevY);
// 次の行動の候補を列挙し、GameOver にならなければキューに入れる
final char[] history = state.getHistory();
final Direction backward =
history.length == 0 ? null
: Direction.fromLiteral(
state.getHistory()[state.getHistory().length - 1]).opposite();
final List<Direction> candidates = Lists.newArrayList();
for (Direction dir : Direction.values()) {
if (dir == STAY) {
if (!board_.useStay()) {
continue;
}
if (backward == STAY) {
// 前回の移動も STAY だったら候補から除外
// TODO 連続 STAY は除外しているが、本当にこれで最適解といえるか証明する
continue;
}
if (state.stayUsedOnThisWalkWay()) {
continue;
}
candidates.add(dir);
continue;
}
if (!board_.canGo(prevX, prevY, dir)) {
continue;
}
if (board_.isWalkWay(prevX, prevY) && dir == backward) {
if (state.backUsedOnThisWalkWay()
|| backOnWalkWayTimeLimit_ < state.getTime()) {
// FIXME 戻らないとGameOver の場合はもどるようにする
continue;
}
}
candidates.add(dir);
}
for (Direction to : candidates) {
final BoardState newState =
state.move(board_, to, nextIntelligentEnemies,
backward != STAY && backward == to);
if (newState.isAlive()) {
final int score = newState.getScore(board_);
if (bestScore < score) {
bestState = newState;
bestScore = score;
// 記録更新
Board.printBoard(board_, newState);
if (newState.getDots().isEmpty()) {
return bestState;
}
}
enqueue(newState);
}
}
}
return bestState;
}
private void enqueue(BoardState state) {
queue_.offer(state);
}
private boolean hasMoreState() {
return !queue_.isEmpty();
}
private BoardState dequeue() {
return queue_.remove();
}
}
public class PacManBfsSolverMain {
public static void main(String[] args) throws Exception {
final boolean useStay = true;
final Board board =
Board.buildBoard(new BufferedReader(new InputStreamReader(
System.in, "UTF-8")), useStay);
final String mapName =
Board.KNOWN_MAPS.get(Integer.valueOf(board.hashCode()));
if (mapName != null) {
System.out.println("mapname: " + mapName);
}
System.out.println("timelimit: " + board.getTimeLimit());
System.out.println("width: " + board.getWidth());
System.out.println("height: " + board.getHeight());
Board.printInitialBoard(board);
final int backOnWalkWayTimeLimit = Integer.MAX_VALUE; /* Lv1 なら戻る制限なしでも解ける */
final BoardState answer =
new BFSPacManSolver(
board,
backOnWalkWayTimeLimit,
null).solve();
System.out.println("");
if (answer.isCleared()) {
System.out.println("Game Cleared (score=" + answer.getScore(board)
+ ").");
} else {
System.out.println("Gema Over(score=" + answer.getScore(board)
+ ").");
}
System.out.println(answer.getEatenDotCount(board) + " dots eaten in "
+ answer.getTime() + " steps.");
System.out.println(answer.getHistory());
}
}
PacManDfsSolverMain.java
/*
* PacMan を深さ優先で探索するための Main クラス。
*
* (C) YAMAZAKI Makoto <makoto1975@gmail.com> 2010.
*
* 依存ライブラリとして Google Collections を使用している。
*
* Lv2
* 以下のところまでこのプログラムで求め、Lv1 で使用した幅優先探索プログラムで残りを解いた。
* kkkllljjjhhhkkkllkkkllljjjh.lljjjlllllhhkkklllllkkkllljjj.hhjjjhhhkkk.ll.
* kkkhkklljjhhhhhhhh.ljjjhhjk.hkkklkkhhhhjjhhkklllkkklhhkkkllljjjlllkkkllll
* lhhjjjhhjjjhllllkkkllkkkllljjjhhjjjlljjjjjhhhhhhhhhhhjjjhhhkkkllllllllkkk
* kkhhhhhhhjkllkkkhkkklhhhhjjj
*
* $Id: PacManDfsSolverMain.java 132 2010-08-22 10:05:51Z zaki $
*/
package org.zakky.gdd2010.pacman;
import static org.zakky.gdd2010.pacman.Board.Direction.STAY;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import org.zakky.gdd2010.pacman.Board.Direction;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
final class DFSPacManSolver {
private final boolean debug_;
private final Board board_;
private final char[] staticRoute_;
private final int backOnWalkWayTimeLimit_;
private int cutOffTime_;
private BoardState bestState_;
private int bestScore_;
private int callCountOffindBest_ = 0;
public DFSPacManSolver(Board board, int backOnWalkWayTimeLimit,
char[] staticRoute, int cutOffTime, boolean debug) {
assert board != null;
board_ = board;
backOnWalkWayTimeLimit_ = backOnWalkWayTimeLimit;
cutOffTime_ = Math.min(cutOffTime, board.getTimeLimit());
staticRoute_ = staticRoute;
debug_ = debug;
}
public BoardState solve() throws Exception {
final BoardState initialState = new BoardState(board_);
// まずは最初の状態をベストとしておく。
bestState_ = BoardState.batchMove(initialState, board_, staticRoute_);
bestScore_ = bestState_.getScore(board_);
return findBest(bestState_);
}
private BoardState findBest(BoardState state) {
callCountOffindBest_++;
if ((callCountOffindBest_ & 0xfffff) == 0) {
System.out.print(callCountOffindBest_);
System.out.print(": ");
System.out.println(state.getHistory());
if ((callCountOffindBest_ & 0xffffff) == 0) {
Board.printBoard(board_, bestState_);
System.out.println("current best");
System.out.print("current cut-off time: ");
System.out.println(cutOffTime_);
}
}
if (debug_) {
Board.printBoard(board_, state);
}
if (state.isCleared() || !state.isAlive()) {
return state;
}
if (cutOffTime_ - state.getDots().size()
+ getShortestTimeToNearestDot(state) < state.getTime()) {
return new GameOverBoardState(state.getPacmanX(),
state.getPacmanY(), state.getDots(),
state.getIntelligentEnemies(), state);
}
final char[] history = state.getHistory();
final Direction last =
history.length == 0 ? null
: Direction.fromLiteral(state.getHistory()[state.getHistory().length - 1]);
final Direction forward =
(last != STAY) ? last
: history.length == 0 ? null
: Direction.fromLiteral(state.getHistory()[state.getHistory().length - 2]);
final Direction backward = forward == null ? null : forward.opposite();
LinkedList<Direction> candidates = Lists.newLinkedList();
for (Direction dir : allDirsBySearchOrder(forward)) {
if (dir == Direction.STAY) {
if (!board_.useStay()) {
continue;
}
if (last == STAY) {
// 前回の移動も STAY だったら候補から除外
// TODO 連続 STAY は除外しているが、本当にこれで最適解といえるか証明する
continue;
}
if (state.stayUsedOnThisWalkWay()) {
continue;
}
}
if (!board_.canGo(state.getPacmanX(), state.getPacmanY(), dir)) {
continue;
}
if (board_.isWalkWay(state.getPacmanX(), state.getPacmanY())
&& dir == backward) {
if (state.backUsedOnThisWalkWay()
|| backOnWalkWayTimeLimit_ < state.getTime()) {
// FIXME 戻らないとGameOver の場合はもどるようにする
continue;
}
}
candidates.add(dir);
}
final int pacmanX = state.getPacmanX();
final int pacmanY = state.getPacmanY();
final ImmutableList<Enemy> nextIntelligentEnemies =
Board.updateEnemies(board_, state.getIntelligentEnemies(),
pacmanX, pacmanY);
// 敵との当りがない場合は STAY を探索候補から除外する
{
boolean stayIncluded = false;
boolean unsafeCandidatesIncluded = false;
final Iterable<Enemy> nextEnemies =
Iterables.concat(nextIntelligentEnemies,
board_.getNonIntelligentEnemies(state.getTime()));
for (final Direction d : candidates) {
if (d == STAY) {
stayIncluded = true;
continue;
}
if (!Board.isSafe(nextEnemies, pacmanX + d.dx, pacmanY + d.dy,
pacmanX, pacmanY)) {
unsafeCandidatesIncluded = true;
break;
}
}
if (stayIncluded && !unsafeCandidatesIncluded) {
candidates.remove(STAY);
}
}
candidates = reorderByPriority(candidates, state);
BoardState currentBestState = state;
int currentBestScore = currentBestState.getScore(board_);
if (debug_) {
System.out.println("candidates: " + candidates);
System.out.println("Press any Key to continue.");
try {
System.in.read();
} catch (IOException e) {
// assert true;
}
}
for (Direction candidate : candidates) {
final BoardState nextState =
state.move(board_, candidate, nextIntelligentEnemies, false/*とりあえず*/);
final BoardState result = findBest(nextState);
final int score = result.getScore(board_);
if (currentBestScore < score) {
currentBestState = result;
currentBestScore = score;
if (bestScore_ < score) {
bestState_ = result;
bestScore_ = score;
Board.printBoard(board_, state);
System.out.println("new record!");
if (bestState_.isCleared()) {
cutOffTime_ = bestState_.getTime();
}
System.out.print("current cut-off time: ");
System.out.println(cutOffTime_);
}
}
}
return currentBestState;
}
private int getShortestTimeToNearestDot(BoardState state) {
final int pacmanX = state.getPacmanX();
final int pacmanY = state.getPacmanY();
final Collection<Point> dots = state.getDots();
if (dots.isEmpty()) {
return 0;
}
int shortestTime = Integer.MAX_VALUE;
for (Point dot : dots) {
// とりあえず壁は無視する
final int requiredTime =
Math.abs(dot.x - pacmanX) + Math.abs(dot.y - pacmanY);
if (requiredTime < shortestTime) {
shortestTime = requiredTime;
}
}
return shortestTime;
}
private static final ImmutableList<Direction> VALUES_FOR_UNKNOWN =
ImmutableList.of(Direction.STAY, Direction.UP, Direction.RIGHT,
Direction.LEFT, Direction.DOWN);
private static final ImmutableList<Direction> VALUES_FOR_UP =
ImmutableList.of(Direction.STAY, Direction.RIGHT, Direction.UP,
Direction.LEFT, Direction.DOWN);
private static final ImmutableList<Direction> VALUES_FOR_RIGHT =
ImmutableList.of(Direction.STAY, Direction.DOWN, Direction.RIGHT,
Direction.UP, Direction.LEFT);
private static final ImmutableList<Direction> VALUES_FOR_DOWN =
ImmutableList.of(Direction.STAY, Direction.LEFT, Direction.DOWN,
Direction.RIGHT, Direction.UP);
private static final ImmutableList<Direction> VALUES_FOR_LEFT =
ImmutableList.of(Direction.STAY, Direction.UP, Direction.LEFT,
Direction.DOWN, Direction.RIGHT);
private ImmutableList<Direction> allDirsBySearchOrder(Direction heading) {
if (heading == null) {
return VALUES_FOR_UNKNOWN;
}
// 進行方向に対して STAY、右、正面、左、後ろの順
switch (heading) {
case UP:
return VALUES_FOR_UP;
case RIGHT:
return VALUES_FOR_RIGHT;
case DOWN:
return VALUES_FOR_DOWN;
case LEFT:
return VALUES_FOR_LEFT;
case STAY:
/* fall-through */
default:
throw new IllegalArgumentException("invalid head direction: "
+ heading);
}
}
private LinkedList<Direction> reorderByPriority(
LinkedList<Direction> candidates, BoardState state) {
List<Direction> noDot = null;
final ListIterator<Direction> it = candidates.listIterator();
while (it.hasNext()) {
final Direction candidate = it.next();
final int nextX = state.getPacmanX() + candidate.dx;
final int nextY = state.getPacmanY() + candidate.dy;
if (!board_.existsDot(nextX, nextY, state.getDots())) {
if (noDot == null) {
noDot = Lists.newArrayListWithCapacity(candidates.size());
}
it.remove();
noDot.add(candidate);
}
}
if (noDot != null) {
candidates.addAll(noDot);
}
// 探索の優先順を決定する
return candidates;
}
}
public class PacManDfsSolverMain {
private static final ImmutableMap<String, String> STATIC_ROUTES =
ImmutableMap.of("Lv1", "", "Lv2", "", "Lv3",
"hhkkhhlljjlllkklllkllllkkkkkkkklllllllljjjjjhhhllljjj");
private static final ImmutableMap<String, Integer> CUT_OFF_TIMES =
ImmutableMap.of("Lv1", Integer.valueOf(37), "Lv2",
Integer.valueOf(221), "Lv3", Integer.valueOf(451));
public static void main(String[] args) throws Exception {
final boolean useStay = false;
final boolean debug = false;
final BufferedReader input =
new BufferedReader(new InputStreamReader(System.in, "UTF-8"));
final Board board = Board.buildBoard(input, useStay);
final String mapName =
Board.KNOWN_MAPS.get(Integer.valueOf(board.hashCode()));
System.out.println("mapname: "
+ (mapName == null ? "unknown" : mapName));
Board.printInitialBoard(board, true);
final String staticRoute =
mapName == null ? null : STATIC_ROUTES.get(mapName);
final Integer cutOffTime =
mapName == null ? null : CUT_OFF_TIMES.get(mapName);
final BoardState answer =
new DFSPacManSolver(board, Integer.MAX_VALUE,
staticRoute == null ? null : staticRoute.toCharArray(),
cutOffTime == null ? Integer.MAX_VALUE
: cutOffTime.intValue(), debug).solve();
System.out.println("");
if (answer.isCleared()) {
System.out.println("Game Cleared (score=" + answer.getScore(board)
+ ").");
} else {
System.out.println("Gema Over(score=" + answer.getScore(board)
+ ").");
}
System.out.println(answer.getEatenDotCount(board) + " dots eaten in "
+ answer.getTime() + " steps.");
System.out.println(answer.getHistory());
}
}