1.1 --- a/icfp-model/src/main/java/ru/bosony/model/mine/Mine.java Mon Jul 16 13:19:10 2012 +0400
1.2 +++ b/icfp-model/src/main/java/ru/bosony/model/mine/Mine.java Mon Jul 16 15:20:48 2012 +0400
1.3 @@ -23,7 +23,7 @@
1.4 * 14.07.2012 2:02:18
1.5 *
1.6 */
1.7 -public class Mine implements TextRepresentable {
1.8 +public class Mine implements TextRepresentable, Cloneable {
1.9
1.10 protected Cell[][] cells;
1.11 protected int sizeX;
1.12 @@ -309,4 +309,9 @@
1.13 return toText().hashCode();
1.14 }
1.15
1.16 + @Override
1.17 + public Mine clone() throws CloneNotSupportedException {
1.18 + return new Mine(toText());
1.19 + }
1.20 +
1.21 }
2.1 --- a/icfp-solver/src/main/java/ru/bosony/solvers/AbstractSolver.java Mon Jul 16 13:19:10 2012 +0400
2.2 +++ b/icfp-solver/src/main/java/ru/bosony/solvers/AbstractSolver.java Mon Jul 16 15:20:48 2012 +0400
2.3 @@ -20,7 +20,6 @@
2.4 public AbstractSolver(Mine mine, SolverListener listener) {
2.5 this.mine = mine;
2.6 this.listener = listener;
2.7 - solve();
2.8 }
2.9
2.10 protected void addNewRoute(String route, int score) {
2.11 @@ -39,5 +38,5 @@
2.12 return maxScore;
2.13 }
2.14
2.15 - protected abstract void solve();
2.16 + public abstract void solve();
2.17 }
3.1 --- a/icfp-solver/src/main/java/ru/bosony/solvers/DijkstraSolver.java Mon Jul 16 13:19:10 2012 +0400
3.2 +++ b/icfp-solver/src/main/java/ru/bosony/solvers/DijkstraSolver.java Mon Jul 16 15:20:48 2012 +0400
3.3 @@ -1,8 +1,10 @@
3.4 package ru.bosony.solvers;
3.5
3.6 import java.util.ArrayList;
3.7 +import java.util.HashMap;
3.8 import java.util.HashSet;
3.9 import java.util.List;
3.10 +import java.util.Map;
3.11 import java.util.Set;
3.12
3.13 import ru.bosony.graph.CellsLink;
3.14 @@ -12,6 +14,7 @@
3.15 import ru.bosony.model.game.GameState;
3.16 import ru.bosony.model.mine.Cell;
3.17 import ru.bosony.model.mine.Mine;
3.18 +import ru.bosony.model.moving.Coordinate;
3.19 import ru.bosony.model.moving.Movement;
3.20 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
3.21 import edu.uci.ics.jung.graph.DirectedSparseGraph;
3.22 @@ -24,48 +27,78 @@
3.23 */
3.24 public class DijkstraSolver extends AbstractSolver {
3.25
3.26 + protected Map<Mine, Set<Cell>> testedTargetCells = new HashMap<Mine, Set<Cell>>();
3.27 +
3.28 public DijkstraSolver(Mine mine, SolverListener listener) {
3.29 super(mine, listener);
3.30 }
3.31
3.32 @Override
3.33 - protected void solve() {
3.34 + public void solve() {
3.35 while (true) {
3.36 - Game game = new Game(mine);
3.37 + Mine testMine = null;
3.38 + try {
3.39 + testMine = mine.clone();
3.40 + } catch (CloneNotSupportedException e1) {
3.41 + throw new RuntimeException(e1);
3.42 + }
3.43 + Game game = new Game(testMine);
3.44
3.45 while (game.getState() == GameState.Game) {
3.46 - try {
3.47 - Set<Cell> targets = mine.findCells(CellContent.Lambda);
3.48 - targets.addAll(mine.findCells(CellContent.HighOrderRock));
3.49 - if (targets.size() == 0)
3.50 - targets = mine.findCells(CellContent.OpenLambdaLift);
3.51 - if (targets.size() == 0)
3.52 + if (!testedTargetCells.containsKey(testMine)) {
3.53 + testedTargetCells.put(testMine, new HashSet<Cell>());
3.54 + }
3.55 + Set<Cell> targets = testMine.findCells(CellContent.Lambda);
3.56 + targets.addAll(testMine.findCells(CellContent.HighOrderRock));
3.57 + if (targets.size() == 0)
3.58 + targets = testMine.findCells(CellContent.OpenLambdaLift);
3.59 + if (targets.size() == 0 || testedTargetCells.get(testMine).containsAll(targets)) {
3.60 + // No targets. Walking around
3.61 + Cell robotCell = testMine.getRobotCell();
3.62 + for (Coordinate nextCoordinate : robotCell.getCoordinate().getAdjacentCoordinates()) {
3.63 + Cell nextCell = testMine.getCell(nextCoordinate);
3.64 + targets.add(nextCell);
3.65 + }
3.66 + if (testedTargetCells.get(testMine).containsAll(targets)) {
3.67 + // Fail. All cases are tried.
3.68 + game.move(Movement.ABORT);
3.69 break;
3.70 - Graph<Cell, CellsLink> graph = getDirectedGraph();
3.71 - DijkstraShortestPath<Cell, CellsLink> alg = new DijkstraShortestPath<Cell, CellsLink>(graph,
3.72 - new CellsLinkTransformer<CellsLink, Double>());
3.73 - Cell nextTarget = null;
3.74 - List<CellsLink> routeToNextTarget = null;
3.75 - double shortestDist = Double.MAX_VALUE;
3.76 - for (Cell target : targets) {
3.77 - List<CellsLink> route = alg.getPath(mine.getRobotCell(), target);
3.78 - Number dist = alg.getDistance(mine.getRobotCell(), target);
3.79 - if (dist != null && dist.doubleValue() < shortestDist) {
3.80 - shortestDist = dist.doubleValue();
3.81 - nextTarget = target;
3.82 - routeToNextTarget = route;
3.83 - }
3.84 }
3.85 - if (nextTarget != null) {
3.86 - for (CellsLink link : routeToNextTarget) {
3.87 - Movement mov = link.getSource().getCoordinate()
3.88 - .getNecessaryMovement(link.getTarget().getCoordinate());
3.89 - game.move(mov);
3.90 - break;
3.91 - }
3.92 + }
3.93 + Graph<Cell, CellsLink> graph = getDirectedGraph(testMine);
3.94 + DijkstraShortestPath<Cell, CellsLink> alg = new DijkstraShortestPath<Cell, CellsLink>(graph,
3.95 + new CellsLinkTransformer<CellsLink, Double>());
3.96 + Cell nextTarget = null;
3.97 + List<CellsLink> routeToNextTarget = null;
3.98 + double shortestDist = Double.MAX_VALUE;
3.99 + for (Cell target : targets) {
3.100 + if (target == null)
3.101 + continue;
3.102 + List<CellsLink> route = null;
3.103 + Number dist = null;
3.104 + try {
3.105 + route = alg.getPath(testMine.getRobotCell(), target);
3.106 + dist = alg.getDistance(testMine.getRobotCell(), target);
3.107 + } catch (IllegalArgumentException e) {
3.108 + // hmmm...
3.109 + testedTargetCells.get(testMine).add(target);
3.110 + continue;
3.111 }
3.112 - } catch (IllegalArgumentException e) {
3.113 - // hmmm...
3.114 + if (dist != null && route != null && dist.doubleValue() < shortestDist
3.115 + && !testedTargetCells.get(testMine).contains(target)) {
3.116 + shortestDist = dist.doubleValue();
3.117 + nextTarget = target;
3.118 + routeToNextTarget = route;
3.119 + testedTargetCells.get(testMine).add(target);
3.120 + }
3.121 + }
3.122 + if (nextTarget != null) {
3.123 + for (CellsLink link : routeToNextTarget) {
3.124 + Movement mov = link.getSource().getCoordinate()
3.125 + .getNecessaryMovement(link.getTarget().getCoordinate());
3.126 + game.move(mov);
3.127 + break;
3.128 + }
3.129 }
3.130 }
3.131 if (game.getState() == GameState.Win) {
3.132 @@ -75,22 +108,22 @@
3.133 }
3.134 }
3.135
3.136 - protected Graph<Cell, CellsLink> getDirectedGraph() {
3.137 + protected Graph<Cell, CellsLink> getDirectedGraph(Mine mine) {
3.138 Graph<Cell, CellsLink> graph = new DirectedSparseGraph<Cell, CellsLink>();
3.139 - for (CellsLink link : getCellLinks()) {
3.140 + for (CellsLink link : getCellLinks(mine)) {
3.141 graph.addEdge(link, link.getSource(), link.getTarget());
3.142 }
3.143 return graph;
3.144 }
3.145
3.146 - protected List<CellsLink> getCellLinks() {
3.147 + protected List<CellsLink> getCellLinks(Mine mine) {
3.148 List<CellsLink> links = new ArrayList<CellsLink>();
3.149 Cell robotCell = mine.getRobotCell();
3.150 - findAllCellLinks(robotCell, links, new HashSet<Cell>());
3.151 + findAllCellLinks(mine, robotCell, links, new HashSet<Cell>());
3.152 return links;
3.153 }
3.154
3.155 - protected void findAllCellLinks(Cell cell, List<CellsLink> links, Set<Cell> processedCells) {
3.156 + protected void findAllCellLinks(Mine mine, Cell cell, List<CellsLink> links, Set<Cell> processedCells) {
3.157 if (processedCells.contains(cell))
3.158 return;
3.159 else
3.160 @@ -104,10 +137,10 @@
3.161 || neighboringContent == CellContent.OpenLambdaLift) {
3.162 CellsLink link = new CellsLink(mine, cell, neighboringCell);
3.163 links.add(link);
3.164 - findAllCellLinks(neighboringCell, links, processedCells);
3.165 + findAllCellLinks(mine, neighboringCell, links, processedCells);
3.166 } else if (!CellContent.getTargets().contains(cell.getContent())
3.167 && CellContent.getTargets().contains(neighboringContent)) {
3.168 - findAllCellLinks(neighboringCell, links, processedCells);
3.169 + findAllCellLinks(mine, neighboringCell, links, processedCells);
3.170 }
3.171 }
3.172 if (CellContent.getTrampolines().contains(cell.getContent())) {
3.173 @@ -116,7 +149,7 @@
3.174 continue;
3.175 CellsLink link = new CellsLink(mine, cell, target);
3.176 links.add(link);
3.177 - findAllCellLinks(target, links, processedCells);
3.178 + findAllCellLinks(mine, target, links, processedCells);
3.179 }
3.180 }
3.181 }
4.1 --- a/icfp-solver/src/main/java/ru/bosony/solvers/SimpleSolver.java Mon Jul 16 13:19:10 2012 +0400
4.2 +++ b/icfp-solver/src/main/java/ru/bosony/solvers/SimpleSolver.java Mon Jul 16 15:20:48 2012 +0400
4.3 @@ -14,7 +14,7 @@
4.4 }
4.5
4.6 @Override
4.7 - protected void solve() {
4.8 + public void solve() {
4.9 String route = "";
4.10 while (true) {
4.11 try {
5.1 --- a/icfp-solver/src/main/java/ru/bosony/solvers/Solver.java Mon Jul 16 13:19:10 2012 +0400
5.2 +++ b/icfp-solver/src/main/java/ru/bosony/solvers/Solver.java Mon Jul 16 15:20:48 2012 +0400
5.3 @@ -32,6 +32,7 @@
5.4 route = newRoute;
5.5 }
5.6 });
5.7 + solver.solve();
5.8 }
5.9
5.10 public static void main(String[] args) throws IOException, InterruptedException {