1.1 --- a/icfp-model/src/main/java/ru/bosony/model/game/Game.java Mon Jul 16 15:46:08 2012 +0400
1.2 +++ b/icfp-model/src/main/java/ru/bosony/model/game/Game.java Mon Jul 16 18:59:13 2012 +0400
1.3 @@ -12,7 +12,9 @@
1.4 import static ru.bosony.model.cellscontents.CellContent.WadlersBeard;
1.5
1.6 import java.util.ArrayList;
1.7 +import java.util.HashMap;
1.8 import java.util.List;
1.9 +import java.util.Map;
1.10
1.11 import ru.bosony.model.cellscontents.CellContent;
1.12 import ru.bosony.model.mine.Cell;
1.13 @@ -32,6 +34,7 @@
1.14 protected int lastScoreChange = 0;
1.15 protected GameState state = GameState.Game;
1.16 protected int lambdaCollectedCount = 0;
1.17 + protected List<Mine> history = new ArrayList<Mine>();
1.18 protected List<Movement> route = new ArrayList<Movement>();
1.19 protected int underwater = 0;
1.20
1.21 @@ -69,6 +72,11 @@
1.22
1.23 // Moving and scoring
1.24 route.add(mov);
1.25 + try {
1.26 + history.add(mine.clone());
1.27 + } catch (CloneNotSupportedException e) {
1.28 + throw new RuntimeException(e);
1.29 + }
1.30 Cell robotCell = mine.getRobotCell();
1.31 Coordinate robotCoord = robotCell.getCoordinate();
1.32 Coordinate nextRobotCoord = null;
1.33 @@ -349,4 +357,18 @@
1.34 public int getUnderwater() {
1.35 return underwater;
1.36 }
1.37 +
1.38 + public boolean hasViciousCircle() {
1.39 + if (route.size() != history.size())
1.40 + throw new RuntimeException("Desynchronized history");
1.41 + Map<Mine, Movement> state = new HashMap<Mine, Movement>();
1.42 + for (int i = route.size() - 1; i >= 0; i--) {
1.43 + Mine mine = history.get(i);
1.44 + Movement mov = route.get(i);
1.45 + if (state.get(mine) == mov)
1.46 + return true;
1.47 + state.put(mine, mov);
1.48 + }
1.49 + return false;
1.50 + }
1.51 }
2.1 --- a/icfp-model/src/main/java/ru/bosony/model/moving/Movement.java Mon Jul 16 15:46:08 2012 +0400
2.2 +++ b/icfp-model/src/main/java/ru/bosony/model/moving/Movement.java Mon Jul 16 18:59:13 2012 +0400
2.3 @@ -10,12 +10,12 @@
2.4 public enum Movement implements TextRepresentable {
2.5
2.6 LEFT("L"),
2.7 + UP("U"),
2.8 RIGHT("R"),
2.9 - UP("U"),
2.10 DOWN("D"),
2.11 WAIT("W"),
2.12 - ABORT("A"),
2.13 - RAZOR("S");
2.14 + RAZOR("S"),
2.15 + ABORT("A");
2.16
2.17 private String text;
2.18
3.1 --- a/icfp-solver/src/main/java/ru/bosony/solvers/DijkstraSolver.java Mon Jul 16 15:46:08 2012 +0400
3.2 +++ b/icfp-solver/src/main/java/ru/bosony/solvers/DijkstraSolver.java Mon Jul 16 18:59:13 2012 +0400
3.3 @@ -14,7 +14,6 @@
3.4 import ru.bosony.model.game.GameState;
3.5 import ru.bosony.model.mine.Cell;
3.6 import ru.bosony.model.mine.Mine;
3.7 -import ru.bosony.model.moving.Coordinate;
3.8 import ru.bosony.model.moving.Movement;
3.9 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
3.10 import edu.uci.ics.jung.graph.DirectedSparseGraph;
3.11 @@ -27,7 +26,8 @@
3.12 */
3.13 public class DijkstraSolver extends AbstractSolver {
3.14
3.15 - protected Map<Mine, Set<Cell>> testedTargetCells = new HashMap<Mine, Set<Cell>>();
3.16 + protected Map<String, Set<Movement>> loseMovs = new HashMap<String, Set<Movement>>();
3.17 + protected Set<CellsLink> loseLinks = new HashSet<CellsLink>();
3.18
3.19 public DijkstraSolver(Mine mine, SolverListener listener) {
3.20 super(mine, listener);
3.21 @@ -45,26 +45,14 @@
3.22 Game game = new Game(testMine);
3.23
3.24 while (game.getState() == GameState.Game) {
3.25 - if (!testedTargetCells.containsKey(testMine)) {
3.26 - testedTargetCells.put(testMine, new HashSet<Cell>());
3.27 + String map = testMine.toText();
3.28 + if (!loseMovs.containsKey(map)) {
3.29 + loseMovs.put(map, new HashSet<Movement>());
3.30 }
3.31 Set<Cell> targets = testMine.findCells(CellContent.Lambda);
3.32 targets.addAll(testMine.findCells(CellContent.HighOrderRock));
3.33 if (targets.size() == 0)
3.34 targets = testMine.findCells(CellContent.OpenLambdaLift);
3.35 - if (targets.size() == 0 || testedTargetCells.get(testMine).containsAll(targets)) {
3.36 - // No targets. Walking around
3.37 - Cell robotCell = testMine.getRobotCell();
3.38 - for (Coordinate nextCoordinate : robotCell.getCoordinate().getAdjacentCoordinates()) {
3.39 - Cell nextCell = testMine.getCell(nextCoordinate);
3.40 - targets.add(nextCell);
3.41 - }
3.42 - if (testedTargetCells.get(testMine).containsAll(targets)) {
3.43 - // Fail. All cases are tried.
3.44 - game.move(Movement.ABORT);
3.45 - break;
3.46 - }
3.47 - }
3.48 Graph<Cell, CellsLink> graph = getDirectedGraph(testMine);
3.49 DijkstraShortestPath<Cell, CellsLink> alg = new DijkstraShortestPath<Cell, CellsLink>(graph,
3.50 new CellsLinkTransformer<CellsLink, Double>());
3.51 @@ -81,24 +69,44 @@
3.52 dist = alg.getDistance(testMine.getRobotCell(), target);
3.53 } catch (IllegalArgumentException e) {
3.54 // hmmm...
3.55 - testedTargetCells.get(testMine).add(target);
3.56 continue;
3.57 }
3.58 - if (dist != null && route != null && dist.doubleValue() < shortestDist
3.59 - && !testedTargetCells.get(testMine).contains(target)) {
3.60 - shortestDist = dist.doubleValue();
3.61 - nextTarget = target;
3.62 - routeToNextTarget = route;
3.63 - testedTargetCells.get(testMine).add(target);
3.64 + if (dist != null && route != null && route.size() > 0 && dist.doubleValue() < shortestDist) {
3.65 + CellsLink firstLink = route.get(0);
3.66 + Movement mov = firstLink.getSource().getCoordinate()
3.67 + .getNecessaryMovement(firstLink.getTarget().getCoordinate());
3.68 + if (!loseMovs.get(map).contains(mov)) {
3.69 + shortestDist = dist.doubleValue();
3.70 + nextTarget = target;
3.71 + routeToNextTarget = route;
3.72 + break;
3.73 + }
3.74 }
3.75 }
3.76 if (nextTarget != null) {
3.77 for (CellsLink link : routeToNextTarget) {
3.78 - Movement mov = link.getSource().getCoordinate()
3.79 - .getNecessaryMovement(link.getTarget().getCoordinate());
3.80 - game.move(mov);
3.81 + Cell source = link.getSource();
3.82 + Cell target = link.getTarget();
3.83 + if (isSafeMovement(testMine, source, target)) {
3.84 + Movement mov = source.getCoordinate().getNecessaryMovement(target.getCoordinate());
3.85 + GameState state = game.move(mov);
3.86 + if (state == GameState.Lose || state == GameState.Abort || game.hasViciousCircle()) {
3.87 + loseMovs.get(map).add(mov);
3.88 + loseLinks.add(link);
3.89 + }
3.90 + }
3.91 break;
3.92 }
3.93 + } else {
3.94 + for (Movement mov : Movement.values()) {
3.95 + if (!loseMovs.get(map).contains(mov)) {
3.96 + GameState state = game.move(mov);
3.97 + if (state == GameState.Lose || state == GameState.Abort || map.equals(testMine.toText())
3.98 + || game.hasViciousCircle())
3.99 + loseMovs.get(map).add(mov);
3.100 + break;
3.101 + }
3.102 + }
3.103 }
3.104 }
3.105 if (game.getState() == GameState.Win) {
3.106 @@ -108,6 +116,28 @@
3.107 }
3.108 }
3.109
3.110 + protected boolean isSafeMovement(Mine mine, Cell source, Cell target) {
3.111 + if (source == null || target == null)
3.112 + return false;
3.113 + if (source.getContent().getTrampolineTarget() == target.getContent())
3.114 + return true;
3.115 + Cell upCell = mine.getCell(target.getCoordinate().up());
3.116 + if (upCell == null)
3.117 + return true;
3.118 + Cell upUpCell = mine.getCell(target.getCoordinate().up().up());
3.119 + Cell upUpLeftCell = mine.getCell(target.getCoordinate().up().up().left());
3.120 + Cell upUpRightCell = mine.getCell(target.getCoordinate().up().up().right());
3.121 + if (upCell.getContent() == CellContent.Empty
3.122 + && (upUpCell != null
3.123 + && (upUpCell.getContent() == CellContent.Rock || upUpCell.getContent() == CellContent.HighOrderRock)
3.124 + || upUpLeftCell != null
3.125 + && (upUpLeftCell.getContent() == CellContent.Rock || upUpLeftCell.getContent() == CellContent.HighOrderRock) || upUpRightCell != null
3.126 + && (upUpRightCell.getContent() == CellContent.Rock || upUpRightCell.getContent() == CellContent.HighOrderRock))) {
3.127 + return false;
3.128 + }
3.129 + return true;
3.130 + }
3.131 +
3.132 protected Graph<Cell, CellsLink> getDirectedGraph(Mine mine) {
3.133 Graph<Cell, CellsLink> graph = new DirectedSparseGraph<Cell, CellsLink>();
3.134 for (CellsLink link : getCellLinks(mine)) {
3.135 @@ -135,9 +165,13 @@
3.136 if (neighboringContent == CellContent.Earth || neighboringContent == CellContent.Empty
3.137 || neighboringContent == CellContent.HuttonsRazor || neighboringContent == CellContent.Lambda
3.138 || neighboringContent == CellContent.OpenLambdaLift) {
3.139 - CellsLink link = new CellsLink(mine, cell, neighboringCell);
3.140 - links.add(link);
3.141 - findAllCellLinks(mine, neighboringCell, links, processedCells);
3.142 + if (isSafeMovement(mine, cell, neighboringCell)) {
3.143 + CellsLink link = new CellsLink(mine, cell, neighboringCell);
3.144 + if (!loseLinks.contains(link)) {
3.145 + links.add(link);
3.146 + findAllCellLinks(mine, neighboringCell, links, processedCells);
3.147 + }
3.148 + }
3.149 } else if (!CellContent.getTargets().contains(cell.getContent())
3.150 && CellContent.getTargets().contains(neighboringContent)) {
3.151 findAllCellLinks(mine, neighboringCell, links, processedCells);
3.152 @@ -147,9 +181,13 @@
3.153 for (Cell target : mine.findCells(cell.getContent().getTrampolineTarget())) {
3.154 if (target == null)
3.155 continue;
3.156 - CellsLink link = new CellsLink(mine, cell, target);
3.157 - links.add(link);
3.158 - findAllCellLinks(mine, target, links, processedCells);
3.159 + if (isSafeMovement(mine, cell, target)) {
3.160 + CellsLink link = new CellsLink(mine, cell, target);
3.161 + if (!loseLinks.contains(link)) {
3.162 + links.add(link);
3.163 + findAllCellLinks(mine, target, links, processedCells);
3.164 + }
3.165 + }
3.166 }
3.167 }
3.168 }