1.1 --- a/icfp-model/src/main/java/ru/bosony/model/mine/Mine.java Tue Jul 17 21:38:39 2012 +0400
1.2 +++ b/icfp-model/src/main/java/ru/bosony/model/mine/Mine.java Wed Jul 18 01:25:43 2012 +0400
1.3 @@ -8,6 +8,7 @@
1.4 import static ru.bosony.model.cellscontents.CellContent.OpenLambdaLift;
1.5 import static ru.bosony.model.cellscontents.CellContent.Rock;
1.6
1.7 +import java.util.Collection;
1.8 import java.util.HashSet;
1.9 import java.util.Set;
1.10 import java.util.regex.Matcher;
1.11 @@ -78,6 +79,10 @@
1.12 return text;
1.13 }
1.14
1.15 + public String toTextWithoutRobot() {
1.16 + return toText().replaceAll(CellContent.MiningRobot.toText(), CellContent.Empty.toText());
1.17 + }
1.18 +
1.19 protected void fromText(String str) {
1.20 Matcher matcher = minePattern.matcher(str);
1.21 if (!matcher.matches())
1.22 @@ -178,6 +183,18 @@
1.23 return cells[x - 1][sizeY - y];
1.24 }
1.25
1.26 + public Set<Cell> getCells(Collection<Coordinate> coordinates) {
1.27 + Set<Cell> cells = new HashSet<Cell>();
1.28 + if (coordinates == null)
1.29 + return cells;
1.30 + for (Coordinate coordinate : coordinates) {
1.31 + Cell cell = getCell(coordinate);
1.32 + if (cell != null)
1.33 + cells.add(cell);
1.34 + }
1.35 + return cells;
1.36 + }
1.37 +
1.38 @Override
1.39 public String toString() {
1.40 return toText();
1.41 @@ -219,15 +236,21 @@
1.42
1.43 public Set<Cell> getNeighboringCells(Cell cell) {
1.44 Set<Cell> cells = new HashSet<Cell>();
1.45 - for (Coordinate coordinate : cell.getCoordinate().getNeighboringCoordinates())
1.46 - cells.add(getCell(coordinate));
1.47 + for (Coordinate coordinate : cell.getCoordinate().getNeighboringCoordinates()) {
1.48 + Cell nextCell = getCell(coordinate);
1.49 + if (nextCell != null)
1.50 + cells.add(nextCell);
1.51 + }
1.52 return cells;
1.53 }
1.54
1.55 public Set<Cell> getAdjacentCells(Cell cell) {
1.56 Set<Cell> cells = new HashSet<Cell>();
1.57 - for (Coordinate coordinate : cell.getCoordinate().getAdjacentCoordinates())
1.58 - cells.add(getCell(coordinate));
1.59 + for (Coordinate coordinate : cell.getCoordinate().getAdjacentCoordinates()) {
1.60 + Cell nextCell = getCell(coordinate);
1.61 + if (nextCell != null)
1.62 + cells.add(nextCell);
1.63 + }
1.64 return cells;
1.65 }
1.66
2.1 --- a/icfp-solver/src/main/java/ru/bosony/solvers/AbstractSolver.java Tue Jul 17 21:38:39 2012 +0400
2.2 +++ b/icfp-solver/src/main/java/ru/bosony/solvers/AbstractSolver.java Wed Jul 18 01:25:43 2012 +0400
2.3 @@ -1,7 +1,6 @@
2.4 package ru.bosony.solvers;
2.5
2.6 import java.text.DecimalFormat;
2.7 -import java.util.Date;
2.8 import java.util.HashSet;
2.9 import java.util.Set;
2.10
2.11 @@ -15,14 +14,14 @@
2.12 */
2.13 public abstract class AbstractSolver {
2.14
2.15 - protected Mine mine = null;
2.16 + protected Mine initialMine = null;
2.17 protected SolverListener listener = null;
2.18 protected Set<Game> games = new HashSet<Game>();
2.19 protected long attemptsCount = 0;
2.20 protected long startTime = System.currentTimeMillis();
2.21
2.22 public AbstractSolver(Mine mine, SolverListener listener) {
2.23 - this.mine = mine;
2.24 + this.initialMine = mine;
2.25 this.listener = listener;
2.26 }
2.27
2.28 @@ -34,8 +33,8 @@
2.29 listener.foundNextRoute(game.getStringRoute());
2.30 // TODO delete
2.31 System.out.println(new DecimalFormat("0.00").format((((System.currentTimeMillis() - startTime) / 1000d)))
2.32 - + " seconds, State = " + game.getState() + ", Score = " + game.getScore() + ", Route = "
2.33 - + game.getStringRoute());
2.34 + + " seconds, State = " + game.getState() + ", Score = " + game.getScore() + ", Route("
2.35 + + game.getRoute().size() + ") = " + game.getStringRoute());
2.36 }
2.37 games.add(game);
2.38 }
3.1 --- a/icfp-solver/src/main/java/ru/bosony/solvers/DijkstraSolver.java Tue Jul 17 21:38:39 2012 +0400
3.2 +++ b/icfp-solver/src/main/java/ru/bosony/solvers/DijkstraSolver.java Wed Jul 18 01:25:43 2012 +0400
3.3 @@ -14,6 +14,7 @@
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 @@ -26,8 +27,10 @@
3.12 */
3.13 public class DijkstraSolver extends AbstractSolver {
3.14
3.15 - protected Map<String, Set<Movement>> loseMovs = new HashMap<String, Set<Movement>>();
3.16 - protected Set<CellsLink> loseLinks = new HashSet<CellsLink>();
3.17 + protected Map<String, Set<Movement>> loseMovs = new HashMap<String, Set<Movement>>();
3.18 + protected Map<String, Set<CellsLink>> loseLinks = new HashMap<String, Set<CellsLink>>();
3.19 + protected Map<String, Set<Coordinate>> attendedWalkingAroundCoordinates = new HashMap<String, Set<Coordinate>>();
3.20 + protected Map<String, Set<Coordinate>> noWay = new HashMap<String, Set<Coordinate>>();
3.21
3.22 public DijkstraSolver(Mine mine, SolverListener listener) {
3.23 super(mine, listener);
3.24 @@ -36,46 +39,80 @@
3.25 @Override
3.26 public void solve() {
3.27 while (true) {
3.28 - Mine testMine = null;
3.29 - testMine = mine.clone();
3.30 - Game game = new Game(testMine);
3.31 + Mine mine = null;
3.32 + mine = initialMine.clone();
3.33 + Game game = new Game(mine);
3.34
3.35 while (game.getState() == GameState.Game) {
3.36 - String map = testMine.toText();
3.37 + Cell robotCell = mine.getRobotCell();
3.38 + String map = mine.toText();
3.39 + String mapWithoutRobot = mine.toTextWithoutRobot();
3.40 if (!loseMovs.containsKey(map)) {
3.41 loseMovs.put(map, new HashSet<Movement>());
3.42 }
3.43 - Set<Cell> targets = testMine.findCells(CellContent.Lambda);
3.44 - targets.addAll(testMine.findCells(CellContent.HighOrderRock));
3.45 - if (targets.size() == 0)
3.46 - targets = testMine.findCells(CellContent.OpenLambdaLift);
3.47 - Graph<Cell, CellsLink> graph = getDirectedGraph(testMine);
3.48 + if (!loseLinks.containsKey(map)) {
3.49 + loseLinks.put(map, new HashSet<CellsLink>());
3.50 + }
3.51 + if (!noWay.containsKey(map)) {
3.52 + noWay.put(map, new HashSet<Coordinate>());
3.53 + }
3.54 + if (!attendedWalkingAroundCoordinates.containsKey(mapWithoutRobot)) {
3.55 + attendedWalkingAroundCoordinates.put(mapWithoutRobot, new HashSet<Coordinate>());
3.56 + }
3.57 + attendedWalkingAroundCoordinates.get(mapWithoutRobot).add(robotCell.getCoordinate());
3.58 + Set<Cell> targets = new HashSet<Cell>();
3.59 + boolean isFreeWay = false;
3.60 + for (Cell cell : mine.getAdjacentCells(robotCell)) {
3.61 + Movement mov = robotCell.getCoordinate().getNecessaryMovement(cell.getCoordinate());
3.62 + isFreeWay |= !attendedWalkingAroundCoordinates.get(mapWithoutRobot).contains(cell.getCoordinate())
3.63 + && !loseMovs.get(map).contains(mov);
3.64 + }
3.65 + if (isFreeWay) {
3.66 + targets.addAll(mine.findCells(CellContent.Lambda));
3.67 + targets.addAll(mine.findCells(CellContent.HighOrderRock));
3.68 + if (targets.size() == 0)
3.69 + targets.addAll(mine.findCells(CellContent.OpenLambdaLift));
3.70 + targets.removeAll(mine.getCells(noWay.get(map)));
3.71 + } else {
3.72 + targets.addAll(mine.findCells(CellContent.Empty));
3.73 + targets.addAll(mine.findCells(CellContent.Earth));
3.74 + targets.addAll(mine.findCells(CellContent.HuttonsRazor));
3.75 + for (CellContent content : CellContent.getTrampolines()) {
3.76 + targets.addAll(mine.findCells(content));
3.77 + }
3.78 + targets.removeAll(mine.getCells(attendedWalkingAroundCoordinates.get(mapWithoutRobot)));
3.79 + targets.removeAll(mine.getCells(noWay.get(map)));
3.80 + if (targets.size() == 0) {
3.81 + game.move(Movement.ABORT);
3.82 + continue;
3.83 + }
3.84 + }
3.85 + Graph<Cell, CellsLink> graph = getDirectedGraph(mine);
3.86 DijkstraShortestPath<Cell, CellsLink> alg = new DijkstraShortestPath<Cell, CellsLink>(graph,
3.87 new CellsLinkTransformer<CellsLink, Double>());
3.88 Cell nextTarget = null;
3.89 List<CellsLink> routeToNextTarget = null;
3.90 double shortestDist = Double.MAX_VALUE;
3.91 for (Cell target : targets) {
3.92 - if (target == null)
3.93 - continue;
3.94 List<CellsLink> route = null;
3.95 Number dist = null;
3.96 try {
3.97 - route = alg.getPath(testMine.getRobotCell(), target);
3.98 - dist = alg.getDistance(testMine.getRobotCell(), target);
3.99 + route = alg.getPath(mine.getRobotCell(), target);
3.100 + dist = alg.getDistance(mine.getRobotCell(), target);
3.101 } catch (IllegalArgumentException e) {
3.102 - // hmmm...
3.103 + noWay.get(map).add(target.getCoordinate());
3.104 continue;
3.105 }
3.106 if (dist != null && route != null && route.size() > 0 && dist.doubleValue() < shortestDist) {
3.107 CellsLink firstLink = route.get(0);
3.108 Movement mov = firstLink.getSource().getCoordinate()
3.109 .getNecessaryMovement(firstLink.getTarget().getCoordinate());
3.110 - if (!loseMovs.get(map).contains(mov)) {
3.111 + if (!loseMovs.get(map).contains(mov)
3.112 + && !attendedWalkingAroundCoordinates.get(mapWithoutRobot).contains(
3.113 + target.getCoordinate())) {
3.114 shortestDist = dist.doubleValue();
3.115 nextTarget = target;
3.116 routeToNextTarget = route;
3.117 - break;
3.118 }
3.119 }
3.120 }
3.121 @@ -83,26 +120,52 @@
3.122 for (CellsLink link : routeToNextTarget) {
3.123 Cell source = link.getSource();
3.124 Cell target = link.getTarget();
3.125 - if (isSafeMovement(testMine, source, target)) {
3.126 + if (isSafeMovement(mine, source, target)) {
3.127 Movement mov = source.getCoordinate().getNecessaryMovement(target.getCoordinate());
3.128 GameState state = game.move(mov);
3.129 if (state == GameState.Lose || state == GameState.Abort) {
3.130 loseMovs.get(map).add(mov);
3.131 - loseLinks.add(link);
3.132 + loseLinks.get(map).add(link);
3.133 }
3.134 }
3.135 break;
3.136 }
3.137 } else {
3.138 + // Walking around
3.139 for (Movement mov : Movement.values()) {
3.140 if (!loseMovs.get(map).contains(mov)) {
3.141 - GameState state = game.move(mov);
3.142 - if (state == GameState.Game && map.equals(testMine.toText())) {
3.143 - if (mov != Movement.WAIT)
3.144 + if (mov == Movement.RAZOR && mine.getRazorsCount() > 0) {
3.145 + boolean isRazorApplied = false;
3.146 + for (Cell cell : mine.getNeighboringCells(robotCell)) {
3.147 + isRazorApplied |= cell.getContent() == CellContent.WadlersBeard;
3.148 + }
3.149 + if (!isRazorApplied)
3.150 + continue;
3.151 + }
3.152 + Cell movCell = null;
3.153 + for (Cell cell : mine.getAdjacentCells(robotCell)) {
3.154 + if (robotCell.getCoordinate().getNecessaryMovement(cell.getCoordinate()) == mov) {
3.155 + if (!attendedWalkingAroundCoordinates.get(mapWithoutRobot).contains(
3.156 + cell.getCoordinate())) {
3.157 + movCell = cell;
3.158 + break;
3.159 + }
3.160 + }
3.161 +
3.162 + }
3.163 + if (mov == Movement.WAIT
3.164 + || mov == Movement.RAZOR
3.165 + || movCell != null
3.166 + && !attendedWalkingAroundCoordinates.get(mapWithoutRobot).contains(
3.167 + movCell.getCoordinate())) {
3.168 + GameState state = game.move(mov);
3.169 + if (movCell != null && mapWithoutRobot.equals(mine.toTextWithoutRobot()))
3.170 + attendedWalkingAroundCoordinates.get(mapWithoutRobot).add(movCell.getCoordinate());
3.171 + if (state == GameState.Game && map.equals(mine.toText())) {
3.172 loseMovs.get(map).add(mov);
3.173 - game.move(Movement.ABORT);
3.174 + }
3.175 + break;
3.176 }
3.177 - break;
3.178 }
3.179 }
3.180 }
3.181 @@ -154,6 +217,7 @@
3.182 return;
3.183 else
3.184 processedCells.add(cell);
3.185 + String map = mine.toText();
3.186 for (Cell neighboringCell : mine.getAdjacentCells(cell)) {
3.187 if (neighboringCell == null)
3.188 continue;
3.189 @@ -163,7 +227,7 @@
3.190 || neighboringContent == CellContent.OpenLambdaLift) {
3.191 if (isSafeMovement(mine, cell, neighboringCell)) {
3.192 CellsLink link = new CellsLink(mine, cell, neighboringCell);
3.193 - if (!loseLinks.contains(link)) {
3.194 + if (!loseLinks.get(map).contains(link)) {
3.195 links.add(link);
3.196 findAllCellLinks(mine, neighboringCell, links, processedCells);
3.197 }
3.198 @@ -179,7 +243,7 @@
3.199 continue;
3.200 if (isSafeMovement(mine, cell, target)) {
3.201 CellsLink link = new CellsLink(mine, cell, target);
3.202 - if (!loseLinks.contains(link)) {
3.203 + if (!loseLinks.get(map).contains(link)) {
3.204 links.add(link);
3.205 findAllCellLinks(mine, target, links, processedCells);
3.206 }